成都某回收公司在锦江区的运输路线分析与优化

谢漓媛 肖寒月 吴童

摘 要：成都某回收公司是国内首家专业从事城市居民垃圾分类服务及资源化的企业。截至2016年11月，该公司已覆盖成都市锦江区、成华区、青羊区等共567个小区。

随着公司的发展壮大，小区数量增多，收运车数量有限，如何分配才能充分利用少数车辆运输整个成都市的回收品并使总运费最少？车辆与对应小区分配之后，如何设计运输路线使工作效率最高？这将是文章讨论的两个中心。作者利用运筹学中的知识——表上作业法、避圈法、破圈法、最小部分树解决了这一实际问题。文章仅以小区覆盖率最大的锦江区中的部分小区为例，分析探讨运输路线的优化问题。

关键词：锦江区；表上作业法；避圈破圈法；最小部分树；路线最优

一、成都某回收公司现状描述与问题的提出

相比于传统垃圾处理模式，该回收公司通过“垃圾分类”对可再生资源进行回收利用，是一种对资源的更高效率处理方式。截至2016年11月，公司已覆盖成都锦江区、成华区、青羊区等共567个小区。截止2016年末用户累计投递3565784次，共回收9989余吨可回收物。

每天可回收垃圾数量都在增长，但可调配车辆数仍是14辆不变，公司坚持分类后的垃圾单独收运，保障众多小区的垃圾回收、定期保障八百多个分类回收箱及时清运。

在做周末兼职时，作者可以看到该小区的清场历史，正常是从下午四点到七点，但有些小区有时清场时间很晚，甚至到十一点。于是作者思考该现象的原因，是因为有的司机没有事先规划好路线，需要往返好几趟。

由此，可看出事先预测与规划路线的重要性，所以要分配出最优方案使总运费最少、工作效率最高。

二、利用表上作业法和避圈破圈法合理规划运输路线

1、基本材料与数据

图1中的粗体大号数字代表不同的小区，共16个；细体小号数字代表路线规划上的路线节点，共34个；黑色线条代表城市道路（此图仅供参考）。

仅以这16个小区为代表，来讨论最优分配问题。

2、表上作业法

第一步、将产销不平衡问题转换为产销平衡问题列出总表

左列字母A、B、C代表小区类型，从A到B到C意味着回收量依次递减。

左列代号代表上节地图中小区，一个数字对应一个小区，随机编号。

横向字母代表车辆，A、B代表大车，C代表中车，d、e、f、g代表小车，总共7辆，另外7辆忙于成都市其他小區运输工作；字母后面的乘号和数字代表车辆往小区跑的次数。

右列数字代表对应该行代号所代表小区当天垃圾回收量。

最下面数字代表各型号车辆的载重，大车1.2吨，中车0.8吨，小车0.4吨。一辆大车3趟可载3.6吨可回收物，一辆中车2趟可载1.6吨，一辆小车4趟可载1.6吨。

中间的数字代表运价，大车运价为15元/h·t，中车为12元/h·t，小车为10元/h·t。

由于所有小区回收总重量不可能刚好等于所有车辆的载重之和，要全部拉完只能再拉一趟，这样车子总载重数就超过了小区回收总量，所以最后添加一排假想小区（运价为0）使小区回收重量等于汽车总载重量，从而把产销不平衡转换为产销平衡的表上作业法。

第二步、用Vogel（沃格尔）法解决车辆与小区的分配问题

由沃格尔法易得，分配方案为：

A车拉0.6吨10号小区、0.4吨14号小区、0.2吨假想小区、0.6吨14号小区、0.2吨1号小区、0.4吨2号小区、0.1吨2号小区、0.3吨11号小区、0.4吨12号小区、0.4吨15号小区；

B车拉0.9吨9号小区、0.3吨10号小区、1吨13号小区、0.2吨14号小区、1.2吨16号小区；

C车拉0.8吨4号小区、0.7吨8号小区、0.1吨9号小区；

d车拉0.4吨10号小区、0.4吨13号小区、0.4吨14号小区、0.4吨16号小区；

e车拉0.4吨9号小区、0.4吨1号小区、0.4吨2号小区、0.4吨11号小区；

f车拉0.4吨8号小区、0.4吨12号小区、0.4吨15号小区、0.4吨4号小区；

g车拉0.4吨7号小区、0.2吨8号小区、0.2吨3号小区、0.1吨9号小区、0.3吨5号小区、0.2吨10号小区、0.2吨6号小区。

显然，这还不是最优的分配方案，因为该方案没有综合考虑各个小区在地图的相对位置，没有利用避圈破圈法来规划出最短路径。

3、分配方案的进一步优化

（1）分配方案的一级优化

根据上一节得出的分配方案，综合考虑各个小区在地图上的相对位置，尽量避免汽车绕路甚至绕城的情况。

经过一级优化的分配方案：

A车拉0.6吨10号小区、0.4吨14号小区、0.2吨假想小区、0.6吨14号小区、0.2吨10号小区、0.4吨11号小区、0.1吨9号小区、0.3吨11号小区、0.4吨12号小区、0.4吨15号小区；

B车拉0.9吨9号小区、0.3吨10号小区、1吨13号小区、0.2吨14号小区、1.2吨16号小区；

C车拉0.8吨4号小区、0.7吨8号小区、0.1吨9号小区；

d车拉0.4吨10号小区、0.4吨13号小区、0.4吨14号小区、0.4吨16号小区；

e车拉0.4吨9号小区、0.4吨1号小区、0.4吨2号小区、0.4吨2号小区；

f车拉0.4吨8号小区、0.4吨12号小区、0.4吨15号小区、0.4吨4号小区；

g车拉0.4吨7号小区、0.2吨8号小区、0.2吨3号小区、0.1吨2号小区、0.3吨5号小区、0.2吨1号小区、0.2吨6号小区。

（2）分配方案最终定型——运输路线规划

利用运筹学中的避圈破圈法、最小树将已分配好的方案规划出最短路径，使汽车回收路径最短、工作效率最高。

A车路线：

（1）—（2）—（3）—（4）—（5）；

（1）—（6）—（7）—（8）—（9）—（4）—（5）；

（10）—（3）—（4）—（11）—（12）—（13）—（9）—（14）—（8）

B车路线：

（10）—（3）—（2）—（1）；（5）—（12）—（15）；（16）

C车路线：

（17）/（18）；（19）——（20）——（21）——（22）——（10）

d车路线：

（1）/（23）；（15）；（5）/（24）；（16）

e车路线：

（10）；（25）；（26）

f车路线：

（19）；（14）；（11）；（17）/（18）

g车路线：

（27）；（28）——（29）——（30）——（19）；（26）——（29）——（32）——（31）；

（25）——（34）——（29）——（32）——（33）

参考文献

[1]成都某回收公司的2016年年度工作报告…………2016.11

[2]运筹学基础及应用（第六版）胡运权.高等教育出版社…2014.2

（作者单位：西华大学）