A note on the hierarchical multi-switch multi-echelon vehicle routing problem

This paper introduces the Hierarchical Multi-Switch Multi-Echelon Vehicle Routing Problem, a new variant of the well-known Vehicle Routing Problem. It is a real-world problem originating from the policies of a Nordic distribution company. The problem includes a single depot, a non-predetermined hierarchy of intermediate facilities, and two different fleets, consisting of homogeneous original and homogeneous local vehicles, which are pulling swap-bodies. Original vehicles with attached swap-bodies depart from the central depot. They can either visit customers directly if only one swap-body is attached or visit one or two consecutive switch points in order to transfer one or two loaded swap-bodies to a corresponding number of local vehicles, which are subsequently routed to customers while the original vehicle itself proceeds to serve customers with the remaining loaded swap-body. A mixed-integer formulation of the problem is proposed. A short bibliographic review, relations, shared characteristics, and differences of the proposed variant and several known VRP variants are analyzed and discussed. The solution of an illustrative instance is presented in order to demonstrate the solution concept for the problem as well as to compare with solution concepts for previously stated VRP variants. Computational experiments on small instances that could be solved within one hour are also presented. The problem is computationally hard to solve. Thus, the development of heuristics and metaheuristics is an important future task in order to enable solution of real case instances or instances of realistic sizes.

Automated summary

This paper introduces a new variant of the Vehicle Routing Problem called the Hierarchical Multi-Switch Multi-Echelon Vehicle Routing Problem. It analyzes the problem and proposes a mixed-integer formulation. The paper compares the proposed variant with other known VRP variants and presents the solution concept through an illustrative instance and computational experiments. Due to the computational difficulty of the problem, the development of heuristics and metaheuristics is deemed important for solving real case instances.