Decentralized message passing algorithm for heterogeneous multi-depot vehicle routing problems

In this paper, a novel message-passing algorithm, named AMP-R, based on belief propagation is proposed to solve the heterogeneous multi-depot vehicle routing problem (HMDVRP) in a distributed manner. Unlike traditional approaches, this is the first attempt to decentralize the solution process for the HMDVRP at the depot level, enabling each depot to independently compute and exchange messages to derive conflict-free solutions. The HMDVRP requires assigning customers to depots and determining routes that minimize total travel cost. By reformulating the problem as a maximum a posteriori estimation in a graphical model comprising depot and customer nodes, The proposed approach enables decentralized message calculation and exchange between depots, effectively addressing various types of the HMDVRP. In this process, it is derived that each message calculation can be reduced to a subset-visit traveling salesman problem or a capacitated vehicle routing problem, and approximation techniques are proposed to address these computational challenges. Furthermore, to ensure solution convergence and feasibility, message buffers and a refinement process are introduced. Extensive simulations demonstrate that the proposed AMP-R algorithm yields near-optimal solutions with computational efficiency, offering practical performance for complex large-scale instances where finding optimal solutions is challenging.