A cumulative service state representation for the pickup and delivery problem with transfers

Monirehalsadat Mahmoudi, Junhua Chen, Tie Shi, Yongxiang Zhang, Xuesong Zhou

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


The pickup and delivery problem with transfers is a challenging version of the vehicle routing problem. In order to tackle this problem, we add a time dimension to physical transportation networks to not only track the location of vehicles at any time but also impose parcels’ pickup/delivery time windows, synchronization time points, and precedence constraints to the problem. We also add another dimension, described as the “cumulative service state” to the constructed space-time network to track the service status of parcels at any time. The constructed network not only handles real-life transportation networks but also is well-suited for connecting microscopic cumulative service states to macroscopic cumulative flow count diagrams. We develop a continuous time approximation approach using cumulative arrival, departure, and on-board count diagrams to effectively assess the performance of the system and dynamically constrict the search space. To handle a large-scale set of parcels, we develop the traditional cluster-first, route-second approach. We reach optimality for the clusters derived from the original set of parcels. We also propose an integer programming model to improve the vehicles’ efficiency. We perform extensive numerical experiments over the standard data set used by Ropke and Pisinger (2006) and real-world large-scale data set proposed by Cainiao Network (with about 10,000 delivery orders) to examine the computational efficiency of our developed algorithm.

Original languageEnglish (US)
Pages (from-to)351-380
Number of pages30
JournalTransportation Research Part B: Methodological
StatePublished - Nov 2019


  • Cumulative flow count diagrams
  • Cumulative service states
  • Dynamic programming
  • Lagrangian heuristics
  • Pickup and delivery problems with transfers

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'A cumulative service state representation for the pickup and delivery problem with transfers'. Together they form a unique fingerprint.

Cite this