Multi-type attention for solving multi-depot vehicle routing problems

Publication Type

Journal Article

Publication Date

11-2024

Abstract

In recent years, there has been a growing trend towards using deep reinforcement learning (DRL) to solve the NP-hard vehicle routing problems (VRPs). While much success has been achieved, most of the previous studies solely focused on single-depot VRPs, which became less effective in handling more practical scenarios, such as multi-depot VRPs. Although there are many preprocessing measures, such as natural decomposition, those scenarios are still more challenging to optimize. To resolve this issue, we propose the multi-depot multi-type attention (MD-MTA) to solve the multi-depot VRP (MDVRP) and multi-depot open VRP (MDOVRP), respectively. We design a multi-type attention in the network to combine different types of embeddings and the state of the environment at each step, so as to accurately select the next node to visit and construct the route. We introduce a depot rotation augmentation to enhance solution decoding. Results show that it performs favorably against various representative traditional baselines and DRL-based baselines.

Keywords

Vehicle routing, Transformers, Heuristic algorithms, Decoding, Decision making, Computer architecture, Training, Deep reinforcement learning, learning to optimize, multi-depot vehicle routing problem, multi-depot open vehicle routing problem, attention mechanism, transformer model

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering | Transportation

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Digital transformation

Publication

IEEE Transactions on Intelligent Transportation Systems

Volume

25

Issue

11

First Page

17831

Last Page

17840

ISSN

1524-9050

Identifier

10.1109/TITS.2024.3413077

Publisher

Institute of Electrical and Electronics Engineers

Additional URL

https://doi.org/10.1109/TITS.2024.3413077

Link to Full Text

Share

COinS