多配送中心車輛調(diào)度問題的模型與算法研究

1、 doc80 共享資料網(wǎng)多配送中心車輛調(diào)度問題的模型與算法研究郎茂祥北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044 摘 要：在對多配送中心車輛調(diào)度問題進(jìn)行直觀描述的根底上，建立了該問題的數(shù)學(xué)模型。提出了采用距離最近分配法將多配送中心車輛調(diào)度問題分解為多個(gè)單配送中心車輛調(diào)度問題進(jìn)行求解的策略?；谇蠼鈫闻渌椭行能囕v調(diào)度問題的禁忌搜索算法，設(shè)計(jì)了求解多配送中心車輛調(diào)度問題的算法，并進(jìn)行了實(shí)驗(yàn)計(jì)算。計(jì)算結(jié)果說明，用本文設(shè)計(jì)的算法求解多配送中心車輛調(diào)度問題，不僅可以取得很好的計(jì)算結(jié)果，而且算法的計(jì)算效率較高，收斂速度較快，計(jì)算結(jié)果也較穩(wěn)定。 關(guān)鍵詞：多配送中心車輛調(diào)度問題；模型；算法 Study on

2、 the Model and Algorithm for Multi-depot Vehicle Scheduling ProblemLANG Mao-xiangSchool of Traffic and Transportation，Beijing Jiaotong University，Beijing 100044，ChinaAbstract： On the basis of describing the multi-depot vehicle scheduling problem naturally, the model of the problem is built in this p

3、aper. The solving tactics of dividing a multi-depot vehicle scheduling problem into several single-depot vehicle scheduling problems by using the minimum distance distribution method is presented. The algorithm for the multi-depot vehicle scheduling problem is designed based on the tabu search algor

4、ithm for single-depot vehicle scheduling problem. The computational results demonstrates that the high quality solutions to the multi-depot vehicle scheduling problem can be obtained by using the new algorithm and the algorithm is also efficient and robust. Keywords：multi-depot vehicle scheduling pr

5、oblem; model; algorithm1 引言配送是現(xiàn)代化物流系統(tǒng)的一個(gè)重要環(huán)節(jié)，它是指按用戶的訂貨要求，在配送中心進(jìn)行分貨、配貨，并將配好的貨物及時(shí)送交收貨人。在配送業(yè)務(wù)中，存在許多優(yōu)化決策問題，其中配送車輛調(diào)度問題對配送企業(yè)加快配送速度、提高效勞質(zhì)量、降低配送本錢的影響較大。根據(jù)配送中心數(shù)目的多少，配送車輛調(diào)度問題有單配送中心車輛調(diào)度問題和多配送中心車輛調(diào)度問題之分。在城市物流體系中，往往存在多個(gè)配送中心。因此，對多配送中心車輛調(diào)度問題的研究具有重要的現(xiàn)實(shí)意義?，F(xiàn)有對配送車輛調(diào)度問題的研究主要集中在單配送中心問題上，對多配送中心車輛調(diào)度問題的研究很少，國內(nèi)對該問題的研究根本上是空白

6、。國外的Renaud、Desaulniers、Wu、Kazaz、Sumichrast、Irnich等專家對多配送中心車輛調(diào)度問題進(jìn)行了研究1-6，并取得了一些有價(jià)值的研究成果。本文在現(xiàn)有研究成果的根底上，建立了多配送中心車輛調(diào)度問題的基于直觀描述的數(shù)學(xué)模型，提出了采用距離最近分配法將多配送中心車輛調(diào)度問題分解為多個(gè)單配送中心車輛調(diào)度問題進(jìn)行求解的策略，利用求解單配送中心車輛調(diào)度問題的禁忌搜索算法，設(shè)計(jì)了求解多配送中心車輛調(diào)度問題的算法，最后通過實(shí)驗(yàn)計(jì)算驗(yàn)證了該算法的良好性能。2 多配送中心車輛調(diào)度問題的數(shù)學(xué)模型多配送中心車輛調(diào)度問題可以描述為：從多個(gè)配送中心用多臺(tái)車輛向多個(gè)客戶送貨，每個(gè)配送中

7、心的位置一定，每個(gè)客戶的位置和需求量一定，每臺(tái)車輛的載重量一定，其一次配送的最大行駛距離一定，配送中心供給的貨物，能夠滿足所有客戶的需求，要求合理安排車輛配送路線，使目標(biāo)函數(shù)得到優(yōu)化，并滿足以下條件：1每條配送路徑上各客戶的需求量之和不超過車輛的載重量；2每條配送路徑的長度不超過車輛一次配送的最大行駛距離；3每個(gè)客戶的需求必須滿足，且只能由一臺(tái)車輛送貨。設(shè)某城市中有H個(gè)配送中心，要給M個(gè)客戶送貨，每個(gè)配送中心效勞的客戶構(gòu)成一個(gè)配送分區(qū)。設(shè)第h個(gè)配送中心要向h=1，2，···，H個(gè)客戶送貨，第h個(gè)配送中心有Kh臺(tái)配送車輛，每臺(tái)車輛的載重量為Qhkk=1，2，

8、3;··，Kh，其一次配送的最大行駛距離為Dhk。第h個(gè)配送中心效勞的第i個(gè)客戶的貨物需求量為qhii=1，2，···，客戶i到j(luò)的運(yùn)距為diji，j=1，2，···，該配送中心到第j個(gè)客戶的距離為dhjh=1，2，···，H；j=1，2，···，再設(shè)nhk為第h個(gè)配送中心中第k臺(tái)車輛配送的客戶數(shù)nhk=0表示未使用第k臺(tái)車輛，用集合Rhk表示第h個(gè)區(qū)域中的第k條路徑，其中的第i個(gè)元素rhki表示客戶rhki在第h個(gè)區(qū)域中的路徑k中的順序?yàn)閕不包括配送中心

9、，令rhk0=0表示配送中心，假設(shè)以配送總里程最短為目標(biāo)函數(shù)，那么可建立如下多配送中心車輛調(diào)度問題的數(shù)學(xué)模型： 1s.t. 2 3 4 5 6 7 8 9上述模型中，1式為目標(biāo)函數(shù)，即要求配送總里程即各條配送路徑的長度之和最短；2式保證每條路徑上各客戶的貨物需求量之和不超過車輛的載重量；3式保證每條配送路徑的長度不超過車輛一次配送的最大行駛距離；4式說明某配送分區(qū)每條路徑上的客戶數(shù)不超過該分區(qū)的總客戶數(shù)；5式說明某配送分區(qū)各條配送路徑上的客戶數(shù)之和等于該分區(qū)的總客戶數(shù)；6式說明每個(gè)客戶都得到配送效勞；7式表示每條路徑的客戶的組成；8式限制每個(gè)客戶僅能由一臺(tái)車輛送貨；9式表示當(dāng)區(qū)域h中第k輛車效

10、勞的客戶數(shù)1時(shí)，說明該臺(tái)車參加了配送，那么取sign(nhk)=1，當(dāng)?shù)趉輛車效勞的客戶數(shù)<1時(shí)，表示未使用該臺(tái)車輛，因此取sign(nhk)=0。 上述多配送中心車輛調(diào)度問題的基于直觀描述的數(shù)學(xué)模型與相關(guān)研究文獻(xiàn)中基于網(wǎng)絡(luò)圖的模型相比，具有以下特點(diǎn)：考慮的目標(biāo)函數(shù)和約束條件較為全面和接近實(shí)際；決策變量、目標(biāo)函數(shù)和約束條件的表示較為自然、直觀和易于理解；便于設(shè)計(jì)求解算法和用計(jì)算機(jī)編程求解。3 多配送中心車輛調(diào)度問題的求解策略和算法由于多配送中心車輛調(diào)度問題涉及面廣、影響因素眾多，為了求解方便，需要將問題做適當(dāng)簡化。為此，本文提出將一個(gè)多配送中心車輛調(diào)度問題轉(zhuǎn)化成多個(gè)單配送中心車輛調(diào)度問題

11、進(jìn)行求解的策略。在將多配送中心車輛調(diào)度問題轉(zhuǎn)化成多個(gè)單配送中心車輛調(diào)度問題時(shí)，決定每個(gè)配送中心效勞的具體客戶是問題的關(guān)鍵。本文根據(jù)以下距離最近分配方法確定為某客戶提供效勞的配送中心：計(jì)算某客戶與各配送中心的距離，該客戶離哪個(gè)配送中心最近，就將其分配給哪個(gè)配送中心。設(shè)表示第i個(gè)客戶到第h個(gè)配送中心的距離，選擇，并將該客戶分配給配送中心m。得到為每個(gè)客戶效勞的配送中心后，也就得到了每個(gè)配送中心效勞的具體客戶。作者曾在文獻(xiàn)7中對單配送中心車輛調(diào)度問題的求解算法進(jìn)行了研究，結(jié)論是禁忌搜索算法的效果較優(yōu)。因此，本文在對由多配送中心車輛調(diào)度問題轉(zhuǎn)化成的單配送中心車輛調(diào)度問題進(jìn)行求解時(shí)也采用禁忌搜索算法。

12、根據(jù)上述多配送中心車輛調(diào)度問題的求解策略，參考文獻(xiàn)7、8中求解單配送中心車輛調(diào)度問題的禁忌搜索算法，作者設(shè)計(jì)了求解多配送中心車輛調(diào)度問題的算法見算法1。算法1 多配送中心車輛調(diào)度問題的求解算法 輸入無時(shí)限多配送中心車輛調(diào)度問題的條件； 輸入算法的運(yùn)行參數(shù)，包括終止迭代步數(shù)T，每次迭代搜索當(dāng)前解的鄰居的個(gè)數(shù)N，禁忌長度l，對不可行路徑的懲罰權(quán)重Pw等； for(i=1; i<=M; i+) /i為客戶編號 D=很大的數(shù);num=0; for(h=1; h<=H; h+) /h為配送中心編號 計(jì)算dih; /dih為客戶i到配送中心h的距離 if (dih<D) D= dih;n

13、um=h;將客戶i劃分給配送中心num; /實(shí)現(xiàn)多配送中心問題向單配送中心問題的轉(zhuǎn)化for(h=1;h<=H;h+) /求解單配送中心車輛調(diào)度問題 導(dǎo)入配送中心h及其效勞的客戶的位置、需求量信息、車輛信息；初始化禁忌表H； 隨機(jī)產(chǎn)生一個(gè)初始解S作為當(dāng)前解，迭代步數(shù)t=0； 利用解的評價(jià)方法計(jì)算S的評價(jià)值； 當(dāng)前最好解Sbest=S； 當(dāng)前最好解的評價(jià)值Ebest=S的評價(jià)值； whilet<終止迭代步數(shù)Tdo 本次迭代已搜索鄰居的個(gè)數(shù)n=0； 對本次迭代的最好解的評價(jià)值Elocalbest賦一個(gè)很大的正數(shù)； whilen<Ndo 對S用兩交換法實(shí)施鄰域操作，得S的一個(gè)鄰居S；

14、 ifS不是禁忌表H中的元素 利用解的評價(jià)方法計(jì)算解S的評價(jià)值； ifS的評價(jià)值< Elocalbest Slocalbest =S； Elocalbest=S的評價(jià)值； n=n+1； ifElocalbest < Ebest Sbest= Slocalbest； Ebest= Elocalbest； S= Slocalbest； 將禁忌表中的第一個(gè)元素解禁，將Slocalbest放在禁忌表中，作為禁忌表中的最后一個(gè)元素； t=t+1； 導(dǎo)出Sbest對應(yīng)的配送路徑方案及其目標(biāo)函數(shù)值； 輸出多配送中心車輛調(diào)度問題的計(jì)算結(jié)果；4 實(shí)驗(yàn)計(jì)算和結(jié)果分析 作者利用算法1，通過編制C語言程序

15、對一個(gè)由計(jì)算機(jī)隨機(jī)產(chǎn)生的多配送中心車輛調(diào)度問題問題見例1進(jìn)行了實(shí)驗(yàn)計(jì)算。例1：設(shè)3個(gè)配送中心和30個(gè)客戶分布在一個(gè)邊長為20km的正方形地域內(nèi)，每個(gè)客戶的貨物需求量都在2t及其以下，每個(gè)配送中心有4臺(tái)車輛，車輛的載重量均為10t，車輛一次配送的最大行駛距離均為50km。作者利用計(jì)算機(jī)隨機(jī)產(chǎn)生了配送中心和30個(gè)客戶的位置坐標(biāo)以及各客戶的貨物需求量，其中3個(gè)配送中心的坐標(biāo)分別為：配送中心，、配送中心，、配送中心，30個(gè)客戶的坐標(biāo)及其貨物需求量見表1。要求合理安排配送車輛的行車路線，使配送總里程最短。為簡便起見，本文設(shè)各客戶相互之間及配送中心與客戶之間的距離均采用直線距離，該距離可根據(jù)客戶和配送中心

16、的坐標(biāo)計(jì)算得到。利用距離最近分配方法，通過程序計(jì)算得到如下的分區(qū)結(jié)果：1配送中心為6個(gè)客戶效勞，客戶編號分別為：3、5、11、18、25、26；2配送中心為10個(gè)客戶效勞，客戶編號分別為：1、4、6、7、9、10、12、15、28、29；3配送中心為14個(gè)客戶效勞，客戶編號分別為：2，8，13，14，16，17，19，20，21，22，23，24，27，30。使用禁忌搜索算法分別對三個(gè)配送分區(qū)構(gòu)成的單配送中心車輛調(diào)度問題隨機(jī)求解10次，得到的最好解分別是：第一分區(qū)：使用1臺(tái)車輛，對應(yīng)的配送路徑為配送中心1131826525配送中心，其配送路徑長度為。第二分區(qū)：使用2臺(tái)車輛，對應(yīng)的兩條配送路線分

17、別為：配送中心912615428配送中心和配送中心291041配送中心，配送路徑總長度為。第三分區(qū)：使用2臺(tái)車輛，對應(yīng)的兩條配送路線分別是：配送中心19142221816172520配送中心和配送中心242721323配送中心；配送路徑總長度為。 表1 例1的條件表客戶編號12345678910橫坐標(biāo)x (km)縱坐標(biāo)y (km)貨物需求量q (t)客戶編號11121314151617181920橫坐標(biāo)x (km)縱坐標(biāo)y (km)貨物需求量q (t)客戶編號21222324252627282930橫坐標(biāo)x (km)縱坐標(biāo)y (km)貨物需求量q (t)將上述三個(gè)配送分區(qū)的質(zhì)量最高的解進(jìn)行合并

18、，即可得該多配送中心車輛調(diào)度問題的解，該解對應(yīng)的配送方案共使用了5輛車，5條配送路線的路徑總長度為。可見，利用本文設(shè)計(jì)的算法求解多配送中心車輛調(diào)度問題，可以得到很好的計(jì)算結(jié)果。5 結(jié)論1論文在對多配送中心車輛調(diào)度問題進(jìn)行描述的根底上，建立了該問題的基于直觀描述的數(shù)學(xué)模型，該模型考慮了較為接近實(shí)際的約束條件，具有簡單、直觀、易于理解、易于設(shè)計(jì)算法求解等優(yōu)點(diǎn)。2論文提出了多配送中心車輛調(diào)度問題的求解策略，即利用距離最近分配方法劃定每個(gè)配送中心效勞的客戶，進(jìn)而將一個(gè)多配送中心車輛調(diào)度問題轉(zhuǎn)化成多個(gè)單配送中心車輛調(diào)度問題進(jìn)行求解。3論文設(shè)計(jì)并實(shí)現(xiàn)了多配送中心車輛調(diào)度問題的求解算法，并通過實(shí)驗(yàn)計(jì)算證明了

19、該算法的良好性能。參考文獻(xiàn)1 Renaud J, Laporte G, Boctor F F. A tabu search heuristic for the multi-depot vehicle routing problemJ. Computers Ops Res, Vol.23, No.3, pp229-235, 1996.2 Desaulniers G, Lavigne J, Soumis F. Multi-depot vehicle scheduling problems with time windows and waiting costsJ. European Journal of Operational Research, 111(1998)479-494.3 Wu T H, Low C, Bai J W. Heuristic solutions to multi-depot location-routing problemsJ. Com