露天矿开采点到加工地间运输车辆的安排问题

露天矿开采点到加工地间运输车辆的安排问题 摘 要 物流配送车辆调度优化问题在当今社会有着广泛的应用，而露天矿开采点到加工地间运输车辆的安排问题是典型的物流配送车辆调度优化问题。本文旨在运用数学建模的思想，设计出最优的运输车辆行驶路线以及运输车辆数量等来解决矿石运输问题。 对于问题一，由于车站的选取要保证车辆出发运输完矿石后，并在规定的时间内再回到车站，并且要使总路径最短，因此考虑运用重心法进行求解，使车站尽可能接近矿石集中的地方，以此求出车站位置坐标为（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 -