Publication Type
Conference Proceeding Article
Version
acceptedVersion
Publication Date
5-2024
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.
Keywords
Multi-objective vehicle routing problems, Deep reinforcement learning, Attention network, Collaborative active search
Discipline
Artificial Intelligence and Robotics
Research Areas
Intelligent Systems and Optimization
Areas of Excellence
Digital transformation
Publication
AAMAS '24: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, Auckland, New Zealand, 2024 May 6-10
First Page
1956
Last Page
1965
ISBN
9798400704864
Identifier
10.5555/3635637.3663059
Publisher
ACM
City or Country
New York
Citation
WU, Yaoxin; FAN, Mingfeng; CAO, Zhiguang; GAO, Ruobin; HOU, Yaqing; and SARTORETTI, Guillaume.
Collaborative deep reinforcement learning for solving multi-objective vehicle routing problems. (2024). AAMAS '24: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, Auckland, New Zealand, 2024 May 6-10. 1956-1965.
Available at: https://ink.library.smu.edu.sg/sis_research/9328
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.5555/3635637.3663059