Continuous approximation for demand balancing in solving large-scale one-commodity pickup and delivery problems. (March 2018)

• Record Type: Journal Article
• Authors: Lei, Chao; Ouyang, Yanfeng
• Is Part Of: Transportation research. Volume 109(2018)
• Page Start: 90
• Page End: 109
• Publication Date: 2018-03
• Subjects: One-commodity pickup and delivery -- Demand balancing -- Bike-sharing -- Continuum approximation -- Lagrangian relaxation; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2018.01.009
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: Hybrid continuous-discrete model for 1-commodity pickup and delivery problems. Continuum approximation for balancing local pickup and delivery demand. Lagrangian relaxation to decompose the discrete and continuous parts of the model. Application contexts include redistribution of shared bikes and cars. Performance tests show superiority of the proposed approach. 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.