带循环时间窗口的独立路径配送问题

Delivery problems of independent path with cyclic time window

通过优化物流的配送运输网络,可以有效降低配送成本.带循环时间窗口的独立路径配送问题实际是车辆路径优化问题,属于NP-hard问题类.定义了循环时间窗口,并设计了图形预处理算法,通过建立有向赋权网络上带循环时间窗口的物流配送问题的数学模型,构造有向网络赋权辅助图,在辅助图上采用最大流的Ford-Fulkerson算法来解决弧独立路径问题,判断问题是否有解,之后用最小费用流的最小费用路算法来求权值和最小的R条弧独立路径,得到该问题的一个最优算法,为物流配送环节提供新思路.

By optimizing the delivery of logistics and transportation network,the delivery cost can be reduced effectively. The Independent Route Delivery Problem with Cyclic Time Window is a vehicle routing problem first proposed by Dantzig and Ramser in 1959. It is a NP-hard delivery problem of independent path with cyclic time window. This paper defines the cyclic time window and designs a graphic preprocessing algorithm. A mathematical model of logistics delivery with time windows on the directed weighted network is built,and a weighted auxiliary digraph of the directed network is constructed. On the auxiliary digraph,the Ford-Fulkerson algorithm of the maximum flow is used to solve the arc-independent path problems,and then the minimum cost path of the minimum cost flow algorithm is used to find R independent paths with the minimum total cost and to get an optimal solution in order to offer new ideas for logistics delivery.