1. Simultaneous Pickup and Delivery Traveling Salesman Problem considering the Express Lockers Using Attention Route Planning Network
- Author
-
Qiang Zhou, Yu Du, Chunfang Li, Shaochuan Fu, and Changxiang Lu
- Subjects
Mathematical optimization ,Article Subject ,General Computer Science ,Total cost ,Computer science ,General Mathematics ,Computer applications to medicine. Medical informatics ,0211 other engineering and technologies ,R858-859.7 ,Neurosciences. Biological psychiatry. Neuropsychiatry ,02 engineering and technology ,Travelling salesman problem ,0202 electrical engineering, electronic engineering, information engineering ,Reinforcement learning ,Pickup ,Travel ,021103 operations research ,General Neuroscience ,Commerce ,General Medicine ,Power (physics) ,Order (business) ,Software deployment ,020201 artificial intelligence & image processing ,Stochastic optimization ,Algorithms ,RC321-571 ,Research Article - Abstract
This paper presents a simultaneous pickup and delivery route designing model, which considers the use of express lockers. Unlike the traditional traveling salesman problem (TSP), this model analyzes the scenario that a courier serves a neighborhood with multiple trips. Considering the locker and vehicle capacity, the total cost is constituted of back order, lost sale, and traveling time. We aim to minimize the total cost when satisfying all requests. A modified deep Q-learning network is designed to get the optimal results from our model, leveraging masked multi-head attention to select the courier paths. Our algorithm outperforms other stochastic optimization methods with better optimal solutions and O(n) computational time in evaluation processes. The experiment has shown that reinforcement learning is a better choice than traditional stochastic optimization methods, consuming less power and time during evaluation processes, which indicates that this approach fits better for large-scale data and broad deployment.
- Published
- 2021