货物的独立配送路径问题

The Problem of Independent Distribution Path of Goods

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

Abstract: 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.

1. 问题描述

本文中，我们考虑的问题是货物独立路径配送的情况下，选择车辆配送路线，使得总运费成本最小。在现实生活中，从任意配送中心i到配送中心j的最大配送量一致，而且不同的两个配送中心i与j之间没有直接到达的配送路线这是可能的，但是我们需要从i配送货物到j，因此我们需要从i出发配送货物到达其他配送中心k，然后再从k出发配送货物到其他配送中心s，如此不断的交替，最后从某一配送中心t出发配送货物到达j。问题是如此交替循环的配送过程中，如何安排货车从不同的配送中心按照独立的车辆路线，使得按照该路线配送总成本最小。

货物的独立路径配送问题的数学描述：图 $D=\left(V,A,\omega ,c\right)$，这里权重函数 $\omega :A\to R^{+}$，表示通过该弧所需要的配送时间，c是定义在弧 $\left(i,j\right)$ 上的容量，且 $c\equiv L\left(L\in N^{+}\right)$ 其中L为定值，以吨为单位。点 $s,t\in V$，s为源点，t为汇点，令F为从s点出发的总货物质量，F以吨为单位。目标是求满足条件的总配送时间最短的 $s-t$ 路 $p_1,p_2,\cdots ,p_R$，其中 $R=\lceil F/L\rceil$。

2. 算法设计

算法1 [3]

Step0：取第一个可行流f为零流，取 $c\equiv 1$。

Step1：求X增广链。

1.0给s标号 $l_s=\text{0}$，把所有点规定为未检验点。

1.1若所有已经标号的顶点已经检验完毕，转Step3；否则，任意取一个已经标号却未获得检查的点i，检验与点i关联的弧。 $\forall \left(i,j\right)\in A$，如果 $x_{ij}=0$ 并且j没有标号，则给j标号 $l_j=+i$ ； $\forall \left(j,i\right)\in A$，如果 $x_{ji}=1$ 并且j没有标号，那么就给j标号 $l_j=-i$。当点i的所有关联弧都已经检验完成，则令点i为已经检验，转1.2。

1.2：如果t获得标号，则找到一条增广链，转Step2。否则转1.1。

Step2：对X增广。

2.0：令 $j=t$。

2.1：若j的前点标号 $l_j=0$，即j是s，对X增广结束，消除D中所有顶点的标号，转Step1。否则转2.2。

2.2：如果 $l_i=+i$，则输出 $\left(i,j\right)$，取 $x_{ij}:=x_{ij}+1$，用点i代替点j，转2.1；如果 $l_i=-i$，则输出 $\left(j,i\right)$，取 $x_{ji}:=x_{ji}-1$，用点i代替点j，转2.1。

Step3：X的最大流就是有向图D的独立配送路径数，输出配送路径条数K。

算法2 [4]

Step0：令零流为初始可行流。

Step1：假如 $v\left(x\right)=R$，则X所经过的弧就是有向图D的配送总费用最小的R条独立路径，结束。否则，转Step2。

Step2：把X所经过的弧方向反向，并且令所经弧的权值 $\omega =-\omega$，新的图记为 $H\left(x\right)$。

Step3：用Frod算法在有向图 $H\left(x\right)$ 中求最短路P，转Step4。

Step4：使X沿P增广1，获得新的X，转Step1。

算法3

Step1：通过算法1求图D中s到t的弧独立路径数K，若 $K\ge R$，转Step2。否则，输出问题无解。

Step2：通过算法2求图D中配送总费用最小的R条独立配送路径。

3. 算法可行性的分析

引理3.1 [3]： $D=\left(V,A,\omega ,c\right)\left(c\equiv 1\right)$ 上的K (K为正整数)条独立配送路径与流值为K的0~1整数流一一对应。

引理3.2 [4]：有向图 $D=\left(V,A,\omega ,c\right)$ 是一个带源点s与汇点t的容量–费用网络，f是D上流值为v的最小费用流，P是 $D\left(f\right)$ 中从s到t的最小费用路， $\delta$ 是P的容量， $\theta =\delta =1$， $f^{\prime }$ 是定义在 $D\left(f\right)$ 的路P上流值为 $\theta =\text{1}$ 的一个可行流，

${f^{\prime }}_{ij}=\{\begin{array}{l}1,若\left(i,j\right)\in A\left(P\right)\\ 0,若\left(i,j\right)\notin A(P)\end{array}$

则 $f+f^{\prime }$ 是D上流值为 $v+\theta$ 的最小费用流。

定理3.1算法3是货物的独立路径配送问题的最优算法。

证明：由引理3.1，我们采用最大流的Ford-Fulkerson算法来解决独立配送路径问题，判断有向图D是否有解。由引理3.2，我们在有向图D上用算法2求配送总费用最小的R条独立配送路径。算法3的Step1所需要的时间上界是 $O\left(nm\right)$。Step2的计算量为 $O\left(Rmn\right)$，因此算法3的时间复杂度为 $O\left(Rmn\right)$。定理得证。