露天矿开采点到加工地间运输车辆的安排问题
摘 要
物流配送车辆调度优化问题在当今社会有着广泛的应用,而露天矿开采点到加工地间运输车辆的安排问题是典型的物流配送车辆调度优化问题。本文旨在运用数学建模的思想,设计出最优的运输车辆行驶路线以及运输车辆数量等来解决矿石运输问题。
对于问题一,由于车站的选取要保证车辆出发运输完矿石后,并在
的时间内再回到车站,并且要使总路径最短,因此考虑运用重心法进行求解,使车站尽可能接近矿石集中的地方,以此求出车站位置坐标为(79.80100,44.20717)(单位:km)
对于问题二,在第一问的前提下,采用两阶段法将开采点分为四部分其中每一部分都有一个加工厂,分别对各个区域进行优化。运用混合遗传算法设计,利用求解大系统优化问题时采用的分解协调思想,首先通过扫描法将问题转换为若干个单加工厂的车辆优化调度问题,然后利用改进的遗传算法分别对每个单加工厂问题进行行车路线优化。最终得到最少车次为3,各车行驶路径分别为372.00km、346.45km、309.19km,最短总行驶路径为1027.64km。
对于问题三,在前两问的前提下,可以将加工厂的容量进行放宽,再次运用用启发式算法求解分区域情况,将加工厂的容量限制去掉,最终确定需要加大加工点S3的最大日加工量到608t,由此可以明显提高运输效率。
在对问题解决之后,对模型的适用性与稳定性进行了检验,同时还对模拟个性进行了推广,得出了更为适合实际的快速算法,可用于非技术人员的一般性应用,提高了模型的普适性。
关键词:矿石运输 重心法 两阶段法 混合遗传算法 扫描法 快速算法
目 录
一 问题重述 - 1 -
二 基本假设及符号说明 - 1 -
2.1 基本假设 - 1 -
2.2 符号说明 - 2 -
三 问题分析 - 2 -
3.1 问题一的分析 - 3 -
3.2 问题二的分析 - 4 -
3.3 问题三的分析 - 4 -
四 模型的建立与求解 - 4 -
4.1问题一模型的建立与求解 - 4 -
4.1.1问题一模型的建立 - 4 -
4.1.2问题一模型的求解 - 5 -
4.2问题二模型的建立与求解 - 6 -
4.2.1问题二模型的建立 - 6 -
4.2.2问题二模型的求解 - 9 -
4.3问题三模型的建立与求解 - 11 -
4.3.1问题三模型的建立 - 11 -
4.3.2问题三模型的求解 - 11 -
五 结果分析 - 12 -
六 模型评价 - 13 -
6.1模型的优点 - 13 -
6.2模型的缺点 - 13 -
七 模型的改进及推广 - 14 -
7.1模型的改进 - 14 -
7.2模型的推广 - 15 -
参考文献 - 15 -
附录 - 16 -
一 问题重述
某矿区有 4 个加工厂,65 个开采点,其分布见附录图1,坐标见附录(
1、表2)。各加工厂每天的最大加工量见附录(表1),各开采点每天的开采量见附录(表2)。矿区位于一个平原地带,任意两点均可连通,它们之间的距离为几何距离。
现将这个矿区从开采点到加工厂的运输任务交给某运输队,运输队首先要根据运输任务大小及加工厂和开采点的分布确定一个车站位置,并建设车站的基础设施。该车队所用运输车型最大载重量100t,行驶速度31km/h。每天上午八点,运输车从车站出发,到达各个开采点并将开采点前一天开采的矿石运往加工厂(如路径:车站→23→32→33→S1→车站;或路径:车站→21→22→S2→30→29
→S2→车站等)。晚上八点之前,所有前一天开采的矿石都需要被运往加工厂,运输车则要回到车站进行加油保养等处理。
根据给定的数据,解决以下问题:
1. 给出车站的位置。
2. 运输车耗油量很大,因此希望在完成每天的运输任务前提下,使所有运输车行驶的总路程最小。此时至少需要多少车辆参与运输,试给出每辆车的运输路线和工作时间,求出各车辆每天行驶的总距离。
3. 加大哪些加工点的最大日加工量可以明显提高运输效率。
二 基本假设及符号说明
2.1 基本假设
1.加工厂和开采点每两点之间都有路径,且其距离为几何距离;
2.运输车尽量保证每次运输载重量为其最大载重量,即100t;
3.运输车在工作过程中不发生故障和交通事故,行驶速度保持31km/h;
4.假设运输车在完成其负责线路上的运输任务后,如有剩余时间,可调度到其他线路上继续工作至运输任务结束;
5.从长远看,开采点的位置和产量会发生变化,但本题将位置和产量视为定点和定值;
6.假设装运和卸载矿石时间可以忽略不计。
2.2 符号说明
L
运输路程
为车站到采矿点的直线距离
(,)
车站的位置坐标
min Z
最短运输距离
Q
行驶的总路程变化率
各开采点的等效重量
G
所有开采点的等效重量
三 问题分析
通过对题目所给出的数据及加工厂和开采点的分布图,可以初步分析对于问题的求解,应该运用图论的知识进行求解,可以将该问题看作一个多旅行商问题,即TSP问题,但对于大规模的TSP问题通常无法求得最优解,因而需要对已有的单人TSP问题求解的办法进行改进,对本题目建立相应的模型,然后逐步优化,最终找到优化程度较好的结果。
对于题目的进一步探究,我们发现本问题主要有以下几个难点:
1. 题目中的约束条件很多,例如每辆车的最大载重量以及工作时间;
2. 每次装载量达到最大值时,车辆就要将矿石运到加工厂,而不是在当前开采点或到下一个开采点积蓄装运,因而计算量大大增加;
3. 有些采矿点可能一次无法将其所产矿石一次运完,因而车辆需要继续返回进行二次装运;
4. 有的车辆可能会提前完成任务,所以为了保证总体完成任务,需要将其调到其他需要装运的位置继续进行装运,直到全部任务结束;
5. 加工厂的容量有限,有可能会使同一辆车去到两个加工厂运送矿石。
面对这样大规模的TSP问题,运用精确算法的效果没有近似算法的效果好。因此,我们选择具有良好的全局搜索能力的遗传算法(Genetic Algorithm,GA),可以快速的将解空间里的全体解搜出。具体解题时,我们将问题简化成最简单的TSP问题,然后逐步增加约束条件进行分析,逐步优化,最后满足题目的所有要求。
运输车从车站出发后,要将所有开采点的矿石收集完并运往各加工厂,但是运输车的载重量不能超过100t,所以,在运输车负载达到最大载重量时要前往加工厂,卸下所有矿石后再返回继续装运。可以先假设运输车的载重量无限大,可一次将矿石全部收集完毕,因此暂不考虑加工厂问题,而直接从车站出发,找到一条遍历所有收集点的最短路径,从而将问题转化为TSP问题,这样就可求得最短收集路线。但是由于开采点多达65个,使用常规方法根本无法在有效时间内完成计算,因此这里考虑使用现代优化算法中的遗传算法进行求解。然后,再让运输车沿求出的路线运载矿石,当矿石量等于或略小于100t时前往加工厂,卸载完矿石后再前往下一个开采点,如此往复进行。进而可以计算出所需时间,以此可以确定至少需要使用的运输车数目。将经历每次到加工厂之间的收集路线作为一条子路线,将这些子路线均衡地分配给每辆车执行即可。
3.1 问题一的分析
对于车站位置的选定,涉及到对四个加工厂和开采点进行分组,分组应遵循各组车辆工作时间时间近似相等,还需要考虑各加工厂的日最大加工量、车辆在其工作时间内需要将该组内前一天所开采的矿石全部运输到加工厂并且还要回到车站进行加油保养等处理。
可以将该问题看作多目标优化问题,即分别对四个加工厂进行优化处理,最终得到最优的运输分组情况,其中车站位置可由一个虚拟点代替,最终得到该位置的具体坐标。
3.2 问题二的分析
在问题一的基础上,要在完成每天的运输任务的前提下,使运输车辆行驶的总路程最小此时可以看作对四组的路径进行优化,通过求解最短路径得出各组的最短路径,但并不能保证是整体的最短路径,因此可以在人为调节下使各组的工作时间尽量相等。
要使参与运输的车辆最少,则应保证在运输任务完成的前提下使工作时间尽量长,进而通过若干步优化后可求的各车辆的运输路线、工作时间以及行驶的总路程。
3.3 问题三的分析
在前两问的基础上,将加工厂的容量设为无穷大,可以将其看作是对加工厂容量的小的设计问题,由于忽略了装运和卸载矿石的时间,所以四组比较的就是行驶的总路程,只要保证在规定的时间内,能够在行驶路径最短的情况下,使得车辆的工作时间最短,这样得到的各加工厂的块矿石量即为最终容量,也就可以通过对比分析得出效率的提高程度。
四 模型的建立与求解
4.1问题一模型的建立与求解
4.1.1问题一模型的建立
对于车站的选址,应该尽量保证高效、便利、行走的路径最短,因此根据开采点的分布情况,初步猜测车站位置应比较偏向于加工点密集的地方,在上述分析的基础上,我们运用重心法确定车站位置建立如下模型:
设有n个开采点,分布在不同的坐标点上(,)上,先假设车站的位置在(,)处。运输路程L可表示为
式中采矿点i的矿石运输量;为车站到采矿点的直线距离,
。
车站在选址时应保证总运量最小,即L最小。
按照重心法,将个采矿点视为有重量的质点,为各质点的等效重量,重心是到各质点的距离最短的点。这样,寻找车站位置的地址问题,就转化为求重心坐标的问题,根据重心法的思想可以容易求出重心坐标。其中
设等效重心为G,根据重心的特性,等效重量对原点在平面XOY上产生的力矩等于各质点对原点在平面XOY产生的力矩,用方程表示为
将力矩沿X,Y轴分解,重心对X、Y轴产生的力矩分别等于各质点对X、Y轴产生力矩,用下列两式表示
最终得到重心坐标为
4.1.2问题一模型的求解
在模型建立下,将坐标点的数据代入上述公式,其中n=69,采矿点i的矿石运输量;为车站到采矿点的直线距离,最终可以求得车站的位置坐标
(,)=(79.80100,44.20717)
4.2问题二模型的建立与求解
4.2.1问题二模型的建立
1.目标函数及约束条件
对于多个加工厂的车辆调度问题,可以采用两阶段法对其研究。首先,把需要运载矿石的开采点划分为不同的区域,每个区域只有一个加工厂,可同时有多辆车进行配送,然后,对每个区域进行最有线路的求解。若以行走路径为最小的目标,则可将其过程的逆过程看作多个加工厂车辆调度问题,则从加工厂回到车站的距离是不变的,可变的是循环到不同开采点配送线路距离,则建立相应的数学模型如下:
其中,式中H代表加工厂的个数;M表示开采点的个数;表示第个加工厂需要运输的开采点个数;表示第个加工厂的车辆数;Q表示车辆的载重量;D表示车辆一次行驶的最大距离;表示第个加工厂的第个开采点的开采量;表示车站到第个加工厂的直线距离;表示第个加工厂第辆车运输的开采点数( =0表示未启用);表示第个开采点到第个开采点的直线距离;表示第个区域中的第条路径;表示在第个运输区域的第条路径上的顺序为的开采点(令=0表示加工厂)。
上述模型中,式(1)为目标函数,即要求运输总路程(即各条运输路径的长度之和)最短;式(2)保证每条路径上各开采点的矿石量不超过车辆的载重量;式(3)保证每条运输路径的长度不超过车辆一次运送的最大行驶距离;式(4)表明某运输分区每条路径上的开采点数不超过该分区的总开采点数;式(5)表明某运送分区各条配送路径上的开采点数之和等于该分区的总开采点数;式(6)表明每个开采点都要保证运输;式(7)表示每条路径的开采点的组成;式(8)限制每个开采点仅能由一辆车运输;式(9)是开采点运输矿石的时间窗约束;式(10)表示当区域中第辆车经过的开采点数大于或等于1时,说明该辆车参加了运输,则取,当第辆车运输的开采点数小于1时,表示未使用该台车辆,因此取。
2.混合遗传算法没计
通过对上述模型形式特点的分析,发现可利用求解大系统优化问题时采用的分解协调思想,首先,将上述模型问题通过扫描法转换为H个单加工厂的车辆优化调度问题,然后利用改进的遗传算法分别对每个单加工厂问题进行行车路线优化。
(Ⅰ)分区运输算法
分区采用扫描法,扫描法是求解车辆数目不要限制的VSP的启发式算法。求解过程包括以步骤:
(1)以起始点(加工厂)为原点建立极坐标系;
(2)从最小角度的两个开采点开始建立一个组;
(3)按逆时针方向将开采点按时间逐个加入到组中,直到开采点的需求总量超出了车辆的载重定额;
(4)建立一个新的组,继续该过程,直到将全部开采点都加入到组中。
扫描法是一种逐次逼近法,用该方法不一定能求得物流配送车辆路径优化问题的最优解,但是能够有效地求得问题的最优解。对于某个具体的运输车辆路径优化问题,由于存在多种开采点编号方法,当仅选择一种开采点编号
用扫描法求解时,其计算量相对较小,但相应解的质量可能不会很高;当选用多种开采点编号方案用扫描法求解时,一般能得到精度较高的最优解,但相应地,计算量会成倍增加。在该文中利用扫描法将开采点分到不同的加工厂负责运送,然后通过改进的遗传算法对单加工厂的车辆调度问题求解,这样极大地提高了算法的效率。
(Ⅱ)改进的遗传算法
该文构造的遗传算法是在基本遗传算法的基础上改进的,具体步骤如下:
(1)编码设计:为了计算机方便处理,在此遗传编码采用自然数编码,模型的解向量可编成一条长度为n+M+1的染色体编码,如
(0,,,…,,0,,…,,0,…,0,,…,,0),表示某个线路上第个货栈,0表示车场,其数目为m+1个。这样的染色体结构可以理解为车辆从车0场出发,经过,,…,后回到车场0,形成子路1;而第二台车辆也是从车场出发,经过,…,后回到车场0,形成子路2;如此反复,直到所有的货栈都被访问过。这样,染色体具有了子路内部是有序,而子路间是无序的特性。
(2)种群的初始化:随机产生n个货栈的全排列,在首尾处插入0,表示车辆从车场出发,最后又回到车场,如(O,,,…,,0)。然后计算且≤≤,否者把0向后移动1个位置,重复上面的步骤直到将m-1个O全部插入染色体内为止。如此反复,直到产生满足种群数目。
(3)适应度评价:在此采用的适应度函数与Z一致,根据实际情况可对后几项,即车辆载重和时间窗口的惩罚限制进行取舍,由此可见函数值越小的染色体越优良。
(4)选择操作:将所有染色体按照函数值大小进行排序并编号,函数值越小越靠前,假如一个规模为P的种群,函数值最小的染色体编号为0,最大的染色体编号为P-l。随机产生一个符合标准正态分布的随机数r,因为99.9%的标准正态分布随机数的范围在[-3,3]之间。取=| r/3 |(若r大于3,则重新生成)。此时的范围在[0,1]之间,t= ( P-1),选取第t号染色体进入新种群,由此选取染色体是越靠近0,概率越大,则选取较优的染色体可能性就越高。
(5)交叉操作:VSP问题具有组间无序、组内有序的特性,如果单纯地使用一般的交叉算子往往会使些优良的子串被破坏,并且在两父个体相同时,无法再产生新的个体。在此采用一种有效的交叉算子,是在传统的顺序交叉的基础上进行了改进。该交叉算子运用编码的特殊结构,即两个0之间的基因码表示车辆的配送顺序,所以在选择交叉点时,要选择车场的位置,即0基因码。在交叉时,并不是直接把选中的子串复制过去,而是移位到首位。这样既可以最大限度地保留己成为最优路径的子路径,而且在两个双亲相同的情况下,该算子也会产生新的染色体,在变异的配合下,就会产生新的有效的染色体,从而提高了算法的寻优能力,降低了过早收敛的性能,避免了早熟现象的产生。其操作过程为:
①子路线交叉复制:选择两个染色体A和B,在[1,M]之间随机产生两个自然数和 (在此假没<),若和对应染色体A中的基因码为0,否则,向左或向右移动到最近的0,然后将选中的字串移到临时串temp的首位,其他依次后移。
②确定剩下子路线位置:删去染色体B中与选中子串中相同基因码,得到后代需要的其他基因码的顺序;照此顺序,从左到右替代temp中非选中的字串基因码,得到后代,同理照此方式得到另一后代。
(6)变异操作:随机选择一个染色体,在[1,n+M]之间随机产生两个自然数tl和t2,若tl和t2对应的基因是非零的,交叉其位置变异成新的基因,否则重新产生。
至此一次循环结束,重复上述步骤,根据遗传算法迭代次数或种群的收敛停止循环,输出最终结果。
4.2.2问题二模型的求解
通过Matlab程序(见附录)得到各加工厂与开采点之间的最短路径后,我们让车辆沿着最短路径遍历所有开采点,即从车站出发开始装运矿石,当运载车内装运的矿石达到100t时,运载车开往加工厂,在加工厂卸下所有收运的矿石后,再到下一开采点继续装运矿石,如此反复,直到所有开采点的矿石都被收集完,运载车返回车站。
在给车辆分配具体路径时,可根据这样的思路:先让一辆车开始从车站出发,遍历开采点,当达到最大载重量,或工作时间超过12h时,该车辆停止工作,下一辆车继续沿着上一辆车遍历的路径开始遍历,依次收集下一开采点的矿石。依次类推。为了使车辆数最小,我们可以在上述思想的基础上,对路径进行局部优化,具体做法是可以分配一辆车专门遍历矿石多的开采点,这样可以最大限度的调用车辆。
基于以上算法,通过Matlab程序得到车辆行驶路线及车辆任务分配表。
各运输车辆路径图如下:
图一 各运输车辆路径图
注:车辆1行驶路线如上图蓝色路径所示;
车辆2行驶路线如上图红色路径所示;
车辆3行驶路线如上图虚线路径所示。
基于以上算法,通过Matlab程序得到车辆路线分配表,如下表所示:
车辆编号
具体行车路线
行车路程(km)
工作时间(h)
总行车路程(km)
1
车站->31->50->49->54->53->58->S4->62->59->
57->S4->63->56->S4->61->65->64->60->S4->52
->48->55->S4->47->41->28->19->29->S2->车站
372.00
12.00
1027.64
2
车->43->42->30->S2->20->15->16->6->S2->21
->7->22->S2->5->3->1->4->S3->40->26->27
->36->39->46->S1->车站
346.45
11.18
3
车站->23->17->18->S3->8->S3->14->11->12->
S3->9->2->S3->13->10->S3->25->35->38->34->
S1->45->51->44->S1->37->S1->33->32->24->
S1->车站
309.19
9.97
表一 车辆路线分配表
4.3问题三模型的建立与求解
4.3.1问题三模型的建立
由于考虑的是运输效率的提高问题,涉及到加工厂容量的变化,我们可以事先假定加工厂的容量无限大,在前两问的基础上,由于在进行分区考虑的时候,加入了加工厂的容最大量限制的约束条件,所以在用启发式算法求解分区域情况时可以将加工厂的容量限制去掉,由于忽略了运输过程中的装运卸载时间,所以最终对比的是各车的行驶路径近似相同的情况下,对开采点和加工点的分组情况。
4.3.2问题三模型的求解
通过对开采点加工厂的分布情况可以发现,加工厂S3的位置更加接近重心法求出的等效重心位置,因此在加大加工厂S3的加工量的同时,就能够在很大程度上提高运输效率。具体的实现过程可以参照第二问中的启发式算法实现过程中对区域的划分,得出的个区域中的开采点矿石的总产量即为加工厂加工量的变化,具体变化情况见下表:
加工厂
无限制加工量(t)
开始时加工量(t)
S1
337
500
S2
386
S3
608
S4
436
表二 各加工点加工量变化情况
从上表可以看出加工厂S3的加工量超出原加工量108t,因此,加大加工点S3的最大日加工量可以明显提高运输效率
五 结果分析
(1)模型的适用性
建模中首先用到了分区域优化,在很大程度上对问题进行了简化,这种简化的方法同样可以用来处理其他复杂的问题;其次,在处理运输车行驶路线问题上,运用混合遗传算法设计,利用求解大系统优化问题时采用的分解协调思想,先通过扫描法将问题转换为若干个单加工厂的车辆优化调度问题,然后利用改进的遗传算法分别对每个单加工厂问题进行行车路线优化求得了最短路线,该方法同样可以用来处理旅行商等问题,对于点较多的情况,仍具有很好的适用性;最后在提高运输效率的讨论时,将加工厂的容量设计为无穷大,在进行调运,因此对工厂选址规模的确定问题有一定的启发作用。总体来说,模型的适用性较好,易于推广。
(2)算法的稳定性
当开采点的数目继续增多,只要密集程度改变不大,在进行聚类处理的时候,只需将聚类数稍加改动即可;另外,划分的区域数将会增多,由于区域内总的矿石量不得超过运输车的工作时间内最大装载量,所以区域内的聚类点不会增多,同样可以采用改良圈算法求解运输车的最短行驶路线。总之,模型的稳定性较好。
六 模型评价
6.1模型的优点
(1)由于遗传算法是一种随机规划算法, 具有隐含并行性和全局信息有效利用的特点, 能够通过对解空间不同区域中的多个点的搜索, 以很大概率找到全局的最优解;
(2)模型可以最大程度的得到车辆调度问题的近似最优解。在满足运输车辆最少的情况下,所求的路径最短且均满足时间要求;
(3)将车辆优化调度问题分解为车辆分配和单一车辆路线安排两个子问题分别求解, 使每个子问题有较少的约束条件, 从而提高了求解速度。
(4).运用Matlab、Excel、Visual C++6.0等多种软件进行编程计算,严格的对模型进行求解,具有科学性。
(5)对模型的合理性进行了讨论,为模型的推广和解决同类型问题提供了有价值的参考。
6.2模型的缺点
(1)建模过程中采用了简化,但是通过模型的改进得到了比较好的结果。
(2)求解过程中为了使结果更加理想化,忽略了一些次要因素。例如:将所有车辆行驶速度时间看作同一常量,并且没有考虑运输车在工作过程中出现的问题以及交通状况对运输状况的影响,因而得出的结果不能精确的反应运输车作业的真实情况。
(3)算法本身具有一定的局限性,容易陷入局部最优。
七 模型的改进及推广
7.1模型的改进
针对本文矿石运送问题,我们是在未考虑加工厂、单车最大装载量等约束条件的前提下,运用基于遗传的TSP算法求解出的近似最优路径。但是考虑到这些约束条件时,我们所求得的矿石运输路线不一定是最优的。由于为了使模型方便求解,做了适当的假设,但实际情况往往比这种情况要复杂得多,为了保证其更加接近实际我们可以进行以下改进:
1. 将运输车辆类型改为多种,以满足不同矿区生产运输任务的不同;
2. 将运输车的平均装载时间及卸载时间考虑进去,使之更符合实际;
3. 考虑车辆在运输过程中可能会发生交通事故等问题,所以应该有代替该车辆维修时间的工作方案。
由于物流配送车辆调度优化问题是一个与生活实际密切相关的事,我们希望解决方法尽可能简单,所以设计求解的快速算法是很有必要的。在上述讨论的基础上,将模型进行简化,可以得到一个快捷方便的算法,算法主要思想为:
(1) 规定一个饱和因子P(P=1说明运输车不停歇工作,通常情况下很难达到),因此取P=0.9;
(2) 以各条路径上的运输车数量为求解量,运输车的总运量为目标函数,已饱和因子为约束,应用线性规划解法求解;
(3) 判断运输车数量是否满足要求,满足则执行第四步,否则回到第二步;
(4) 采用人工调优法进行调试。
此模型比较简单,速度较快,但不能保证求出的就是最优解。不过很适合快速的车辆调度问题。
7.2模型的推广
由于物流运输在社会中应用极为广泛,而本问题对矿石的运输情况可以看作其应用的一个典型例子,此外由于本问题具有良好的推广性以及普适性,因而可以将其进行进一步优化后的结果,进行适当的推广。例如对城市内垃圾的回收运往加工厂、对于物流配送的车辆调度问题的优化、飞机航线的规划、电路设计等问题具有一定的启示作用。
参考文献
1、 西北工业大学数学建模指导委员会 编. 数学建模简明教程. 北京:高等教育 出版社,2008.
2、 李明哲 金俊 石瑞银 编著. 图论及其算法. 北京:机械工业出版社,2010.
3、 严蔚敏 吴伟民 编著. 数据结构(C语言版). 北京:清华大学出版社,2008.
4、 梁艳春 吴春国 时小虎 葛洪伟 著. 群智能优化算法理论与应用. 北京:科学出版社,2009.
附录
图1 矿区加工厂和开采点分布图
表1各加工厂每天的最大加工量及加工地坐标
加工地编号
加工地最大日加工量/t
加工地x/km
加工地y/km
S1
500
87.00000
49.40000
S2
500
73.93333
33.00000
S3
500
103.46670
42.73333
S4
500
15.66667
47.86667
表2 各开采点每天的开采量及开采的坐标
开采地编号
开采地日开采量/t
开采地x/km
开采地y/km
1
12
111.46670
18.00000
2
49
122.73330
15.33333
3
48
109.66670
6.13333
4
18
101.73330
18.66667
5
11
89.86667
7.46667
6
35
79.20000
13.86667
7
29
93.20000
24.13333
8
37
102.60000
29.26667
9
49
109.93330
37.00000
10
70
114.80000
36.53333
11
31
126.06670
47.66667
12
34
117.86670
42.60000
13
28
110.66670
41.53333
14
24
120.53330
53.13333
15
31
55.80000
8.46667
16
8
73.20000
20.20000
17
24
94.93333
34.06667
18
30
99.13333
36.46667
19
38
39.60000
8.06667
20
36
57.40000
16.20000
21
41
75.26667
28.26667
22
32
80.93333
32.86667
23
39
87.40000
39.53333
24
44
97.20000
44.46667
25
34
104.26670
46.73333
26
7
112.73330
56.06667
27
16
118.60000
59.80000
28
7
35.80000
17.40000
29
18
55.13333
29.33333
30
26
64.46667
35.80000
31
2
77.66667
46.80000
32
39
86.66667
43.46667
33
16
86.20000
47.73333
34
9
90.60000
50.33333
35
7
100.80000
53.26667
36
12
105.86670
58.13333
37
82
84.80000
49.33333
38
35
93.40000
54.66667
39
19
104.80000
62.46667
40
15
112.13330
53.06667
41
7
32.80000
23.26667
42
31
53.60000
43.60000
43
28
67.13333
47.53333
44
16
76.20000
52.53333
45
27
83.13333
54.13333
46
8
94.66667
60.93333
47
27
28.26667
24.80000
48
36
31.46667
31.86667
49
27
63.53333
56.33333
50
14
64.86667
58.53333
51
23
73.33333
59.80000
52
18
24.46667
35.93333
53
14
41.13333
50.60000
54
22
49.80000
57.26667
55
27
7.60000
32.20000
56
24
17.73333
43.80000
57
31
31.60000
48.00000
58
20
34.53333
52.06667
59
58
37.33333
61.73333
60
43
1.80000
43.20000
61
10
21.00000
51.80000
62
7
28.26667
60.00000
63
58
11.33333
51.66667
64
40
4.20000
52.53333
65
9
8.40000
56.00000
改进的遗传算法源程序:
Function varargout = mtspf_ga(dmat->salesmen->min_tour->pop_size->num_iter->show_prog->show_res)
nargs = 7;
for k = nargin:nargs-1
switch k
case 0
dmat = 10*rand(20->20);
case 1
salesmen = 5;
case 2
min_tour = 2;
case 3
pop_size = 80;
case 4
num_iter = 1e5;
case 5
show_prog = 1;
case 6
show_res = 1;
otherwise
end
end
[nr->nc] = size(dmat);
if nr ~= nc
error('Invalid XY or DMAT inputs!')
end
n = nr - 1;
salesmen = max(1->min(n->round(real(salesmen(1)))));
min_tour = max(1->min(floor(n/salesmen)->round(real(min_tour(1)))));
pop_size = max(8->8*ceil(pop_size(1)/8));
num_iter = max(1->round(real(num_iter(1))));
show_prog = logical(show_prog(1));
show_res = logical(show_res(1));
num_brks = salesmen-1;
dof = n - min_tour*salesmen;
addto = ones(1->dof+1);
for k = 2:num_brks
addto = cumsum(addto);
end
cum_prob = cumsum(addto)/sum(addto);
% 初始化种群
pop_rte = zeros(pop_size->n); % 路径集合的种群
pop_brk = zeros(pop_size->num_brks); % 断点集合的种群
for k = 1:pop_size
pop_rte(k->:) = randperm(n)+1;
pop_brk(k->:) = randbreaks();
end
clr = [1 0 0; 0 0 1; 0.67 0 1; 0 1 0; 1 0.5 0];
if salesmen > 5
clr = hsv(salesmen);
end
% 开始运行遗传算法过程
global_min = Inf; %初始化最短路径
total_dist = zeros(1->pop_size);
dist_history = zeros(1->num_iter);
tmp_pop_rte = zeros(8->n); %当前的路径设置
tmp_pop_brk = zeros(8->num_brks); %当前的断点设置
new_pop_rte = zeros(pop_size->n); %更新的路径设置
new_pop_brk = zeros(pop_size->num_brks);%更新的断点设置
if show_prog
pfig = figure('Name'->'MTSPF_GA | Current Best Solution'->'Numbertitle'->'off');
end
for iter = 1:num_iter
% 评价每一代的种群 适应情况并作出选择。
for p = 1:pop_size
d = 0;
p_rte = pop_rte(p->:);
p_brk = pop_brk(p->:);
rng = [[1 p_brk+1];[p_brk n]]';
for s = 1:salesmen
d = d + dmat(1->p_rte(rng(s->1))); % 添加开始的路径
for k = rng(s->1):rng(s->2)-1
d = d + dmat(p_rte(k)->p_rte(k+1));
end
d = d + dmat(p_rte(rng(s->2))->n); % 添加结束的的路径
dis(p->s)=d;
%d=d+myLength(dmat->p_rte(rng(s->1):rng(s->2)));%可调用函数处理
end
total_dist(p) = d;
%distan(p)=max(dis(p->:));%计算二个人中的最大值
end
% 在每代种群中找到最好的路径
[min_dist->index] = min(total_dist);
dist_history(iter) = min_dist; %+max(distan);
if min_dist < global_min
global_min = min_dist;
opt_rte = pop_rte(index->:); %最优的最短路径
opt_brk = pop_brk(index->:); %最优的断点设置
rng = [[1 opt_brk+1];[opt_brk n]]'; %设置
断点的方法
end
% 遗传算法算子的操作集合
rand_grouping = randperm(pop_size);
for p = 8:8:pop_size
rtes = pop_rte(rand_grouping(p-7:p)->:);
brks = pop_brk(rand_grouping(p-7:p)->:);
dists = total_dist(rand_grouping(p-7:p));
[ignore->idx] = min(dists);
best_of_8_rte = rtes(idx->:);
best_of_8_brk = brks(idx->:);
rte_ins_pts = sort(ceil(n*rand(1->2)));
I = rte_ins_pts(1);
J = rte_ins_pts(2);
for k = 1:8 % 产生新的方案
tmp_pop_rte(k->:) = best_of_8_rte;
tmp_pop_brk(k->:) = best_of_8_brk;
switch k
case 2 % 倒置操作
tmp_pop_rte(k->I:J) = fliplr(tmp_pop_rte(k->I:J));
case 3 % 互换操作
tmp_pop_rte(k->[I J]) = tmp_pop_rte(k->[J I]);
case 4 % 滑动平移操作
tmp_pop_rte(k->I:J) = tmp_pop_rte(k->[I+1:J I]);
case 5 % 更新断点
tmp_pop_brk(k->:) = randbreaks();
case 6 % 倒置并更新断点
tmp_pop_rte(k->I:J) = fliplr(tmp_pop_rte(k->I:J));
tmp_pop_brk(k->:) = randbreaks();
case 7 % 互换并更新断点
tmp_pop_rte(k->[I J]) = tmp_pop_rte(k->[J I]);
tmp_pop_brk(k->:) = randbreaks();
case 8 % 评议并更新断点
tmp_pop_rte(k->I:J) = tmp_pop_rte(k->[I+1:J I]);
tmp_pop_brk(k->:) = randbreaks();
otherwise % 不进行操做
end
end
new_pop_rte(p-7:p->:) = tmp_pop_rte;
new_pop_brk(p-7:p->:) = tmp_pop_brk;
end
pop_rte = new_pop_rte;
pop_brk = new_pop_brk;
end
% 返回结果部分
rng = [[1 opt_brk+1];[opt_brk n]]';
dis_e=zeros(1->salesmen); %设置并计算每个旅行商的最短路径
for s = 1:salesmen
dis_e(s)=myLength(dmat->opt_rte(rng(s->1):rng(s->2)));
end
if nargout
varargout{1} = opt_rte;
varargout{2} = opt_brk;
varargout{3} = min_dist;
varargout{4} = dis_e;
end
%做出迭代过程的图示
plot(dist_history);
grid on;xlabel('迭代的代数');ylabel('所走的路径之和');
% 随机产生一套断点 的集合
function breaks = randbreaks()
if min_tour == 1 % 一个旅行商时,没有断点的设置
tmp_brks = randperm(n-1);
breaks = sort(tmp_brks(1:num_brks));
else % 强制断点至少 找 到最短的履行长度
num_adjust = find(rand < cum_prob->1)-1;
spaces = ceil(num_brks*rand(1->num_adjust));
adjust = zeros(1->num_brks);
for kk = 1:num_brks
adjust(kk) = sum(spaces == kk);
end
breaks = min_tour*(1:num_brks) + cumsum(adjust);
end
end
end
- 11 -