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

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

Transportation Research Part B: Methodological, 2019, vol. 129, issue C, 351-380

Abstract: 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.

Keywords: Pickup and delivery problems with transfers; Dynamic programming; Cumulative service states; Cumulative flow count diagrams; Lagrangian heuristics (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261517306859
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:129:y:2019:i:c:p:351-380

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2019.09.015

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().