The Dial-a-Ride problem with meeting points: A problem formulation for shared demand–responsive transit

Document Type

Journal Article

Publication Date

2024

Subject Area

mode - demand responsive transit, planning - methods

Keywords

Dial-a-Ride, shared demand–responsive transit, meeting points

Abstract

In this paper, a formulation for the Dial-a-Ride Problem with Meeting Points (DARPmp) is introduced. The problem consists of defining routes that satisfy trip requests between pick-up and drop-off points while complying with time window, ride time, vehicle load, and route duration constraints. A set of meeting points is defined, and passengers may be asked to use these meeting points as alternative pickup or drop-off points if this results in routes with lower costs. Incorporating meeting points into the DARP is achieved by formulating a mixed-integer linear program. Two preprocessing steps and three valid inequalities are introduced, which improve the computational performance when solving the DARPmp to global optimality. Two versions of the Tabu Search metaheuristic are proposed to approximate the optimal solution in large-scale networks due to the NP-hardness of DARPmp. Performing numerical experiments with benchmark instances, this study demonstrates the benefits of DARPmp compared to DARP in terms of reducing vehicle running costs.

Rights

Permission to publish the abstract has been given by Elsevier, copyright remains with them.

Comments

Transportation Research Part C Home Page:

http://www.sciencedirect.com/science/journal/0968090X

Link to Full Text

Share

COinS