Research And Implementation On Carpooling Algorithm With The Common Departure

With the improvement of citizens’ economic level,the number of private cars owned by commuters is increasing day by day,and the traffic situation is getting worse.Under the situation of high cost of car purchase and maintenance,demand for carpool services among employees within the company has increased sharply.The carpool has been noticed and accepted by people.This way can not only reduce the cost of private car travel,but relieve traffic pressure.Therefore,an efficient strategy to achieve carpooling between employees in the same companies is particularly important.The existing research on the ridesharing is mainly aimed at the taxis,and there is less research work on the carpooling with the common departure(CCD)under the global optimization.In this paper,a CCD problem was proposed and studied,the goal is to find the best matching plan with the least global travel cost.Firstly,grid space index technology and bidirectional shortest path query technology based on coordinate orientation are proposed in the pre-processing of data.The former facilitates the query and management of spatial data information,while the latter can reduce the expansion of irrelevant nodes,then the expansion direction approaches the target query point and speed up the optimal path query rate.Secondly,a three-level matching strategy for solving the CCD problem is established,including destination grid-based allocation,driving route and grid-based allocation,and passenger supplement strategy.The aim is to reduce the detour distance traveled for the driver to serve passenger.Meanwhile,this algorithm can reduce the possibility of passengers traveling individual,and minimize the global travel cost.Finally,the simulation experiment is conducted on real-road networks of Oldenburg,Germany.The results show that compared with the naive algorithm,the error rate of the total driving distance on the three-level matching strategy is 8%,which proved the correctness of the algorithm.In addition,compared with the non-matching method,the global travel cost is reduced by 66.7%.Simultaneously,when the experimental data nodes density was 16%,the average system response time is 2.65 min.It shows that the method has achieved satisfactory performance.Therefore,the three-level matching strategy is an effective algorithm for solving CCD problem.