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. 
The Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries and Two-Dimensional Loading Constraints