University of Twente Student Theses
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.
|
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 |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page