Heuristics for vehicle routing problems with backhauls, time windows, and 3D loading constraints

Sebastian Reil, Andreas Bortfeldt and Lars Mönch

European Journal of Operational Research, 2018, vol. 266, issue 3, 877-894

Abstract: In this paper, we consider vehicle routing problems with backhauls and time windows (VRPBTW). Different backhaul variants are studied, namely clustered backhauls (CB), mixed linehauls and backhauls, and variants with simultaneous delivery and pickup and with divisible delivery and pickup. Three dimensional loading constraints are assumed. A two-phase approach following the principle packing first, routing second is proposed. In the first phase, the packing of goods is carried out by solving a 3D strip packing problem for each customer using tabu search. The resulting VRPTW instance is solved in the second phase using first a multi-start evolutionary strategy to minimize the number of vehicles while again tabu search is applied to minimize the total travel distance. We show that the various backhaul types can be incorporated into this framework. For the backhaul variants different from CB, unloading and reloading efforts are taken into account. Moreover, side loading and a separation of the loading space into separate compartments for goods of linehaul and backhaul customers are proposed. Computational results for benchmark instances and new randomly generated problem instances are presented that demonstrate that the heuristics determine high-quality solutions in a short amount of computing time. The unloading and reloading strategies outperform the strategies based on two separate compartments.

Keywords: Transportation; Packing; Vehicle routing with backhauls and time windows; Three dimensional loading constraints; Integrated routing and packing problem (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717309426
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:266:y:2018:i:3:p:877-894

DOI: 10.1016/j.ejor.2017.10.029

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().