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

Dongyang Xu, Lu Zhen, Hing Kai Chan, Jianjiang Wang, Ligang Cui

Research output: Journal PublicationArticlepeer-review


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, our 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 our 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.

Original languageEnglish
Article number104488
JournalTransportation Research Part C: Emerging Technologies
Publication statusPublished - Mar 2024


  • Branch-and-cut
  • Transportation
  • Unpaired pickup and delivery
  • Valid inequalities
  • Vehicle routing

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Automotive Engineering
  • Transportation
  • Management Science and Operations Research


Dive into the research topics of 'An exact algorithm for unpaired pickup and delivery vehicle routing problem with multiple commodities and multiple visits'. Together they form a unique fingerprint.

Cite this