A congestion-aware Tabu search heuristic to solve the shared autonomous vehicle routing problem

In this study, we aim to solve the shared autonomous vehicle (SAV) routing problem under the effects of congestion in the road network. The SAV routing problem is the problem of finding an optimal SAV-traveler assignment as well as the SAV route choice. Since widespread use of SAVs would cause significant congestion of road networks, it is essential to consider the effects of traffic congestion on SAV route choice. We develop a tabu search (TS) heuristic to solve for SAV routing problem. The heuristic aims to minimize the total person travel time experienced by travelers by exploring the solution space using a swap procedure. The total person travel time is defined as the total time spent by all travelers entering the network in an SAV trip. A Nearest Traveler Neighborhood is defined to choose candidate travelers to consider for the swap procedure. An agent based simulation of the traffic network is used to determine the experienced travel times for each solution from the TS heuristic. The Sioux Falls network is used to test the performance of TS for various demand and fleet sizes. A series of experiments are performed to understand the sensitivity of the heuristic to its parameters and the congestion in the road network. The heuristic is found to produce encouraging results in reducing the total person travel time for differing fleet sizes and demand levels.