空车配货VRP问题的路径匹配算法

Path-Matching Algorithm for Vehicle Routing Problem of Freight Load Matching

针对现有VRP(Vehicle routing problem)问题的精确解法和启发式算法应用于空车配货信息检索时的局限,引入图的概念,提出了一个基于交通路网的路径匹配算法,给出了算法复杂度分析。该算法利用交通路网中各结点之间的距离关系,检索给定起讫点间及起讫点与各自邻近结点群之间存在的配货信息,同时规划出收益费用比最优的行驶路径,并能根据配货行驶路径的特点对检索出的所信息进行分析、评价和优选,以方便空车配货组织。最后用一个仿真实例验证算法的有效性。

To overcome the limitation of the existing exact solution and heuristic algorithms in load matching information retrieval, the graph theory was introduced. Then, an algorithm based on traffic network was put forward, at the same time, the algorithm＇s complexity analysis was done. The algorithm, which uses the distance relation among the nodes in the traffic network, can search information of freight trips between the given OD points and their adjacent node groups, meanwhile, can calculate the freight route with the best benefit cost ratio separately. In addition, the algorithm can analyze, evaluate and filter the information in the light of the characteristics of the freight route so that the load matching become convenient. The availability of the algorithm is proved by a simulation at the end of the paper.