Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/325818 
Erscheinungsjahr: 
2025
Quellenangabe: 
[Journal:] Operations Research Perspectives [ISSN:] 2214-7160 [Volume:] 14 [Article No.:] 100341 [Year:] 2025 [Pages:] 1-15
Verlag: 
Elsevier, Amsterdam
Zusammenfassung: 
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.
Schlagwörter: 
Belief propagation
Heterogeneous multi-depot VRP
Heuristic algorithm
Message passing
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by-nc-nd Logo
Dokumentart: 
Article

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.