Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/325818 
Year of Publication: 
2025
Citation: 
[Journal:] Operations Research Perspectives [ISSN:] 2214-7160 [Volume:] 14 [Article No.:] 100341 [Year:] 2025 [Pages:] 1-15
Publisher: 
Elsevier, Amsterdam
Abstract: 
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.
Subjects: 
Belief propagation
Heterogeneous multi-depot VRP
Heuristic algorithm
Message passing
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by-nc-nd Logo
Document Type: 
Article

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.