The Dial-a-Ride Problem with Transfers and Walking

Abstract:
The Dial-a-Ride Problem (DARP) consists of defining routes and schedules for a fleet of vehicles serving multiple transportation requests within a service area. In this work, we define and study a new variant of the DARP which considers both transfers and walking, namely, the DARP with Transfers and Walking (DARPTW). In particular, passengers are allowed to transfer multiple times and their itineraries may include several walking segments. The goal of the DARPTW is to minimize a bi-objective function consisting of the total distance covered by the vehicles and the total excess time of the passengers, while considering limitations on the number of transfers performed by each user and the total distance walked.

Introducing transfers and walking presents several opportunities. Multiple transfers may allow balancing the vehicle loads and reducing the service area covered by each vehicle, by decomposing itineraries to separate service segments that would be served by different vehicles. Walking may assist in reducing unnecessary vehicle detours to extreme regions of the service area. Additionally, walking may facilitate significant shortcuts that cannot be fulfilled by the vehicles due to travel directions imposed by the road network . Nevertheless, these opportunities
generate a challenging problem to solve. Specifically, the DARPTW generalizes the DARP and therefore is also
NP-Hard.
We devise an efficient algorithm for the scheduling sub-problem, which minimizes the total travel time of the passengers. The algorithm determines the feasibility of given routing plans and applies fast heuristics to construct good schedules. We implement the algorithm within a Large Neighborhood Search framework in search for promising solutions of the DARPTW. Numerical experiments are conducted using real-world data obtained from Bubble-Dan in Tel Aviv. Preliminary results over thousands of scheduling sub-problem instances demonstrate that our heuristic algorithm finds the optimal schedule in more than 90% of the cases and that the entire framework produces high quality solutions.
This work was performed under the supervision of Dr. Mor Kaspi

Bio:
Idan Meshualmi is a Master student at the Department of Electrical Engineering at Tel-Aviv University. He holds a B.Sc. in Electrical Engineering and Electronics and a B.Sc. in Physics from Tel Aviv University. In parallel with his studies, Idan serves as an officer at the IDF satellite unit. As part of his position, he develops optimization algorithms and applies computer vision and deep learning techniques.

The lecture will be heldon

Tuesday, November 16, 2021, 14:00 PM at Room 206

and Via Zoom - https://tau-ac-il.zoom.us/j/81388449216?pwd=QU91L0pXVHc0dS90bFZaUjBoS1FkZz09