Continuous approximation for demand balancing in solving large-scale one-commodity pickup and delivery problems

Chao Lei and Yanfeng Ouyang

Transportation Research Part B: Methodological, 2018, vol. 109, issue C, 90-109

Abstract: The one-commodity pickup and delivery problem (1-PDP) has a wide range of applications in the real world, e.g., for repositioning bikes in large cities to guarantee the sustainable operations of bike-sharing systems. It remains a challenge, however, to solve the problem for large-scale instances. This paper proposes a hybrid modeling framework for 1-PDP, where a continuum approximation (CA) approach is used to model internal pickup and delivery routing within each of multiple subregions, while matching of net surplus or deficit of the commodity out of these subregions is addressed in a discrete model with a reduced problem size. The interdependent local routing and system-level matching decisions are made simultaneously, and a Lagrangian relaxation based algorithm is developed to solve the hybrid model. A series of numerical experiments are conducted to show that the hybrid model is able to produce a good solution for large-scale instances in a short computation time.

Keywords: One-commodity pickup and delivery; Demand balancing; Bike-sharing; Continuum approximation; Lagrangian relaxation (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261517306586
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:109:y:2018:i:c:p:90-109

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.2018.01.009

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 ().