Research On Ride-sharing Route Planning For Online Car-hailing

Online ride-sharing has largely alleviated the pressure on travel,environment and resources.The ride-sharing work mainly has two aspects: ride-matching and route planning.Starting from these two aspects and taking into account the interests of riders and drivers,this paper proposes Matrix Partition-based Multi-Objective Order Assignment Algorithm(MPB-MOOAA)and Landmark Segmentation-based Multi-Objective Route Planning Algorithm(LSB-MORPA)to solve the problem of ride-matching and route planning in the ride-sharing environment,and the main important work of this paper:1.An optimization model of the multi-objective order assignment problem was established with the objectives of maximizing service quality and maximizing shared mileage rate,MPB-MOOAA was proposed.First,the approximate shortest distance between two points is proposed to replace the computationally expensive shortest path distance.Thus,the time complexity of the algorithm is reduced;then the partition is adopted to gather riders and drivers with similar journeys,the relation matrix construction algorithm is proposed,which decomposes a matrix into multiple small matrices for processing and greatly reduces the scale of the problem;finally,the matrix compression mechanism is proposed to reduce the storage space,reducing the space complexity of the algorithm.The experimental results show that MPB-MOOAA is suitable for different practical scenarios and has more advantages in order assignment than other classic multi-objective evolutionary algorithms.2.An optimization model of the multi-objective path planning problem was established with the objectives of the minimum travel distance and the maximum number of compatible passengers,and LSB-MORPA was proposed.The algorithm takes the evolutionary algorithm as the basic algorithm.introduces bi-directional random walk in the initial population structure,designs a new crossover and mutation operator and predicts the non-dominated solution set to provide drivers with multiple route options.In order to improve the efficiency and diversity of recommended routes,the algorithm segmented the route by introducing landmarks to improve the route coverage rate of passengers.Experimental results show that the diversity and convergence of LSB-MORPA solutions are better.Compared with the algorithm without landmarks,LSB-MORPA has significantly improved the success rate of non-dominated path recommendation.3.Implement the online car-hailing route planning system.MPB-MOOAA and LSBMORPA are implemented based on the open-source j Metal framework.To make it more suitable for route planning,a new crossover operator and mutation operator are added.Use JSP combined with Servlet to implement the visual interface.