使用AMPL实现中国邮递员问题，你get到了吗

Love The Way You Lie 2022-10-17 13:56 175阅读 0赞

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

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

## 1、哥尼斯堡七桥问题 ##

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

![BFDE921726CF0ED45A2A6FF6BCD0A6CA.jpg][]

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

![894F5C0CA7932DFD823DB28B4668A8F4.jpg][]

在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题)

![34E12C9A-54A9-46D2-A28D-F9B89A9C7A7A.png][]

### （5）数学模型 ###

m i n ∑ ( i , j ) ∈ E D i , j X i , j min\\sum\_\{(i,j)\\in E\}D\_\{i,j\}X\_\{i,j\} min(i,j)∈E∑Di,jXi,j

s.t.  
 ∑ j X j , i − ∑ i X i , j = 0 , ( i = 1 , 2 , . . . , n ) \\sum\_jX\_\{j,i\}-\\sum\_i X\_\{i,j\}=0 ,(i=1,2,...,n) j∑Xj,i−i∑Xi,j=0,(i=1,2,...,n)

X i , j + X j , i ≥ 1 , ∀ ( i , j ) ∈ E X\_\{i,j\}+X\_\{j,i\}\\geq1,∀(i,j)\\in E Xi,j\+Xj,i≥1,∀(i,j)∈E

X i , j = 0 或 1 , ∀ ( i , j ) ∈ E X\_\{i,j\}=0或1,∀(i,j)\\in E Xi,j=0或1,∀(i,j)∈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];

*  **数据模型**

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;

*  **运行结果**

reset;
    model cpp1.mod;
    data cpp1.dat;
    option solver cplex;
    solve;
    display X;

详细如下图所示：

![1FD1EF842A71892EE1758A9D67F34AE7.jpg][]

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

**如有问题可以去WX问**

![F28378BFA71CADA0A0E56AA0A8F0249C.jpg][]

[BFDE921726CF0ED45A2A6FF6BCD0A6CA.jpg]: /images/20221014/56a701058a534bfaa34be5e59f801d3e.png
[894F5C0CA7932DFD823DB28B4668A8F4.jpg]: /images/20221014/1e146bcfceb14c4d979eebc5ead61d18.png
[34E12C9A-54A9-46D2-A28D-F9B89A9C7A7A.png]: /images/20221014/7074854647d3427ebd19e2242e376be0.png
[1FD1EF842A71892EE1758A9D67F34AE7.jpg]: /images/20221014/3cac777aa9fb426a9b76b35ac7fae61b.png
[F28378BFA71CADA0A0E56AA0A8F0249C.jpg]: /images/20221014/0ddcc734d77c4390949af1a125259672.png