An Exact Method for a First-Mile Ridesharing Problem

Motivated by the worldwide development of shared mobility, the authors investigate a vehicle routing problem with time windows and deadlines called the first-mile ridesharing problem (FMRSP). The FMRSP involves routing a fleet of vehicles, each servicing customers within specific time windows. The FMRSP generalizes the well-known vehicle routing problem with time windows (VRPTW), additionally imposing that each vehicle route arrives at the destination before the earliest deadline associated with the set of customers served by the route. The FMRSP is also related to the VRPTW and release dates, where in addition to time window constraints, a release date is associated with each customer defining the earliest time that the order is available to leave the depot for delivery. For the FMRSP, the authors present an exact method based on a branch-price-and-cut (BPC) algorithm combining state-of-the-art techniques and an innovative pricing algorithm. The pricing algorithm is based on a bidirectional bucket graph-based labeling algorithm, in which the backward extension of a label is computed in a constant time. Effective dominance rules used to speed up the computation are also described. Extensive computational studies demonstrate that the authors' proposed BPC algorithm can solve optimality-modified Solomon benchmark instances involving up to 100 customers and real-world instances involving up to 290 customers.

• Record URL:
  • https://doi.org/10.1287/trsc.2022.0139
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Supplemental Notes:
  • Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
• Authors:
  • Wang, Sihan
  • Baldacci, Roberto
  • Yu, Yang
  • Zhang, Yu
  • Tang, Jiafu
  • Luo, Xinggang
  • Sun, Wei
• Publication Date: 2023-11

Language

• English

Media Info

• Media Type: Web
• Features: References;
• Pagination: 1581-1604
• Serial:
  • Transportation Science
  • Volume: 57
  • Issue Number: 6
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Customers; First mile and last mile; Optimization; Routing; Shared mobility; Time windows; Vehicle fleets
• Subject Areas: Freight Transportation; Operations and Traffic Management; Planning and Forecasting;

Filing Info

• Accession Number: 01902146
• Record Type: Publication
• Files: TRIS
• Created Date: Dec 15 2023 8:44AM