基于多目標規劃的城市垃圾運輸車輛調度問題研究

郭禹+朱大鵬

【摘 要】隨著城市化的發展，城市垃圾問題已成為危害城市環境、制約城市發展的頑疾，如何及時高效的轉運城市垃圾是目前各大城市面臨的嚴峻挑戰。本文針對該問題，運用運籌學的原理建立了垃圾轉運車輛調度方案的多目標規劃模型，并運用實例分析的形式驗證了該模型在減少垃圾車輛運營成本、提高運營效率方面的有效性。

【關鍵詞】 垃圾運輸 ?車輛調度 ?運營費用 ?多目標規劃

【Abstract】 With the development of city， city garbage transfer hazards has become a city environment，restricting the development of the city. Aiming at this problem， a scheme of vehicle scheduling garbage transfer established principles of operational research （including route scheduling，scheduling time and working mode） multi-objective programming model， and an example is used to analysis the form to verify the validity of the model.

【Keywords】 garbage transport ?vehicle scheduling ?operating expenses multi-objective programming

1 引言

隨著現階段“綠色城市、健康城市”的觀念日益深入人心，人們對城市的發展提出了更高的要求，如何建設“綠色城市、宜居城市”[1][2]使之符合可持續性發展的理念是現階段城市發展的重中之重，而解決城市垃圾問題更是之題中應有之義。

2 問題提出

假設某城區有個垃圾集中點，第個集中點存放垃圾的數量為噸，運輸車輛載重為噸，運輸車輛平均速度為千米/小時，每臺車每日平均工作時間為小時，運輸車輛重載費用為元/噸千米，運輸輛車和垃圾裝卸鏟車空載費用為元/噸千米，第個垃圾集中點的坐標為。如何調度運輸車輛，使得總的運營費用最小[3]。

3 數學模型的建立

3.1 模型假設

垃圾只在晚上運輸，每天每站的垃圾量不變化;街道方向均平行于坐標軸，車輛可以任意選擇路徑;運輸車到站后必須把該站的垃圾裝完;運輸車空載與重載速度均為40公里/小時;無塞車狀況，車輛運輸狀況良好;運輸車最大超載量不大于0.1噸;運輸車的使用數量足夠;每臺車每天的工作時間不超過4小時。

以垃圾處理廠為坐標原點，建立平面直角坐標系，給出各個垃圾集中點的坐標，則垃圾集中 點到垃圾處理廠的運輸距離可表示為（假設街道方向均平行于坐標軸）[4]-[5]。

3.2 符號約定

：序號為站點的垃圾量;：序號為站點的坐標; ：運輸車總重載費用;：運輸車總空載費用;：運輸車總費用;：需用運輸車的總車次數;：第輛車出車次數;

3.3 問題分析

由于運營路費是最主要的，車輛安排、路線選擇都是為運營路費的最小化提供條件，所以應首先考慮運營路費，之后再考慮車輛安排。為了使運輸車運費最小，總的思路是讓空載運輸車一直開到最遠站，在保證時間、重載量有限的前提下，沿途把各站點的垃圾帶回。根據這一思路，全部過程運輸車的重載費用可表示為：

（1）

從上式中可以看出，運輸車的重載費用是恒定的，又由于總運費為重載與空載運費之和，所以總運費的確定就可以轉化為滿足一定條件下的各車次最遠點的選擇問題。某車次運輸車經過的路徑選擇應遵循以下原則：一是遠者優先原則。某車次最遠起始點的選擇直接關系到運費多少，所以該車次在沿途返回中應盡量把較遠點的垃圾帶回;二是不走冤枉路原則。一方面，離遠點較遠的站點坐標應分別大于離遠點較近站點的坐標，在各個坐標上均不走回頭路;另一方面，由于在路途相等的條件下，重載費用要比空載費用大的多，因此，盡量讓車輛空載跑路，當然在現實中顯然不成立。

3.4 模型建立

根據問題分析及假設，運輸車費用建立以下數學模型：

重載費用 ? ? ? ? ? ? ? ? ? ? ? ?（2）

空載費用 ? ? ? ? ? ? ? ? ? ? ? （3）

總費用： ? ? ? ? ? ? ? ? ? ? ? ? ?（4）

滿足以下約束要求：

（5）

式（5）為時間約束。

載重量約束： ? ? ? ? ? ? ? ? ? ? ? ? ? （6）

路線約束： ? ? ? ? ? ? ? ?（7）

3.5 實例分析

某市共有36個垃圾集中點，以垃圾處理廠為坐標原點，每個垃圾集中點的坐標及其垃圾量如表1。endprint

垃圾處理場的運輸設備及每個垃圾集中點的基本情況如下表2。

根據上述約束條件6知：站點30（28，18）、28（24，20）、36（30，12）首先必須作為某車次的最遠點，再結合約束條件4、5，依次選出各車次的次遠點，一直到滿足約束條件的最大值為之。依次選出各個路線，最后確定出各車次的行走路線如圖1所示。

根據上面確定的路線，把各車次所經過的垃圾站數、最遠點、所用時間、總載重量進行歸納，計算出各車次運營費用及總費用，如下表3所示。

根據時間約束，最少要派7輛車執行任務，其中把4與11、5與10、6與9、7與8車次分別合并，讓4輛車執行任務;其余的3個車次分別派3輛車執行。

考慮到要把司機休息的時間合并到一塊，應該把某車輛所執行的兩個車次放在一塊，做出安排如下表4所示。

在上述模型中，車輛用了7輛，而總運輸時間為22.12小時，每天每輛車平均工作時間為3.16小時，車輛安排上還需要修正。下面給出車輛修改模型。

假設（8）中，車輛每天工作時間都不大于4小時，應該修正為每臺車幾天工作總時間之和除以天數不大于4即可，這樣可以進一步滿足題目要求。則式（9.4）可以修正為：

（8）

其中：為車輛每天工作天數。

由于，所以最少安排6輛車，安排車輛的總體思路是讓工作時間少的與工作時間多的車輛交替輪流擔任各車次的運輸工作，同時考慮到要把司機休息時間合并到一起，應該把某車輛所執行的兩個車次放在一起，盡量使每個車輛滿意，做出安排如下表5所示。

以上是對載重量都為6噸的運輸車的調度方案。

4 結語

從上述模型中可以看出，運輸車輛額定載重量越大、最遠點的垃圾數量越少、轉運的運營費用就越小。由于垃圾集中點的設置對車輛路線的選擇有一定的影響，間接的增加了運營費用。而垃圾集中點的設置又由居民的分布確定的，對垃圾處理廠而言屬于不可控因素，因此只有進一步考察運輸車輛的型號，才能最大程度的降低運營費用。

參考文獻：

[1]陳冠華.北京城市生活垃圾狀況預測及效益評價[D].北京：北方工業大學，2009.

[2]曾堅，左長安.基于可持續性與和諧理念的綠色城市設計理論[J].建筑學報，2006（12）：10-13.

[3]李引珍.管理運籌學[M].北京：科學出版社，2012：198-205.

[4]孫宏，杜文，徐杰.最小費用最大流問題在航班銜接問題中的應用[J].南京航空航天大學學報，2001（5）：478-481.

[5]方道元，韋明俊.數學建模——方法引導與案例分析[M].浙江：浙江大學出版社，2011：25-30.endprint

垃圾處理場的運輸設備及每個垃圾集中點的基本情況如下表2。

根據上述約束條件6知：站點30（28，18）、28（24，20）、36（30，12）首先必須作為某車次的最遠點，再結合約束條件4、5，依次選出各車次的次遠點，一直到滿足約束條件的最大值為之。依次選出各個路線，最后確定出各車次的行走路線如圖1所示。

根據上面確定的路線，把各車次所經過的垃圾站數、最遠點、所用時間、總載重量進行歸納，計算出各車次運營費用及總費用，如下表3所示。

根據時間約束，最少要派7輛車執行任務，其中把4與11、5與10、6與9、7與8車次分別合并，讓4輛車執行任務;其余的3個車次分別派3輛車執行。

考慮到要把司機休息的時間合并到一塊，應該把某車輛所執行的兩個車次放在一塊，做出安排如下表4所示。

在上述模型中，車輛用了7輛，而總運輸時間為22.12小時，每天每輛車平均工作時間為3.16小時，車輛安排上還需要修正。下面給出車輛修改模型。

假設（8）中，車輛每天工作時間都不大于4小時，應該修正為每臺車幾天工作總時間之和除以天數不大于4即可，這樣可以進一步滿足題目要求。則式（9.4）可以修正為：

（8）

其中：為車輛每天工作天數。

由于，所以最少安排6輛車，安排車輛的總體思路是讓工作時間少的與工作時間多的車輛交替輪流擔任各車次的運輸工作，同時考慮到要把司機休息時間合并到一起，應該把某車輛所執行的兩個車次放在一起，盡量使每個車輛滿意，做出安排如下表5所示。

以上是對載重量都為6噸的運輸車的調度方案。

4 結語

從上述模型中可以看出，運輸車輛額定載重量越大、最遠點的垃圾數量越少、轉運的運營費用就越小。由于垃圾集中點的設置對車輛路線的選擇有一定的影響，間接的增加了運營費用。而垃圾集中點的設置又由居民的分布確定的，對垃圾處理廠而言屬于不可控因素，因此只有進一步考察運輸車輛的型號，才能最大程度的降低運營費用。

參考文獻：

[1]陳冠華.北京城市生活垃圾狀況預測及效益評價[D].北京：北方工業大學，2009.

[2]曾堅，左長安.基于可持續性與和諧理念的綠色城市設計理論[J].建筑學報，2006（12）：10-13.

[3]李引珍.管理運籌學[M].北京：科學出版社，2012：198-205.

[4]孫宏，杜文，徐杰.最小費用最大流問題在航班銜接問題中的應用[J].南京航空航天大學學報，2001（5）：478-481.

[5]方道元，韋明俊.數學建模——方法引導與案例分析[M].浙江：浙江大學出版社，2011：25-30.endprint

垃圾處理場的運輸設備及每個垃圾集中點的基本情況如下表2。

根據上述約束條件6知：站點30（28，18）、28（24，20）、36（30，12）首先必須作為某車次的最遠點，再結合約束條件4、5，依次選出各車次的次遠點，一直到滿足約束條件的最大值為之。依次選出各個路線，最后確定出各車次的行走路線如圖1所示。

根據上面確定的路線，把各車次所經過的垃圾站數、最遠點、所用時間、總載重量進行歸納，計算出各車次運營費用及總費用，如下表3所示。

根據時間約束，最少要派7輛車執行任務，其中把4與11、5與10、6與9、7與8車次分別合并，讓4輛車執行任務;其余的3個車次分別派3輛車執行。

考慮到要把司機休息的時間合并到一塊，應該把某車輛所執行的兩個車次放在一塊，做出安排如下表4所示。

在上述模型中，車輛用了7輛，而總運輸時間為22.12小時，每天每輛車平均工作時間為3.16小時，車輛安排上還需要修正。下面給出車輛修改模型。

假設（8）中，車輛每天工作時間都不大于4小時，應該修正為每臺車幾天工作總時間之和除以天數不大于4即可，這樣可以進一步滿足題目要求。則式（9.4）可以修正為：

（8）

其中：為車輛每天工作天數。

由于，所以最少安排6輛車，安排車輛的總體思路是讓工作時間少的與工作時間多的車輛交替輪流擔任各車次的運輸工作，同時考慮到要把司機休息時間合并到一起，應該把某車輛所執行的兩個車次放在一起，盡量使每個車輛滿意，做出安排如下表5所示。

以上是對載重量都為6噸的運輸車的調度方案。

4 結語

從上述模型中可以看出，運輸車輛額定載重量越大、最遠點的垃圾數量越少、轉運的運營費用就越小。由于垃圾集中點的設置對車輛路線的選擇有一定的影響，間接的增加了運營費用。而垃圾集中點的設置又由居民的分布確定的，對垃圾處理廠而言屬于不可控因素，因此只有進一步考察運輸車輛的型號，才能最大程度的降低運營費用。

參考文獻：

[1]陳冠華.北京城市生活垃圾狀況預測及效益評價[D].北京：北方工業大學，2009.

[2]曾堅，左長安.基于可持續性與和諧理念的綠色城市設計理論[J].建筑學報，2006（12）：10-13.

[3]李引珍.管理運籌學[M].北京：科學出版社，2012：198-205.

[4]孫宏，杜文，徐杰.最小費用最大流問題在航班銜接問題中的應用[J].南京航空航天大學學報，2001（5）：478-481.

[5]方道元，韋明俊.數學建模——方法引導與案例分析[M].浙江：浙江大學出版社，2011：25-30.endprint