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

Publication Type

Journal Article

Publication Date

6-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

First Page

1

Last Page

10

ISSN

1524-9050

Identifier

10.1109/TITS.2024.3413077

Publisher

Institute of Electrical and Electronics Engineers

Copyright Owner and License

Authors

Additional URL

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

This document is currently not available here.

Share

COinS