成都某回收公司在錦江區(qū)的運(yùn)輸路線分析與優(yōu)化

謝漓媛 肖寒月 吳童

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

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

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

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

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

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

在做周末兼職時(shí)，作者可以看到該小區(qū)的清場(chǎng)歷史，正常是從下午四點(diǎn)到七點(diǎn)，但有些小區(qū)有時(shí)清場(chǎng)時(shí)間很晚，甚至到十一點(diǎn)。于是作者思考該現(xiàn)象的原因，是因?yàn)橛械乃緳C(jī)沒(méi)有事先規(guī)劃好路線，需要往返好幾趟。

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

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

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

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

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

2、表上作業(yè)法

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

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

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

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

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

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

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

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

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

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

A車?yán)?.6噸10號(hào)小區(qū)、0.4噸14號(hào)小區(qū)、0.2噸假想小區(qū)、0.6噸14號(hào)小區(qū)、0.2噸1號(hào)小區(qū)、0.4噸2號(hào)小區(qū)、0.1噸2號(hào)小區(qū)、0.3噸11號(hào)小區(qū)、0.4噸12號(hào)小區(qū)、0.4噸15號(hào)小區(qū)；

B車?yán)?.9噸9號(hào)小區(qū)、0.3噸10號(hào)小區(qū)、1噸13號(hào)小區(qū)、0.2噸14號(hào)小區(qū)、1.2噸16號(hào)小區(qū)；

C車?yán)?.8噸4號(hào)小區(qū)、0.7噸8號(hào)小區(qū)、0.1噸9號(hào)小區(qū)；

d車?yán)?.4噸10號(hào)小區(qū)、0.4噸13號(hào)小區(qū)、0.4噸14號(hào)小區(qū)、0.4噸16號(hào)小區(qū)；

e車?yán)?.4噸9號(hào)小區(qū)、0.4噸1號(hào)小區(qū)、0.4噸2號(hào)小區(qū)、0.4噸11號(hào)小區(qū)；

f車?yán)?.4噸8號(hào)小區(qū)、0.4噸12號(hào)小區(qū)、0.4噸15號(hào)小區(qū)、0.4噸4號(hào)小區(qū)；

g車?yán)?.4噸7號(hào)小區(qū)、0.2噸8號(hào)小區(qū)、0.2噸3號(hào)小區(qū)、0.1噸9號(hào)小區(qū)、0.3噸5號(hào)小區(qū)、0.2噸10號(hào)小區(qū)、0.2噸6號(hào)小區(qū)。

顯然，這還不是最優(yōu)的分配方案，因?yàn)樵摲桨笡](méi)有綜合考慮各個(gè)小區(qū)在地圖的相對(duì)位置，沒(méi)有利用避圈破圈法來(lái)規(guī)劃出最短路徑。

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

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

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

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

A車?yán)?.6噸10號(hào)小區(qū)、0.4噸14號(hào)小區(qū)、0.2噸假想小區(qū)、0.6噸14號(hào)小區(qū)、0.2噸10號(hào)小區(qū)、0.4噸11號(hào)小區(qū)、0.1噸9號(hào)小區(qū)、0.3噸11號(hào)小區(qū)、0.4噸12號(hào)小區(qū)、0.4噸15號(hào)小區(qū)；

B車?yán)?.9噸9號(hào)小區(qū)、0.3噸10號(hào)小區(qū)、1噸13號(hào)小區(qū)、0.2噸14號(hào)小區(qū)、1.2噸16號(hào)小區(qū)；

C車?yán)?.8噸4號(hào)小區(qū)、0.7噸8號(hào)小區(qū)、0.1噸9號(hào)小區(qū)；

d車?yán)?.4噸10號(hào)小區(qū)、0.4噸13號(hào)小區(qū)、0.4噸14號(hào)小區(qū)、0.4噸16號(hào)小區(qū)；

e車?yán)?.4噸9號(hào)小區(qū)、0.4噸1號(hào)小區(qū)、0.4噸2號(hào)小區(qū)、0.4噸2號(hào)小區(qū)；

f車?yán)?.4噸8號(hào)小區(qū)、0.4噸12號(hào)小區(qū)、0.4噸15號(hào)小區(qū)、0.4噸4號(hào)小區(qū)；

g車?yán)?.4噸7號(hào)小區(qū)、0.2噸8號(hào)小區(qū)、0.2噸3號(hào)小區(qū)、0.1噸2號(hào)小區(qū)、0.3噸5號(hào)小區(qū)、0.2噸1號(hào)小區(qū)、0.2噸6號(hào)小區(qū)。

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

利用運(yùn)籌學(xué)中的避圈破圈法、最小樹(shù)將已分配好的方案規(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）

參考文獻(xiàn)

[1]成都某回收公司的2016年年度工作報(bào)告…………2016.11

[2]運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用（第六版）胡運(yùn)權(quán).高等教育出版社…2014.2

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