SHUTTLE-LINE ROUTING FOR MOBILITY-ON-DEMAND SYSTEMS WITH RIDESHARING

Abstract

Minimizing the number of private cars on the road is one of the most effective solutions for reducing traffic congestion. Mobility-on-Demand (MoD) is one of the schemes that focuses on more efficient use of cars to reduce their total number. MoD is a car-sharing scheme in which users pick up a vehicle from one rack and drive to another rack near their destination. This allows MoD to provide a private car service that is cheaper than owning one. Differently from MoD, ridesharing is a concept in which multiple users with a similar journey share one vehicle. The operation costs such as fuel are shared among the riders, offering a cheaper operation cost than a private car.

Introducing ridesharing into MoD can further reduce the vehicle fleet size, thus decreasing traffic congestion. Dynamic Vehicle Routing Problem (DVRP) solutions can be used to optimize MoD systems with ridesharing. However, DVRP solutions are extremely complex in terms of the number of passengers and vehicles. Furthermore, these solutions require reoptimization during execution and thus do not scale well for problems with frequently arriving requests.

In order to provide a more scalable solution for shared MoD systems, we propose a problem formulation for designing shuttle-lines for MoD systems. A shuttle-line is very similar to bus lines. Shuttle-line routes are defined as a sequence of stops and the vehicles are deployed at a specific rate for each shuttle-line.

We propose Shuttle-line Routing Problem (SRP), which consists of optimizing shuttle-line routes and their vehicle rates, ensuring a convenient commute for frequently arriving passengers. The objective of SRP is to minimize the number of vehicles deployed on shuttle-line routes for transporting the passengers continuously. Unlike bus lines, SRP is concerned with providing convenient transportation without the need of passengers to transfer between different lines.

In this thesis, we present our Mixed-Integer Bilinear Programming (MIBLP) models for solving SRP variants and linearization of these models using the linearization technique. In addition, we propose a nested optimization approach using Bayesian Optimization for solving our MIBLP models, which provides a more scalable solution of our MIBLP models than the existing solution techniques.