Clustered tabu search optimization for reservation-based shared autonomous vehicles

ABSTRACT

This paper investigates the optimization of Reservation-based Autonomous Car Sharing (RACS) systems, aiming at minimizing the total vehicle travel time and customer waiting time. Thus, the RACS system and its routing are formulated with a consideration for system efficiency and passengers’ concerns. A meta-heuristic Tabu search method is investigated as a solution approach, in combination with K–Means (KMN–Tabu) or K–Medoids (KMD–Tabu) clustering algorithms. The proposed solution algorithms are tested in two different networks of varying complexity, and the performance of the algorithms is evaluated. The evaluation results show that the TS method is more suitable for small-scale problems, while KMD–Tabu is suitable for large-scale problems. However, KMN-Tabu has the least computation time, although the solution quality is lower.

KEYWORDS:

• Autonomous Vehicles (AV)
• Shared Autonomous Vehicle (SAV)
• shared mobility
• car sharing
• vehicle assignment
• routing optimization
• tabu search
• clustering

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research has been supported by the European Union’s Horizon 2020 research and innovation programme under grant agreement No. [815069] [project MOMENTUM (Modelling Emerging Transport Solutions for Urban Mobility)]; the German Research Foundation – Deutsche Forschungsgemeinschaft (DFG) Project number [392047120] (Research grants in collaboration with China); and the International Graduate School of Science and Engineering – IGSSE (MO3 Project) [12.04 - MO3].