物流運(yùn)輸中多車型配送車輛的調(diào)度模型

潘新元　崔艷　鐘秋平

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

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

【中圖分類號(hào)】U492.2 【文獻(xiàn)標(biāo)識(shí)碼】A

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

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

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

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

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

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

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

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

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

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

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

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

gi： 配送點(diǎn)i的需求量；

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

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

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

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

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

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

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

clkij=dijclrlkij（i，j）∈E；l∈φ；k∈φl(shuí)；

rlkij： l型車的第k輛從第i點(diǎn)到第j點(diǎn)車輛的重量；

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

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

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

式（3）表示進(jìn)入每個(gè)貨物需求點(diǎn)的車輛卸載后會(huì)離開；

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

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

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

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

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

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

式（11）是l型車的第k輛從第i點(diǎn)到第j點(diǎn)的費(fèi)用計(jì)算公式.

3.算法過程

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

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

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

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

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

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

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

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

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

4.實(shí)驗(yàn)計(jì)算和結(jié)果分析

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

5.結(jié) 論

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

【參考文獻(xiàn)】

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

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

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