AMPL实现中国邮递员问题，你get到了吗_中国邮局问题运筹学

本文所有代码全部使用AMPL语言实现

中国邮递员问题和旅行商问题不太相同，旅行商问题是不能回头的，而邮递员问题要求是访问所有街道，也就是说每个街道必须访问到。

1、哥尼斯堡七桥问题

要解出中国邮递员问题，首先我们一起来了解哥尼斯堡七桥问题，这样助于后面的学习。这个故事是发生在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？

将将哥尼斯堡七桥问题中的每一块地看作一个点，而每一座桥看作一条线，则可得到下图，不难看出，下面图的每一点所连接的线数目皆为奇数，则引入欧拉概念。

在1736年29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文，在解答问题的同时，开创了数学的一个新的分支——图论与几何拓扑，也由此展开了数学史上的新历程。
由于欧拉对于哥尼斯堡的七桥问题的解决，图论中把可完成“一笔画”的图称作欧拉图(Euler Graph)，由此又有了欧拉回路(Euler Circuit)与欧拉路径(Euler Path)的概念。
概念：欧拉路径是指通过图中所有边的简单路，而欧拉回路指闭合的欧拉路径。拥有欧拉回路的图即可称为欧拉图。

2、中国邮递员问题

（1）介绍

邮递员问题，若把它抽象为图的语言，就给定一个连通图，在每边ei上赋予一个非负的权W(ei)，要求一个圈，每边至少一次，并使圈的总权最小。该问题是中国数学家管梅谷在1962年首先提出了这个问题，在国际上通称为中国邮递员问题。广泛比如：扫雪车、处理垃圾车、散水车、送信员等。

（2）欧拉回路

• 给定一个连通多重图G，若存在一条链，过每边一次，且仅一次，则称为这条链为欧拉链。
• 若存在一个简单图，过每边一次，且仅一次，称为这个圈为欧拉圈。
• 一个图若有欧拉圈，则称为欧拉图。

（3）邮递员案例

通过上面，我们知道图若能一笔画出，这个必是欧拉图，它是没有奇点的。现在我们讨论中国邮递员对于有奇数又如何求解。

在任何一个图中，奇点个数必为偶数，才能构成欧拉回路。如果图中有奇点，我们将它们变为偶数点，所有将它们配成对，也就是给奇点添加一条重复边，这样就无奇点了，也就构成欧拉图一个可行方案。

（4）中国邮递员问题例子

现在一个邮递员从邮局出发，要走完他所管辖范围内的每一条街道至少一次再返回邮局，如何选择一条尽可能短的路线，现假设该城市的区域，道路网络如下图所示，线代表道路，点代表十字路口。各条路的成本为（i, j, d)，距离在图中已经标出（单位KM），现在请问：送货员从“1”点出发,如何选择最短路线，每条街道至少经过一次，送完邮件后返回“1” 点。(本例题来自运筹学第4版课后习题，328页11.16题)

（5）数学模型

$$min\sum _{(i,j)\in E}{D}_{i,j}{X}_{i,j}$$

​ s.t.
$$\sum _j{X}_{j,i}-\sum _i{X}_{i,j}=0,(i=1,2,...,n)$$

$$X_{i,j}+X_{j,i}\ge 1,\forall (i,j)\in E$$

$$X_{i,j}=0或1,\forall (i,j)\in E$$

解释上述数学公式：

• i,j = (1,2,…,n)代表顶点集合，也就是所有相邻街道交叉的点
• d代表i，j两点之间的距离或单位行驶成本
• Min代表单位时间内产生成本或距离的最小值
• Xi,j代表连接i，j两点组成的线段（即街道）送信员是否行驶通过(0是代表不通过道路，1 是代表通过道路)

（6）代码实现

• 模型文件

#1 集合
set node;#定义node集合，表示存放每个结点的意思
set road within node cross node;#代表所有线的一个子集
#2 参数
param d{road};##每一条道路的距离
#3 变量（注意这个是未知的所以正好设置为变量）
var X{(i,j)in road}binary;#0,1变量(0是代表不通过道路，1是代表通过道路)
#4 目标函数
#d[i,j]*X[i,j];【表示i与j间距离】乘【i与j间是否可行1表示可行0表示不可行】还不懂意思就慢慢想
minimize CPP:sum{(i,j)in road}d[i,j]*X[i,j];
#5 约束条件(根据上述数学模型，很简单这里就不解释了)
subject to limit1{(i,j) in road}:
X[i,j]+X[j,i]>=1;
subject to limit2{k in node}:
sum{(i,k) in road}X[i,k] = sum{(k,j)in road}X[k,j];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 数据模型

set node:=1 2 3 4 5 6 7 8 9 10 11 12;#根据上图有12个点
set road:=
(1,3)  (3,1)  (1,2)  (2,1)  (2,5)   (5,2)  (2,6)   (6,2)
(3,6)  (6,3)  (3,7)  (7,3)  (4,6)   (6,4)  (4,5)   (5,4)
(4,11) (11,4) (7,10) (10,7) (7,9)   (9,7)  (8,12)  (12,8)
(8,11) (11,8) (9,12) (12,9) (10,12) (12,10) (9,11) (11,9);
#表示区域内各街道构成的行驶距离
param:d:=
1 3 5
3 1 5
1 2 6
2 1 6
2 5 1
5 2 1
2 6 4
6 2 4
3 7 2
7 3 2
3 6 1
6 3 1
4 6 1
6 4 1
4 5 3
5 4 3
4 11 2
11 4 2
7 10 3
10 7 3
7 9 2
9 7 2
8 11 3
11 8 3
8 12 7
12 8 7
9 12 4
12 9 4
9 11 6
11 9 6
10 12 2
12 10 2;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

• 运行结果

reset;
model cpp1.mod;
data cpp1.dat;
option solver cplex;
solve;
display X;
1
2
3
4
5
6

详细如下图所示：

创作不易，熬夜不易，你的【一键三连】是我最大鼓励与支持。

如有问题可以去WX问