A congestion-aware Tabu search heuristic to solve the shared autonomous vehicle routing problem. Issue 4 (4th July 2021)

• Record Type: Journal Article
• Authors: Venkatraman, Prashanth; Levin, Michael W.
• Is Part Of: Journal of intelligent transportation systems. Volume 25:Issue 4(2021)
• Page Start: 343
• Page End: 355
• Publication Date: 2021-07-04
• Subjects: Cell transmission model -- dynamic traffic assignment -- Shared autonomous vehicles -- Tabu search; Intelligent transportation systems -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.312
• DOI: 10.1080/15472450.2019.1665521
• Languages: English
• ISSNs: 1547-2450

Abstract

Abstract: 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.