Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learning

Recently, there is an emerging trend to apply deep reinforcement learning to solve the vehicle routing problem (VRP), where a learnt policy governs the selection of next node for visiting. However, existing methods could not handle well the pairing and precedence relationships in the pickup and delivery problem (PDP), which is a representative variant of VRP. To address this challenging issue, the authors leverage a novel neural network integrated with a heterogeneous attention mechanism to empower the policy in deep reinforcement learning to automatically select the nodes. In particular, the heterogeneous attention mechanism specifically prescribes attentions for each role of the nodes while taking into account the precedence constraint, i.e., the pickup node must precede the pairing delivery node. Further integrated with a masking scheme, the learnt policy is expected to find higher-quality solutions for solving PDP. Extensive experimental results show that the authors' method outperforms the state-of-the-art heuristic and deep learning model, respectively, and generalizes well to different distributions and problem sizes.

• Record URL:
  http://dx.doi.org/10.1109/TITS.2021.3056120
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/41297384
• Supplemental Notes:
  • Copyright © 2022, IEEE.
• Authors:
  • Li, Jingwen
  • 0000-0001-8661-5695
  • Xin, LIang
  • 0000-0002-7449-2453
  • Cao, Zhiguang
  • 0000-0002-4499-759X
  • Song, W
  • Lim, Andrew
  • 0000-0003-0510-8080
  • Song, Wen
  • 0000-0001-7624-1861
  • Zhang, Jie
• Publication Date: 2022-3

Language

• English

Media Info

• Media Type: Web
• Features: Figures; References;
• Pagination: pp 2306-2315
• Serial:
  • IEEE Transactions on Intelligent Transportation Systems
  • Volume: 23
  • Issue Number: 3
  • Publisher: Institute of Electrical and Electronics Engineers (IEEE)
  • ISSN: 1524-9050
  • Serial URL: http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=6979

Subject/Index Terms

• TRT Terms: Heuristic methods; Machine learning; Neural networks; Pickup and delivery service
• Identifier Terms: Vehicle Routing Problem
• Subject Areas: Data and Information Technology; Freight Transportation; Operations and Traffic Management; Planning and Forecasting;

Filing Info

• Accession Number: 01845900
• Record Type: Publication
• Files: TRIS
• Created Date: May 20 2022 9:32AM