Vehicle routing strategies for pick-up and delivery service under two dimensional loading constraints

This work compares the transportation costs incurred by three alternative strategies for shipping items from a central warehouse to a set of customers and vice versa. Two-dimensional loading patterns have to be determined for the transported items. The vehicle routing problem (VRP) with simultaneous pick-ups and deliveries and two-dimensional loading constraints, which considers that vehicles offer simultaneous pick-up and delivery service, is used as the basis for comparisons. Two alternative strategies are considered: the VRP with backhauls and two-dimensional loading constraints, where pick-up items are collected only when the delivery items of a route have been unloaded, and the bi-directional VRP with two-dimensional loading constraints, where pick-up and delivery items are transported by different types of vehicle trips. The examined models are solved via a common local-search method for the routing aspects, integrated with a packing heuristic for developing feasible item loadings. To conduct the model comparison, we solve new benchmark instances with diverse features in terms of the graphs, the characteristics of the transported items, and the participation of pick-up items in the overall set of transported items. Discussion is provided on the routing costs incurred by each transportation model and the behavior of the employed methodology.