IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v113y2018icp1-23.html
   My bibliography  Save this article

The generalized rollon-rolloff vehicle routing problem and savings-based algorithm

Author

Listed:
  • Li, Hongqi
  • Jian, Xiaorong
  • Chang, Xinyu
  • Lu, Yingrong

Abstract

Taking the waste collection management as the practical background, the rollon-rolloff vehicle routing problem (RRVRP) involves tractors pulling large containers between customer locations and the disposal facility. Each used-tractor begins and ends its route at the depot. Customer demand includes emptying a full container, ordering an empty container or changing a container. The objective is to find tractor routes that feature the minimum amount of total nonproductive time. In the literature the RRVRP is formulated as the node routing problem, and the “trip” definition that is the complete transport service of a container is used. To relax some assumptions of the RRVRP to cater to practical desires, we present a variant called the generalized RRVRP (G-RRVRP). The G-RRVRP generalizes the practical background, the objective function and the demand flow, and considers specially container loading and unloading time constraints. The G-RRVRP classifies demand into loaded-container demand and cargo demand with time windows. On condition of respecting container loading/unloading time and customer time windows, the G-RRVRP can design tractor routes for the synchronous scheduling of loaded and empty containers so as to ensure the timeliness of transport service. The G-RRVRP aims to minimize the total running cost of used tractors, instead of the total nonproductive time of tractors adopted by the RRVRP. A mixed integer linear programming model for the G-RRVRP is proposed. The Benders decomposition algorithm involving Pareto-optimal cuts and Benders decomposition-callback implementation, and a two-stage heuristic involving the savings algorithm followed by a local search phase are provided. The mathematical formulation and the two-stage heuristic are tested by solving 40 small-scale instances and 20 benchmark instances. Small-scale instances can be solved directly by CPLEX through the Benders decomposition strategies to find exact solutions. The case study indicates the applicability of the G-RRVRP model and the two-stage heuristic to realistic-size problems abstracted from intercity linehaul systems. The computational experiments and case study indicate that the heuristic can solve various instances of the G-RRVRP such that the solution quality and the computation time are acceptable.

Suggested Citation

  • Li, Hongqi & Jian, Xiaorong & Chang, Xinyu & Lu, Yingrong, 2018. "The generalized rollon-rolloff vehicle routing problem and savings-based algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 113(C), pages 1-23.
    • Handle: RePEc:eee:transb:v:113:y:2018:i:c:p:1-23
    DOI: 10.1016/j.trb.2018.05.005
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261517311177
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2018.05.005?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Di, Zhen & Yang, Lixing & Shi, Jungang & Zhou, Housheng & Yang, Kai & Gao, Ziyou, 2022. "Joint optimization of carriage arrangement and flow control in a metro-based underground logistics system," Transportation Research Part B: Methodological, Elsevier, vol. 159(C), pages 1-23.
    2. Yue Lu & Maoxiang Lang & Xueqiao Yu & Shiqi Li, 2019. "A Sustainable Multimodal Transport System: The Two-Echelon Location-Routing Problem with Consolidation in the Euro–China Expressway," Sustainability, MDPI, vol. 11(19), pages 1-25, October.
    3. Shi, Yong & Boudouh, Toufik & Grunder, Olivier, 2019. "A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 128(C), pages 52-95.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:113:y:2018:i:c:p:1-23. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.