A Column Generation Approach for Public Transit Enhanced Robotic Delivery Services

Yishay Shapira, M.Sc student  Advisor: Dr. Mor Kaspi

Via Zoom click here

Abstract:
Autonomous Mobile Robots (AMRs) is a new concept in technology that relies on vehicle autonomy capabilities. In this concept, small robots provide point-to-point deliveries on sidewalks at pedestrian speed, powered by small batteries that limit their service range to around 3 km. This study aims to improve the service by incorporating public transit into the system. By allowing the robots to travel on board public transit vehicles, the service range can be extended, and energy consumption can be reduced. The operational planning problem in the studied AMR-based services is a special case of the Pickup and Delivery Problem (PDP) with Full Truck Load and multiple modes of transport. We develop two mixed integer programming formulations for the problem: an arc-based and path-based. The path-based formulation is more compact but the number of routes to consider grows exponentially with the number of requests. To overcome this challenge, we develop a column generation approach. We define an initial set of potentially good routes and formulate the subproblem of finding new promising routes as a resource-constrained shortest path problem. We use a dynamic programming algorithm to solve the sub-problem and parallel computing to reduce computing time. The numerical experiment results show that the column generation approach can solve instances with up to 150 requests in a few seconds, while the arc-based formulation only enables solving instances with up to 15 requests. Furthermore, we conducted a case study utilizing real-world data from the city of Tel Aviv. The outcomes of this study demonstrate how the integration of public transit extends the service range of the robots, enabling them to handle a greater number of service requests while conserving their energy. This study highlights the potential benefits of incorporating public transit into AMR-based services and provides a practical approach to solving the operational planning problem.

Bio:

Yishay Shapira is an M.Sc. student at the Department of Industrial Engineering at Tel Aviv University. Yishay holds a B.Sc. degree in Industrial Engineering and Management, from The Jerusalem College of Technology. Yishay works as a Data Scientist at Gett. This work was conducted under the supervision of Dr. Mor Kaspi