物流配送中心選址與路徑問題的模型研究

摘 要:文章分析了物流配送中心的配送模式和傳統的車輛路徑問題，并在前人研究的基礎上建立了基于選址和車輛可重復利用的VRPTW組合模型，即配送中心的LRTWP(Location and Routing with Time Window Problem)模型。該模型縮短了配送距離，節省了費用，提高了速度。

關鍵詞:配送中心 車輛重復利用的VRPTW 模型

中圖分類號:U492.11文獻標志碼:A

文章編號:1004-4914(2010)04-211-02

一、引言

物流配送中心是專門從事配送業務的物流基地，是通過轉運、分類、保管、流通加工和信息處理等作業，根據用戶的訂貨要求備齊商品，并能迅速準確和廉價地進行配送的基本設施。它使得不同地區、不同品種的貨物通過配送中心的調節，按不同需求重新組合，發往收貨人手中。本文將配送中心的合理選址(Location)和車輛路線(Vehicle Routing Problem)的安排結合起來同時考慮，既縮短了配送距離，節省了費用、提高了配送速度，又促進了生產和消費兩種物流活動的有機協調和配合，使整個物流系統處于平衡發展的狀態。

二、L·VRPTW——RV問題的數學模型

1.問題描述。本文所討論的配送模式是生產企業把貨物送到配送中心，通過配送中心的一系列物流功能再把貨物送到其服務區的客戶點上，即找出最優的供應點的位置，同時還要使供應點到各個需求點的運輸費用最少。第一級的貨物運輸，即為生產企業到配送中心的貨物運輸，可以描述為在允許的投資范圍內選擇最佳的配送中心地點，使總成本最小(包括配送中心的建設費用、生產企業和配送中心之間的距離問題)。由于車輛都是滿載，所要解決的實際就是配送中心的選址問題，下一級的貨物運輸是從配送中心到客戶點的運輸。由于在傳統配送中當車輛無法再滿足任何客戶的貨物需求或時間窗限制時，就必須返回倉庫而不能再使用，因此這里考慮更實際的情況即當客戶的需求量較大，車輛在服務了幾個客戶后，剩余載貨量不足以再滿足任何客戶的需求而回到倉庫的情形。在現實中只要車輛回到配送中心補貨后有能力滿足時間窗約束繼續服務客戶，車輛就可以繼續利用。因此，這一級運輸所要解決的就是車輛可重復利用的VRPTW(VRPTW with Re-used Vehicles，VRPTWRV)問題。在該問題中每輛車可能被派出去若干次，存在若干條子路徑，滿足每輛車的每條子路徑上客戶的需求總和不超過其最大負載能力限制，同時每輛車可能離開倉庫、回到倉庫若干次。

將二者綜合在一起就構成了本文所提出的L·VRPTW——RV問題。整個貨物配送過程如圖1所示:

這里在建立模型時為了簡化問題求解難度，在配送中心選址這一級模型中，假定在新物流配送中心建立前不存在已有的配送中心，也就是不考慮新舊物流中心之間的競爭。同時不限制配送中心的能力，其建設費用設為與其服務的客戶需求量呈線性關系。

2.物流配送中心L·VRPTW——RV數學模型。為描述方便首先定義數學符號:

I——潛在的配送中心位置集合;J——客戶點集合，J={J}，j=1，2，…n;

K——車輛集合，K={k}，k=1，2，…m;其中m是使用的車輛數;M——生產企業集合;

G=(N，E)——賦權圖，其中N={0，1，2，…n，n+1}為頂點集，頂點0(出發點)和頂點n+1(返回點)表示配送中心，頂點1，2，…n表示客戶，E為邊集，即連接配送中心與客戶以及客戶之間的邊;

Tij——各頂點間的權值(從頂點i到頂點j的行駛時間，其中i≠j);Qk——車輛k的最大裝載能力;

qj——客戶j的需求;dij——生產企業與配送中心之間的距離(或費用);

Lk——車輛k的子路徑;Nlk——車輛k的第l條子路徑上的頂點集;

Jlk——車輛k的第l條子路徑上的客戶集;Sj——服務客戶j所需的時間，包括固定服務時間s和可變服務時間λqj(λ為權系數)，即Sj=s+λqj，假設配送中心服務時間S0=0，Sn+1=0;

wijk——車輛k從頂點i直接行駛到頂點j，在頂點j的等待時間，其中l+1i≠j;

[a0，b0]——配送中心0的時間窗，(頂點0和n+1的等待時間窗假定相同)也稱行程安排底線，即車輛不能在a0之前離開配送中心，必須在bn+1之前返回;

[aj，bj]——客戶j的時間窗;

Sljk——決策變量，車輛k在第l條子路徑上開始服務頂點j的時間，其中Sl0k表示車輛k在第l條子路徑上離開配送中心的時間;Sn+1，kl表示車輛k在第l條子路徑上回到配送中心的時間;

xijk=1，若點i，j之間存在直接連接且由車輛k服務0，否則

yi=1，若配送中心i被選中0，否則; zij=1，若客戶j分配給配送中心i0，否則;

Gi——建立配送中心i的固定費用;Ulk——子巡回約束的輔助變量;

Pij——生產企業與配送中心之間的流量。

建立的數學模型如下:

目標函數:

minm;(1)

xijk(Slik+Si+Tij-Sljk)≤0 Ai，j∈Nlk，k∈K，l∈Lk;(11)

ai≤Slik≤bi，Ai∈Nlk，k∈K，l∈Lk;(12)

ai≤Slik+Si≤bi，Ai∈Nlk，k∈K，l∈Lk;(13)

Sl+10k=Sln+1，k，Ak∈K，l∈Lk;(14)

xijk={0，1}，Ai，j∈N，k∈K;yi={0，1}，Ai∈I;(15)

Ulk≥0，Al∈J，k∈K;(16)

其中目標⑴是最小化車輛數;目標⑵使三部分之和即配送中心的建設費用、生產企業與配送中心之間的距離(或費用)、車輛行駛費用或時間(包括行駛時間、等待時間和服務時間)最小。約束⑶保證每個客戶點只能被訪問一次;約束⑷車輛容量限制下即每輛車在其每條子路徑上不超過其裝載能力;約束⑸表示子巡回的約束;約束⑹保證每輛車從配送中心0出發;約束⑺保證每輛車到達每個客戶后又離開那個客戶;約束⑻保證每條路線只能包含一個配送中心n+1;約束⑼保證客戶分配給配送中心;約束⑽保證每輛車最后回到配送中心;約束⑾表明前序關系如果車輛k從i直接行駛到j，則其不可能在Slik+Si+Tij之前到達;約束⑿和⒀保證時間窗被滿足;約束⒁保證車輛k在第l條子路徑上回到配送中心的時間等于其在l+1條子路徑上離開倉庫的時間，體現了車輛的重復利用，保證車輛k的運行時間不斷增加;約束⒂是整數約束;約束⒃為中間變量的取值范圍，指路線回路中節點的序號。

三、結論

本文在對傳統的物流中心選址和車輛路徑問題研究的基礎上，將選址問題和物流配送的車輛路徑問題巧妙地結合起來，利用它們各自的特點，同時考慮更為實際的情況，構建了基于選址和車輛可重復利用的VRPTW組合模型。該模型縮短了配送距離，節省了費用，提高了速度，提高了配送效率，促進了生產和消費的協調以及整個物流系統的平穩發展。

參考文獻:

1.Ai-His Wu，Chinyao Low，Jiunn-Wei Bai.Heuristic solutions to multi-depot location-routing problems[J].ComputersOperations Research，2002，(29):1393-1495.

2.J Kennedy，R C Eberhart.Particle swarm optimization[A].Proc IEEE international conference on Networks[C].USA:IEEE Press，1995，4.1942-1948.

3.Y Shi，R C Eberhart.A modified swarm optimizer[A].IEEE International Conference of Evolutionary Computation[C].Anchorage，Alaska:IEEE Press，May，1998.

4.劉佳，秦四平.不確定性決策在配送中心選址方案中的應用研究[J].物流技術，2006(12):52-54

5.吳堅，史忠科.基于遺傳算法的配送中心選址問題[J].華南理工大學學報(自然科學版)，2004，32(6):71-74

6.胡大偉，陳誠.遺傳算法(GA)和禁忌搜索算法(TS)在配送中心選址和路線問題中的應用[J].系統工程理論與實踐，2007(9):171-175

7.張濤，王姍姍，田文馨等.車輛可重復利用VRPTW問題的模型和改進蟻群算法[J].系統工程，2007，25(4):20-26

8.陳森發.復雜系統建模理論與方法[M].南京:東南大學出版社，2005.51-58

9.高自友，孫會君.現代物流與交通運輸系統[M].北京:人民交通出版社，2003.271-283

(作者單位:太原旅游職業學院現代信息技術系 山西太原 030032)(責編:若佳)