Collaborative deep reinforcement learning for solving multi-objective vehicle routing problems
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...
Saved in:
Main Authors: | , , , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2024
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/9328 https://ink.library.smu.edu.sg/context/sis_research/article/10328/viewcontent/55_AAMAS2024_MOVRP.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-10328 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-103282024-09-26T07:42:34Z Collaborative deep reinforcement learning for solving multi-objective vehicle routing problems WU, Yaoxin FAN, Mingfeng CAO, Zhiguang GAO, Ruobin HOU, Yaqing SARTORETTI, Guillaume 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. 2024-05-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/9328 info:doi/10.5555/3635637.3663059 https://ink.library.smu.edu.sg/context/sis_research/article/10328/viewcontent/55_AAMAS2024_MOVRP.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Multi-objective vehicle routing problems Deep reinforcement learning Attention network Collaborative active search Artificial Intelligence and Robotics |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Multi-objective vehicle routing problems Deep reinforcement learning Attention network Collaborative active search Artificial Intelligence and Robotics |
spellingShingle |
Multi-objective vehicle routing problems Deep reinforcement learning Attention network Collaborative active search Artificial Intelligence and Robotics WU, Yaoxin FAN, Mingfeng CAO, Zhiguang GAO, Ruobin HOU, Yaqing SARTORETTI, Guillaume Collaborative deep reinforcement learning for solving multi-objective vehicle routing problems |
description |
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. |
format |
text |
author |
WU, Yaoxin FAN, Mingfeng CAO, Zhiguang GAO, Ruobin HOU, Yaqing SARTORETTI, Guillaume |
author_facet |
WU, Yaoxin FAN, Mingfeng CAO, Zhiguang GAO, Ruobin HOU, Yaqing SARTORETTI, Guillaume |
author_sort |
WU, Yaoxin |
title |
Collaborative deep reinforcement learning for solving multi-objective vehicle routing problems |
title_short |
Collaborative deep reinforcement learning for solving multi-objective vehicle routing problems |
title_full |
Collaborative deep reinforcement learning for solving multi-objective vehicle routing problems |
title_fullStr |
Collaborative deep reinforcement learning for solving multi-objective vehicle routing problems |
title_full_unstemmed |
Collaborative deep reinforcement learning for solving multi-objective vehicle routing problems |
title_sort |
collaborative deep reinforcement learning for solving multi-objective vehicle routing problems |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2024 |
url |
https://ink.library.smu.edu.sg/sis_research/9328 https://ink.library.smu.edu.sg/context/sis_research/article/10328/viewcontent/55_AAMAS2024_MOVRP.pdf |
_version_ |
1814047910842597376 |