基于節(jié)約算法的車輛調(diào)度問題優(yōu)化

王海玲 盧允輝

摘要：本文通過對于車輛調(diào)度現(xiàn)狀建立了單車滿載車輛的分送優(yōu)化模型。首先對問題進行分析，將模型各個需求點的最小需求量作為約束，以總運輸路徑最短為目標，來確定車輛配送路線。并以節(jié)約算法的基本原理為基礎，對模型進來具體求解優(yōu)化。最后給出優(yōu)化后的處理方法的優(yōu)缺點分析，并且對解結(jié)果進行討論和再優(yōu)化。

關鍵詞：車輛調(diào)度;節(jié)約算法;優(yōu)化

中圖分類號：TP242.6文獻標識碼：A文章編號：1672-9129（2018）06-0007-03

Optimization of Vehicle Scheduling Problem Based on C-W

WANG Hailing*， LU Yunhui

（Xiamen University Tan Kah Kee Colledge， College of Information Science and Technology， Fujian Xiamen， 363105， China）

Abstract： In this paper， the distribution optimization model of vehicle load vehicle is established. Firstly， the problem is analyzed， and the minimum demand of each demand point of the model is used as the constraint， and the route of vehicle distribution is determined by the shortest path of the total transportation path. The factors affecting the transportation path are the sum of the distribution of each demand point and the driving distance of the vehicle. Based on the analysis， the model is based on the basic principle of the saving algorithm. Finally， the advantages and disadvantages of the optimized processing method are analyzed， the results are discussed and optimized.

Keywords： Vehicle routing; C-W; Optimizing

引用：王海玲， 盧允輝. 基于節(jié)約算法的車輛調(diào)度問題優(yōu)化[J]. 數(shù)碼設計， 2018， 7（6）： 7-9.

Cite：WANG Hailing， LU Yunhui. Optimization of Vehicle Scheduling Problem Based on C-W[J]. Peak Data Science， 2018， 7（6）： 7-9.

引言

在物流系統(tǒng)中，時常會遇到車輛的路徑規(guī)劃問題，而求解方法有很多種，可分為最優(yōu)化算法、動態(tài)求解算法和啟發(fā)式算法三大類。C-W節(jié)約算法屬于啟發(fā)式算法。是一種被用來解決車輛數(shù)不固定情況下的車輛調(diào)度問題。該算法從起始出發(fā)按所需訪問的所有點作出N-1條線路，計算合并任意兩條路徑后與之前未進行優(yōu)化時的路徑相比較，得出合并線路后所節(jié)約的路程量;然后再將節(jié)約的路程量按大小進行排序;最后依據(jù)排序結(jié)果以及附加的約束條件對合并后的路徑進行判斷線路是否合理，直到所有需要訪問的點都被安排到線路當中。

本文根據(jù)對于車輛調(diào)度現(xiàn)狀，建立了車輛的配送優(yōu)化模型。通過計算，給出了優(yōu)化后的處理方法對優(yōu)缺點進行分析，最后對于求解結(jié)果進行討論和再優(yōu)化。

1? 車輛調(diào)度問題概述

車輛調(diào)度問題最早是由Dantzig和Ramser于1959年提出來的^[1]，并且許多現(xiàn)實生活中的的實際問題的理論都可以歸結(jié)于這一問題。由于應用前景廣闊，所以成為運籌學與組合優(yōu)化領域的研究熱點^[2]。隨著越來越多的專家學者對車輛調(diào)度問題的研究不斷深入和發(fā)展，最近幾十年來，不但獲得了很多有意義的成果，并且使得車輛調(diào)度在當下現(xiàn)實生活中能更好的被節(jié)約算法所解決。

車輛運輸調(diào)度問題一般定義為：對一系列裝貨點和卸貨點規(guī)劃適當?shù)男熊嚶肪€，使車輛有序地通過它們，滿足一定的約束條件，如時間窗口約束、車輛容量限制、車輛行駛里程限制、司機最大工作時間限制等，達到一定的目標如：車輛行駛路程最短、運輸費用最少、使用車輛數(shù)最少、服務質(zhì)量最高等^[3]。

對于車輛調(diào)度問題，許多學者根據(jù)不同的標準，從不同的角度出發(fā)對車輛調(diào)度問題進行了不同的分類：

按照車輛載貨物的情況分，有滿載問題（貨運量不小于整車負荷量）和非滿載問題（貨運量小于車輛容量或者一輛車服務多位客戶）

按照車輛類型分，有單車輛類型問題（使用的所有車輛相同）和多車輛類型的問題（執(zhí)行任務的車輛的類型和負荷能力不完全相同）。

按照任務特征分，有純裝載（純卸貨）問題，即集貨或送貨問題（車輛在所有任務點只裝、卸貨）及裝、卸貨混合問題，即集貨送貨一體化問題（每個客戶有不同的裝、卸點）。

按照任務的性質(zhì)，有對弧服務問題（如郵差問題）和對點服務問題（如旅行商問題）以及混和服務問題（如交通路線的安排問題） 。

按照車輛是否需要返回車庫的關系來分，有車輛開放問題和車輛封閉問題。

按照信息是否全部都是預先知道來分，有動、靜態(tài)VRP問題。

按照不同的數(shù)學模型來分，有TSP問題（旅行商問題）VRP問題（車輛路徑問題）和PDP（裝載和卸載問題）。

按照車庫數(shù)目分，有單車庫對多客戶問題和多車庫對多客戶問題。

按照優(yōu)化目標來來分，有單目標問題和多目標問題^[4]。

其中，車輛調(diào)度問題中最常見的問題之一就是VRP（Vehicle Routing Problem， 車輛路由問題），它是用來確定一些有容量限制的車輛在配送過程中的最優(yōu)路徑，必須經(jīng)過每個訪問點但不能重復訪問^[5。我們可以這樣理解VRP問題：現(xiàn)有單個（或更多）出發(fā)點（也是終止點）和多個需要遍歷訪問的點，現(xiàn)在在出發(fā)點有配送的車隊（車輛數(shù)量已知或未知但是都存在容量限制）， 從出發(fā)點開始進行配送，并且必須經(jīng)過所有需要訪問服務的點。為了使得運輸成本最低應該如何分配線路使得從出發(fā)點到所有需要訪問服務的點的距離最短。VRP的解就是設計出一個或多個滿足這樣要求的最短配送路線，同時必須滿足一系列的約束，可以包括貨品體積約束、車輛需要進行保養(yǎng)和維護的里程數(shù)約束、車輛行駛路程約束、時間窗口約束等。

2? 節(jié)約算法的基本原理

節(jié)約算法（節(jié)約里程法）的基本思路如圖1和圖2所示，設車庫到客戶A和B的距離分別為a和b?？蛻鬉和B之間的距離為c。車輛要向客戶A和B分別運輸貨物，起點為車庫?，F(xiàn)有兩種路徑方式去實現(xiàn)，配送路徑如下圖箭頭標注所示：

在圖1中，車輛的配送距離為2a+2b;在圖2中，車輛的配送距離為a+b+c。由上圖1的中的配送距離與圖2的配送距離做差可以得到：

（1）

由的幾何性質(zhì)可以得知，任意兩邊之和大于第三邊。那么如果把倉庫與客戶A、B看作三角形的三個頂點，則所形成的三角形的三邊長度分別a、b、c。明顯得知的結(jié)果是大于0的。所以單從配送距離的角度來講，選擇圖（B）的方式進行配送更好。

3 ?算法流程

根據(jù)前面所敘述的求解原理，給出具體求解步驟如下：

第一步：計算，使

第二步：在A內(nèi)按從大到小的順序?qū)?img alt="" height="18" src="file：///C：/Users/ADMINI～1.PC-/AppData/Local/Temp/msohtmlclip1/01/clip_image008.gif" width="13"/>排列;

第三步：如果，則終止算法。反之對于第一項所對應的（，）進行判斷，是否滿足以下條件之一：

（1）點和點均不在已構成的路線上;

（2）點或點在已經(jīng)規(guī)劃好的路徑上，但是它并屬于路線內(nèi)的點;

（3）點和點在已經(jīng)規(guī)劃好的的不同路徑上，且都不是路徑內(nèi)的點，且一個為起點，另一個為終點。則轉(zhuǎn)到下一步，否則跳轉(zhuǎn)第六步。

第四步，考察點和點連接后的貨物運輸量Z，若，則轉(zhuǎn)到下一步，否則跳轉(zhuǎn)第六步。

第五步：連接點和點。

第六步：，跳轉(zhuǎn)第三步。

4 ?求解結(jié)果

以長榮物流（上海）有限公司福州分公司點為例o（圖3中的點2），現(xiàn)向A、B、C、D、E五位客戶運輸貨物，即圖3中的1，3，4，5，6五點，單車最大載重15T。通過百度測量出各點到倉庫的距離（Km）以及配送點到配送點之間的距離，點對點的最短距離的如表1所示，連線如圖5所示，客戶貨物需求量如表1所示。

倉庫O與各客戶之間的分布網(wǎng)絡圖4

由表4，可知節(jié)約值最大兩個為3.3和0.9，連接D-E-B，因為配送車輛最大載重15T，D（T）+E（T）+B（T）=21T>15T，所以不可以連接，因此只連接DE兩點。再按節(jié)約值來選擇下一個連接對象為AC（0.7），載重為10T，所以可以連接，剩下B點單獨配送。最終配送的三條線路如下：

（1）0-D-E-0???? 載重12T

（2）0-A-C-0???? 載重10T

（3）0-B-0?????? 載重9T

路程較未優(yōu)化前節(jié)約3.3+0.7=4（Km）。

節(jié)約配送車輛2輛。

由表5，可以看出當每個客戶只能由一輛車服務的時候，多數(shù)車輛滿載率太低。當客戶需求可以分割，即單一客戶的可服務車輛不限于一輛的時候，可以提高車輛的滿載率。因此對此進行額外優(yōu)化考慮。

此時默認車輛滿載，對客戶點的需求進行拆分，得到下表：

根據(jù)表4和表6可以得出此時的配送線路為：

（1.1）O-D-E-B1-0???? 載重15T

（2.1）O-A-C-B2-0????? 載重15T

（3.1）O-B3-0????????? 載重1T

路程較未優(yōu)化前節(jié)約0.7（Km）。

節(jié)約配送車輛2輛。

此種配送方式雖然可以提高多數(shù)車輛的滿載率，但是又由于配送車輛載重量的限制，導致當配送總量超出車輛載重配送總量上限時要多分配一臺車輛。如本案例所示，雖然提高了其中兩輛配送車輛的滿載率，但導致其中一輛配送車輛的滿載率只有6.67%。造成了資源的極大浪費。

此時如果將配送車輛裝載重量類型多樣化處理可以有效解決此種情況帶來的資源浪費問題。

長榮物流（上海）有限公司福州分公司可將運輸車輛業(yè)務外包給中泰運輸公司，讓其提供多種類的配送車輛。

此時配送車輛假設變?yōu)?T、10T、15T三種，且使單車滿載率達到80%以上進行配送。

那么配送路線和車輛分配的情況就會變得多樣化。以下列舉其中一種情況，企業(yè)可根據(jù)實際情況例如優(yōu)先考慮運輸費用、運輸時間等，進行車輛配送情況的選取。

以下為在節(jié)約路程值最大的情況下，優(yōu)先考慮運輸時間，只選取最低裝載車輛（5T）進行同時配送來完成配送目的，將客戶需求貨物量進行拆分（表8），使其滿足車輛滿載率的運輸要求：

此時配送路線為：

（1）0-A-B1-0? 載重5T 滿載率100%

（2）0-B2-0??? 載重5T 滿載率100%

（3）0-C1-O??? 載重4T? 滿載率80%

（4）O-C2-0??? 載重5T 滿載率100%

（5）O-D-O???? 載重4T? 滿載率80%

（6）O-E1-O??? 載重4T? 滿載率80%

（7）O-E2-0??? 載重4T? 滿載率80%

路程較未優(yōu)化前多了7.9（Km）。

配送車輛為7輛，比優(yōu)化前多了2輛。

造成以上結(jié)果的原因為由于求解目標的不同導致節(jié)約路程變少，配送車輛數(shù)量也變多，但提高了車輛的滿載率。同時載重數(shù)量小的車輛的運輸費用也低，運輸速度更快。節(jié)約配送時間也是企業(yè)可以獲得利潤之一，所以不影響企業(yè)采取該作為優(yōu)化配送路線的選項。

5? 結(jié)束語

c-w節(jié)約算法思想簡單，用來解決VRP問題時是一種很好用的算法，可以很快得出問題的滿意解。在算法進行優(yōu)化改進之后，可以節(jié)約了行駛路程和運輸車輛的數(shù)目，從而降低了運輸?shù)某杀?，也可以提高的車輛的滿載率，也可以節(jié)約配送所花費的時間等。根據(jù)不同的求解目的，可以對算法進行多種類、多方面的優(yōu)化，從而可以得到滿足盡可能多的約束又能獲得相對最大的利潤提升。

參考文獻：

[1]????? Dantzig G， Ramser J. The truck dispatching problem. Management Science，1959，10（6）：80-91.

[2]????? 祝崇雋，劉民，吳澄.供應鏈中車輛路徑問題的研究進展及前景[J].計算機集成制造系統(tǒng)-CIMS，2001（11）：1-6.

[3]????? 李軍，郭耀煌. 物流配送車輛優(yōu)化調(diào)度理論與方法?北京：中國物資出版社，2001.

[4]????? 《運籌學》教材編寫組.運籌學[M].北京：清華大學出版社，2005，第三版.

[5]????? 顧坤坤. 不確定環(huán)境下物流配送有關問題的研究[D].中南大學，2009.