?----------------------- Page 1-----------------------
魅力数模 美丽师大
魅力数模 美丽师大
魅力数模 美丽师大
浙江师范大学“同梦杯”第八届数学建模
竞赛
自信 创新 合作 快乐
A B √
论文题目 城市垃圾运输问题
编 号
评 分
监 制：浙江师范大学数学建模研究会（2009 年 5月 7 日）
（说明：评分一栏为评阅人填写，请参赛者不要填写）
----------------------- Page 2-----------------------
城市垃圾运输问题
一、摘要
通过对垃圾运输问题的具体分析，得出运输车问题应先于铲车问题。运输车
利用目标规划模型，运用计算机随机搜索方法得出了 12 条分路径，考虑实际情
况优化成 11 条分路径 。在铲车问题中将 11 条线路用数学方法模拟成 11 个加权
点，构造恰当的有向或无向赋权图，把问题转化成图论中的 TSP 问题，并利用
蚁群算法解决 TSP 问题,.从而使原问题获得满意的解答。
关键词
垃圾运输问题，目标规划模型，计算机随机搜索算法，蚁群算法，哈密顿圈，图
论中的 TSP 问题（旅行商问题）
城市垃圾运输问题 2
----------------------- Page 3-----------------------
二、问题重述
某城区有37个垃圾集中点，每天都要从垃圾处理厂（第38号节点）出发将
垃圾运回。现有一种载重6吨的运输车。每个垃圾点需要用10分钟的时间装车，
运输车平均速度为40公里／小时（夜里运输，不考虑塞车现象）；每台车每日平
均工作 4 小时。运输车重载运费 2 元/吨公里；运输车和装垃圾用的铲车空载费
用 0.5 元/公里；并且假定街道方向均平行于坐标轴。请你给出满意的运输调度
方案以及计算程序。
问题： 1. 运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运
营费用）
2. 铲车应如何调度（需要多少台铲车，每
台铲车的行走路线，运营费用）
3. 如果有载重量为4吨、6吨、8吨三种运输车，又如何调度？
垃圾点地理坐标数据表
序号 站点 垃 圾 坐标(km) 序号 站点 垃 圾 坐标(km)
编号 量T x y 编号 量T x y
1 1 1.50 3 2 20 15 1.40 19 9
2 2 1.50 1 5 21 32 1.20 22 5
3 3 0.75 5 4 22 22 1.80 21 0
4 4 1.20 4 7 23 23 1.40 27 9
5 6 0.85 0 8 24 24 1.60 15 19
6 5 1.30 3 11 25 25 1.90 15 14
7 7 1.20 7 9 26 26 1.00 20 17
8 8 2.30 9 6 27 27 2.00 21 13
9 9 1.40 10 2 28 28 1.00 24 20
10 10 1.80 14 0 29 29 2.10 25 16
11 11 1.10 17 3 30 30 1.20 28 18
12 12 2.70 14 6 31 31 1.90 5 12
13 13 1.80 12 9 32 21 1.30 17 16
14 14 1.80 10 12 33 33 1.60 25 7
15 20 0.60 7 14 34 34 1.20 9 20
16 16 1.50 2 16 35 35 1.50 9 15
17 17 0.80 6 18 36 36 2.30 30 12
18 18 1.50 11 17 37 37 1.70 8 10
19 19 0.90 15 12 38 38 0.00 0 0
表格 1
城市垃圾运输问题 3
----------------------- Page 4-----------------------
三、引言
对于求解 n 个城市的 TSP 问题， 存在（n-1 ）！条闭合路径的排列方案， 因
此 TSP 问题是一个典型的NP 完全问题。对于这类问题很难用全局搜索法精确地
求出其最优解，因此研究相应的有效算法寻找其最优或近似最优解具有重要的理
论意义，另外，很多实际实用的问题，如印刷电路板的钻孔路线方案、连锁店的
货物配送路线等经过简化处理后，均可建模为旅行商问题，因此对旅游商问题求
解方法的研究也具有重要的实用价值。目前求解 TSP 问题的主要方法有启发式
搜索法、模拟退火算法、遗传算法、神经网络算法、二叉树描
述算法，蚁群算法
是求解此类 NP 完全问题的一种比较有效的方法。
四、符号含义
|A | 表示A点到原点的距离，恒正
|B | 表示B点到原点的距离，恒正
|A-B | 表示A,B两点之间的距离,恒正
Ta 表示A点所在地的垃圾量
装的足够多 运输车当前的载重离限载不大于0.6吨(垃圾点的最小垃圾量)
Zcost 载物费用
Kcost 空载费用
Allcost 总费用
分路径 在车辆运输过程中，需要在一次内一起完成垃圾运输的点的连线
所构成的路径
加权点 由分路径模拟成的可以替代原分路径计算的点
五、模型分析
（一）模型的假设
1．假设运输车、铲车数量不受限制。但每个垃圾站点的垃圾只能由一辆运输车
运载。
2 ．车辆的运行状况和路线都设为理想状态，即始终保持已知条件情况。
3 ．街道设为理想状态，即行车线路无需考虑街道影响。
4 ．垃圾设为理想状态，即在运输过程中无新垃圾入站；在垃圾车到达垃圾站时，
垃圾数量已经为题目中给定数量；各垃圾站都能在十分钟内装上运输车。
（二）模型建立及算法的原则
原则 1：运输车最少原则；
原则 2 ：运费最少原则；
原则 3 ：运输车优先于铲车原则；
原则 4 ：运输车先远后进原则；
原则 5：铲车最少原则；
注：以上原则优先级依次降低。
城市垃圾运输问题 4
----------------------- Page 5-----------------------
（三）问题的分析与模型的建立
1.分路径的规划
垃圾运输问题最终可以归结为最优路径搜索问题，根据具体问题设计出计算
机随即搜索法，可以搜寻到令人满意的可行解。
得出搜索的基本原则：
（1）先后顺序并不影响所需的时间。而“先远后近”可以省出车载着
B 点的垃
圾奔到 A 点再返回 B 点即 1.8*|A-B |*2*Tb 这部分的钱，所以在其余同等的情况
下选择“先远后近”。 考虑到时间上单独运输比其余的两种运输要大的多所以一
般情况下，不采用单独运输。
（2）车在装的足够多的情况下应该直接返回原点（38点）；
（3）每一次布局和每条线路的搜索从剩下未搜点中的最大值开始。
（4）在垃圾车的剩余载物量小于垃圾点垃圾量的最小值0.5时，由于对于下一
垃圾点(假设为 A点)内的垃圾而言，无论
是一次装完还是分两次装完，将它们运
回所花费用是恒定的，等于1.8*Ta*，因此|A |车是直接返回38点更合理。
2.铲车路径的规划
先用一辆铲车求解最优路线。
铲车调配问题可以转化为图论中的 TSP 问题，
已知n 个垃圾集中点之间的相互距离，现有一辆铲车必须驶遍这 n 个垃圾集
中点，并且每个垃圾集中点只能访问一次，最后又必须返回出发垃圾集中点。如
何安排他对这些垃圾集中点的行进路线，可使其路线的总长度最短。
用图论的术语来说，假设有一个连同无向图 G=(V,E)，其中V 是顶点集，E 是边
集，设 D=(dij)是由顶点 i 和顶点j 之间的距离所组成的距离矩阵，旅行商问题就
是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路，即最佳
哈密顿圈或 H 圈。
这个问题可分为对称旅行商问题(dij=dji,,任意 i,j=1,2,3，…,n)和非对称旅行商问
题(dij≠dji,,任意 i,j=1,2,3，…,n)。
若对于城市 v={v1,v2,v3,…,vn} 的一个访问顺序为t=(t1,t2,t3,…,ti,…,tn),其中
ti ∈v(i=1,2,3,…,n) ，且记tn+1= t1 ，则旅行商问题的数学模型为：
min l=σd(t(i),t(i+1)) （i=1,…,n ）
旅行商问题是一个典型的组合优化问题，并且是一个 np 难问题，其可能的
路径数目与垃圾集中点数目 n 是成指数型增长的，所以一般很难精确地求出其最
优解，本文采用蚁群算法求其近似解。
（四）模型的求解
1.在不考虑铲车的情况下
首先根据题所给的数据画出散点图（点的坐标及编号是按照题目中所给的
坐标和序号进行标注）
城市垃圾运输问题 5
----------------------- Page 6-----------------------
图表 1
由于载物费用仅和各站点到原点的路程有关，且运输车单位路程单位质量的
运费为常数，所以载物费用恒定，zcost=2639.30。程序见代码 1 。
建立目标规划模型，运用计算机随机搜索方法得出了 12 条分路径。利用
MATLAB 画出 12 条路线图。程序见代码 2 。
图表 2
得出结果后，我们结合实际操作对结果进行分析。发现将38-1和9-12两条
分路径中 1，2两点连接，将12条线路合并成11条分路径，如下图所示
城市垃圾运输问题 6
----------------------- Page 7----------------
-------
图表 3
线路 时间1 时间2 总时间/小时
1 30 29 27 2.30 1/2 2.80
2 28 26 32 25 3 2.20 5/6 3.03
3 36 23 33 2.10 1/2 2.60
4 24 18 35 15 1.70 2/3 2.37
5 34 17 16 5 1.45 2/3 2.12
6 20 11 10 1.40 1/2 1.90
7 19 13 8 1.35 1/2 1.85
8 21 22 1.35 1/3 1.68
9 14 37 7 4 1.10 2/3 1.77
10 12 9 1 1.00 1/2 1.50
11 31 6 2 0.85 1/2 1.35
0.00
16.80 6.17 22.97
表格 2
得出运营总费用为：2639.30 其中运输费用是 2807.30 空载费用为 168。程序
见代码 3 。
2.在加入铲车后
下面用数学方法证明上一步骤中的条分路径可以模拟成加权点。
令某条分路径上有n个点，分别为（X ，Y ），（X ，Y ）……（X ，Y ）,这n个
1 1 2 2 n n
点在路径上依次排列，不妨设X >X >X > ……>X 。
1 2 3 n
起点为（X ,Y ），终点为（X ,Y ）, 起点，终点都在路径外。
0 0 n+1 n+1
设S 为点（X ，Y ）到点（X ,Y ）的距离，S 为起点（X ,Y ）到（X ，Y ）
k k k k+1 k+1 0 0 0 1 1
的距离，S 为（X ，Y ）到终点（X ,Y ）的距离。
n n n n+1 n+1
S =| X -X |+|Y -Y |;
0 0 1 0 1
S =| X -X |+|Y -Y |;
1 1 2 1 2
城市垃圾运输问题 7
----------------------- Page 8-----------------------
S =| X -X |+|Y -Y |;
2 2 3 2 3
……
S =| X -X |+|Y -Y |;
n-1 n-1 n n-1 n
S =| X -X |+|Y -Y |；
n n n+1 n n+1
总距离
S=S +S +……+S +S
0 1 n-1 n
=|X -X |+
|X -X |+| X -X |+……+|X -X |+|X -X |+|Y -Y |+|Y -Y |+|Y -Y |+……
0 1 1 2 2 3 n-1 n n n+1 0 1 1 2 2 3
+|Y -Y | +|Y -Y |
n-1 n n n+1
=|X -X |+X -X +X -X + … … +X -X +|X -X |+|Y -Y |+Y -Y +Y -Y + … …
0 1 1 2 2 3 n-1 n n n+1 0 1 1 2 2 3
+Y -Y +|Y -Y |
n-1 n n n+1
=|X -X |+X -X +|X -X |+|Y -Y |+Y -Y +|Y -Y |
0 1 1 n n n+1 0 1 1 n n n+1
=|X -X |+|Y -Y |+|X -X |+|Y -Y |+X -X +Y -Y
0 1 0 1 n n+1 n n+1 1 n 1 n
令此路径上的 n 个点的重心为（X,Y ），
X=( X +X +X + ……+X )/n ；
1 2 3 n
Y=( Y +Y +Y + ……+Y )/n ；
1 2 3 n
起点（X ,Y ）到重心（X ，Y ）的距离为：
0 0
S =| X X |+ |Y - Y |=| X -( X +X +X + ……+X )/n|+| Y -( Y +Y +Y + ……
a 0- 0 0 1 2 3 n 0 1 2 3
+Y )/n| ；
n
终点（Xn+1,Yn+1 ）到重心（X ，Y ）的距离为：
S =| X X |+ |Y - Y |=| X -( X +X +X + ……+X )/n|+| Y -( Y +Y +Y + ……
b n+1- n+1 n+1 1 2 3 n n+1 1 2 3
+Y )/n| ；
n
路径长度为：
L= |X -X |+|Y -Y |；
1 n 1 n
数学模拟总路径长度为：
·
S = S + S + L
a b
=[| X -( X +X +X + ……+X )/n|+| Y -( Y +Y +Y + ……+Y )/n|]+[| X -( X
0 1 2 3 n 0 1 2 3 n n+1 1
+X +X + ……+X )/n|+| Y -( Y +Y +Y + ……+Y )/n|]+[|X -X |+|Y -Y |]
2 3 n n+1 1 2 3 n 1 n 1 n
又经过计算机数据模拟，
|X -X |+|Y -Y |+X -X +Y -Y ≈[| X -( X +X +X + ……+X )/n|+| Y -( Y
n n+1 n n+1 1 n 1 n 0 1 2 3 n 0 1
+Y +Y + ……+Y )/n|]+[| X -( X +X +X + ……+X )/n|+| Y -( Y +Y +Y + ……
2 3 n n+1 1 2 3 n n+1 1 2 3
+Yn)/n|] ；
所以，S≈S ·。
命题得证。
此重心就称为此路径的加权点。
将11条分路径用数学方法模拟成11个加权点，如下图所示。程序见代码6。
城市垃圾运输问题 8
----------------------- Page 9----------------
-------
图表 4
根据程序求出的铲车最短路径图：程序代码见代码 7 。
图表 5
通过程序，我们找到了铲车的最短路程图（最佳哈密顿圈），见表 5，即为 8
→3→1→2→4→5→11→9→7→10→6 。根据运输车需要数是6 辆，由原则 5 及运
输车和铲车的时间安排，分析知需要 6 辆铲车。根据铲车循环工作思路，分析易
知 5 辆铲车进行循环，一辆铲车，只在一条路径上，每天进行一个来回的工作。
城市垃圾运输问题 9
----------------------- Page 10-----------------------
根据距离最短原则（此处原则是，这条路径的起点到上一条路径的终点与这条路
径的终点到下一条路径的起点的距离和最短），我们找出了路径 2 ，同时我们考
虑到路径 2 只与 1 辆运输车一一对应，分析知路径 2 即为最佳结果。让此路径上
有一辆铲车每天进行一个来回的工作。
于是，得到新的最短路程图 8→3→1→4→5→11→9→7→10→6 。我们又用
了相同程序代码见（代码7 ）进行了计算得到结果如下。
考虑实际情况，去掉点 2 后的铲车路线图
图表 6
六、结论
问题 1
线路 站点序号 时 间 时 间 总 时
1 2 间/ 小
时
1 30 29 27 2.30 1/2 2.80
2 28 26 32 25 3 2.20 5/6 3.03
3 36 23 33 2.10 1/2 2.60
4 24 18 35 15 1.70 2/3 2.37
5 34 17 16 5 1.45 2/3 2.12
6 20 11 10 1.40 1/2 1.90
7 19 13 8 1.35 1/2 1.85
8 21 22 1.35 1/3 1.68
9 14 37 7 4 1.10 2/3 1.77
10 12 9 1 1.00 1/2 1.50
11 31 6 2
0.85 1/2 1.35
16.80 6.17 22.97
表格 3
城市垃圾运输问题 10
----------------------- Page 11-----------------------
调度方案：
第 n 辆 线路
车
一 10,3
二 9,6
三 5,7
四 1,11
五 8,4
六 2
表格 4
运输车重载费用：2639.30 元，运输车空载费用：168.00 元。
运输车营运费用：2809.80 元。
总时间：22.97 小时。
问题2 ：
铲车调度方案：
第 n 辆 所 在 线 起始点：
车 路
一 10,7 12
二 9,11 14
三 5,4 34
四 1,3 30
五 8,6 21
六 2 28
表格 5
铲车营运费用：100.96 元。
问题3 ：
线 路 站点序号 时 间 时 间 总 时
2 1 2 间/ 小
时
1 30 29 27 20 11 2.3 5/6 3.13
2 28 26 32 25 14 3 2.2 1 3.20
3 36 23 33 21 9 2.1 5/6 2.93
4 24 18 35 15 31 5 1.7 1 2.70
5 34 17 16 2 1.45 2/3 2.12
6 19 13 8 1 1.35 2/3 2.02
7 22 10 1.05 1/3 1.38
8 12 1 1/6 1.17
9 37 7 4 0.9 1/2 1.40
10 6 0.7 1/6 0.87
14.75 6.17 20.92
表格 6
城市垃圾运输问题 11
----------------
------- Page 12-----------------------
调度方案：
车型 数量
4t 2
6t 1
8t 3
表格 7
运输车重载费用：2639.30 元，运输车空载费用：154.50 元。
运输车营运费用：2793.8 元。
七、模型优缺点分析
该题的难点在于站点众多，若直接采用计算机枚举运算，其运算将非常惊人，
本模型的优点在于，巧妙地采用目标规划模型，将 38 个站点规划为 11 条分路径，
并利用图论模型将 11 条径转化为 11 个加权点，转化为 TSP 问题，从而极大地
减少运算量，也减少了程序开发难度。利用较少的代价即可实现近似最优解。
第二个优点在于受站点数量影响较小，当站点数量发生变化时，程序依然成
立。
本模型的局限性在于，模型依据一辆车行驶的情况建立，因此车辆分配上需
手工完成，当然依据现实情况，车辆数一般不会太多，故影响不大。
八、模型的推广和应用
该模型可直接应用于交通运输、物资分配、工件加工等常见问题。模型稍作
修改，还可应用于人力资源管理、医疗诊断问题等领域。TSP 问题在邮路问题、
分配线上的螺帽问题、产品生产和安排问题、在电路板钻孔进度的安排、基因测
序和机器人控制等方面有着重要的应用。
九、参考文献
[1]刘育兴.垃圾运输问题的模型及其求解[J]. 江西：赣南师范学院学报,2006,(3):52-55
[2]罗小凯、周谧、马宇来.垃圾运输问题的解决[J/OL].
https://www.doczj.com/doc/2310564517.html,/xibu/sxx/sxjm/jmhd/shuxuejianmo6.doc 2009.5.10
[3]谢胜利.计算机工程与应用.[J].温州.2002.(08)
[4]Gary Chartrand. Introduction to Graph Theory[M]Beijing: posts&telecom press
2007.9:122-137
[5] Marco Dorigo 、 Thomas Stutzle. 蚁群优化.[M]. 北京.清华大学出版社. 2007.
城市垃圾运输问题 12
----------------------- Page 13-----------------------
十、附录
代码作用：
代码 1 求运输车重载费用。
代码 2 求第一问中的分路径。
代码 3 求第一问中运输车空载费用。
代码 4 求第三问中的分路径。
代码 5 求第三问中运输车的空载费用。
代码 6 画加权点的分布图。
代码 7 用蚁群算法求最佳哈密顿圈。
代码 8 求铲车营运费用。
代码 1
%求运输车重载费用。
clear all
x=[3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 17 25 9 9 30
8 0];
y=[2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 18 12 16 7 20 15 12 10
0];
t=[1.5 1.5 0.75 1.2 0.85 1.3 1.2 2.3 1.4 1.8 1.1 2.7 1.8 1.8 0.6 1.5 0.8 1.5 0.9 1.4 1.2 1.8 1.4 1.6
1.9 1 2 1 2.1 1.2 1.9 1.3 1.6 1.2 1.5 2.3 1.7 0];
sum=0;
for i=1:38
sum=sum+2.0*(x(i)+y(i))*t(i);
end
sum
运行结果：
sum =
2.6393e+003
代码 2
%求第一问中的分路径。
clear
x=[3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 17 25 9 9 30
8 0];
y=[2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 18 12 16 7 20 15 12 10
0];
t=[1.5 1.5 0.75 1.2 0.85 1.3 1.2 2.3 1.4 1.8 1.1 2.7 1.8 1.8 0.6 1.5 0.8 1.5 0.9 1.4 1.2 1.8 1.4 1.6
1.9 1 2 1 2.1 1.2 1.9 1.3 1.6 1.2 1.5 2.3 1.7 0.00];
i=1:38;
城市垃圾运输问题 13
----------------------- Page 14-----------------------
a=1:38;
plot(x,y,'*r');grid;
for ii=1:38
k=int2str(ii);
tt=num2str(t(ii));
k=strcat('P',k,'(',tt,')');
% text(x(ii),y(ii),k);
end
w=[i;x;y;t;a];
w(5,:)=0;
jg=zeros(12,12);
for i=1:20
sum=0;
j1=1;
s=0;
m=38;
i3=38;
for j=1:37
if(w(2,j)+w(3,j)>s&w(5,j)==0)
s=w(2,j)+w(3,j);
jg(i,j1)=w(1,j);
sum=w(4,j);
m=j;
else continue;
end
end
w(5,m)=1;
j1=j1+1;
while 1
js=0;
q=40;
for k=1:37
if(q>w(2,m)-w(2,k)+w(3,m)-w(3,k))&w(2,m)>w(2,k)&w(3,m)>w(3,k)&(6-sum)>w(4,k)&w(5,k)
==0
q=w(2,m)+w(3,m)-w(2,k)-w(3,k);
js=1;
jg(i,j1)=w(1,k);
i3=k;
else continue;
end
end
城市垃圾运输问题 14
----------------------- Page 15-----------------------
w(5,i3)=1;
sum=sum+w(4,i3);
j1=j1+1;
m=i3;
if(w(2,i3)==0&w(3,i3)==0|js==0)
break
end
end
end
kcost=0;
zcost=0;
allcost=0;
n=0;
for u1=1:12
for u2=1:12
if jg(u1,u2)~=0
n=jg(u1,u2);
else continue
end
zcost=zcost+w(4,n)*2.0*(w(2,n)+w(3,n));
end
n=jg(u1,1);
kcost=kcost+0.5*(w(2,n)+w(3,n));
end
allcost=zcost+kcost
zcost
kcost
i=1:12;
time=[i];
time(1,:)=0;
n1=0;
n2=0;
n3=0;
for u4=1:12
for u5=1:12
if jg(u4,u5)~=0
n1=jg(u4,u5);
n2=n2+1;
else continue
end
end
n3=jg(u4,1);
time(1,u4)=((w(2,n3)+w(3,n3))*2)/40;
城市垃圾运输问题 15
----------------------- Page 16-----------------------
end
n2
time
jg
运行结果：
time =
Columns 1 through 6
2.3000 2.2000 2.1000 1.7000 1.4500 1.4000
Columns 7 through 12
1.3500 1.3500 1.1000 1.0000 0.8500 0.2500
jg =
Columns 1 through 10
30 29 27 0 0 0 0 0 0 0
28 26 32 25 3 0 0 0 0 0
36 23 33 0 0 0 0 0 0 0
24 18 35 15 0 0 0 0 0 0
34 17 16 5 0 0 0 0 0 0
20 11 10 0 0 0 0 0 0 0
19 13 8 0 0 0 0 0 0 0
21 22 0 0 0 0 0 0 0 0
14 37 7 4 0 0 0 0 0 0
12 9 0 0 0 0 0 0 0 0
31 6 2 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
Columns 11 through 12
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
代码 3
求第一问中运输车空载费用。
clear all
x=[28 24 30 15 9 19 15 22 10 14 5;
城市垃圾运输问题 16
----------------------- Page 17-----------------------
18 20 12 19 20 9 12 5 12 6 12];
kcost=0;
for i=1:11
kcost=kcost+0.5*(x(1,i)+x(2,i));
end
kcost
运行结果：
kcost =
168
代码 4
%求第三问中的分路径。
clear
x=[3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 17 25 9 9 30
8 0];
y=[2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 18 12 16 7 20 15 12 10
0];
t=[1.5 1.5 0.75 1.2 0.85 1.3 1.2 2.3 1.4 1.8 1.1 2.7 1.8 1.8 0.6 1.5 0.8 1.5 0.9 1.4 1.2 1.8 1.4 1.6
1.9 1 2 1 2.1 1.2 1.9 1.3 1.6 1.2 1.5 2.3 1.7 0.00];
i=1:38;
a=1:38;
plot(x,y,'*r')
for ii=1:38
k=int2str(ii);
tt=num2str(t(ii));
k=strcat('P',k,'(',tt,')');
text(x(ii),y(ii),k);
end
w=[i;x;y;t;a];
w(5,:)=0;
jg=zeros(10,10);
for i=1:20
sum=0;
j1=1;
s=0;
m=38;
i3=38;
for j=1:37
if(w(2,j)+w(3,j)>=s&w(5,j)==0)
s=w(2,j)+w(3,j);
jg(i,j1)=w(1,j);
城市垃圾运输问题 17
----------------------- Page 18-----------------------
sum=w(4,j);
m=j;
else continue;
end
end
w(5,m)=1;
j1=j1+1;
while 1
js=0;
q=40;
for k=1:37
if(q>=w(2,m)-w(2,k)+w(3,m)-w(3,k))&w(2,m)>w(2,k)&w(3,m)>w(3,k)&(8-sum)>=w(4,k)&w(5,
k)==0
q=w(2,m)+w(3,m)-w(2,k)-w(3,k);
js=1;
jg(i,j1)=w(1,k);
i3=k;
else continue;
end
end
w(5,i3)=1;
sum=sum+w(4,i3);
j1=j1+1;
m=i3;
if(w(2,i3)==0&w(3,i3)==0|js==0)
break
end
end
end
kcost=0;
zcost=0;
allcost=0;
n=1;
for u1=1:10
for u2=1:10
if jg(u1,u2)~=0
n=jg(u1,u2);
else continue
end
zcost=zcost+w(4,n)*2.0*(w(2,n)+w(3,n));
end
n=jg(u1,1);
kcost=kcost+0.5*(w(2,n)+w(3,n));
城市垃圾运输问题 18
----------------------- Page 19-----------------------
end
allcost=zcost+kcost
zcost
kcost
i=1:10;
time=[i];
time(1,:)=0;
n1=0;
n2=0;
n3=0;
for u4=1:10
for u5=1:10
if jg(u4,u5)~=0
n1=jg(u4,u5);
n2=n2+1;
else continue
end
end
n3=jg(u4,1);
time(1,u4)=((w(2,n3)+w(3,n3))*2)/40;
end
n2
time
jg
运行结果：
time =
Columns 1 through 9
2.3000 2.2000 2.1000 1.7000 1.4500 1.3500 1.0500 1.0000
0.9000
Column 10
0.7000
jg =
30 29 27 20 11 0 0 0 0 0
28 26 32 25 14 3 0 0 0 0
36 23 33 21 9 0 0 0 0 0
24 18 35 15 31 5 0 0 0 0
34 17 16 2 0 0 0 0 0 0
19 13 8 1 0 0 0 0 0 0
22 0 0 0 0 0 0 0 0 0
12 0 0 0 0 0 0 0 0 0
37 7 4 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0
城市垃圾运输问题 19
----------------------- Page 20-----------------------
代码 5
%求第三问中运输车的空载费用。
clear all
x=[28 24 30 15 9 15 21 14 8 3;
18 20 12 19 20 12 0 6 10 11];
kcost=0;
for i=1:10
kcost=kcost+0.5*(x(1,i)+x(2,i));
end
kcost
运行结果：
kcost =
147.5000
代码 6
%画加
权点的分布图。
clear all
x=[28 24 30 15 9 19 15 22 10 14 5];
y=[18 20 12 19 20 9 12 5 12 6 12];
plot(x,y,'*r');
text(x+0.5,y,num2cell(1:11));
运行结果：
见正文图表 4 。
代码 7
%用蚁群算法求最佳哈密顿圈。
clear all
m=50;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;
C=[24.6667 15.6667;
%16.2000 14.2000; %第二次运行时删去此行。
27.3333 9.3333;
10.5000 16.2500;
4.2500 15.5000;
16.6667 4.0000;
12.0000 9.0000;
21.5000 2.5000;
7.2500 9.5000;
9.0000 3.3333;
3.0000 9.3333];
城市垃圾运输问题 20
----------------------- Page 21-----------------------
ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
function
[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho
,Q)
%%===================================================================
%% 主要符号说明
%% C n 个垃圾处理厂的坐标，n ×2 的矩阵
%% NC_max 最大迭代次数
%% m 蚂蚁个数
%% Alpha 表征信息素重要程度的参数
%% Beta 表征启发式因子重要程度的参数
%% Rho 信息素蒸发系数
%% Q 信息素增加强度系数
%% R_best 各代最佳路线
%% L_best 各代最佳路线的长度
%%===================================================================
%%第一步：变量初始化
n=size(C,1); %n 表示问题的规模（垃圾处理厂个数）
D=zeros(n,n); %D 表示完全图的赋权邻接矩阵
for i=1:n
for j=1:n
if i~=j
D(i,j)=abs(C(i,1)-C(j,1))+abs(C(i,2)-C(j,2));
else
D(i,j)=eps; %i=j 时不计算，应该为 0，但后面的启发因
子要取倒数，用 eps （浮点相对精度）表示
end
D(j,i)=D(i,j); %对称矩阵
end
end
Eta=1./D; %Eta 为启发因子，这里设为距离的倒数
Tau=ones(n,n); %Tau 为信息素矩阵
Tabu=zeros(m,n); %存储并记录路径的生成
NC=1; %迭代计数器，记录迭代次数
R_best=zeros(NC_max,n);
%各代最佳路线
L_best=inf.*ones(NC_max,1); %各代最佳路线的长度
L_ave=zeros(NC_max,1); %各代路线的平均长度
达到最大迭代次数，停止
while NC<=NC_max %停止条件之一：
%%第二步：将 m 只蚂蚁放到 n 个垃圾处理厂上
Randpos=[]; %随即存取
城市垃圾运输问题 21
----------------------- Page 22-----------------------
for i=1:(ceil(m/n))
Randpos=[Randpos,randperm(n)];
end
Tabu(:,1)=(Randpos(1,1:m))';
%%第三步：m 只蚂蚁按概率函数选择下一座垃圾处理厂，完成各自的周游
for j=2:n %所在垃圾处理厂不计算
for i=1:m
visited=Tabu(i,1:(j-1)); %记录已访问的垃圾处理厂，避免重复访问
J=zeros(1,(n-j+1)); %待访问的垃圾处理厂
P=J; %待访问垃圾处理厂的选择概率分布
Jc=1;
for k=1:n
if length(find(visited==k))==0 %开始时置 0
J(Jc)=k;
Jc=Jc+1; %访问的垃圾处理厂个数自加 1
end
end
%下面计算待选垃圾处理厂的概率分布
for k=1:length(J)
P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
end
P=P/(sum(P));
%按概率原则选取下一个垃圾处理厂
Pcum=cumsum(P); %cumsum ，元素累加即求和
Select=find(Pcum>=rand); %若计算的概率大于原来的就选择这条路线
to_visit=J(Select(1));
Tabu(i,j)=to_visit;
end
end
if NC>=2
Tabu(1,:)=R_best(NC-1,:);
end
%%第四步：记录本次迭代最佳路线
L=zeros(m,1); %开始距离为 0，m*1 的列向量
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+D(R(j),R(j+1)); %原距离加上第j 个垃圾处理厂到第j+1 个垃
圾处理厂的距离
end
L(i)=L(i)+D(R(1),R(n)); %一轮下来后走过的距离
end
城市垃圾运输问题 22
-------------------
---- Page 23-----------------------
L_best(NC)=min(L); %最佳距离取最小
pos=find(L==L_best(NC));
R_best(NC,:)=Tabu(pos(1),:); %此轮迭代后的最佳路线
L_ave(NC)=mean(L); %此轮迭代后的平均距离
NC=NC+1 %迭代继续
%%第五步：更新信息素
Delta_Tau=zeros(n,n); %开始时信息素为 n*n 的0 矩阵
for i=1:m
for j=1:(n-1)
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
%此次循环在路径（i，j ）上的信息素增量
end
Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
%此次循环在整个路径上的信息素增量
end
Tau=(1-Rho).*Tau+Delta_Tau; %考虑信息素挥发，更新后的信息素
%%第六步：禁忌表清零
Tabu=zeros(m,n); %%直到最大迭代次数
end
%%第七步：输出结果
Pos=find(L_best==min(L_best)); %找到最佳路径（非 0 为真）
Shortest_Route=R_best(Pos(1),:) %最大迭代次数后最佳路径
Shortest_Length=L_best(Pos(1)) %最大迭代次数后最短距离
subplot(1,2,1) %绘制第一个子图形
DrawRoute(C,Shortest_Route) %画路线图的子函数
subplot(1,2,2) %绘制第二个子图形
plot(L_best)
hold on %保持图形
plot(L_ave,'r')
title('铲车的平均路程和最短路程') %标题
function DrawRoute(C,R)
%%===================================================================
%% DrawRoute.m
%% 画路线图的子函数
%%-------------------------------------------------------------------------
%% C Coordinate 结点坐标，由一个 N ×2 的矩阵存储
%% R Route 路线
%%===================================================================
N=length(R);
scatter(C(:,1),C(:,2));
hold on
plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)],'g')
hold on
城市垃圾运输问题 23
----------------------- Page 24-----------------------
for ii=2:N
plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)],'g')
hold on
end
title('铲车最短路程图（最佳哈密顿圈）')
运行结果：
见正文图表 5，6 。
代
码 8
%求铲车营运费用。
clear all
x=[28 24 30 15 9 19 15 22 10 14 5;
21 5 25 7 0 14 9 21 4 3 1];
y=[13 4 7 14 8 0 6 0 7 2 5;
18 20 12 19 20 9 12 5 12 6 12];
s=0;
for i=1:11
s=s+abs(x(1,i)-x(2,i))+abs(y(1,i)-y(2,i));
end
ccost=s*0.5;
l=83.8334;
(s+l/2)*0.5
运行结果：
ans =
100.9584
城市垃圾运输问题 24