謝漓媛 肖寒月 吳童

摘 要：成都某回收公司是國內(nèi)首家專業(yè)從事城市居民垃圾分類服務(wù)及資源化的企業(yè)。截至2016年11月，該公司已覆蓋成都市錦江區(qū)、成華區(qū)、青羊區(qū)等共567個小區(qū)。

隨著公司的發(fā)展壯大，小區(qū)數(shù)量增多，收運車數(shù)量有限，如何分配才能充分利用少數(shù)車輛運輸整個成都市的回收品并使總運費最少？車輛與對應(yīng)小區(qū)分配之后，如何設(shè)計運輸路線使工作效率最高？這將是文章討論的兩個中心。作者利用運籌學(xué)中的知識——表上作業(yè)法、避圈法、破圈法、最小部分樹解決了這一實際問題。文章僅以小區(qū)覆蓋率最大的錦江區(qū)中的部分小區(qū)為例，分析探討運輸路線的優(yōu)化問題。

關(guān)鍵詞：錦江區(qū)；表上作業(yè)法；避圈破圈法；最小部分樹；路線最優(yōu)

一、成都某回收公司現(xiàn)狀描述與問題的提出

相比于傳統(tǒng)垃圾處理模式，該回收公司通過“垃圾分類”對可再生資源進行回收利用，是一種對資源的更高效率處理方式。截至2016年11月，公司已覆蓋成都錦江區(qū)、成華區(qū)、青羊區(qū)等共567個小區(qū)。截止2016年末用戶累計投遞3565784次，共回收9989余噸可回收物。

每天可回收垃圾數(shù)量都在增長，但可調(diào)配車輛數(shù)仍是14輛不變，公司堅持分類后的垃圾單獨收運，保障眾多小區(qū)的垃圾回收、定期保障八百多個分類回收箱及時清運。

在做周末兼職時，作者可以看到該小區(qū)的清場歷史，正常是從下午四點到七點，但有些小區(qū)有時清場時間很晚，甚至到十一點。于是作者思考該現(xiàn)象的原因，是因為有的司機沒有事先規(guī)劃好路線，需要往返好幾趟。

由此，可看出事先預(yù)測與規(guī)劃路線的重要性，所以要分配出最優(yōu)方案使總運費最少、工作效率最高。

二、利用表上作業(yè)法和避圈破圈法合理規(guī)劃運輸路線

1、基本材料與數(shù)據(jù)

圖1中的粗體大號數(shù)字代表不同的小區(qū)，共16個；細體小號數(shù)字代表路線規(guī)劃上的路線節(jié)點，共34個；黑色線條代表城市道路（此圖僅供參考）。

僅以這16個小區(qū)為代表，來討論最優(yōu)分配問題。

2、表上作業(yè)法

第一步、將產(chǎn)銷不平衡問題轉(zhuǎn)換為產(chǎn)銷平衡問題列出總表

左列字母A、B、C代表小區(qū)類型，從A到B到C意味著回收量依次遞減。

左列代號代表上節(jié)地圖中小區(qū)，一個數(shù)字對應(yīng)一個小區(qū)，隨機編號。

橫向字母代表車輛，A、B代表大車，C代表中車，d、e、f、g代表小車，總共7輛，另外7輛忙于成都市其他小區(qū)運輸工作；字母后面的乘號和數(shù)字代表車輛往小區(qū)跑的次數(shù)。

右列數(shù)字代表對應(yīng)該行代號所代表小區(qū)當(dāng)天垃圾回收量。

最下面數(shù)字代表各型號車輛的載重，大車1.2噸，中車0.8噸，小車0.4噸。一輛大車3趟可載3.6噸可回收物，一輛中車2趟可載1.6噸，一輛小車4趟可載1.6噸。

中間的數(shù)字代表運價，大車運價為15元/h·t，中車為12元/h·t，小車為10元/h·t。

由于所有小區(qū)回收總重量不可能剛好等于所有車輛的載重之和，要全部拉完只能再拉一趟，這樣車子總載重數(shù)就超過了小區(qū)回收總量，所以最后添加一排假想小區(qū)（運價為0）使小區(qū)回收重量等于汽車總載重量，從而把產(chǎn)銷不平衡轉(zhuǎn)換為產(chǎn)銷平衡的表上作業(yè)法。

第二步、用Vogel（沃格爾）法解決車輛與小區(qū)的分配問題

由沃格爾法易得，分配方案為：

A車拉0.6噸10號小區(qū)、0.4噸14號小區(qū)、0.2噸假想小區(qū)、0.6噸14號小區(qū)、0.2噸1號小區(qū)、0.4噸2號小區(qū)、0.1噸2號小區(qū)、0.3噸11號小區(qū)、0.4噸12號小區(qū)、0.4噸15號小區(qū)；

B車拉0.9噸9號小區(qū)、0.3噸10號小區(qū)、1噸13號小區(qū)、0.2噸14號小區(qū)、1.2噸16號小區(qū)；

C車拉0.8噸4號小區(qū)、0.7噸8號小區(qū)、0.1噸9號小區(qū)；

d車拉0.4噸10號小區(qū)、0.4噸13號小區(qū)、0.4噸14號小區(qū)、0.4噸16號小區(qū)；

e車拉0.4噸9號小區(qū)、0.4噸1號小區(qū)、0.4噸2號小區(qū)、0.4噸11號小區(qū)；

f車拉0.4噸8號小區(qū)、0.4噸12號小區(qū)、0.4噸15號小區(qū)、0.4噸4號小區(qū)；

g車拉0.4噸7號小區(qū)、0.2噸8號小區(qū)、0.2噸3號小區(qū)、0.1噸9號小區(qū)、0.3噸5號小區(qū)、0.2噸10號小區(qū)、0.2噸6號小區(qū)。

顯然，這還不是最優(yōu)的分配方案，因為該方案沒有綜合考慮各個小區(qū)在地圖的相對位置，沒有利用避圈破圈法來規(guī)劃出最短路徑。

3、分配方案的進一步優(yōu)化

（1）分配方案的一級優(yōu)化

根據(jù)上一節(jié)得出的分配方案，綜合考慮各個小區(qū)在地圖上的相對位置，盡量避免汽車繞路甚至繞城的情況。

經(jīng)過一級優(yōu)化的分配方案：

A車拉0.6噸10號小區(qū)、0.4噸14號小區(qū)、0.2噸假想小區(qū)、0.6噸14號小區(qū)、0.2噸10號小區(qū)、0.4噸11號小區(qū)、0.1噸9號小區(qū)、0.3噸11號小區(qū)、0.4噸12號小區(qū)、0.4噸15號小區(qū)；

B車拉0.9噸9號小區(qū)、0.3噸10號小區(qū)、1噸13號小區(qū)、0.2噸14號小區(qū)、1.2噸16號小區(qū)；

C車拉0.8噸4號小區(qū)、0.7噸8號小區(qū)、0.1噸9號小區(qū)；

d車拉0.4噸10號小區(qū)、0.4噸13號小區(qū)、0.4噸14號小區(qū)、0.4噸16號小區(qū)；

e車拉0.4噸9號小區(qū)、0.4噸1號小區(qū)、0.4噸2號小區(qū)、0.4噸2號小區(qū)；

f車拉0.4噸8號小區(qū)、0.4噸12號小區(qū)、0.4噸15號小區(qū)、0.4噸4號小區(qū)；

g車拉0.4噸7號小區(qū)、0.2噸8號小區(qū)、0.2噸3號小區(qū)、0.1噸2號小區(qū)、0.3噸5號小區(qū)、0.2噸1號小區(qū)、0.2噸6號小區(qū)。

（2）分配方案最終定型——運輸路線規(guī)劃

利用運籌學(xué)中的避圈破圈法、最小樹將已分配好的方案規(guī)劃出最短路徑，使汽車回收路徑最短、工作效率最高。

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]運籌學(xué)基礎(chǔ)及應(yīng)用（第六版）胡運權(quán).高等教育出版社…2014.2

（作者單位：西華大學(xué)）