Research On Model And Algorithms Of Highway Vehicle Ride Matching Problem

With the rapid development of social economy, the domestic highway network is in thegradual improvement, making an important contribution in the freight and short-distancepassenger transport. But in the highway transportation, there still exists problems of a lot ofno-load rate, resulting in a waste of resources. Vehicle ride matching problem is designed tointegrate the information of vehicles and demands, reduce the rate of no-load, and optimizevehicles’ routes from an overall perspective; In the environmental perspective, the research ofvehicle ride matching problem will reduce the number of vehicles on the road while reducing theno-load rate, and reduce vehicles’ exhaust emissions, which has significance for governance hazeand creating a resource-friendly society.Current research of vehicle ride matching problem is mostly in the background of urbantraffic network.Relatively little research is for the highway network. Compared with the urbanvehicle ride matching problem, highway vehicle ride matching problem has features such aslonger travel distance, relatively fixed travel routes and sites, weaker time-dependent nature,high travel costs, which determine the particularity of highway vehicle ride matching problemstudies. Based on the unique features of the highway network, a mathematical model andalgorithm for highway vehicle ride matching problem is proposed. And Shandong highwaynetwork as a background is used to verify the mathematical model and algorithm.The maincontribution of this paper and the main innovations are as follows:(1) For highway vehicle ride matching problem, propose a matching optimization algorithmof combining genetic algorithm and pushing forward insertion based on direction.Aiming at the highway vehicle ride matching problem, a matching optimization algorithmof combining genetic algorithm and pushing forward insertion based on direction is proposed,which effectively solves the highway vehicle ride matching problem. The pushing forwardinsertion based on direction is used in the initialization, cross and mutation of the geneticalgorithm. What is more, the unexpected incidents are considered in the model. And onlyconsider unexpected incidents probability of sections having low connectivity reliability. Whenoptimizing the routes, the more realistic better routes will be found considering the unexpectedincidents probability parameters. Experimental results show that the algorithm can get a better matching solution.(2) For highway vehicle ride matching problem with transfers, put forward an ant colonyalgorithm based on neighborhood search.Based on the basic highway vehicle ride matching problem, highway vehicle ride matchingproblem with transfers is proposed. Design ant colony algorithm based on neighborhood searchwhich effectively solves the problem. Firstly, expand the search space using the neighborhoodsearch algorithm and determine the start and end set of new demands; Secondly, determine theinitial optimal routes using the ant colony algorithm; Finally, fine-tune the routes. Experimentalresults show that the algorithm can successfully add the new demands to the original routes,which does not change the existing constraints.(3) Design prototype system based on Shandong highway network, testing the variousalgorithms mentioned in this paper.Design prototype system based on Shandong highway network testing the variousalgorithms. The prototype system implements data entry, the algorithm functions and pathsdisplay. Verify the validity of the algorithms. Display the paths of vehicles in an intuitive way. Ithas important reference for the follow-up study of optimization algorithms.This paper proposes the basic highway vehicle ride matching problem and the highwayvehicle ride matching problem with transfers, and gives a detailed mathematical model and thespecific algorithm, and designs the corresponding prototype system in the background ofShandong highway network, which verifies the rationality of the mathematical model and thevalidity algorithms.