TY - JOUR
T1 - Continuous Approximation for Demand Balancing in Solving Large-scale One-commodity Pickup and Delivery Problems
AU - Lei, Chao
AU - Ouyang, Yanfeng
N1 - Funding Information:
This research was supported in part by the U.S. National Science Foundation via Grants CMMI-1234085 , CMMI-1662825 , a grant from the Zhejiang University - University of Illinois at Urbana-Champaign (UIUC) Institute Research Program, and a Departmental Innovation Research Grant from the Department of Civil and Environmental Engineering at UIUC. We would like to thank Mr. Xiaotong Guo (Tongji University) for helpful discussion at the early stage of this research (when he was a summer intern at UIUC). Very helpful comments from the two anonymous reviewers are also gratefully acknowledged.
Publisher Copyright:
© 2018 Elsevier Ltd
PY - 2018/3
Y1 - 2018/3
N2 - 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.
AB - 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.
KW - Lagrangian relaxation
KW - One-commodity pickup and delivery
KW - bike-sharing
KW - continuum approximation
KW - demand balancing
UR - http://www.scopus.com/inward/record.url?scp=85044660437&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85044660437&partnerID=8YFLogxK
U2 - 10.1016/j.trb.2018.01.009
DO - 10.1016/j.trb.2018.01.009
M3 - Article
AN - SCOPUS:85044660437
VL - 109
SP - 90
EP - 109
JO - Transportation Research, Series B: Methodological
JF - Transportation Research, Series B: Methodological
SN - 0191-2615
ER -