Continuous Approximation for Demand Balancing in Solving Large-scale One-commodity Pickup and Delivery Problems

Chao Lei, Yanfeng Ouyang

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)90-109
Number of pages20
JournalTransportation Research Part B: Methodological
Volume109
DOIs
StatePublished - Mar 2018

Keywords

  • Lagrangian relaxation
  • One-commodity pickup and delivery
  • bike-sharing
  • continuum approximation
  • demand balancing

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Fingerprint Dive into the research topics of 'Continuous Approximation for Demand Balancing in Solving Large-scale One-commodity Pickup and Delivery Problems'. Together they form a unique fingerprint.

Cite this