基于中国邮递员问题的物流配送线路优化

6/6基于中国邮递员问题的物流配送线路优化基于中国邮递员问题的物流配送线路优化

[

回到原出发点，这样的线路称为欧拉图。

定义2：设G是一个无向连通图，若存在一个回路，经过G中的每一条边一次且仅一次，则称这个同路为欧拉回路：

定义3：设G足一个无向连通图，若在G中通过某顶点的弧的个数为偶数时，这个顶点被称为偶点，否则被称为奇点。

定理1：一个非空连通图是欧拉图当且仅当它没有奇点。定理2：一个连通图有欧拉迹当且仅当它最多有两个奇点。

定理3：设C是一条经过赋权连通图C的每条边至少一次的回路，则C是G的最优回路，当且仅当C对应的欧拉图G满足：

(1)G的每条边至多重复出现一次；

(2)G的每个圈上重复出现的边的权之和不超过该圈总权的一半。基于以上定义和定理，应用图论描述中国邮递员问题如下：

在一个连通图G=(V，E)中，E中的每一条边对应一条街道，每条边的权重l(e)=街道的长度。v中某一个顶点为邮局，其余为街道的交叉点。在连通图c=(V，E)上找一个圈，该圈过每边至少一次，且圈上所有边的权和最小。

此问题分为两种情况：

（1）若G中的顶点均为偶点，即G中存在欧拉回路，则该回路过每条边一次且仅一次，此回路即为所求的投递路线；

（2）若G中有奇点，不存在欧拉回路，所投递的路线至少有一街道要重复走一次或多次。

在G中有奇点的情况中，选择的最佳投递路线就等同于选择重复边的权和最小的路线。下面我们来介绍初始邮递路线的确定、改进，以及一个邮递路线是否是最优路线的判定标准的方法图上作业法。

（1）初始邮递路线的确定方法。

任何一个图中，若奇点的个数为偶数，就可以把它们两两配成对，而每对奇点之间必有一条链（图是连通的），我们把这条链的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点，这就给出了初始投递路线。

如在下图中，v1是邮局所在地，并有四个奇点v2,v4,v6,v8,将它们两两配对，比如v2和v4为一对，v6和v8为一对。

v7

v8

v1

v7

v8

v1

2

4

（2）改进邮递路线，使重复边的总长不断减少。

一般地，在邮递路线上，如果在边[vi,vj]旁边有两条以上的重复边，从中去掉偶数条，那么可以得到一个总长度较少的邮递路线。根据定理3的满足条件，在最优邮递路线上，图中每一个圈的重复边的总权

小于或者等于该圈总权的一半，得出下列欧拉圈就是最优邮递路线。

3.网络最小树法求解中国邮递员问题

中国邮递员问题简单图上作业法虽然最后找出了最优路线，但寻找奇点的配对关系，难免带有一定的盲目性，不如针对这一症结所在，尽可能地将初始方案做得好一些，以减少后期调整所出现的麻烦，这就需要考虑和利用网络最小树的理念。

v6v3v4

v5

v22

5594

4

34

6

44

3v9v6v3

v4

v5

v25594

436

44

3v9

v6

v4

v5

v22

5

594434

6443v9

v7v6

v3

v4

v5

v8

v1v22

559

4

4

34

6

44

3

V9v3

v1

v8

v7

管谷梅先生在1960的时候给出过求最优集的相关判定定理，然而实际操作中我们却有更贴近实际的解决方法，这即是判优准则。以上面提到的线路为例，

演示此方法，具体的步骤如下：(1)奇点出作出标记。

(2)求该网络最小树(使用避圈法或是破圈法，在操作中尽可能多保留与奇点相连的边)。

(3)在最小树的奇点处添加添加重复边，以消灭奇点。(4)同到原来的问题，且按判优准则。

(5)检验和调整，直至最优。经过判优法检验，可知已经为最优解，该题圆满解决!

v7v6v3v4v5

v8v1v22559443464

43v9v7v6v3

v4

v5

v8v1v22

55

9443

4

644

3v9v7

v6

v3v4v5v8

v1

v2

2

5

5

944

3

4

6

4

4

3v9

v7v6

v3v4v5v8v1v2255944

3

464

43V9

在此寻找最优解的过程中，始终遵循的两个准则为：准则1：最优解中重边的重数不多于2；

准则2：最优解中每个初等圈中，重边总权数不大于该圈总权数的一半。通过实际解决最优路径问题发现，借助最小树的理念处理中国邮路问题时，能够充分的考虑原有网络的信息，这样在添加重边，消失奇点的过程中可以做到有的放矢。而避免了之前使用方法局部求解导致的局限性。

当然这种方法是一种初级方案，还有待于进一步的验证。因为在实际计算中，逐一验证全部有效圈的工作量实在太大，作为一种很接近于求解最优解的初始解的办法，这不失为一种不错的方法，值得我们去使用。

4.中国邮递员问题规划模型的建立

在用图上作业法求解中国邮递员问题时，需检查图中的每一条回路。当图中回路较多时，检查不便且容易出错。对此，受求解最短路问题的EXCEL解法的启发，本文建立基于EXCEL的“中国邮递员问题”的整数规划模型。

1

,01

,01

1

.min''''''''1

.1

,==+=+<=+=++=∑∑∑∑∑∑∈∈∈∈==x

xxxxxxxxxx

cxcpq

ijn

NqpqnMjijnNqpqnMjijqppqji

ij

pq

n

qppq

ij

njiij

t

sz}{}{n

qpnjipNiMn

pnin

qpnji?=?=???

?

???==?=?=?=?=2,1,2,1,2,12,12,1,2,1,点直接相连的与直接相连的点与

式中：

的距离

到顶点的距离到顶点图中顶点数量

型决策变量

型决策变量配送总路程

qpjinzc

cxxpq

ij

pq

ij

1010

在此模型中，将线路分为实际弧cij和虚拟弧cpq是无向的，设定0-1型决策变量xij和xpq，目标函数∑∑==+

=n

jin

qppq

pq

ijijx

cxcz1,1

.min表示为所走的实际弧和虚

拟弧的最小路程。将线路分别设为实际边和虚拟边，边是有向的。约束条件

1=+x

xji

ij

表示每一条实际边走且只能走一次。而虚拟边的约束条件是xxqp

pq+≤1，即每条虚拟边最多走一次。设定流入某一顶点的线路为正，而流出此顶点的线路为负，则约束条件

∑∑∑∑∈∈∈∈+=+M

jN

qpqijM

jN

qpqijxxx

x'''''''

'

是用来保证每一个顶点

流人流出的线路总和为零，即保证每一个节点为偶点。

4、应用推广

本文研究了物流配送路径优化问题。基于EXCEL通过构建图书配送的中国邮递员问题优化模型，实现了物流配送路径的遍历性和路程的最小化。通过本文的研究，可以在物流配送过程中节省物流配送时间，降低配送成本，也可为其它遍历路程最小化问题路径优化提供借鉴。。

利用中国邮递员问题的图上作业法或最小树法来分析得出投递的最优路线。在时间、路