Path-matching Algorithm For Vehicle Routing Problem Of Freight Load Matching

Freight transportation load matching is a kind of transportation modes in traffic transport industry with particular historical circumstance, which made great contributes for raising transportation efficiency. During this transportation mode, one of the most important links is information communication. Traditional communication of freight load matching information is mainly through freight transportation stations on both sides of road. This results low efficiency or lose trading opportunity, because sometimes cannot find proper vehicle when exist supply of goods, and also sometimes just in contrary. Therefore, in 1998 ministry of communication invested 10 billion to contribute HuaXia transport online, developing stowage with network. In subsequent years, a few more website was put into operation. Freight load matching information communicating with network can widen channel, benefit to transaction, reduce no-load rate to some extent, and improve transport efficiency, which is the correct direction of freight load matching transportation mode. However, publish and select information through browsing web page is stile in low rate, so we need a new auto select method based on rout characters.Freight load matching routing matching problem belongs to a kind of open vehicle routing problem. At present, the research of these problems often oriented to mathematic model, which need a long time to set up the model and calculate. This is not on real-time, and cannot solve the actual freight transportation load matching problems directly.According to this situation, investigating the production, development and operation of freight transpiration in our country sufficiently, the thesis evaluates stowage mode with website and the function, introducing network graph mode, and proposes a path matching algorithm based on traffic network. The algorithm which using the distance relation of the nodes in the traffic network, can search information of freight trips between given O D points and trips which intersect groups of adjacent points respectively of O D points, calculate the freight route with best benefit cost ratio separately, also can analyze and evaluate and filter these information in the light of characteristic of freight route so that the load matching be convenient. Besides introducing the thought of the algorithm, the thesis also analyzes the complexity in time and space, in order to calculate the availability. In the end, the thesis introduces necessary data structure, performance function and some key code in this algorithm.