货物的独立配送路径问题

The Problem of Independent Distribution Path of Goods

通过优化物流的配送运输网络,可以有效降低配送成本。货物的独立配送路径问题实际是车辆路径优化问题,车辆路径优化问题最早由Dantzig和Ramser于1959年提出,属于NP-hard问题类。本文通过在有向图上采用最大流的Ford-Fulkerson算法来解决弧独立路径问题,判断问题是否有解,之后用最小费用流的最小费用路算法来求权值和最小的R条弧独立路径,得到该问题的一个最优算法,为物流配送环节提供新思路。

By optimizing the distribution of logistics and transportation networks, the cost of distribution can be reduced effectively. The problem of independent path distribution of goods is vehicle routing problem. Vehicle routing problem was first proposed by Dantzig and Ramser in 1959. It is NP-hard problem. In this paper, the Ford-Fulkerson algorithm of maximum flow is used to solve the arc-independent path problems, and then the minimum cost path of minimum cost flow algorithm is used to find R independent paths with minimum total cost. And an optimal solution is obtained to provide new ideas for logistics distribution.