A hybrid algorithm for the vehicle routing problem with three-dimensional loading constraints and mixed backhauls

Henriette Koch (), Maximilian Schlögell and Andreas Bortfeldt
Additional contact information
Henriette Koch: Otto-von-Guericke-University Magdeburg
Maximilian Schlögell: Otto-von-Guericke-University Magdeburg
Andreas Bortfeldt: Otto-von-Guericke-University Magdeburg

Journal of Scheduling, 2020, vol. 23, issue 1, No 4, 93 pages

Abstract: Abstract In this paper, a variant of the vehicle routing problem with mixed backhauls (VRPMB) is presented, i.e. goods have to be delivered from a central depot to linehaul customers, and, at the same time, goods have to be picked up from backhaul customers and brought to the depot. Both types of customers can be visited in mixed sequences. The goods to be delivered or picked up are three-dimensional (cuboid) items. Hence, in addition to a routing plan, a feasible packing plan for each tour has to be provided considering a number of loading constraints. The resulting problem is the vehicle routing problem with three-dimensional loading constraints and mixed backhauls (3L-VRPMB). The simultaneous transport of linehaul and backhaul items presents a particular challenge of the problem. We consider two different loading variants in order to avoid any reloading during the tour: (i) rear loading with separate linehaul and backhaul sections and (ii) loading at a long side. In order to solve the problem, we propose a hybrid metaheuristic consisting of a reactive tabu search for the routing problem and different packing heuristics for the loading problem. Numerical experiments are reported with benchmark instances from the literature for the one-dimensional VRPMB to examine the performance of the routing algorithm and with newly generated instances for the 3L-VRPMB.

Keywords: Vehicle routing; Backhauls; Tabu search; Packing (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-019-00625-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:23:y:2020:i:1:d:10.1007_s10951-019-00625-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-019-00625-7

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().