Stablely Optimal Vechicle Scheduling Strategy For Shred-vechicle Network Based On Matching Theory

Taxi is one of the most popular transportation in urban areas because they provide great convenience for passengers.However,different ways of obtaining taxi services have many serious shortcomings,such as uncertain waiting time,introducing traffic congestion,service only available at fixed locations,and higher prices for reservations.Currently,many drawbacks of traditional taxi services are overcome by shared-vehicle services that are reserved through the Internet,which provides passengers with more convenient travel.It is a promising traffic service mode,which is more and more popular.Compared with traditional taxi services,this new kind of travel service is favored by people at cheaper prices and better convenience.In addition,such a new kind of vehicle services is appreciated for reducing energy consumption,environmental pollution and traffic congestion.The various vehicle scheduling algorithms currently applied in the field of shared-vehicle service have great deficiencies,which hinders the further development of the new kind model of vehicle services.The shortcomings of current vehicle scheduling algorithms mainly include: scheduling scheme is unstable,the algorithm need to do too much calculation to respond to passengers' requests in time,the algorithm needs to deploy a large number of devices which lead to large cost of deployment and maintenance.In this paper,we mainly study the vehicle scheduling algorithm in the two scenarios of no-sharing and sharing,which are suitable for the shared-vehicle service.We propose the order fee to ensure the optimality and stability of the vehicle scheduling scheme.In order to obtain the appropriate order fee,we propose a distributed algorithm similar to the auction mechanism.In no-sharing vehicle scheduling problem,the distributed algorithm work like this: all passengers repeatedly increases the cost of picking them up,then each vehicle selects the passenger with the most revenue to serve.Algorithm repeats the above two steps until no passengers pursued by more than one vehicle and we finally get the stably optimal vehicle scheduling solution.We demonstrate the stability and optimality of the distributed algorithm.The simulation results show that the distributed algorithm converges to a stable state fastly,and as long as the parameters are set properly,the maximum social benefit can be obtained with great probability,or the social benefit obtained by distributed algorithm has little difference with the optimal solution.In addition,we expand the distributed algorithm slightly and combine the exhaustive method to design a distributedly sharing algorithm to apply to the vehicle scheduling problem in the scenario of sharing.According to simulation,we find that the distributedly sharing algorithm can not find the optimal scheduling scheme,but it can botain a solution whose social benefit can be accepted much faster than the optimal solution.For vehicle scheduling problem with no-sharing and sharing,our algorithms are easy to implement and it can greatly reduce the workload of the central server,which can speed up the system's response to passengers' requests.