Hybrid algorithms for the vehicle routing problem with clustered backhauls and 3D loading constraints

Andreas Bortfeldt, Thomas Hahn, Dirk Männel and Lars Mönch

European Journal of Operational Research, 2015, vol. 243, issue 1, 82-96

Abstract: In this paper, we extend the vehicle routing problem with clustered backhauls (VRPCB) to an integrated routing and three-dimensional loading problem, called VRPCB with 3D loading constraints (3L-VRPCB). In the VRPCB each customer is either a linehaul or a backhaul customer and in each route all linehaul customers must be visited before any backhaul customer. In the 3L-VRPCB, each customer demand is given as a set of 3D rectangular items (boxes) and the vehicle capacity is replaced by a 3D loading space. Moreover, some packing constraints, e.g. concerning stacking of boxes, are also integrated. A set of routes of minimum total length has to be determined such that each customer is visited once. For each route two packing plans have to be provided that stow all boxes of all visited linehaul and backhaul customers, respectively, taking into account the additional packing constraints. We propose two hybrid algorithms for solving the 3L-VRPCB, each of them consisting of a routing and a packing procedure. The routing procedures follow different metaheuristic strategies (large vs. variable neighborhood search) and in both algorithms a tree search heuristic is responsible for packing boxes. Extensive computational experiments were carried out using 95 3L-VRPCB benchmark instances that were derived from well-known VRPCB instances. Good results are also achieved for the capacitated vehicle routing problem with 3D loading constraints as a special case of the 3L-VRPCB.

Keywords: Transportation; Vehicle routing with clustered backhauls; Large neighborhood search; Variable neighborhood search (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221714009837
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:243:y:2015:i:1:p:82-96

DOI: 10.1016/j.ejor.2014.12.001

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 ().