馬江浩姚明山,2趙　磊,3朱道立,3（.上海交通大學(xué)中美物流研究院，上海 200030；2.同濟大學(xué)經(jīng)濟與管理學(xué)院，上海 200092；3.上海交通大學(xué)安泰經(jīng)濟與管理學(xué)院，上海 200030）

取貨車輛與卸貨車位集成調(diào)度問題研究

馬江浩1姚明山1,2趙磊1,3朱道立1,3
（1.上海交通大學(xué)中美物流研究院，上海 200030；2.同濟大學(xué)經(jīng)濟與管理學(xué)院，上海 200092；3.上海交通大學(xué)安泰經(jīng)濟與管理學(xué)院，上海 200030）

取貨車輛與卸貨車位集成調(diào)度問題（Vehicle and Dock Synchronized Scheduling Problem, VDSSP）是汽車零部件入廠物流中運輸計劃員面臨的關(guān)鍵問題之一。由于VDSSP是一個復(fù)雜的組合優(yōu)化問題，無論在理論上還是實踐中都難以得到精確最優(yōu)解。本文通過對VDSSP問題特點的分析，建立VDSSP問題的混合整數(shù)規(guī)劃模型，并設(shè)計了一種基于任務(wù)列表的模擬退火算法對該問題進行求解。通過某第三方物流企業(yè)數(shù)據(jù)進行仿真試驗，結(jié)果表明本文設(shè)計的算法可在可控時間內(nèi)得到滿意可行解，有效輔助運輸計劃員制定取貨車輛運輸計劃與卸貨車位分配計劃，為汽車物流企業(yè)的取貨車輛與卸貨車位集成調(diào)度提供決策支持。

車零部件入廠物流；取貨車輛運輸；卸貨車位分配；集成調(diào)度；模擬退火

1　引言

目前學(xué)術(shù)界在汽車零部件入廠物流循環(huán)取貨方面的研究主要集中于取貨路徑計劃,大部分學(xué)者將取貨路徑計劃視為車輛路徑問題(Vehicle Routing Problem, VRP)的一種特殊情況,其主要特點為在VRP問題的基礎(chǔ)上考慮卸貨車位等其他資源約束。Sadjadi等(2009)考慮某汽車制造企業(yè)實際需求來定制優(yōu)化方案,建立循環(huán)取貨VRP的混合整數(shù)模型,并設(shè)計遺傳算法求解。Hosseini等(2014)分析了存在直送、越庫和循環(huán)取貨的運輸問題,建立整數(shù)規(guī)劃模型,并設(shè)計了基于模擬退火算法的和聲搜索(Harmony Search, HS)算法。王旭等(2011)建立汽車零部件循環(huán)取貨模式下具有車輛容積、最大行程和時間窗約束的VRP模型,設(shè)計啟發(fā)式節(jié)約算法求解。汪金蓮等(2009)考慮庫存限制,建立路線規(guī)劃模型,設(shè)計禁忌搜索算法求解。Rieck等(2010)在VRP中增加裝卸貨車位的約束來實現(xiàn)協(xié)調(diào)的貨物流。藺宇等(2015)考慮有限卸貨車位對車輛路徑成本的影響,卸貨時間窗的依據(jù)是車輛到達順序。另一方面,一部分學(xué)者單純就卸貨車位分配問題進行研究。鐘勰(2011)建立入庫多卸貨車位車輛調(diào)度問題數(shù)學(xué)模型,假設(shè)車輛同時到達卸貨車位,用遺傳算法求解。沈飛等(2009)針對多卸貨車位分配問題,以總卸貨時間最小化為目標,建立無時間窗約束的混合整數(shù)模型,并且提出貪婪算法求解車輛卸貨車位訪問順序和卸貨車位服務(wù)車輛順序。而集成考慮取貨車輛調(diào)度和卸貨車位分配的文章相對較少,但取貨車輛調(diào)度和卸貨車位分配的集成考慮是汽車零部件入廠物流實踐中的要求。

在實際業(yè)務(wù)情境中,取貨路徑計劃相對較為獨立,由路線計劃員制定;運輸計劃員需考慮路線計劃員所制定取貨路徑的時間長度、卸貨時間、車型等信息,進而計劃取貨車輛和卸貨車位資源的安排。此外,取貨車輛運輸計劃和卸貨車位分配計劃都需要對取貨路徑的作業(yè)順序進行安排,這兩者安排的取貨路徑的作業(yè)順序必須具有一致性,否則將導(dǎo)致取貨車輛運輸計劃和卸貨車位分配計劃的不協(xié)調(diào),從而影響運輸計劃員安排計劃的可行性。因此,取貨車輛運輸計劃和卸貨車位分配計劃具有緊密的關(guān)聯(lián)性,需要將取貨車輛運輸計劃與卸貨車位分配計劃作為一個整體問題協(xié)調(diào)考慮,而路線計劃與這些資源限制的關(guān)聯(lián)性相對較弱。本文定義協(xié)調(diào)考慮安排取貨車輛運輸計劃和卸貨車位分配計劃的問題為取貨車輛與卸貨車位集成調(diào)度問題(Vehicle and Dock Synchronized Scheduling Problem, VDSSP)。

為了解決上述VDSSP問題,本文提出一套建模與求解方案。文章的結(jié)構(gòu)如下：第二節(jié)描述VDSSP問題,并構(gòu)建混合整數(shù)規(guī)劃模型;第三節(jié)提出求解VDSSP問題的模擬退火求解算法,在可控時間內(nèi)能得到滿意可行解;第四節(jié)通過某第三方物流企業(yè)的仿真數(shù)據(jù)對模型進行測試,并比較直接應(yīng)用商用求解器Gurobi求解和模擬退火算法求解的效果和性能;第五節(jié)是總結(jié)。計算實驗結(jié)果表明,模擬退火算法能更有效地求解VDSSP問題,為汽車物流企業(yè)提供VDSSP問題的決策支持。

2　VDSSP問題描述與數(shù)學(xué)模型

由于第三方物流企業(yè)所考慮的成本主要與使用車輛數(shù)有關(guān),因此本節(jié)研究的VDSSP問題以實現(xiàn)最少車輛使用量為目標,尋找取貨車輛運輸計劃和卸貨車位分配計劃。該問題已知一些既定的取貨路徑集合,其中每一條取貨路徑都具有車型要求和卸貨窗口時間;并有一隊不同車型的取貨車輛和多個具有工作窗口時間的卸貨車位。需要安排出車輛所需執(zhí)行取貨路徑的順序和起止時間,以及卸貨車位卸貨的路徑順序和起止時間。其中任一取貨車輛每完成一條取貨路徑之后必須到卸貨車位進行卸貨。同時,VDSSP問題還需滿足：

(1)每條取貨路徑只能由一輛車執(zhí)行一次;

(2)每條取貨路徑的貨物只在一個卸貨車位卸貨一次;

(3)每條取貨路徑存在卸貨窗口時間約束,即必須在其窗口時間內(nèi)進行卸貨;

(4)每條取貨路徑存在車型限制,即該路徑只能由與之相對應(yīng)車型的車輛執(zhí)行;

(5)每個卸貨車位有工作時間窗限制,即該卸貨車位的可用卸貨時間必須在其工作窗口時間之內(nèi);

(6)時間邏輯約束,即每條取貨路徑任務(wù)開始卸貨時間必須晚于其路徑完成時間。

根據(jù)上述描述,VDSSP問題的集合、參數(shù)和變量定義如下：

R={1,…,n}：取貨路徑集合;

R'={0,…,n+1}：路徑集合,其中0和n+1是虛擬路徑,0為每輛車的起始路徑,n+1為終止路徑,即每輛車的工作必須從0開始,以n+1結(jié)束;

V={1,…,k}：取貨車輛集合;

B={1,…,l}：卸貨車位集合。.

RDi：取貨路徑i的持續(xù)時間,i?R;

RTi：取貨路徑i的車型要求,i?R;

[REi,RLi]：取貨路徑i的卸貨時間窗,i?R;

VTk：取貨車輛k的車型,k?V;

VSk：取貨車輛k的最早出發(fā)時間,k?V;

VRk：取貨車輛k的運行輪次上限,k?V;

BUl：卸貨車位l卸一條路徑所需時間,l?B;

[BEl,BLl]：卸貨車位l的工作時間窗,l?B;

M：一個很大的常數(shù),可取作所有要求時間窗的最大值。

xijk：車輛k(kV)若先執(zhí)行路徑i再執(zhí)行路徑j(luò),則xijk=1,否則xijk=0;

wik：車輛k(kV)開始執(zhí)行取貨路徑i的時間;

yijl：卸貨車位l(lB) 若先完成路徑i再完成路徑j(luò),則yijl=1,否則yijl=0;

vil：卸貨車位l(lB)開始卸貨路徑i的時間。

基于以上集合、參數(shù)和變量,VDSSP問題可用下述混合整數(shù)規(guī)劃模型表示：

式(1)描述該模型的目標函數(shù),即最小化所使用的車輛數(shù)。式(2)-(22)為約束條件,該模型的約束條件主要可分為三類：

2.4.1取貨車輛調(diào)度約束

車輛調(diào)度約束指約束中決策變量只包含xijk和wik。式(2)-(4)表示每輛車從執(zhí)行路徑0開始到路徑n+1 結(jié)束;式(5)表示每個取貨路徑被一輛車完成且僅被完成一次;式(6)表示取貨車輛k若執(zhí)行路徑i,則開始執(zhí)行路徑i的時間不能早于其最早出發(fā)時間,此外該式還約束取貨車輛若不執(zhí)行路徑i,則wik=0;式(7)表示每輛車執(zhí)行路徑的輪次不能超過其上限;式(8)表示執(zhí)行路徑i的車輛車型要與路徑要求的車型一致。

2.4.2卸貨車位調(diào)度約束

卸貨車位調(diào)度約束指約束中決策變量只包含yijl和vil。式(9)-(11)表示每個卸貨車位從卸貨路徑0開始到路徑n+1結(jié)束;式(12)表示每個路徑任務(wù)在一個車位卸貨且僅被卸一次;式(13)表示若卸貨車位先卸貨路徑i再卸貨路徑j(luò),則j的開始時間不能早于i的開始卸貨時間與卸貨持續(xù)時間的和;式(14)表示卸貨車位開始卸路徑i的時間要在卸貨車位的工作時間窗內(nèi),此外該式還約束了若卸貨車位l不卸路徑i,則vil=0;式(15)表示路徑i的開始卸貨的時間在完成取貨的時間窗內(nèi)。

2.4.3耦合約束

耦合約束指約束中決策變量既包含xijk或wik也包含yijl或vil。式(16)表示若某車輛先執(zhí)行路徑i再執(zhí)行路徑j(luò),則j的開始取貨時間不能早于i的開始取貨時間與取貨持續(xù)時間及卸貨持續(xù)時間的和;式(17)表示路徑i開始取貨時間與持續(xù)時間的和等于卸貨車位開始卸貨i的時間,即車輛取貨完畢即開始卸貨。

除了上述三類主要約束之外,其余5個約束描述變量的特殊情況及取值范圍：式(18)表示若i=j,則xijk和yijl為0;式(19)表示0路徑之前沒有其他路徑;式(20)表示從n+1之后不會再執(zhí)行任何路徑;式(21)表示任何xijk和yijl的取值非0即1;式(22)表示開始取貨時間與開始卸貨時間均非負。

3　基于任務(wù)列表的模擬退火算法

上述VDSSP混合整數(shù)規(guī)劃模型同時考慮了取貨車輛、卸貨車位的調(diào)度約束及協(xié)調(diào)要求,完整體現(xiàn)實際問題需求。但由于該模型較為復(fù)雜,屬于NP-hard問題,現(xiàn)有商用軟件很難在可控時間內(nèi)完成實際規(guī)模問題的求解。因此,本節(jié)使用一種基于任務(wù)列表的模擬退火算法,在可控時間內(nèi)得出原問題的可接受可行解。

模擬退火(Simulated Annealing, SA)算法最早由Kirkpatrick等(1983)引入組合優(yōu)化領(lǐng)域。這一算法是一種局部搜索算法,但能以一定概率接受一個劣解,從而有效避免陷入局部最優(yōu)?；谌蝿?wù)列表的模擬退火算法框架如圖1所示。

算法步驟如下：

Step1：初始化參數(shù),設(shè)定初始溫度T=T0;

Step2：隨機生成初始任務(wù)列表R-list,并計算目標函數(shù)f(R-list);

Step3：擾動產(chǎn)生新的任務(wù)列表解R'-list,重新計算目標函數(shù)f(R'-list);

Step4：判斷目標函數(shù)是否更優(yōu),若是則接受新任務(wù)列表與新解,否則按Metropolis準則以一定概率接受新任務(wù)列表與新解;

圖1　模擬退火算法框架圖

Step5：判斷是否達到迭代次數(shù),若是則執(zhí)行Step6,否則執(zhí)行Step3;

Step6：降溫過程,以一定速率進行冷卻退火;

Step7：判斷是否達到終止條件,若是則輸出解,否則執(zhí)行Step3。

根據(jù)已知路徑集合R,隨機生成一組包含1-n的任務(wù)列表R-list。例如當路徑集合有10條路徑時,任務(wù)列表R-list為一包含1-10的列向量[5;7;8;9;2;10;3;6;1;4]。

目標函數(shù)值的變化用于判斷新解的優(yōu)劣,對于最小化問題,目標函數(shù)值降低則表明解更優(yōu)。以使用車輛數(shù)作為目標函數(shù)值,根據(jù)任務(wù)列表計算目標函數(shù)值的流程如下：

0.【卸貨車位工作時間分段】為了使算法更貼現(xiàn)實情況,采用實際運作中卸貨車位調(diào)度方式進行預(yù)處理。即在進行卸貨車位作業(yè)分配之前,首先將卸貨車位工作時間按卸貨一條路徑的時間進行分段。如圖2所示,將卸貨車位工作時間窗[BEl,BLl]分成H個時間段。其中前H-1個時間段長度為BUl,最后一個時間段長度為：

BU*= BLl-BEl-(H-1)·BUl

圖2　卸貨車位卸貨時間段

1.【車型匹配校驗】校驗車輛集合V中空閑且未滿足輪次上限的車輛k與任務(wù)列表R-list中未分配的路徑i所需車型是否匹配。若有滿足上述條件的匹配,則進入2。

2.【最早卸貨時間校驗】計算車輛k最早開始時間與路徑i持續(xù)時間的和是否早于路徑i最早開始卸貨時間。若是則進入3,否則進入4。

3.【卸貨車位卸貨時間窗校驗】根據(jù)第0步預(yù)處理所得卸貨車位卸貨時間段,校驗卸貨車位l空閑卸貨時間段[t(h),t(h+1)]中,時刻t(h)是否在路徑i的卸貨時間窗[max{VS(k)+RD(i),RE(i)},RL(i)]內(nèi)。若校驗成功,則將路徑i分配給取貨車輛k與卸貨車位l,并倒推取貨車輛k出發(fā)時間為t(h)與路徑持續(xù)時間的差,同時將取貨車輛k最早開始時間更新到t(h+1)。若校驗失敗則重選卸貨車位。

4.【最晚卸貨時間校驗】計算車輛k最早開始時間與路徑i持續(xù)時間的和是否早于路徑i最晚開始卸貨時間。若是則進入3,否則重選車輛。

5.【車輛使用量計算】待任務(wù)列表中所有路徑都分配完畢,計算所使用的車輛數(shù)量,得到目標函數(shù)值。

采用隨機置換的方法對當前任務(wù)列表進行擾動,即在當前任務(wù)列表中隨機選兩個位置id-1與id-2,交換兩個位置的路徑任務(wù)R-list(id-1)與R-list(id-2)。例如隨機選擇到3.2中任務(wù)列表的第3位與第6位,置換對應(yīng)位置的路徑任務(wù)后,則新任務(wù)列表變?yōu)閇5;7;10;9;2;8;3;6;1;4]。

對于最小化問題,若Δf＜0,則接受新任務(wù)列表以及所求得的新解;若Δf≥0則采用Metropolis接受準則,即計算接受概率exp(-df/T),若大于(0, 1)之間的隨機數(shù)rand,則同樣接受新任務(wù)列表以及新解;否則保留當前任務(wù)列表以及當前解。

冷卻進度表影響模擬退火算法的性能,其包括初始溫度T0,結(jié)束溫度Tend,冷卻速率r, Mapkob鏈長L?？紤]到算例規(guī)模,所采用的參數(shù)為：T0=1000,Tend=0.001,r=0.95,L=100。參數(shù)設(shè)置可使Metropolis接受概率在高溫狀態(tài)接近1;在低溫時概率接近0。

4　算例實驗

為了驗證所設(shè)計的基于任務(wù)列表的模擬退火算法對VDSSP問題的求解效果,選擇某第三方物流企業(yè)的集貨數(shù)據(jù)進行仿真實驗,并對比商用求解器Gurobi和啟發(fā)式算法的求解效果和性能。

某第三方物流公司負責(zé)為一家汽車制造企業(yè)提供零部件入廠服務(wù)。表1展示了2個卸貨車位卸貨時間和工作時間窗信息。表2是物流公司的車輛信息：假設(shè)現(xiàn)有11輛車,小型車5輛,大型車6輛,其中第10和11輛是備用車;11輛車的最早出發(fā)時間都是300min,車輛運行輪次上限均已知。表3為路徑任務(wù)列表,現(xiàn)有26條取貨路徑任務(wù),每條路徑的車型要求、持續(xù)時間與所需卸貨的時間窗已知。

表1　卸貨車位信息

表2　車輛信息

表3　路徑任務(wù)列表

根據(jù)4.1中的已知數(shù)據(jù),設(shè)置對應(yīng)參數(shù),利用基于任務(wù)列表的模擬退火算法求解。算例求解結(jié)果是需使用9輛車,包括4輛小型車和5輛大型車,兩輛備用車未被使用。取貨車輛運輸計劃與卸貨車位分配計劃的甘特圖如圖3和圖4所示。甘特圖橫軸為時間軸,縱軸表示不同取貨車輛號或卸貨車位號,矩形條表示執(zhí)行任務(wù),矩形條內(nèi)的數(shù)字對應(yīng)路徑任務(wù)的編號。基于任務(wù)列表的模擬退火算法可得到取貨車輛與卸貨車位的集成調(diào)度計劃,同時求得最少車輛數(shù),因此有助于支持物流企業(yè)的車輛配置決策,有助于支持其完成取貨車輛調(diào)度與卸貨車位安排的日常運營計劃。

圖3　取貨車輛運輸計劃甘特圖

圖4　卸貨車位分配計劃甘特圖

首先設(shè)計實驗對比商用求解器Gurobi和本模擬退火算法的求解性能,如表4所示。實驗1,算例是14條路徑任務(wù)時,SA只需42.57秒的運算時間,而Gurobi所需時間是SA的10多倍。實驗2和3,SA在1分鐘左右求出結(jié)果,而Gurobi運算時間已達到實驗設(shè)置的上限。實驗4-6,隨著算例的規(guī)模增大,SA求解耗時也逐漸增加,不過仍可在幾分鐘內(nèi)即到結(jié)果,而Gurobi在規(guī)定時間內(nèi)均無法求解。因此從實驗結(jié)果可知,設(shè)計的啟發(fā)式算法在求解效率上顯著優(yōu)于商用求解器,可以有效提高求解規(guī)模。

其次關(guān)于算法收斂性,基于任務(wù)列表的模擬退火算法求解4.1算例的收斂曲線如圖5所示。由圖可知,模擬退火有一定的概率保留目標值升高的解;但隨著迭代次數(shù)增加,目標值逐漸降低,對于目標值增大的解的保留概率也逐漸降低;當?shù)螖?shù)到達163次時,算法求得的目標值不再波動,達到穩(wěn)定狀態(tài)。

表4　算法求解結(jié)果與時間對比

圖5　模擬退火算法收斂曲線

5　總結(jié)

本文研究了循環(huán)取貨中的取貨車輛與卸貨車位集成調(diào)度問題(VDSSP),以使用車輛最少為目標,建立了取貨車輛與卸貨車位集成調(diào)度問題的混合整數(shù)規(guī)劃模型。為了提高求解效率,提出一種基于任務(wù)列表的模擬退火算法對該問題進行求解,并利用某第三方物流的數(shù)據(jù)進行仿真實驗,實驗結(jié)果表明該算法可有效計算出取貨車輛與卸貨車位集成調(diào)度方案,為汽車物流企業(yè)的取貨車輛與卸貨車位集成調(diào)度提供高效的決策支持。最后與Gurobi求解器進行了對比實驗,結(jié)果表明該基于任務(wù)列表的模擬退火算法具有更強的時間有效性,在可控時間內(nèi)能得到滿意的可行方案。

[1] Sadjadi S J, Jafari M, Amini T. A New Mathematical Modeling and a Genetic Algorithm Search for Milk Run Problem (an Auto Industry Supply Chain Case Study)[J]. The International Journal of Advanced Manufacturing Technology, 2009, 44(1-2): 194-200.

[2] Hosseini S D, Shirazi M A, Karimi B. Cross-docking and Milk Run Logistics in a Consolidation Network: A Hybrid of Harmony Search and Simulated Annealing approach[J]. Journal of Manufacturing Systems, 2014, 33(4): 567-577.

[3] 王旭, 陳棟, 王振鋒. 汽車零部件 Milk-run 車輛調(diào)度優(yōu)化模型和算法[J]. 計算機應(yīng)用, 2011, 31(4): 1125-1128.

[4] 汪金蓮, 蔣祖華. 汽車制造廠零部件入廠物流的循環(huán)取貨路徑規(guī)劃[J]. 上海交通大學(xué)學(xué)報, 2009 (11): 1703-1708.

[5] Rieck J, Zimmermann J. A New Mixed Integer Linear Model for a Rich Vehicle Routing Problem with Docking Constraints[J]. Annals of Operations Research, 2010, 181(1): 337-358.

[6] 藺宇,徐天依.循環(huán)取貨帶有時間窗約束的入庫道口車輛調(diào)度[J].工業(yè)工程與管理,2015,20(1): 28-33.

[7] 鐘勰.循環(huán)取貨模式下入庫道口車輛調(diào)度問題研究[J]. 上海汽車,2011 (3): 54-58.

[8] 沈飛,陳杰,陳峰.循環(huán)取料下的多道口分配問題及算法研究[J].物流技術(shù),2009(9): 46-48.

[9] Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by SimulatedAnnealing[J]. Science, 1983, 220(4598): 671-680.

Research on the Vehicle and Dock Synchronized Scheduling Problem

Ma Jianghao Yao Mingshan Zhao Lei Zhu Daoli

The Vehicle and Dock Synchronized Scheduling Problem (VDSSP) is one of the key problems faced by the automotive inbound logistics transport planners. VDSSP is a complicated combinatorial optimization problem; it is difficult to obtain an optimal solution theoretically or practically. In this paper,a mixed integer programming model is established for VDSSP considering the characteristics of the problem. Moreover, a list-based Simulated Annealing (SA) algorithm isproposed to solve the problem. Furthermore, computational experimentsare conducted based on the simulated data of a third-party logistics enterprise. The numerical results indicate that feasible solutions of VDSSP can be obtained efficiently and effectively via the list-based SA algorithm. The proposed method can be used to support the decision of VDSSP in automobile logistics enterprises.

automotive inbound logistics; vehicle scheduling; dock scheduling; synchronized scheduling; simulated annealing

F252

A

國家自然科學(xué)基金資助項目(71471112)。

馬江浩,上海交通大學(xué)物流工程碩士研究生,研究方向：汽車物流與供應(yīng)鏈;姚明山,同濟大學(xué)管理科學(xué)與工程博士研究生,研究方向：汽車物流與供應(yīng)鏈;趙磊,上海交通大學(xué)管理科學(xué)與工程博士研究生,研究方向：車輛路徑優(yōu)化,物流與供應(yīng)鏈;朱道立,上海交通大學(xué)教授,研究方向：管理決策,物流與供應(yīng)鏈研究。