中国邮递员模型研究.doc

中国邮递员模型研究一、 中国邮递员问题概述 著名图论问题之一。邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线?关于邮递员最优投递路线问题最早是由管梅谷首先提出并进行研究的, 国际上现在统称之为中国邮递员问题。管梅谷给出了这一问题的奇偶点图上作业法。Edmonds 等给出了中国邮递员问题的改进算法, 较前者的计算更为有效。管梅谷对有关中国邮递员问题的研究情况进行了综述。早期关于中国邮递员问题的讨论总是基于无向图展开的,事实上,由于单行线或上下行路线的坡度等原因, 这一问题有时必须借助于有向图来进行研究和解决。到目前为止,对中国邮递员问题的研究主要是从图论角度展开的, 给出的多数都是各种启发式算法或递推算法。本文从数学规划的角度进行研究。数学规划建模具有借助软件包求解方便、 易于修改和推广等多方面的优点,即使对于大型问题也易于建模分析和解决的优点。1、 传统中国邮递员问题的建模一些基本概念:定义 经过的每条边的迹叫做的Euler迹；闭的Euler迹叫做Euler回路或回路；含Euler回路的图叫做Euler图。直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。定理（i）是Euler图的充分必要条件是连通且每顶点皆偶次。（ii）是Euler图的充分必要条件是连通且，是圈，。（iii）中有Euler迹的充要条件是连通且至多有两个奇次点。问题（管梅谷，1960） ：一位邮递员从邮局出发投递邮件，经过他所管辖的每条街道至少一次，然后回到邮局。请为他选择一条路线，使其所行路程尽可能短。 图论模型：求赋权连通图中含有所有边的权最小的闭途径。这样的闭途径称为最优回路。思想：（1）若 G是 Euler图，则 G的 Euler环游便是最优回路，可用 Fleury 算法求得； （2）若 G 不是 Euler 图，则含有所有边的闭途径必须重复经过一些边，最优回路要求重复经过的边的权之和达到最小。闭途径重复经过一些边，实质上可看成给图 G 添加了一些重复边（其权与原边的权相等） ，最终消除了奇度顶点形成一个 Euler 图。因此，在这种情况下求最优回路可分为两步进行：首先给图 G 添加一些重复边得到 Euler 图 ，使得添加边的权之和最小， （其中 ） ；然后用 Fleury 算法求 的一条 Euler环游。这样便得到 G的最优回路。 问题是：如何给图 G添加重复边得到 Euler图 ，使得添加边的权之和 最小？方法一（图上作业法） 定理1设 C 是一条经过赋权连通图 G 的每条边至少一次的回路，则 C 是 G 的最优回路当且仅当 C 对应的Euler图满足： （1）G的每条边在中至多重复出现一次； （2）G的每个圈上在 中重复出现的边的权之和不超过该圈总权的一半。奇偶点图上作业法： 先分奇偶点，奇点对对联；联线不重迭，重迭要改变；圈上联线长，不得过半圈。 基本步骤：1、确定第一个可行方案。找到图中所有奇顶点（必有偶数点）将它们两两配对。新图中无奇顶点，得到第一个可行方案。2、调整可行方案，使重复边总长度下降。3 检查图中的每个圈，如果每个圈重复边总长度不超过该圈总长度的一半，则已求得最优解。否则进行调整：将这个圈的重复边去了，而将原来没有重复边的各边加上重复边，其他各圈的边不变，根据 2 再一次调整。奇偶点图上作业法虽然通俗易懂，但使用时需要检查图的每个圈，对于有很多圈的图，计算量很大，实际当中用得较少。 方法二（Edmonds-Johnson 方法）定理2设 G是赋权连通图，G中有个奇度顶点。设 则是以G的奇度顶点为起点和终点的条无公共边的最短路。基于此定理，Edmonds 和 Johnson 于 1973 年给出了求解邮递员问题的有效算法。Edmonds-Johnson算法：对于非Euler图，1973年，Edmonds和Johnson给出下面的解法：设是连通赋权图。（i）求。（ii）对每对顶点，求（是与的距离，可用Floyd算法求得）。（iii）构造完全赋权图，以为顶点集，以为边的权。（iv）求中权之和最小的完美对集。（v）求中边的端点之间的在中的最短轨。（vi）在（v）中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端点共权的边）。（vii）在（vi）中得的图上求Euler回路即为中国邮递员问题的解。若此连通赋权图是Euler图，则可用Fleury算法求Euler回路，此回路即为所求。Fleury算法：（1）任取，令.（2）设已经行遍，按下面方法来从中选取：（a）与相关联；（b）除非无别的边可供行遍，否则不应该为中的桥。（3）当（2）不能再进行时，算法停止。 判断是否为欧拉图（连通性和奇度点）图 YesNo输出无欧拉回路与相关联i=i+1, 非桥Yes、输出欧拉回路 Fleury算法流程图2、 利用LINGO中国邮递员0-1规划求解在中国邮递员问题中，不算出地点，n个邮局有(n-1)!种排列方法，每一种投递路线是排列中的一种，当n变大时，计算量呈指数增长，穷举法所费时间是难以承受的。我们把中国邮递员问题转化为0-1规划，然后用LINGO来求解。(1). 判断各边包含在投递路线中引入0-1整数变量 (且ij):=1表示路线从i到j，即边i-j在旅行路线中，而0则表示不走i-j路线。目标函数：首先必须满足约束条件：对每个投递点访问一次且仅一次。从投递点i出发一次(到其它投递点去),表示为从某个投递点到达j一次且仅一次，表示为以上建立的模型类似于指派问题的模型，对中国邮递员问题只是必要条件，并不充分。例如，用图示路线连接六个点，满足以上两个约束条件，但这样的路线出现了两个子回路，两者之间不通，不构成整体巡回路线。312654为此需要考虑增加充分的约束条件以避免产生子巡回增加变量,i=2,3,n，（它的大小可以取整数：例如从起点出发所达到的投递点u=2,依此类推）。证明：(1)任何含子巡回的路线都必然不满足该约束条件（不管如何取值）；(2)全部不含子巡回的整体巡回路线都可以满足该约束条件（只要取适当值）。用反证法证明(1),假设存在子巡回，则至少有两个子巡回。那么（必然）至少有一个子巡回中不含起点1，如上图中的4564，则必有把这三个不等式加起来得到，不可能，故假设不能成立。而对整体巡回，因为附加约束中j2,不包含起点投递点1，故不会发生矛盾。对于整体巡回路线，只要ui取适当值，都可以满足该约束条件：()对于总巡回上的边，, 可取访问投递点i的顺序数，则必有，约束条件变成：-1+n n-1，必然成立。()对于非总巡回上的边，因为 ，约束条件变成-1n-1，肯定成立。综上所述，该约束条件只限止子巡回，不影响其它，于是中国邮递员问题转化成了一个混合整数线性规划问题。中国邮递员问题可以表示为规划：例1 有一个县城，有五个乡邮局，现在又一个邮车从县邮局出发派送物品，如何为这个邮车设计一条最短的派送路线（从驻地出发，经过每个投递点恰好一次，最后返回驻地）？（数据在下表中） 乡一乡二邮局乡三乡四乡五乡一034795乡二306111622邮局460332155乡三7113301710乡四9162117013乡五5225510130（单位：千米）Lingo代码：model:sets: country/1,2,3,4,5,6/:u;！定义6个点 link(country,country): dist, ！距离矩阵 x; ！决策变量 endsets n= size( country); data: ！距离矩阵 dist=0 3 4 7 9 5 3 0 6 22 11 16 4 6 0 33 21 55 7 11 33 0 17 10 9 16 21 17 0 13 5 22 55 10 13 0;enddata ！目标函数 min=sum(link:dist*x); FOR( country(K): ！进入邮局 sum( country( I)| I #ne# K: x(I,K)=1; ！离开邮局 sum( country( j)| J #ne# K: x(K,J)=1; ); ！保证不出现子圈 FOR( country(I) | I #gt# 1: FOR( country( J)| j #gt# 1: u(I)-u(J)+n*x(I,J)=n-1); ); FOR( country(I) : u(I)=n-1); FOR( link:bin(x); ！定义0-1变量END运算结果：Objective value: 53.00000X( 1, 3) 1.000000 4.000000X( 2, 4) 1.000000 11.00000X( 3, 2) 1.000000 6.000000X( 4, 6) 1.000000 10.00000X( 5, 1) 1.000000 9.000000X( 6, 5) 1.000000 13.00000由此可以看出最优解为 53千米路线为：1-3-2-4-6-5-12.对投递点进行排序，找出最优排序在现实中的交通图中，有些投递点之间有直接道路，有些则没有，如果两点之间没有直接的通路，则两点之间的距离取最短路（经过其它点），即用任意两点之间的最短路作为图的距离矩阵，于是该图可以看成是一个完全图（即任意一对顶点都有一条边相连的图），此时形式上的环形巡回路线实际上个别点有可能不止经过一次。设从某个邮局为投递的出发地和终点（相当于总部所在地），邮递员从该点出发到其它n个各一次且仅一次，最后回到出发地。我们把行进路线分成n步，每一步到一个投递点（第n+1步返回出发地），于是一条旅行路线就相当于n个投递点的一种排列，n个投递点共有n!种排列方式。排序不同则总里程可能不同，总里程最小的排序就是要寻找的最优路。引入0-1型决策变量，下标k表示旅行的步数，下标j表示到达哪一个投递点，表示旅行者第k个目的地（到达点）是投递点j，则表示否。用表示总部到各投递点的距离，用表示投递点i与投递点j之间的最短路。从出发地到第1个点的路程为：从最后一个点返回出发地的里程为 ：假设在第k步邮车达到投递点i，在第k+1步达到支局j，即，则走过的里程为：从第1点到第n点走过的总里程为：目标函数为：约束条件：(1) 每一步到达一个投递点，即(2) 每一个投递点必须到一次且只需一次可以把邮递员问题转化成如下非线性0-1 规划例2 某县邮局和四个乡镇支局组成该县的邮政运输网络，已知县局到各支局的距离和支局之间的距离矩阵。用一辆邮车完成邮件运输任务，邮车从县局出发到各支局去一次且只需一次，最后回到县局，求总路程最短的行驶路线。（数据在下表中）乡一乡二乡三乡四县邮局71562730乡一0154447乡二1502932乡三4429020乡四4732200（单位：千米）程序：MODEL:SETS: COUNTRY /1,2,3,4/:JL; STEP/1,2,3,4/; LINE(STEP, COUNTRY):X; LINKS(COUNTRY, COUNTRY):C;ENDSETSDATA: JL=71 56 27 30; C=0 15 44 47 15 0 29 32 44 29 0 20 47 32 20 0 ;ENDDATAFOR(LINE : BIN(X);M1=SIZE(STEP);FOR(COUNTRY (I):SUM(STEP(N):X(N,I)=1);FOR(STEP(N):SUM(COUNTRY (I):X(N,I)=1);L1=SUM(COUNTRY (I):(X(1,I)+X(M1,I)*JL(I);LX=SUM(STEP(N)|N#LT#M1:SUM(LINKS(I,J):C(I,J)*X(N,I)*X(N+1,j);MIN=L1+LX;END运算结果：Objective value: 148.0000X( 1, 4) 1.000000 0.000000X( 2, 1) 1.000000 35.99985X( 3, 2) 1.000000 0.4100000E-04X( 4, 3) 1.000000 0.000000由此可以看出最优解： 148最优解路线为：1-4-3-2-1。3. 多邮递员问题在现实中问题中，有时候不是由一人走遍所有点，而是由几个人分工合作，每个人只到其中部分投递点，每个点都有人来过一次且只需一次，事先不指定谁到哪些点，求出使总路程最小的投递规划（每个人的行走路线）。为了在允许的时间内完成邮件运输任务，县局的邮车往往不止1辆，而是用若干辆邮车分工运输，只要保证每个支局有邮车来过即可，为了节省行驶费用，需要规划几辆邮车的最佳路线。问题：有n+1个投递点，相互间的路程为已知，有k个邮递员都从总部所在邮局出发，赴其它投递点投递，分工遍历其余n个投递点，即每个投递点各有任意一名邮递员来过一次且仅一次，最后都回到出发地，目标是总路程最短。多邮递员问题在物流配送、邮路优化等方面具有较高的实用价值，而在现实问题中，研究对象往往不是单纯的邮递员问题，而要考虑各种约束条件，例如时间约束、载重量约束等等。研究这一类带约束条件的多邮递员问题具有很强的现实意义。 例3 某县邮政局管辖16个支局，已知县局到各支局的距离以及16个支局之间的距离矩阵。寄达各支局和各支局收寄的邮件如下表所示：支1支2支3支4支5支6支7支8支9支10寄达1015691361141317收寄914510910139159支11支12支13支14支15支16寄达11211211314收寄6713151016（单位：袋）每一辆邮车最多装载65袋邮件，邮车的运行成本为3元/公里。试用最少邮车，并规划邮车的行驶路线使总费用最省。（距离数据在下表）支1支2支3支4支5支6支7支8支9支10县局27361711243144403020支11支12支13支14支15支16县局252121182736支1 支2 支3 支4 支5 支6 支7 支8 支9 支10 支11 支12 支13 支14 支15 支16支1 0 31 27 38 51 58 71 67 57 47 52 48 21 41 52 61 支2 31 0 19 33 27 32 45 64 53 47 61 57 52 48 56 63支3 27 19 0 14 27 34 47 49 39 29 42 38 38 29 38 44支4 38 33 14 0 13 20 33 35 25 15 33 32 32 15 24 30支5 51 27 27 13 0 9 21 37 26 26 43 45 45 28 29 38支6 58 32 34 20 9 0 13 32 32 35 47 52 52 35 33 42支7 71 45 47 33 21 13 0 19 30 39 50 65 65 48 44 40支8 67 64 49 35 37 32 19 0 11 20 31 54 61 34 25 21支9 57 53 39 25 26 32 30 11 0 10 20 43 51 24 14 13支10 47 47 29 15 26 35 39 20 10 0 18 36 41 14 9 18支11 52 61 42 33 43 47 50 31 20 18 0 23 46 25 14 23支12 48 57 38 32 45 52 65 54 43 36 23 0 27 22 33 42支13 21 52 38 32 45 52 65 61 51 41 46 27 0 39 48 57支14 41 48 29 15 28 35 48 34 24 14 25 22 39 0 11 20支15 52 56 38 24 29 33 44 25 14 9 14 33 48 11 0 9支16 61 63 44 30 38 42 40 21 13 18 23 42 57 20 9 0(单位：千米)考虑最少邮车数量，由题目所给表中数据，寄达16个支局的邮件总数为176袋，从各支局收寄的邮件总数170为袋，每一辆邮车最多容纳65袋邮件，至少需要，由于邮车的数量是整数所以需要3辆邮车。运输费用与行驶里程成正比，总里程最短对应总费用最省。把16个支局放在一起作为一个整体考虑，找出3条邮路，每条邮路都从县局出发，到若干支局进行卸装，最后回到县局。各邮车路过的支局数量未知，合理安排各邮车的行驶路线，由3辆邮车分别承包运输，在满足运载量约束前提下，把3条巡回路线的总里程最小作为优化的目标。该问题相当于附带约束条件的多邮递员模型。引入0-1型决策变量，分别表示3辆邮车第k步到达支局j，下标k表示邮车行走的步数，下标j表示到达哪一个支局，当决策变量等于1时分别表示某邮车第k个装卸点是支局j，等于0时表示否。设各邮车管辖的支局数量分别为，则。约束条件：(1) 任何一辆车在任何一步到达一个支局 ：(2) 任何一个支局必须有一辆邮车到达一次且只需要一次：(3) 在邮车行进的任何路段上，装载的邮件不超过47袋：设寄达各支局的邮件量为，各支局收寄的邮件量为。 装载量是动态变化的，以第1辆邮车为例，出发时的装载量为： 到第1个支局卸装以后，装载量变为：在行驶过程中，装载量的递推公式为： 数量的约束条件建立多邮递员问题的0-1规划模型如下： 程序如下：MODEL:SETS: STATION/1.16/: JL,P,Q; STEPX/1.6/:WX; STEPY/1.5/:WY; STEPZ/1.5/:WZ; LINEX( STEPX, STATION): X; LINEY( STEPY, STATION): Y; LINEZ( STEPZ, STATION): Z; LINKS(STATION,STATION):C;ENDSETSDATA: JL=27 36 17 11 24 31 44 40 30 20 25 21 21 18 27 36; P=10 15 6 9 13 6 11 4 13 17 11 2 11 21 13 14; Q=9 14 5 10 9 10 13 9 15 9 6 7 13 15 10 16; C= 0 31 27 38 51 58 71 67 57 47 52 48 21 41 52 61 31 0 19 33 27 32 45 64 53 47 61 57 52 48 56 63 27 19 0 14 27 34 47 49 39 29 42 38 38 29 38 44 38 33 14 0 13 20 33 35 25 15 33 32 32 15 24 30 51 27 27 13 0 9 21 37 26 26 43 45 45 28 29 38 58 32 34 20 9 0 13 32 32 35 47 52 52 35 33 42 71 45 47 33 21 13 0 19 30 39 50 65 65 48 44 40 67 64 49 35 37 32 19 0 11 20 31 54 61 34 25 21 57 53 39 25 26 32 30 11 0 10 20 43 51 24 14 13 47 47 29 15 26 35 39 20 10 0 18 36 41 14 9 18 52 61 42 33 43 47 50 31 20 18 0 23 46 25 14 23 48 57 38 32 45 52 65 54 43 36 23 0 27 22 33 42 21 52 38 32 45 52 65 61 51 41 46 27 0 39 48 57 41 48 29 15 28 35 48 34 24 14 25 22 39 0 11 20 52 56 38 24 29 33 44 25 14 9 14 33 48 11 0 9 61 63 44 30 38 42 40 21 13 18 23 42 57 20 9 0;ENDDATAFOR( LINEX : BIN( X); FOR( LINEY : BIN( Y); FOR( LINEZ : BIN( Z);M1=SIZE(STEPX); M2=SIZE(STEPY);M3=SIZE(STEPZ); FOR(STATION(I):SUM(STEPX(N):X(N,I)+SUM(STEPY(N):Y(N,I)+SUM(STEPZ(N): Z(N,I) = 1);FOR(STEPX(N):SUM(STATION(I):X(N,I)=1);FOR(STEPY(N):SUM(STATION(I):Y(N,I)=1);FOR(STEPZ(N):SUM(STATION(I):Z(N,I)=1);WX0=SUM(STATION(I):P*SUM(STEPX(N):X(N,I); WY0=SUM(STATION(I):P*SUM(STEPY(N):Y(N,I); WZ0=SUM(STATION(I):P*SUM(STEPZ(N):Z(N,I);WX(1)=WX0-SUM(STATION(J):(P(J)-Q(J)*X(1,J);WY(1)=WY0-SUM(STATION(J):(P(J)-Q(J)*Y(1,J);WZ(1)=WZ0-SUM(STATION(J):(P(J)-Q(J)*Z(1,J);FOR(STEPX(N)|N#GE#2:WX(N)=WX(N-1)-SUM(STATION(J):(P(J)-Q(J)*X(N,J);FOR(STEPY(N)|N#GE#2:WY(N)=WY(N-1)-SUM(STATION(J):(P(J)-Q(J)*Y(N,J);FOR(STEPZ(N)|N#GE#2:WZ(N)=WZ(N-1)-SUM(STATION(J):(P(J)-Q(J)*Z(N,J);WX0=65; WY0=65; WZ0=65;FOR(STEPX(N):WX(N)=65); FOR(STEPY(N):WY(N)=65); FOR(STEPZ(N):WZ(N)=65);L1=SUM(STATION(I):(X(1,I)+X(M1,I)*JL(I);L2=SUM(STATION(I):(Y(1,I)+Y(M2,I)*JL(I);L3=SUM(STATION(I):(Z(1,I)+Z(M3,I)*JL(I);LX=SUM(STEPX(N)|N#LT#M