潘新元　崔艷　鐘秋平

【摘要】多車型多路徑的單個配送中心的車輛調(diào)度優(yōu)化是城市配送中的典型問題.針對該問題，本文從空駛成本、運輸成本兩個維度構(gòu)建了一個VRP的數(shù)學模型，并采用爬山算法對模型加以求解.通過實例仿真，獲得其最低運輸成本的方案.

【關(guān)鍵詞】車輛調(diào)度；物流配送；多車型

【中圖分類號】U492.2 【文獻標識碼】A

配送車輛調(diào)度問題是運籌學和組合優(yōu)化領(lǐng)域的熱點問題.多車型配送車輛調(diào)度問題是配送車輛調(diào)度問題的一個分支，一般情況下，配送企業(yè)為了適應(yīng)配送商品種類繁多、性質(zhì)各異、客戶要求各不相同的情況，往往配置多種類型的配送車輛，以提高車輛的滿載率，降低配送成本.可見，研究多車型配送車輛調(diào)度問題具有重要的理論和現(xiàn)實意義.

本文在現(xiàn)有研究成果的基礎(chǔ)上，建立了多車型配送車輛調(diào)度問題的基于直觀描述的數(shù)學模型，考慮的目標函數(shù)和約束條件比較接近實際，決策變量、目標函數(shù)和約束條件的表示較為自然、直觀和易于理解.

1.對多車型配送車輛調(diào)度問題的描述

現(xiàn)實中的多車型配送車輛調(diào)度問題十分復(fù)雜，為了方便建模和求解，需要對現(xiàn)實問題進行一些抽象和簡化.現(xiàn)對本文研究的多車型配送車輛調(diào)度問題作如下描述：

1）從一個配送中心向多個客戶送貨，配送中心供應(yīng)的貨物能夠滿足所有客戶的需求；

2）各個客戶需求的貨物均可以混裝，單一客戶的貨物需求量不超過配送車輛的最大載重量，每個客戶的送貨要求必須滿足，且僅能由一輛車完成，不允許分批配送；

3）配送車輛按載重量分類，每種車型的最大載重量一定且不允許超載，每種車型

的一次配送最大行駛距離一定，不允許超過.配送車輛均由配送中心出發(fā)，向一些客戶提供配送服務(wù)，最后返回配送中心；

4）配送中心與客戶之間及客戶相互之間的最短距離已知且固定.

在滿足上述條件下，我們要求運輸成本最小.

2.構(gòu)建數(shù)學模型

現(xiàn)有一個有向圖G=（V，E），其中V={0，1，…，N}有N+1個頂點，E={（i，j）|i，j∈V，i≠j}表示弧集，頂點0表示配送中心，剩余的頂點集V′=V＼{0}表示N個配送點，為構(gòu)建多車型最小費用車輛路徑問題數(shù)學模型，定義以下參數(shù)：

gi： 配送點i的需求量；

φ={1，2，…，L}為車輛類型的集合，類型總數(shù)為L；

Kl：l車型的數(shù)量；

φl：車型l的車輛數(shù)集，φl={1，2，…，Kl}；

dij： 兩個節(jié)點間的最短距離，i，j∈V；

Ql： 車型l的裝載能力，Q0l表示車型l的空重；

cl： l型車每公里每噸的載重費用，單位：元/噸·公里；

clkij： l型車的第k輛從第i點到第j點的費用，與距離和載重有關(guān)：

clkij=dijclrlkij（i，j）∈E；l∈φ；k∈φl；

rlkij： l型車的第k輛從第i點到第j點車輛的重量；

xlkij=1 l型車的第k輛從第i點行駛到第j點0 否則

式（1）表示目標函數(shù)，即總配送成本最??；

式（2）保證車輛都是從配送中心出發(fā)，最后回到配送中心；

式（3）表示進入每個貨物需求點的車輛卸載后會離開；

式（4）、（5）確保每個貨物需求點只能被一輛車服務(wù)一次；

式（6）表示車輛承載的貨物量之和不得大于車輛的容量；

式（7）是遞推車輛行駛路徑的總車質(zhì)量；

式（8）是車輛回到配送中心時車輛的重量；

式（9）是不超過車輛的裝載能力；

式（10）是經(jīng)過某一配送點時車輛重量不能小于空車重量；

式（11）是l型車的第k輛從第i點到第j點的費用計算公式.

3.算法過程

在多車型低耗車輛路徑問題解決過程中，本文采用爬山算法作為求解的主要算法.爬山算法是一種局部擇優(yōu)的方法，它采用啟發(fā)式方法，是對深度優(yōu)先搜索的一種改進，它利用反饋信息幫助生成解的決策.該算法每次從當前解的臨近解空間中選擇一個最優(yōu)解作為當前解，直到達到一個局部最優(yōu)解.屬于人工智能算法的一種.爬山算法結(jié)構(gòu)比較簡單，在某些情況下，整體效率還是很好的.但它的主要缺點是有時會陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解.但由于它求解時可以把復(fù)雜問題簡單化，且解的結(jié)果與最優(yōu)解比較接近，所以在很多領(lǐng)域中都有著廣泛的應(yīng)用.

爬山算法的基本步驟如下：

第一步：輸入多車型低耗車輛路徑問題，包括配送中心、顧客點之間的坐標，配送

點需求，車型參數(shù)（載重能力、空重、不同車型固定成本）等.任意選定一個初始解x0，記錄當前最優(yōu)解為xbest，且令xbest=x0，令U（xbest）代表xbest的鄰域.

第二步：從xbest的鄰域U（xbest）中按照某一規(guī)則選出一個解xnow，轉(zhuǎn)到第三步；

若當U（xbest）=φ時，或滿足其他停止運算的規(guī)則時，轉(zhuǎn)到第四步；

第三步：計算xnow的目標函數(shù)值minZ1，若xnow的目標函數(shù)值minZ1小于xbest的目標函數(shù)值minZ，則xbest=xnow，minZ=minZ1，U=U（xbest），轉(zhuǎn)到第二步；否則 U=U-xnow，轉(zhuǎn)到第二步；

第四步：輸出計算結(jié)果，停止.

在爬山算法中，第一步的初始解可以采用隨機方法產(chǎn)生，也可以用一些經(jīng)驗方法或者采用其他算法得到初始解.第二步中在U（xbest）中選取xnow的規(guī)則也可以采用隨機選取的規(guī)則.

4.實驗計算和結(jié)果分析

實例：設(shè)配送中心（0，0）和16 個客戶配送點分布及需求情況，具體數(shù)據(jù)見表1，假設(shè)該配送中心有3種車型，見表2.根據(jù)以上的爬山算法，我們應(yīng)用Lingo語言來求解，獲得費用最少的行駛路徑，見表3，此時費用為3654.40元.

5.結(jié) 論

總的來說，對于復(fù)雜的VRP，如果僅憑決策者的經(jīng)驗，是很難在較短時間內(nèi)作出一個合理的運輸路徑規(guī)劃的，本文利用優(yōu)化模型，采用爬山算法，再通過Lingo自動搜索得到費用最少的最優(yōu)路徑和車輛調(diào)度數(shù).最終結(jié)果是比較令人滿意的.

【參考文獻】

[1]楊浩雄，胡靜，何明珂.配送中多車場多任務(wù)多車型車輛調(diào)度研究[J].計算機工程與應(yīng)用，2013，49（10）.

[2]錢艷婷，王鵬濤，魏國利.動態(tài)車輛路徑問題的算法研究[J].天津理工大學學報，2010，26（6）.

[3]郭海湘，楊娟，等.煤礦物資多車型配送的改進遺傳算法求解[J].運籌與管理，2011，20（2）.