The Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries and Two-Dimensional Loading Constraints

Emmanouil E. Zachariadis, Christos D. Tarantilis and Chris T. Kiranoudis

European Journal of Operational Research, 2016, vol. 251, issue 2, 369-386

Abstract: We introduce and solve the Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries and Two-Dimensional Loading Constraints (2L-SPD). The 2L-SPD model covers cases where customers raise delivery and pick-up requests for transporting non-stackable rectangular items. 2L-SPD belongs to the class of composite routing-packing optimization problems. However, it is the first such problem to consider bi-directional material flows dictated in practice by reverse logistics policies. The aspect of simultaneously satisfying deliveries and pick-ups has a major impact on the underlying loading constraints: feasible loading patterns must be identified for every arc traveled in the routing plan. This implies that 2L-SPD generalizes previous routing problem variants with two-dimensional loading constraints which call for one feasible loading per route. From a managerial perspective, the simultaneous service of deliveries and pick-ups may bring substantial cost-savings, but the generalized loading constraints are very hard to tackle in reasonable computational times. To this end, we propose an optimization framework which employs memorization techniques designed for the 2L-SPD model, to accelerate the solution methodology. To assess the performance of our routing and packing algorithmic components, we have solved the Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries (VRPSPD) and the Vehicle Routing Problem with Two-Dimensional Constraints (2L-CVRP). Computational results are also reported on newly constructed 2L-SPD benchmark problems. Apart from the basic 2L-SPD version, we introduce the 2L-SPD with LIFO constraints which prohibit item rearrangements along the routes. Computational experiments are conducted to understand the impact of the LIFO constraints on the routing plans obtained.

Keywords: Logistics; Vehicle routing; Loading constraints; Simultaneous Pick-ups and Deliveries; Heuristics (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171501067X
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:251:y:2016:i:2:p:369-386

DOI: 10.1016/j.ejor.2015.11.018

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