成都某回收公司在錦江區的運輸路線分析與優化

謝漓媛 肖寒月 吳童

摘 要：成都某回收公司是國內首家專業從事城市居民垃圾分類服務及資源化的企業。截至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

（作者單位：西華大學）