Deep attention models with dimension-reduction and gate mechanisms for solving practical time-dependent vehicle routing problems

Feng Guo, Qu Wei, Miao Wang, Zhaoxia Guo and Stein Wallace

Transportation Research Part E: Logistics and Transportation Review, 2023, vol. 173, issue C

Abstract: Time dependencies of travel speeds in time-dependent vehicle routing problems (TDVRPs) are usually accounted for by discretizing the planning horizon into several time periods. However, travel speeds usually change frequently in real road networks, so many time periods are needed to evaluate candidate solutions accurately in model and solution construction for practical TDVRPs, which increases substantially the computational complexity of TDVRPs. We develop two deep attention models with dimension-reduction and gate mechanisms to solve practical TDVRPs in real urban road networks. In the two models, a multi-head attention-based dimension-reduction mechanism is proposed to reduce the dimension of model inputs and obtain enhanced node representation, whereas a gate mechanism is introduced to obtain better information representation. On the basis of a travel speed dataset from an urban road network, we conduct extensive experiments to validate the effectiveness of the proposed models on practical TDVRPs with or without consideration of time windows. Experimental results show that our models can solve TDVRPs with 240 time periods and up to 250 customers effectively and efficiently and provide significantly superior overall performances over two representative heuristics and two state-of-the-art deep reinforcement learning models. Especially, compared with a recent tabu search method, our models can reduce the computation time by up to 3,540 times and improve the solution performance by up to 23%. Moreover, our models have an outstanding generalization performance. The model trained for the 30-customer TDVRP with time windows can be used directly to solve problems with up to 250 customers effectively by generating superior solutions over those generated by benchmarking methods.

Keywords: Time-dependent vehicle routing problems; Deep reinforcement learning; Attention model; Dimension-reduction mechanism; Gate mechanism (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554523000832
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:173:y:2023:i:c:s1366554523000832

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2023.103095

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().