University of Twente Student Theses

Login

The dial-a-ride problem with meeting points : a problem formulation for shared demand responsive transit

Cortenbach, L.E. (2023) The dial-a-ride problem with meeting points : a problem formulation for shared demand responsive transit.

[img] PDF
1MB
Abstract:Recent developments in the communication technology make Demand-Responsive Transit (DRT) more accessible for everyone. In the ride-sharing version of DRT, vehicles have to make detours from the shortest path to pickup and drop off passengers, which increases the travel time for both the operator and the passengers. This problem could be avoided if passengers are asked to walk a short distance from their origin to their pickup location and from their drop off location to their destination. These alternative pickup and drop off points are called meeting points. The aim of this work is to incorporate finding optimal meeting points in a well-known problem formulation for DRT, which is the Dial-a-Ride Problem (DARP). The objective of the DARP is to find optimal routes for a number of trip requests from passengers with different origins and destinations. Incorporating meeting points in the DARP is done by formulating a Mixed-Integer Linear Program, which is called the DARPmp. The DARP is extended to find optimal meeting points while generating optimal routes by adding sets, parameters, variables and constraints. Two preprocessing steps and two valid inequalities are introduced, which improve the computational performance when solving the DARPmp to global optimality. Next to that, two meta-heuristics are proposed to approximate the optimal solution for the DARPmp for a large number of trip requests. A Tabu Search framework is proposed to find solutions for the problem. In the first version of the Tabu Search, a low-cost solution for the DARP is found, for which in the last step the best meeting points are inserted into the routes. For the second version of the Tabu Search, meeting points are inserted in the routes every step of the search proces. The exact solution method and both Tabu Search algorithms are tested on 12 benchmark instances with 2 to 4 vehicles, 16 to 48 trip requests and 24 to 72 meeting points. When using the preprocessing steps and valid inequalities, an optimal solution is found for the 5 smallest benchmark instances. Both Tabu Search algorithms are able to find a solution for all 12 benchmark instances. The first Tabu Search algorithm finds solutions with an optimality gap ranging from 0\% to 1,65\%, compared to the optimal solution. The run times for this algorithm range from 14,07 seconds to 850,51 seconds. The second Tabu Search algorithm finds solutions with an optimality gap ranging from 0\% to 2,24\% and has run times ranging from 38,20 to 9051,69 seconds. On passenger level, the meeting points sometimes decrease the travel time and in other cases they increase the travel time. However, the DARPmp has the potential to minimize the total routing costs.
Item Type:Essay (Master)
Clients:
TNO, Den Haag, The Netherlands
Faculty:ET: Engineering Technology
Subject:31 mathematics, 50 technical science in general, 55 traffic technology, transport technology, 56 civil engineering
Programme:Civil Engineering and Management MSc (60026)
Link to this item:https://purl.utwente.nl/essays/94545
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page