覃運(yùn)梅 （廣西工學(xué)院，廣西 柳州 545006）

多源點(diǎn)物流配送車輛調(diào)度模型探討

覃運(yùn)梅 （廣西工學(xué)院，廣西 柳州 545006）

根據(jù)問題的復(fù)雜性，考慮車輛條件的約束，建立了以總費(fèi)用最小為目標(biāo)的數(shù)學(xué)模型，并根據(jù)模型的特點(diǎn)設(shè)計(jì)出相應(yīng)的啟發(fā)式算法，使問題在合理的時(shí)間內(nèi)得出由多個(gè)配送中心為所有需求點(diǎn)配送貨物的車輛分派方案。實(shí)例證明，該模型符合實(shí)際問題，算法合理，具有實(shí)際應(yīng)用價(jià)值。

多源點(diǎn)；物流配送；模型；啟發(fā)式算法

0 引 言

物流配送優(yōu)化主要是對配送車輛調(diào)度的優(yōu)化問題[1]，它是一個(gè)復(fù)雜的組合優(yōu)化問題，需要考慮多種約束、多個(gè)目標(biāo)，屬于NP難題[1-4]。車輛調(diào)度問題又可以分為單源點(diǎn)調(diào)度問題和多源點(diǎn)調(diào)度問題。單源點(diǎn)調(diào)度問題是指只從一個(gè)貨源點(diǎn)調(diào)度車輛為多個(gè)需求點(diǎn)配送貨物，多源點(diǎn)調(diào)度問題則是指從多個(gè)貨源點(diǎn)調(diào)度車輛為多個(gè)需求點(diǎn)配送貨物。前不久，作者對單源點(diǎn)配送車輛調(diào)度問題進(jìn)行了研究，建立了雙目標(biāo)模型，并把問題分成2階段進(jìn)行求解，第1階段用改進(jìn)的動態(tài)聚類算法分派車輛的配送任務(wù)，第2階段用動態(tài)規(guī)劃方法求出車輛的行車路線[5]，取得了很好的效果。

本文在文獻(xiàn)[5]的研究基礎(chǔ)上，進(jìn)一步對多源點(diǎn)調(diào)度問題進(jìn)行研究，把問題描述為數(shù)學(xué)模型，并根據(jù)模型的特點(diǎn)設(shè)計(jì)了相應(yīng)的啟發(fā)式算法進(jìn)行求解。

1 建立模型

1.1 問題假設(shè)

（1）各個(gè)配送中心的貨物供應(yīng)量充足；

（2）沒有特殊裝載要求的貨物，即所有的貨物都可以混裝在一起；

（3）對于裝載的貨物，僅考慮體積和重量的限制；

（4）車輛的容積和額定載重量都相同，各個(gè)配送中心的車輛數(shù)有限，總的車輛數(shù)充足；

（5）對于滿足整車運(yùn)輸?shù)男枨簏c(diǎn)，優(yōu)先從最近的配送中心直接派車，故文中模型假設(shè)每個(gè)需求點(diǎn)的貨物都不夠裝滿一整車。

1.2 變量定義

將模型中所涉及的變量定義如下：

M——表示可用車輛總數(shù) （模型中假設(shè)車輛數(shù)M足夠用）

Ml——表示配送中心l可供調(diào)度的車輛數(shù)

L——表示配送中心個(gè)數(shù)

N——表示網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)，即配送中心及需求點(diǎn)數(shù)的總和，需求點(diǎn)有N-L個(gè) （1個(gè)需求點(diǎn)所需的貨物視為1件，即總的貨物件數(shù)為N-L）

dij——表示從i到j(luò)的距離 （當(dāng)i,j=1,2,…,L時(shí)表示物流中心，當(dāng)i,j=L+1,L+2,…,N時(shí)表示需求點(diǎn)）

V——表示車輛額定容積

W——表示車輛額定載重

Vj——表示需求點(diǎn)j所需貨物的體積

Wj——表示需求點(diǎn)j所需貨物的重量

C0——表示指派一輛車的固定費(fèi)用

C1——表示車輛行駛的每公里運(yùn)輸單價(jià)

1.3 模型建立

建立配送車輛調(diào)度的數(shù)學(xué)模型如下：

在上述模型中，式 （1）表示求最少的運(yùn)輸費(fèi)用；式 （2）表示每個(gè)需求點(diǎn)只由一輛車配送；式 （3）表示每輛車裝貨不超過其額定容積；式 （4）表示每輛車裝貨不超過其額定載重；式 （5）表示若＞0， 則Xlk=1， 即如果配送中心l的車輛k為需求點(diǎn)j配送貨物，則該車輛執(zhí)行運(yùn)輸任務(wù)，此時(shí)目標(biāo)函數(shù)需計(jì)算指派該車的固定費(fèi)用；式 （6）表示指派的車輛只駛?cè)胨拓浀男枨簏c(diǎn)；式 （7）表示指派的車輛只駛出所送貨的需求點(diǎn)；式 （8）表示每個(gè)配送中心指派的車輛數(shù)不超過其可調(diào)度的車輛總數(shù)。

2 模型求解

上述模型屬于復(fù)雜的數(shù)學(xué)難題，為在合理的時(shí)間內(nèi)得到滿意解，本文根據(jù)模型特點(diǎn)提出了一種啟發(fā)式算法，算法描述如下：

步驟1 計(jì)算每個(gè)需求點(diǎn)與各個(gè)配送中心的距離，按照就近原則進(jìn)行歸類分群，即把各個(gè)需求點(diǎn)歸入與之距離最近的配送中心。判斷各個(gè)群內(nèi)所有需求點(diǎn)所需貨物的總體積是否超過所有車輛的總?cè)莘e，或者需求點(diǎn)所需貨物的總重量是否超過所有車輛的總?cè)葜?，若是，則記該群為超飽和群。

步驟2 考慮未分派車輛的所有配送中心，計(jì)算其地理位置重心，若存在超飽和群，則優(yōu)先對超飽和群內(nèi)分派車輛執(zhí)行配送任務(wù)；否則對與該重心距離最遠(yuǎn)的配送中心所對應(yīng)的群分派車輛執(zhí)行配送任務(wù)。

步驟3 從該群內(nèi)與重心距離最遠(yuǎn)的需求點(diǎn)開始，以該需求點(diǎn)為中心，添加相鄰的需求點(diǎn)，直至達(dá)到一輛車的體積、重量的最大容量，把這些需求點(diǎn)分派給同一輛車；同樣的方法分配該群內(nèi)的其它需求點(diǎn)。若該群內(nèi)的所有需求點(diǎn)均分配完畢且滿足所分派車輛的體積、重量的約束，轉(zhuǎn)入步驟5，否則，轉(zhuǎn)入步驟4。

步驟4 把剩下的需求點(diǎn)歸入與之距離最近的未分派車輛的需求點(diǎn)所在的群，返回步驟2和步驟3，直至所有的群都分派車輛完畢。轉(zhuǎn)到步驟5。

步驟5 對每一輛車分派到的需求點(diǎn)，用Dijkstra算法[6]求出該車的最短行駛路線。

3 算 例

3.1 算例描述

有3個(gè)物流配送中心向25個(gè)需求點(diǎn)配送貨物，車輛的額定載重量為9t，額定容積為20m3，指派一輛車的固定費(fèi)用C0為30元，車輛行駛的每公里運(yùn)輸單價(jià)C1為2元/公里，各個(gè)配送中心及需求點(diǎn)的坐標(biāo)、配送中心的車輛數(shù)、需求點(diǎn)的坐標(biāo)所需貨物的體積及重量如表1所示，試制定一個(gè)合理的運(yùn)輸方案，使總的運(yùn)輸費(fèi)用最少。

表1 基本信息表

3.2 算例求解

步驟 （1） 按照步驟1的方法，歸入配送中心1的需求點(diǎn)有 { 4,5,6,7,8,9,10,17,21,22 } ；歸入配送中心2的需求點(diǎn)有 { 11,12,13,14,15,20,25 } ；歸入配送中心3的需求點(diǎn)有 { 16,18,19,23,24,26,27,28 } 。其中配送中心1對應(yīng)的群為超飽和群。

步驟 （2） 計(jì)算未分派車輛的配送中心1、2、3的重心坐標(biāo)得到 ( 27 , 23 ) ，配送中心1對應(yīng)的群為超飽和群，因此優(yōu)先考慮對配送中心1分派車輛。

步驟 （3） 計(jì) 算配送中心1對應(yīng)的各需求點(diǎn)與重心坐標(biāo) ( 27 , 2 3 ) 的距離為{27.8,22,15,9.85,14.9,18,22.4,8.54,20.9,15.2}，最大者為27.8，即以需求點(diǎn)4為中心，添加相鄰的需求點(diǎn)。該群內(nèi)與需求點(diǎn)4的距離為{0,6.71,18.4,19.7,23.4,23,12.4,23.1,16.3 } ，按照從小到大排序的對應(yīng)需求點(diǎn)為 { 4.5,10,22.6,7,17,9,21,8 } ，需求點(diǎn)4的重量、體積集合為 { W ,V }={3. 1 ,6 . 8}，依次添加需求點(diǎn)5后 { W ,V } ={5. 1 ,1 0 .3}，添加需求點(diǎn)10后 { W ,V }={8. 2 ,1 4.9}，添加需求點(diǎn)22后 { W ,V }={10 . 6 , 21 } ，此時(shí)重量、體積均超過車輛的額定值，故需求點(diǎn)22不能分派給該車輛。該車輛記為X11，所以得到車輛X11分派的需求點(diǎn)為 { 4, 5 ,1 0 } ，對該群內(nèi)剩下的需求點(diǎn) { 6,7,8,9,17,21,22}用同樣的方法分派車輛，得到車輛X12分派的需求點(diǎn)為 { 6, 8 ,2 1 }，X13分派的需求點(diǎn)為 { 7, 9 ,2 2 } 。此時(shí)，配送中心1的車輛已經(jīng)分派完畢，但還有需求點(diǎn) { 17 } 未分派到車輛，故轉(zhuǎn)入 （4）。

步驟 （4） 把剩下的需求點(diǎn) { 17}歸入與之距離最近的未分派車輛的需求點(diǎn)所在的群。計(jì)算需求點(diǎn) { 17}與未分派車輛的需求點(diǎn){11,12,13,14,15,16,18,19,20,23,24,25,26,27,28}的距離為{18.9,17.3,13.3,23.3,31.3,24.6,29.1,8.06,32.5,31,14.2,28.6,21.5,13.6,12.1}，最小為8.06，對應(yīng)需求點(diǎn) { 19}，故把需求點(diǎn) { 17}歸入需求點(diǎn) { 19}對應(yīng)的配送中心3所在的群。 轉(zhuǎn)到步驟 （2）。

用同樣的方法得到配送中心2的車輛X21分派的需求點(diǎn)為 { 12,14,25 }，車輛X22分派的需求點(diǎn)為 { 11 , 13 } ，車輛X23分派的需求點(diǎn)為 { 15 , 20 } ；配送中心3的車輛X31分派的需求點(diǎn)為 { 17,19,24,27,28 } ，車輛X32分派的需求點(diǎn)為{16,18,23,26 } 。所有的群都已經(jīng)分派車輛完畢，轉(zhuǎn)到步驟 （5）。

步驟 （5） 用Dijkstra算法求出每一輛配送車輛的最短行駛路線。

按照以上步驟得到優(yōu)化方案見表2。

表2 車輛調(diào)度優(yōu)化方案

4 結(jié)束語

本文的研究成果可以為物流配送調(diào)度人員提供依據(jù)，從而實(shí)現(xiàn)物流科學(xué)化，對物流企業(yè)降低物流成本、提高服務(wù)質(zhì)量、增加經(jīng)濟(jì)效益有顯著意義。

[1] 張之富.物流配送車輛優(yōu)化調(diào)度研究[D].上海：上海海事大學(xué) （碩士學(xué)位論文），2007.

[2] L.Cooper.Location-Allocation Problem[J].Operations Research，2006,11(3):331-343.

[3] 鄭稱德，黃達(dá).客戶需求驅(qū)動的多層物流網(wǎng)絡(luò)選址規(guī)劃模型與算法[J].系統(tǒng)管理學(xué)報(bào)，2009(2):232-236.

[4] 程賜勝，蒲云虎，吳穎.集成化物流選址—路徑問題優(yōu)化模型的算法研究[J].中南林業(yè)科技大學(xué)學(xué)報(bào) （自然科學(xué)版），2008,28(5):113-118.

[5] 覃運(yùn)梅，王玲玲，郝忠娜.基于改進(jìn)的動態(tài)聚類算法的配送車輛調(diào)度研究[J].合肥工業(yè)大學(xué)學(xué)報(bào) （自然科學(xué)版），2009,32(7):962-965.

[6] 胡運(yùn)權(quán).運(yùn)籌學(xué)教程[M].3版.北京：清華大學(xué)出版社，2007:250-253.

Research on Vehicle Scheduling Model of Multi-source-point Distribution

QIN Yun-mei (Guangxi University of Technology,Liuzhou 545006,China)

According to complexity of the problem,considering the constraint condition of vehicles,the optimal model with the minimization of total cost as the object was established,and the corresponding heuristic algorithm was put forward to solve the model.So the vehicle assignment scheme for delivering goods from numbers of distribution center to all of demand points could obtained in acceptable time.The practical application shows that the model in line with the practical problems and the algorithm is appropriate.Both model and algorithm are of practical value.

multi-source-point;logistics distribution;model;heuristic algorithm

F224

A

1002-3100(2010)09-0032-04

2010-07-23

廣西工學(xué)院青年基金項(xiàng)目，項(xiàng)目編號：院科社1074205。

覃運(yùn)梅（1976－），女，廣西貴港人，廣西工學(xué)院汽車工程系，講師，碩士，研究方向：物流系統(tǒng)優(yōu)化與管理。