Loading Constraints for a Multi-Compartment Vehicle Routing Problem
Manuel Ostermeier  1, *@  , Sara Martins  2@  , Pedro Amorim  2@  , Alexander Hübner  1@  
1 : Katholische Universität Eichstätt-Ingolstadt  -  Website
2 : Universidade do Porto; INESC TEC
* : Corresponding author

Little attention has so far been paid to multi-compartment vehicles routing problems with flexible compartments. Practice shows that many retailers use these technical advanced vehicles in their distribution. Multi-compartment vehicles (MCV) offer the possibility to deliver various product segments jointly and therefore can reduce the number of customer stops. Besides classical routing decisions, the configuration of each truck becomes an essential part in tour planning when using MCV. This requires defining the segment mix, compartment sizes, and the combinations of different orders and therefore customers on vehicles. As orders of one segment can only be loaded jointly and as the orders cannot be rearranged on the loading area during the tour, customers and segments need to be sequenced so that no blocking during unloading occurs. Routing and loading layout planning are interdependent for MCVs.

Our work addresses the problem to obtain feasible MCV loading and cost-optimal routing. An MCVRP is formulated that takes into account loading constraints. We present a specialized packing problem to account for loading constraints. It is integrated into a branch-and-cut algorithm and a Large Neighborhood Search (LNS). The tailored LNS iteratively solves the routing and packing problem. In numerical studies we show that the proposed LNS reaches the optimal solution for small instances and can be applied efficiently to larger problems. Additionally, we perform tests on larger instances to derive general rules for the influence of loading constraints. To conclude the numerical experiments, a case study was analyzed with an European retailer.

Online user: 1 RSS Feed