An exact algorithm for unpaired pickup and delivery vehicle routing problem with multiple commodities and multiple visits

This paper addresses a new multi-commodity unpaired pickup and delivery vehicle routing problem in which each vehicle is allowed to visit each customer more than once for both pickup and delivery of each commodity. It is a complex variant of the classical capacitated vehicle routing problem and comes from resource transfer among different plants in a distributed manufacturing environment. Notably, the pairing decisions of pickup and delivery for each commodity and the routing decisions among customers are interdependent, and they need to be made simultaneously and collaboratively. Firstly, a mixed integer programming model is developed, and then new valid inequalities are derived to improve the linear programming relaxation. Afterwards, a branch-and-cut algorithm is proposed by exploring different branching strategies and tailored separation algorithms. Computational results based on real-case instances from an automobile manufacturing company demonstrate that the costs are considerably reduced by considering the multiple visits compared to the single visit of each customer. In addition, the authors' proposed branch-and-cut algorithm outperforms a manual solution method adopted by the company in practice and two solution methods in the literature. Furthermore, two adaptations of the authors' branch-and-cut algorithm also perform better than two state-of-the-art algorithms in solving two closely-related problems in terms of solution quality and computation time. Sensitivity analyses with respect to vehicle capacity, vehicle duration, and vehicle speed are conducted to derive several valuable managerial insights.

• Record URL:
  • https://doi.org/10.1016/j.trc.2024.104488
• Record URL:
  • http://www.sciencedirect.com/science/article/pii/S0968090X24000093
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/0968090X
• Supplemental Notes:
  • © 2024 Elsevier Ltd. All rights reserved. Abstract reprinted with permission of Elsevier.
• Authors:
  • Xu, Dongyang
  • Zhen, Lu
  • Chan, Hing Kai
  • Wang, Jianjiang
  • 0000-0003-0690-9787
  • Cui, Ligang
  • 0000-0001-6579-9958
• Publication Date: 2024-3

Language

• English

Media Info

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

Subject/Index Terms

• TRT Terms: Algorithms; Commodity flow; Mixed integer programming; Pickup and delivery service; Routing; Vehicle capacity
• Identifier Terms: Vehicle Routing Problem
• Subject Areas: Data and Information Technology; Freight Transportation; Operations and Traffic Management; Vehicles and Equipment;

Filing Info

• Accession Number: 01910374
• Record Type: Publication
• Files: TRIS
• Created Date: Feb 28 2024 2:12PM