Collaborative Deep Reinforcement Learning for Solving Multi-Objective Vehicle Routing Problems

Yaoxin Wu, Mingfeng Fan, Zhiguang Cao, Ruobin Gao, Yaqing Hou, Guillaume Sartoretti

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Downloads (Pure)

Abstract

Existing deep reinforcement learning (DRL) methods for multi-objective vehicle routing problems (MOVRPs) typically decompose an MOVRP into subproblems with respective preferences and then train policies to solve corresponding subproblems. However, such a paradigm is still less effective in tackling the intricate interactions among subproblems, thus holding back the quality of the Pareto solutions. To counteract this limitation, we introduce a collaborative deep reinforcement learning method. We first propose a preference-based attention network (PAN) that allows the DRL agents to reason out solutions to subproblems in parallel, where a shared encoder learns the instance embedding and a decoder is tailored for each agent by preference intervention to construct respective solutions. Then, we design a collaborative active search (CAS) to further improve the solution quality, which updates only a part of the decoder parameters per instance during inference. In the CAS process, we also explicitly foster the interactions of neighboring DRL agents by imitation learning, empowering them to exchange insights of elite solutions to similar subproblems. Extensive results on random and benchmark instances verified the efficacy of PAN and CAS, which is particularly pronounced on the configurations (i.e., problem sizes or node distributions) beyond the training ones. Our code is available at https://github.com/marmotlab/PAN-CAS.
Original languageEnglish
Title of host publicationAAMAS '24
Subtitle of host publicationProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1956-1965
Number of pages10
ISBN (Electronic)979-8-4007-0486-4
Publication statusPublished - 6 May 2024
Event23rd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2024 - Auckland, New Zealand
Duration: 6 May 202410 May 2024

Conference

Conference23rd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2024
Country/TerritoryNew Zealand
CityAuckland
Period6/05/2410/05/24

Fingerprint

Dive into the research topics of 'Collaborative Deep Reinforcement Learning for Solving Multi-Objective Vehicle Routing Problems'. Together they form a unique fingerprint.

Cite this