With the development and popularization of autonomous driving technology, it has become the trend of replacing traditional manned private vehicles with autonomous vehicles in the future. This paper assumes that all travel demands are met by Shared Autonomous Vehicle (SAV). The objective of this paper is to compare the efficiency of two methods, i.e. graph theory method and the Multiple Travelling Salesman Problem (MTSP) method, in solving the minimum fleet size problem. Dataset used in this study is the trajectory data of 50 new energy private cars in Shanghai for one year. Travel demands are first extracted. A specific method for calculating whether two trips can be connected (served by one SAV) is given and the connection matrix is obtained. Then, the specific procedures of transforming the minimum fleet size problem into the minimum path cover problem on directed graph (graph theory method) or into MTSP shortest path problem (MTSP method) are introduced. It is proved that the transformation is effective. Hopcroft-Karp algorithm is adopted in graph theory method, while genetic algorithm (GA) is adopted in the MTSP method. Results show that graph theory method performs better both in the quality of solution and the computing time than the MTSP method. The results indicate that a SAV can replace 2.5 traditional private cars on average.

Shared autonomous vehicle (SAV);;Minimum fleet size;Graph theory;Hopcroft-Karp algorithm;Multiple travelling salesman problem (MTSP);Genetic algorithm (GA)