垃圾运输问题.pdf

1 基于最优搜索算法和 0-1 规划的垃圾运输模型 摘要 本文要求我们规划深圳市南山区的垃圾运输问题，首先确定了各垃圾转运站和垃圾处理厂的坐标，然后运用优化理论，基于最优搜索和最优分配的优化理论，求解出了拖车的具体调度方案。随后，在假设增加一个垃圾处理厂的前提下，确定了最优的垃圾处理厂的坐标，具体分析如下：对于问题一，我们通过题目所给的地图，对原图建立坐标系，得到各个垃圾转运站的初始坐标。再通过谷歌地图查找经纬度，以及百度的 API 坐标转换工具，得到实际距离与图中距离的比例关系，将 38 个转运站及两个垃圾处理站的初始坐标转换成实际坐标（单位为公里）。而后得到根据垃圾转运站去更近的垃圾处理厂处理的原则，将垃圾转运站分类。之后根据最优搜索的理论，通过 matlab编程得到最优的运输路线方案，再根据最优分配的理论编写了 lingo 代码，从而得到每辆车的具体调度方案，其中南山垃圾焚烧厂安排 6 辆拖车，下坪固体废弃物填埋场安排 3 辆拖车。同时也求出了总的运营费用为 236287 元。之后我们又通过遗传算法与本题采用的方法进行了比较分析，从算法的准确性来看，本题算法更好。对于问题二，我们通过在南山区内随机模拟第三个处理厂的位置，计算出 38个垃圾站到 3 个站的最短距离，然后以 38 个垃圾站到处理厂距离和最小为目标函数建立了两种类似的 0-1 线性规划模型，运用 lingo 求解得到两个处理厂的位置，然后以新建处理厂与南山区之间的区域包涵的垃圾站输与总垃圾站个数的比值为处理厂位置的合理性指标，得到两个点的比值都是 44.7%然后根据距离最短，得到处理厂的坐标为(33.16563，2.637373),然后根据对居民区的考虑，对处理厂位置的人性化做了处理，增加约束求出更加人性化的处理厂坐标（31.630,1.4）。关键词：垃圾运输 最优搜索 遗传算法 选址 2 一、问题重述 1.1 问题背景 深圳市南山区环境卫生管理总站负责南山区所有 38 个垃圾转运站的垃圾清运，每天晚上都要从垃圾处理厂出发用拖车将垃圾运回，对垃圾作回收、填埋和焚烧等处理。1.2 问题条件 南山区的垃圾清运设备主要是大型拖车，每辆大型拖车可装载十吨垃圾，并且专门用于从转运站运载垃圾到垃圾处理厂。大型拖车的平均吨耗油 25L30L 柴油/百公里。每个垃圾转运站需要用 10 分钟的时间装车，运输车平均速度为 60 公里小时（夜里运输，不考虑塞车现象），每台车每晚平均工作 6 小时。运输车重载运费 20 元/吨公里，运输车空载费用 5 元/公里。1.3 题目要求 题目要求通过适当的假设，为管理总站设计出满意的运输调度方案 1.4 解决的问题（1）给出满意的调度方案（投入运输车台数，每台车的调度方案，运营费用等）。（2）如果计划在区内再增加一个垃圾处理厂，该厂应该建在什么地方？二、问题分析与符号说明 2.1 问题分析 1.问题一的分析：（1）本题首先要获得各垃圾转运站、垃圾处理厂之间的距离，之后便是实现运营费用、车辆数量优化的多目标最优问题。最低这是一个优化问题。在保证能够将每个垃圾转运站的垃圾全都运到垃圾处理厂的情况下，确定派出的车辆数，以及每辆车的运输方案，使投入的成本最低，产生运营费用最小。考虑到求解的便利性，先把目标定为运营费用的最优。运营费用包括两个方面：油费和运输费。油费在载重总量相同时，与路程存在线性的正比例关系，路程越短油费越低。而运输费用，也与运输路程存在正比例的类线性关系。因此，我们可以把运营费用的最优简化成运输距离的最优。（2）由于垃圾处理站有两个，我们需要考虑每个转运站的处理厂的选择，考虑到运输距离的最优，因此采取每个垃圾转运站去更近的垃圾处理厂处理的判断。（3）对于每个垃圾转运站的垃圾总量，对于整 10 的部分，毫无疑问只需派拖车拖运即可，而对于额外的 5 吨的部分，则需要做一个搭配。之后再对所有的拖车的方案进行一个分配，使得每辆拖车的平均工作时间为 6 小时左右。2.问题二的分析：如果计划在区内再增加一个垃圾处理厂，则需要考虑将 38个垃圾站分配到 3 个处理厂，使 38 个垃圾站到 3 个处理厂的运营费用最小，将问题简化成 38 个点到 3 个处理厂的距离最小的问题，通过运输车的载重量约束和垃圾站的垃圾量的约束和最小距离的两种求法建立了两个 0-1 线性规划模型。运用 lingo 进行求解得出了两个第三个处理厂的坐标，然后根据新建处理厂和南山区处理厂之间包涵的垃圾站个数与总数的比值来衡量处理厂的合理性，比较路程所用的长短，得到最终的处理厂坐标。3 2.2 符号说明：三、模型假设 1、忽略车辆转弯时的减速。2、假设车辆在任意两垃圾转运站中途不停车，保持稳定的速率。3、假设在运输垃圾过程中没有新垃圾入站。4、假设各垃圾转运站每天的垃圾量相对稳定。四、问题一的模型建立与求解 4.1 模型一的建立 4.1.1 数据的预处理：根据题目所给的地图，对原图建立坐标系，得到各个垃圾转运站的初始坐标。再通过谷歌地图查找部分转运站间经纬度，再通过百度的 API 坐标转换工具，将经纬度坐标换算成米制坐标。根据实际距离与图中距离的比例关系，将 38 个转运站及两个垃圾处理站的初始坐标转换成实际坐标（单位为公里）。序号 垃圾量 横坐标 x 纵坐标 y 序号 垃 圾量 横坐标 x 纵坐标 y 1 20 29.27314 2.383771 20 25 32.43292 4.412584 2 25 30.78434 2.992415 21 15 29.89136-0.30441 3 20 34.26468 8.723812 22 15 29.15865-0.25369 符号字母 符号意义 单位 a 柴油价格 元/升 L 耗油量 升 ki 第 k 辆车去第 i 个垃圾站需要的趟数 kijd 第 k 辆车去第 i，j 两个站之间的距离 公里 kid 第 k 辆车去的第 i 个垃圾站离处理厂的距离 公里 123,iiiddd 第 i 个垃圾站到第 1，2，3 个处理厂之间的距离 ijx 若从第 i 个垃圾站去第 j 个垃圾站 ijx为 1，否则为 0 f/F 费用 元 kis 第 k 辆车去第 i 个垃圾站所运垃圾量 吨 n 总共需要的车辆数 辆 123,iiittt 第 i 种运输方案是否交由 1，2，3 个处理厂处理（1 表示是，0 表否）i，j 第 i，j 个垃圾站 4 4 25 34.08151 7.861567 23 30 30.57827-4.81852 5 5 30.3264 11.36127 24 30 30.76143-4.25603 6 20 32.13526 0.050636 25 10 37.81372 8.774532 7 5 29.68528 5.477711 26 20 33.23432 7.557244 8 10 31.26518 4.260423 27 35 33.28011 2.28233 9 30 28.90679 1.876568 28 30 34.97449 2.637373 10 25 28.10539-0.86233 29 15 35.61561 4.767627 11 10 31.40256 13.33936 30 25 29.29603 0.405678 12 40 28.21988 3.043135 31 10 33.16563 13.74512 13 20 34.42496 4.970508 32 8 31.8376 12.32496 14 15 28.7694 0.050636 33 30 35.56981 11.66559 15 20 29.11286 1.166483 34 5 39.41651 9.078854 16 30 34.58524 1.065042 35 70 37.76793 1.978009 17 16 28.49464 2.738813 36 40 26.75447-4.41275 18 15 31.63153 1.420085 37 15 32.84507 5.984915 19 15 32.639 8.064448 38 10 37.9282 8.520931 垃圾转运站 横坐标 x 纵坐标 y 垃圾转运站 横坐标 x 纵坐标 y 南山垃圾焚烧厂 24.50136-3.92729 下坪填埋场 51.10574 5.496408 然后根据点的坐标得到了 38 个转运站和 2 个处理厂的大概位置，如图蓝点代表垃圾转运站，红点是垃圾处理厂（其中 39 号点为南山垃圾焚烧厂，40 号点维下坪垃圾填埋场）。5 再用 matlab 可以算出 38 个垃圾转运站到两个处理站的距离及垃圾转运站两两间的距离。4.1.2 模型一的建立步骤 A、目标函数min总F 总费用包括油费和运输费用两部分，即=F+f总油费总运输F 其中（1）油费油价的单价 单位路程耗油量 总路程，即 38kkik1=aL(x)x2/100Nniijijidd油费F(1)（2）运输费用包括运输重载时的费用和空载时的费用即 f=f+f总运输空载（2）考虑到重载时费用远远高于空载时的费用，所以让运输车开到最远处然后再返回时沿途把垃圾运回，这样总的营运费用最少，设每个垃圾处理站到垃圾处理厂距离为i0d，所以运输过程中重载费用可以表示为：38iki ikki=1f=20d sN载（3）6 从上式可以看出运输车的重载时的费用是一定的，所以运输总费用取决于空载费用f空，38kiik=1 i=1=5(d)NijijFd x空(4)空载时费用的取决于各车次的最远点的选择，每次发车运输空载费用能否最少取决于路径的选择，为了使空载费用最少，在选择路径是应该 B、约束条件 1载重量的约束：每个车次的载重量小于 10 吨 2时间约束：每个车次出车的时间和小于 6 小时；3路线约束：每个车次走的路径上一个站点离垃圾厂的距离比下一个站点要远 4垃圾量约束：所有车次在任意垃圾转运站运载的垃圾重量之和等于该站的垃圾总量。4.1.3 最终模型 根据上述基本假设符号说明，以及模型的分析，总的费用如下:以最小费用为目标函数建立了优化模型如下：383838ki kik1ki=1k=1 i=1kiijij38i11111min=aL(x)x2/10020d s+5(d)s2d+d x/6061010(1.38),lNnNNiijijiikiijijkiiiikiijjiiiiiiiiiFddd xSTxcjxlxyly时间约束（）载重量约束 s垃圾量的约束 5路线约束:l 4.2 模型一的求解 4.2.1 模型的简化（1）考虑到图上深圳市南山区的可通行道路大多为横向道路或是纵向道路，因此在计算图中任意两点间的路径时，用两点的横、纵坐标差的绝对值之和来表示，即 dijijijxxyy（2）考虑到南山垃圾焚烧厂和下坪固体废弃物填埋场为两个单位，因此认为大型拖车间互相流通也许不一定适合，因此模型简化成从其中一个单位出发的拖车必须回到原单位。（3）由于费用与行驶距离满足增函数形式的线性关系，因此在模型求解时，将总费用的最小这个目标简化成总运输距离的最小。因此在考虑垃圾转运场的垃圾去哪一个处理厂处理这个问题时，选择更近的处理厂。（4）总的运营费用分为运输费用和油费两部分解，其中油费的百公里油耗取用题目所给的平均值 27.5 升，每升油价使用 7 元/升。4.2.2 数据预处理（1）得到各点坐标，见附录（2）计算出各垃圾转运站到两垃圾处理场的距离 7 垃圾转运站名称 到焚烧厂的距离 到填埋场的距离 垃圾转运站名称 到焚烧厂的距离 到填埋场的距离 九街站 11.082831 24.945235 松坪山站 16.27143 19.756636 玉泉站 13.202677 22.825389 南光站 9.0128722 27.015194 动物园站 22.414418 20.068455 南园站 8.3308884 27.697178 平山村站 21.368997 19.389386 望海路站 6.9681315 30.842393 牛城村站 21.113591 26.644197 花果路站 6.5888069 30.09675 科技园站 11.611821 24.416245 福光站 26.014174 16.57014 同乐村站 14.588917 21.439149 新围村站 20.217485 19.932253 松坪山（二）站 14.951522 21.076544 大冲站 14.988365 21.039701 大新小学站 10.209275 25.818791 沙河市场站 17.037786 18.99028 南山村站 6.6689829 29.359083 龙井 19.809156 16.21891 阳光(白芒关外)站 24.167842 27.54613 南山市场 9.1276346 26.900431 月亮湾大道站 10.688933 25.339133 麻勘站 26.336675 26.188823 光前站 18.821393 17.206673 白芒站 23.588479 26.096681 北头站 8.2459617 27.782104 大石磡站 26.661326 21.705105 涌下村站 9.705264 26.322802 长源村站 27.921286 15.271671 白石洲南站 15.076207 20.951859 华侨城站 19.171857 16.856209 前海公园站 10.659375 25.368691 疏港小区站 2.7385695 34.260429 深圳大学站 12.477536 23.55053 西丽路站 18.255907 18.749172 官龙村站 20.129367 21.034778 塘朗站 25.875058 16.202053 4.2.3 模型的求解方法 8 Step1：根据垃圾转运场与两个垃圾处理厂距离的大小关系，将垃圾转运场分成两类：（1）序号为 1、2、5、6、7、8、9、10、11、12、14、15、16、17、18、19、20、21、22、23、24、27、28、30、32、36、37 交由南山垃圾焚烧厂处理（2）序号为 3、4、13、25、26、29、31、33、34、35、38 交由下坪固体废弃物填埋场处理。Step2：先按 step1 中的两类情况分开讨论，分析拖车的运输路线方案（1）其中整 10 的垃圾的运输没有争议，只需从更近的垃圾处理场发车、托运、原路返回即可；（2）由于多出 6 吨、8 吨垃圾的转运站都属于南山焚烧厂处理，因此对垃圾转运站多出的 5 吨、6 吨、8 吨垃圾分两种情况作如下处理：A、将 6 吨的拆成 5 吨和 1 吨分开运输；B、将 8 吨的拆成 5 吨和 3 吨分开运输。Step3:使用蚁群算法，对之前所说的含 5 吨的情况进行两两配对，实现两两配对后的总运输距离最小，并求出最小的运营费用。Step4：整理出总共的发车方案的时间表，基于每辆车的平均工作时间得到最少的拖车数量，并基于此编写 lingo 代码得到最优的方案 4.2.4 模型的具体求解（1）运输路线方案的获得（最优搜索算法）A、算法思想：先注意到两点的情况，设两点分别为11221212(,)A x yB xyxxyy。且 A、B 处的垃圾数量为 5 吨。考虑三种情况：将垃圾转运场分成两类 分别通过最优搜索算法得到拖车的运输路线方每种路线所用的时间 最小的总运输距离 最佳的调度方案 最小的运营费用 A 9 (i)分开运输费用 21112f=(5+20 5+5)xyxy (ii)先 A 后 B 的费用 111122222)10f=5205*5)(xyxyxyxy (iii)先 B 后 A 的费用 221122113)10f=5205*5)(xyxyxyxy 通过简单的代数运算，显而易见，拖车先赶赴较远的 A 点，带上 5 吨垃圾，再前往较近的 B 点带上剩余的 5 吨垃圾，而后回到垃圾处理站，是更优的方式。基于此，我们可以得出搜索的基本原则：(i)在两点递减的情况下，不采用单独运输；(ii)在其余同等的情况下选择“先远后近”；(iii)不要求时间的情况下，对于并邻两点，采用单独运输的方式最节约钱；(iv)车在装的足够多的情况下应该直接返回原点（37 点）；（v）每一次布局和每条线路的搜索不妨由剩下未搜点中的最大值开始。B、求解结果 最终的计算发现 Step2 中 A、B 两种方案，A 方案最终的费用最低，因此此处只给出 A 方案的具体数据，B 方案的具体数据就不再赘述。(i)下坪固体废弃物填埋场 运输路线方案 进行次数 运输路线方案 进行次数 3 号站（10）2 31 号站（10）1 4 号站（10）2 33 号站（10）3 13 号站（10）2 35 号站（10）7 25 号站（10）1 4 号站（5），29号站（5）1 26 号站（10）2 34 号站（5）1 29 号站（10）1 38 号站（10）1 (ii)南山垃圾焚烧厂 运输路线方案 进行次运输路线方进行次数 B O 10 数 案 1 号站（10）2 18 号站（10）1 2 号站（10）2 19 号站（10）1 6 号站（10）2 20 号站（10）2 8 号站（10）1 21 号站（10）1 9 号站（10）3 22 号站（10）1 10 号站（10）2 23 号站（5）3 11 号站（10）1 24 号站（10）3 12 号站（10）4 27 号站（10）3 14 号站（10）1 28 号站（10）3 15 号站（10）2 30 号站（10）2 16 号站（10）3 36 号站（10）4 17 号站（10）1 37 号站（10）1 5 号站（5）7 号站（5）1 17 号站（5）10 号站（5）1 19 号站（5）20 号站（5）1 30 号站（5）22 号站（5）1 37 号站（5）2 号站（5）1 21 号站（5）14 号站（5）1 27 号站（5）18 号站（5）1 32 号站（8）17 号站（1）1（2）根据得到的运输方案，求出每种运输方案的时间和费用（仅给出部分结果，完整表格见附录）根据公式 11 A、000t2/60+1/610f5205iiiiiddd对于整吨的情况 B、00i00+1/355105205iiijjiijjtdddfddd对于两个 吨组合的情况 按照以上所讲述的运输方案，根据it n总时间T if=60(t)27.5 7nffT油费油费装载总费用F，其中 计算得到的总运输时间为 52.15885 小时（其中下坪固体废弃物填埋场的总运输时间为 18.42909 小时，南山垃圾焚烧厂的总运输时间为 33.72976 小时）计算得到的总的运输费用为 231995 元，油费 4291.84 元，因此总的费用为 236287 元。其中，由于题目中提到每台车每晚的平均工作工作时间为 6 小时，因此我们需要的大型拖车数量为 9 辆。（两站分别安排 3 辆和 6 辆）将总共的 81 次运输时间在分成两类的情况下，进行分组，使得每辆车车的工作时间尽量控制在 6 小时左右，通过 lingo 进行求解，将南山垃圾焚烧厂每辆车的工作时间控制在 6-6.5 小时，将下坪固体废弃物填埋场的工作时间控制在 5.5-5.8 小时，从而得到最终的调配方案。4.3 结果结论 综上所述，得到的最终的运输调度方案：（1）投入大型拖车 9 辆（南山垃圾焚烧厂 6 辆，下坪废弃物填埋场 9 辆）（2）总的运营费用为 236287 元（3）每辆车的调度方案见下表 垃圾处理厂 拖车编号 运输方案 固体废弃物填埋场 1 3 号（10）-26 号（10）-29 号（10)-35 号（10）-38 号（10）-4 号（5）29 号（5）运输路线方案 进行次数 每次时间 每次运输费用 3 号站（10）2 0.835615167 4214.37555 4 号站（10）2 0.812979533 4071.77106 13 号站（10）2 0.740222433 3613.40133 25 号站（10）1 0.719005 3479.729 4 号站（5）29 号站（5）1 1.003933333 4085.809 34 号站（5）1 0.685766667 1679.884 12 2 3 号（10）-13 号（10）-31 号（10）-35 号（50）3 4 号（20）-13 号（10）-25 号（10）-26 号（10）-33 号（10）-35 号（10）-38 号（10）南山垃圾焚烧厂 4 2 号（10）-8 号（10）-9 号（10）-10 号（10）-15 号（10）-28 号（10）-36 号（40）-17 号（5）10 号（5）-21 号（5）14号（5）5 1 号（10）-2 号（10）-6 号（10）-11 号（10）-15 号（10）-23 号（10）-27 号（20）-28 号（10）6 6 号（10）-9 号（10）-18 号（10）-20 号（10）-23 号（10）-24 号（30）-28 号（10）-30 号（5）22 号（5）7 1 号（10）-10 号（10）-12 号（40）-5 号（5）-7 号（5）-27 号（5）18 号（5）-20 号（10）-23 号（10）8 8 号（10）-9 号（10）-16 号（30）-19 号（5）-20 号（5）-21 号（10）-22 号（10）-32 号（8）17 号（1）9 14 号（10）-17 号（10）-37 号（5）2 号（5）-19 号（10）-27 号（10）-30 号（20）-37 号（10）4.4 深入分析 A、模型检验 对于本问的一些中间的求解结果通过人工计算的方式进行检验，例如（1）下坪固体废弃物填埋场的运输方案计算时：（i）按照程序的运行结果，将 4 号站和 29 号站进行配对，34 号站单独运输时，三站总的运输距离约为 97.78 公里；(ii)而如若采用将 4 号站与 34 站配对，29 号站单独运输时，三站总的运输距离约为 98.22 公里;两者差距非常小，但是程序依然很好地做出了判定，说明本题最优搜索的算法 十分准确。（2）对每辆车的调度方案的检验 任取第二组分步进行运算，得到的第二辆车的总工作时间为 6.258164 小时，符合程序中的约束条件。两者共同说明本题的模型求解在求解的准确性上很高，很好地满足了题目的要求，并得到了十分不错的最终调配方案。B、比较性分析 考虑到问题一在运输方案的获取时类似于一个多旅行商的问题，因此在此采用 0-1 规划和遗传算法来重新对问题一求解。使总运输距离最小作为目标函数，根据题中基本假设和前面的分析。所给的约束条件，建立如下基于 0-1 规13 划和遗传算法的模型 n38kijk=11min()iijizdd x目标函数：(1)0381103801,2,382=11,2,3830,38.1,2,38,1,2,n40,1,38501,0,1,381,2,n6010,1,381,2,n7kinikijikinkijkjikijkijkijkisqjq bcibkiiS Txbjkxbixi jkbik或或 上述模型中，k代表收集车的序号，共有n辆车。这些车从出发点（处理厂）出发把 1 至 i 个垃圾站的垃圾收集后运输至出发点，每个垃圾站的垃圾的量是jc,每台车的运量是q。ijd表示从i点到j点的距离，kijx表示车c是否由i使向j,如果是则为 1，否则为 0。kib表示第i点的货是否由车k来完成，是则为1，不是为 0。约束条件：式(2)：车k装运的所有地点的垃圾等于；式(3)：上半部分表示每个地点的任务只能由一台车完成，下半部分表示所有的车都从出发点行驶到终到点；式(4)：到达每个收集点的车有且仅有一台；式(5)：离开每个收集点的车有且仅有一台；式(6):kijx为 01 变量；式(7):kib为 01 变量。然后运用单亲遗传算法，利用 MATLAB 软件进行求解 垃圾收集路线优化问题的单亲遗传算法步骤如下【9】：（1）构造染色体，产生初始种群 采用序号编码方式，解向量可编成一条长度为 k+1+n+1 的染色体，例如0,1,2,n+1,3,4,0,5,n,n+1。在整条染色体中,自然数 1,2,3n 代表 n 个垃圾站点,出发点为 0，n+1 为终止点。初始化染色体时,先生成 n 个收集点的一个全排列，再将总数为 k+1 个 0 和 n+1 按 0,n+1,0,n+1 的顺序随机插入排列中。把第一个 0 放在最前面，当 k+1 为奇数时，最后一位一定是 0,当 k+1 为偶数时，最后一位一定是 n+1,而且在排列中不能出现 0，n+1 连续的现象。（2）确定适应度函数 将目标函数(1)和约束(2)结合作为测量染色体的成本函数，如下：n38kijk=1111min()max,0nniijkikiikizdd xMs bQ 14 M 为一很大的正数,表示当一辆收集车的收集量超过其最大承载量时的惩罚系数。将1/fz作为染色体的适应度函数。（3）基因重组操作 计算初始群体的个体的适应值保留最优个体，然后对剩余的 n-1 个个体采用基因换位、基因移位操作进行进化，比较每个个体的第 n 次与 n+1 次的适应度值，若1nnzz进行基因换位，若1nnzz则进行基因移位操作。（4）基因换位 可采用多对基因换位或单对基因换位。单对基因换位为随机选取两个正整数,(1,)i ji jn，交换染色体12(,)nAc cc中一对基因ic，jc的位置。多对基因换位即选取多个随机数进行换位。注意染色体第一位和最后一位不参与交换，也不能把 0，n+1 互换，当ic与 0 或者 n+1 交换位置后，若出现 0,0 或者0,n+1 或 n+1,n+1 像这样连续的情况，应该重新进行换位，最后再把染色体的 0和 n+1 按 0,n+1,0,n+1 的顺序重新排列。（5）基因移位 单个基因段移位操作是随机取两个正整数,(1,)i ji jn，在染色体12(,)nAc cc中取一个基因段11(,)iijAc cc以一定的概率p，依次向后移动基因段1A中的各个基因，并把最右边的基因移到最左边的位置。若出现0,0 或者 0,n+1 或 n+1,n+1 像这样连续的情况，应该重新进行基因移位，最后再把染色体的 0 和 n+1 按 0,n+1,0,n+1 的顺序重新排列。（6）运算终止 根据初始设定的代数 t，判断是否满足终止条件，若不满足则返回到步骤3。否则，满足终止条件，终止运算，并输出当前的最优解及对应的目标函数值。模型比较说明：采用最基本的遗传算法对本题的算法对本题也是可以进行求解的，但是比较求解结果与之前采取的方式有一定的差距，通过人工的检验，发现部分结果不符合实际，是错误的。因此在没有优化的适合要好得多。本问题的遗传算法的前提下，本题采用的基于最优搜索和分配的算法更为合适。五、问题二的模型建立与求解 5.1 问题二模型的建立：现计划在区内增加处理厂，以总费用最少为目标函数建立了三个处理厂之间的最小运输费。3831ki 1222333ijij1131ki 1222333ki38ki11111minf=s(dd x)25d/6061010(1.38),lnkiiiikiiikiikiiiikiiikiiijjiiiiiiiiitdtd ttdtd txcjstxlxyly运输时间约束（）载重量约束 s垃圾量的约束 5路线约束:l每个垃圾站的垃圾只能123123t1,0,1iiiiiittttt运往一个处理站 15 5.2 问题二的模型求解：5.2.1 模型的简化 因为要在区内增加处理厂，若用上述模型求解，太复杂，很难求出，现对模型简化，不考虑 38 个垃圾站有 5 吨的剩余，把每个垃圾站的垃圾量全看成是 10 的倍数，即拖车只需要从处理厂出发去垃圾站，回来就可，将运费简化成最短路程，为了方便求解增加了区域约束即处理厂的位置需要在一定区域内，不能离的太远：sminminminminijisjxxxyyy同时对模型进行约束，综合上述将模型简化为如下：3831ki 1222333is1233 12233minS=(d)minminminmin,1,2.38,0,110()(j1.38)iiikiiikiiijisjiiiiiiiiijtdtd txxxyyyst i jttttttc路程 用 lingo 求出处理厂的坐标为点 41(32.13526,2.738812)根据另外一种做法，先计算第 i 个转运站到 3 个处理厂的距离，放在一个集合里面 A31ki 1222333d,iiikiiikiitd td t，再求集合 A 的最小值即三个距离的最小值，最后16 对 38 个处理厂的距离进行求和，使距离和最小，建立了如下的模型：3831ki 1222333is1233 12233minS=min(d,)minminminmin,1,2.38,0,110()(j1.38)iiikiiikiiijisjiiiiiiiiijtdtd txxxyyyst i jttttttc路程 5.2.3 结果结论 运用 lingo 求解得到点 41 坐标（33.16563，2.637373）与其他点的相对位置图如下 可以看出两个点的坐标没有太大变化，用新建的处理厂 C 和南山区的处理厂 A 之间保涵的垃圾站的数量与总垃圾站个数的比值代表新建处理厂的效果我们命名为处理厂的合理性 =/(表示两点之间包涵垃圾站的数量，是总垃圾站数)计算出1=2=44.7%，但是计算得出1=559.8 2=385.08看出第二种模型算出的坐标更合理即将处理厂建立在 C（33.16563，2.637373）.5.3 问题二的深入分析 先对问题二求出的处理厂的位置将其在地图上的大概位置找出 17 可以发现处理厂位于居民区集中地，这样对居民身体造成的伤害极大，根据现实情况对处理厂做出人性化处理，以在居民区周围不建立处理厂的原则，根据地图找出一块比较空旷且里居民区较远适合建厂的位置 根据图对处理厂的坐标进行约束 4.2561.40024.30731.630yx 重新对模型进行求解得到处理厂坐标（31.630,1.4）S=420，路程没有增大太多，同时远离了居民区，认为是比较合理的建厂地址。18 六、模型的评价 6.1 模型的优点（1）模型建立考虑全面，运用 matlab 和 lingo 求解，计算结果精确（2）合理的假设，使复杂问题简单化，抽象问题具体化;（3）运用了一些图形，用数形结合法来进行分析，使模型思路更清晰，更有说服力;（4）本文用的数学方法都比较简单易懂，方便方案的利用。我们采用了随机性，更加具有普遍性，这样更能接近真实值。6.2 模型的缺点(1)虽然考虑十分全面，但是求解的时候简化较多，可能产生较大的误差;(2)模型假设的时候可能考虑不周，难免存在一些细小问题被忽略，可以用更加科学的方法对图上的垃圾站进行划分，比如说考虑区域人口数量，或者聚类的方式;(3)模型和算法的选取比较单一，未能用到更多、更好的优化模型，最后用遗传算法未能求解出结果，不能更好的与其他模型对比.七、模型的推广 本文中的模型都是在综合考虑了各种不同情况下得出的满足实际需求的最优解决方案，因此它的适用性较强，可以推广到很多类似的现实问题。（1）可以用更好的软件或方法得到更好的最优方案来满足社会的需求；（2）具体模型可以运用于各种运输路线设置，如：输油管道的设置、西气东输的输气管设置、南水北调的输水管设置、通信电缆的安装路线、仓库地点的设置等。（3）应用于一些最短距离的求法、旅游（省时又省力）的模型中等等。八、参考文献 1.万福永等，数学实验教程(MATLAB 版)，北京：科学出版社 2006.2.姜启源，谢金星，叶俊，数学模型（第三版）M，高等教育出版 2003.8 3.陈超等人，Matlab 应用实例精讲M.,电子工业出版社，2010,03 4.代西武，粮仓选址问题的数学模型，北京建筑工程学院学报，第 27 卷第1 期，2011 年 03 月。5.贾传兴、彭绪亚、刘国涛、刘长玮、伍翔、邓稼佳，城市垃圾中转站选址优化模型的建立及其应用，环境科学学报，第 26 卷第 11 期，2006 年 11 月。6.张光澄，非线性规划最优解计算方法，高等教育出版社，2005.7.刘桐武，刘兆龙。线性规划在城市垃圾运输中的应用J。环境卫生工程，1996 8.闵仲求，李毅华。单目标和多目标系统线性规划M，2004,23 9.陈宝林，最优化理论与算法M,北京：清华大学出版社，1989,49.19 九九、附录附录 9.1 代码 9.1.1 问题一的最优搜索算法代码（question1_1.m）x=-17.02423191-15.49012835-11.68922577 0;y=2.365158251-0.728781382 3.582445542 0;t=5 5 5 0;i=1:4;a=1:4;plot(x,y,*r)for ii=1:4 k=int2str(ii);k=strcat(p,k);text(x(ii),y(ii),k);end w=i;x;y;t;a;w(5,:)=0;jg=zeros(2,2);for i=1:3 sum=0;j1=1;s=0;m=4;i3=4;for j=1:3 if(abs(w(2,j)+abs(w(3,j)s&abs(w(5,j)=0)s=abs(w(2,j)+abs(w(3,j);jg(i,j1)=abs(w(1,j);sum=abs(w(4,j);m=j;else continue;end end w(5,m)=1;j1=j1+1;while 1 js=0;q=60;for k=1:3 if(qabs(w(2,m)-abs(w(2,k)+abs(w(3,m)-abs(w(3,k)&abs(w(2,m)abs(w(2,k)&abs(w(3,m)abs(w(3,k)&(10-sum)=abs(w(4,k)&abs(w(5,k)=0 q=abs(w(2,m)+abs(w(3,m)-abs(w(2,k)-abs(w(3,k);20 js=1;jg(i,j1)=w(1,k);i3=k;else continue;end end w(5,i3)=1;sum=sum+abs(w(4,i3);j1=j1+1;m=i3;if(abs(w(2,i3)=0&abs(w(3,i3)=0|js=0)break end end end n=0;for u1=1:2 for u2=1:2 if jg(u1,u2)=0 n=jg(u1,u2);else continue end end n=jg(u1,1);end i=1:2;time=i;time(1,:)=0;n1=0;n2=0;n3=0;for u4=1:2 for u5=1:2 if jg(u4,u5)=0 n1=jg(u4,u5);n2=n2+1;else continue end end n3=jg(u4,1);if w(3,n2)0 21 time(1,u4)=(abs(w(2,n3)+abs(w(3,n3)*2)/60;else time(1,u4)=(abs(w(2,n3)+abs(w(3,n3)*2)-2*w(3,n2)/60;end end n2 time jg 9.1.2问题1的分配lingo代码(question1_1.lg4)model:sets:n/wh1.wh3/;dc/v1.v12/:d,count;a(n,dc):x;endsets data:d=0.835615167 0.812979533 0.740222433 0.719005 0.831075 0.707297 1.039627 0.675722 0.72854 0.706735 1.003933333 0.685766667;count=2 2 2 1 2 1 1 3 7 1 1 1;enddata for(n(i):sum(dc