A math-heuristic and exact algorithm for first-mile ridesharing problem with passenger service quality preferences

With the growing demand for high-quality mobility services, transportation service providers need to offer transit services that not only fulfill passengers’ basic travel needs but also ensure an appealing quality of service. During rush hours, fleet sizes are often insufficient to cater to all passenger preferences on service quality, such as ride time and number of co-riders, leading to the sacrifice of service quality for some passengers. Motivated by these practices, the authors investigate a first-mile ridesharing problem incorporating passenger service quality preferences. This problem involves intricate decisions about the match between requests and vehicles, vehicle routing, and route schedules. To solve this problem, they first develop an arc-based mixed-integer linear programming (MILP) model for this problem. For obtaining near-optimal solutions within practical computation time requirements, they reformulate the MILP model as a trip-based set-partitioning model and propose a math-heuristic algorithm. This algorithm builds upon the column-generation algorithm and tailored bidirectional labeling algorithms with novel dominance rules. Additionally, they introduce a proposition to determine the best schedule for each ridesharing route. To obtain the optimal solution for large-scale instances, they introduce a branch-and-price exact algorithm. Computational experiments based on real-world road networks and randomly generated instances confirm the effectiveness and efficiency of the proposed approaches, demonstrating that the proposed matheuristic finds near-optimal solutions within 40 s for all instances. The results also show that the presented approach significantly improves the quality of first-mile services for prioritized riders, with the ratio of satisfied requests increasing by 23% even when the fleet is generally insufficient.

• Record URL:
  • https://doi.org/10.1016/j.tre.2024.103749
• Record URL:
  • http://www.sciencedirect.com/science/article/pii/S1366554524003405
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/13665545
• Supplemental Notes:
  • © 2024 Elsevier Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies. Abstract reprinted with permission of Elsevier.
• Authors:
  • He, Ping
  • Jin, Jian Gang
  • Trépanier, Martin
  • Schulte, Frederik
• Publication Date: 2024-12

Language

• English

Media Info

• Media Type: Web
• Features: References;
• Pagination: 103749
• Serial:
  • Transportation Research Part E: Logistics and Transportation Review
  • Volume: 192
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 1366-5545
  • Serial URL: http://www.sciencedirect.com/science/journal/13665545

Subject/Index Terms

• TRT Terms: Algorithms; First mile and last mile; Quality of service; Ridesharing; Stated preferences
• Subject Areas: Data and Information Technology; Highways; Passenger Transportation; Safety and Human Factors;

Filing Info

• Accession Number: 01930475
• Record Type: Publication
• Files: TRIS
• Created Date: Sep 16 2024 8:56AM