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

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.

• Record URL:
  • https://doi.org/10.1016/j.trb.2018.01.009
• Record URL:
  • http://www.sciencedirect.com/science/article/pii/S0191261517306586
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/01912615
• Supplemental Notes:
  • Abstract reprinted with permission of Elsevier.
• Authors:
  • Lei, Chao
  • Ouyang, Yanfeng
• Publication Date: 2018-3

Language

• English

Media Info

• Media Type: Web
• Features: Appendices; Figures; References; Tables;
• Pagination: pp 90-109
• Serial:
  • Transportation Research Part B: Methodological
  • Volume: 109
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 0191-2615
  • Serial URL: http://www.sciencedirect.com/science/journal/01912615

Subject/Index Terms

• TRT Terms: Approximation (Mathematics); Bicycles; Continuum (Mathematics); Demand; Lagrangian functions; Pickup and delivery service; Vehicle sharing
• Uncontrolled Terms: Continuous approximations; Pickup and delivery problem; Repositioning
• Subject Areas: Freight Transportation; Operations and Traffic Management; Pedestrians and Bicyclists; Planning and Forecasting;

Filing Info

• Accession Number: 01662815
• Record Type: Publication
• Files: TRIS
• Created Date: Mar 16 2018 9:52AM