Multi-vehicle routing problems with soft time windows: A multi-agent reinforcement learning approach

Multi-vehicle routing problem with soft time windows (MVRPSTW) is an indispensable constituent in urban logistics distribution systems. Over the past decade, numerous methods for MVRPSTW have been proposed, but most are based on heuristic rules that require a large amount of computation time. With the current rapid increase of logistics demands, traditional methods incur the dilemma between computational efficiency and solution quality. To efficiently solve the problem, the authors propose a novel reinforcement learning algorithm called the Multi-Agent Attention Model that can solve routing problem instantly benefit from lengthy offline training. Specifically, the vehicle routing problem is regarded as a vehicle tour generation process, and an encoder-decoder framework with attention layers is proposed to generate tours of multiple vehicles iteratively. Furthermore, a multi-agent reinforcement learning method with an unsupervised auxiliary network is developed for the model training. By evaluated on four synthetic networks with different scales, the results demonstrate that the proposed method consistently outperforms Google OR-Tools and traditional methods with little computation time. In addition, the authors validate the robustness of the well-trained model by varying the number of customers and the capacities of vehicles.

• Record URL:
  • https://doi.org/10.1016/j.trc.2020.102861
• Record URL:
  • http://www.sciencedirect.com/science/article/pii/S0968090X20307610
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/0968090X
• Supplemental Notes:
  • © 2020 Elsevier Ltd. All rights reserved. Abstract reprinted with permission of Elsevier.
• Authors:
  • Zhang, Ke
  • He, Fang
  • Zhang, Zhengchao
  • Lin, Xi
  • Li, Meng
• Publication Date: 2020-12

Language

• English

Media Info

• Media Type: Web
• Features: Figures; References; Tables;
• Pagination: 102861
• Serial:
  • Transportation Research Part C: Emerging Technologies
  • Volume: 121
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 0968-090X
  • Serial URL: http://www.sciencedirect.com/science/journal/0968090X

Subject/Index Terms

• TRT Terms: Machine learning; Mathematical models; Multi-agent systems; Routing; Time windows; Vehicle fleets
• Subject Areas: Highways; Operations and Traffic Management; Planning and Forecasting;

Filing Info

• Accession Number: 01760059
• Record Type: Publication
• Files: TRIS
• Created Date: Dec 15 2020 10:13AM