動(dòng)態(tài)車(chē)輛路徑優(yōu)化問(wèn)題

現(xiàn)代物流問(wèn)題的眾多研究中，車(chē)輛路徑問(wèn)題一直是焦點(diǎn)問(wèn)題。車(chē)輛路徑優(yōu)化后的配送作業(yè)不僅可以降低物流配送企業(yè)的物質(zhì)消耗、節(jié)約成本，還可以提高客戶的滿意度和服務(wù)水平，最終提高企業(yè)的市場(chǎng)競(jìng)爭(zhēng)力。該文在分析客觀世界動(dòng)態(tài)需求特征的基礎(chǔ)上，對(duì)動(dòng)態(tài)車(chē)輛路徑問(wèn)題進(jìn)行分析，并基于時(shí)刻表建立動(dòng)態(tài)車(chē)輛路徑問(wèn)題優(yōu)化模型。

1引言

隨著信息技術(shù)的發(fā)展，物流已從傳統(tǒng)的運(yùn)輸服務(wù)發(fā)展成為以信息技術(shù)和管理為核心的綜合物流系統(tǒng)。據(jù)統(tǒng)計(jì)，物流成本占產(chǎn)品銷(xiāo)售價(jià)格的75%左右。其中，運(yùn)輸成本在整個(gè)物流成本中占有相當(dāng)大的比例。因此，對(duì)物流配送車(chē)輛調(diào)度進(jìn)行優(yōu)化成為企業(yè)尤為關(guān)注的焦點(diǎn)。

以往對(duì)物流配送和車(chē)輛調(diào)度的研究當(dāng)中，傳統(tǒng)的做法依據(jù)靜態(tài)配送車(chē)輛優(yōu)化調(diào)度理論。但客觀世界存在著大量的不確定性，需要一種可以求解動(dòng)態(tài)車(chē)輛路徑優(yōu)化問(wèn)題的方法。

2 動(dòng)態(tài)車(chē)輛路徑問(wèn)題的相關(guān)理論

動(dòng)態(tài)車(chē)輛路徑問(wèn)題的提出。車(chē)輛路徑問(wèn)題是物流管理當(dāng)中最為典型的問(wèn)題，1959年由Dantzig 和 Ramser[2]提出之后立即引起了很大反響。理論上講，車(chē)輛路徑問(wèn)題屬于組合優(yōu)化問(wèn)題，其對(duì)應(yīng)的優(yōu)化目標(biāo)是在滿足基本約束條件的前提下，使得配送貨物的車(chē)輛的行駛總里程、使用的配送車(chē)輛數(shù)量、行駛時(shí)間的組合達(dá)到最小。

動(dòng)態(tài)車(chē)輛路徑問(wèn)題的定義。靜態(tài)車(chē)輛路徑問(wèn)題中，在對(duì)物流配送路徑進(jìn)行優(yōu)化之前的相關(guān)信息（客戶、車(chē)輛、客戶請(qǐng)求、調(diào)度及其他相關(guān)信息等）是已知且固定的；而動(dòng)態(tài)車(chē)輛路徑優(yōu)化問(wèn)題中的很多信息都是不確定且不可預(yù)知的，可能還會(huì)有部分信息是模糊的、隨機(jī)的，在進(jìn)行路徑規(guī)劃時(shí)要根據(jù)實(shí)時(shí)信息對(duì)車(chē)輛路徑進(jìn)行實(shí)時(shí)的規(guī)劃調(diào)整和優(yōu)化。

3 動(dòng)態(tài)車(chē)輛路徑問(wèn)題模型

動(dòng)態(tài)需求特征分析。車(chē)輛在配送的路程當(dāng)中存在著大量的不確定性：如擁堵、惡劣天氣、車(chē)輛故障、客戶信息改變等，這都將直接影響配送車(chē)輛行駛時(shí)間或者速度的變化，導(dǎo)致等待甚至改變路線，進(jìn)而造成車(chē)輛的調(diào)度成本的增加。這些不確定使優(yōu)化調(diào)度變得復(fù)雜，但當(dāng)信息一旦明確已知，就可以把動(dòng)態(tài)車(chē)輛調(diào)度問(wèn)題轉(zhuǎn)化為靜態(tài)車(chē)輛調(diào)度問(wèn)題來(lái)求解。

為了充分研究動(dòng)態(tài)車(chē)輛調(diào)度問(wèn)題的動(dòng)態(tài)性特性，這里引入兩個(gè)概念：關(guān)鍵點(diǎn)和時(shí)刻表。關(guān)鍵點(diǎn)是指在某個(gè)特定的時(shí)刻正在客戶點(diǎn)進(jìn)行服務(wù)或者正在前往客戶需求點(diǎn)服務(wù)的配送車(chē)輛，每條配送行駛路線最多只有一個(gè)關(guān)鍵點(diǎn)。對(duì)已經(jīng)服務(wù)過(guò)的客戶需求點(diǎn)暫不考慮，而關(guān)鍵點(diǎn)之后的未服務(wù)的客戶需求點(diǎn)稱為未分配點(diǎn)，在接收到新的請(qǐng)求信息，或者配送車(chē)輛路況發(fā)生改變時(shí)，應(yīng)該首先及時(shí)、明確地知道當(dāng)前關(guān)鍵點(diǎn)以及未分配點(diǎn)的信息。

下圖（圖1）通過(guò)一個(gè)簡(jiǎn)單的實(shí)例清晰地展示了動(dòng)態(tài)車(chē)輛路徑問(wèn)題的相關(guān)特性。

圖1 時(shí)刻表和關(guān)鍵點(diǎn)示例圖

按照車(chē)輛的位置狀態(tài)，可以將所有客戶需求點(diǎn)的信息大致分為四類(lèi)：預(yù)先安排已經(jīng)完成服務(wù)的、正在進(jìn)行服務(wù)或正在前往服務(wù)的路上，預(yù)先安排未進(jìn)行服務(wù)的以及新的客戶請(qǐng)求。對(duì)于預(yù)先安排并已經(jīng)完成服務(wù)的客戶點(diǎn)我們不再考慮。如圖1所示，時(shí)刻1的點(diǎn)1、2、4、5為正在進(jìn)行服務(wù)的客戶需求點(diǎn)或者車(chē)輛正在前往服務(wù)客戶需求點(diǎn)的路上，這些點(diǎn)就是所謂的關(guān)鍵點(diǎn)，此時(shí)，車(chē)輛處于工作狀態(tài)中，該資源已經(jīng)被占用。在時(shí)刻2，圖1右邊的點(diǎn)3、6為關(guān)鍵點(diǎn)。此時(shí)，新的需求點(diǎn)7也是我們考慮的。

基于時(shí)刻表的動(dòng)態(tài)車(chē)輛路徑問(wèn)題模型。動(dòng)態(tài)車(chē)輛路徑問(wèn)題的模型是建立在規(guī)定的工作時(shí)間內(nèi)（即調(diào)度周期）的，而該模型選擇以每天的工作時(shí)間為時(shí)刻表，新的客戶請(qǐng)求產(chǎn)生的時(shí)刻，動(dòng)態(tài)車(chē)輛路徑問(wèn)題都會(huì)面對(duì)一個(gè)新的情況，當(dāng)新的請(qǐng)求信息明確時(shí)，動(dòng)態(tài)的調(diào)度問(wèn)題即轉(zhuǎn)變?yōu)殪o態(tài)。其中在確定的時(shí)刻 ，明確該時(shí)刻下的關(guān)鍵點(diǎn)以及該時(shí)刻之后的已經(jīng)預(yù)先安排但還未進(jìn)行服務(wù)的客戶點(diǎn)是很重要的。關(guān)鍵點(diǎn)的個(gè)數(shù)等于處于工作狀態(tài)中的配送車(chē)輛的數(shù)目，其判斷方法如下：（其中， 是車(chē)輛在客戶點(diǎn) 的服務(wù)時(shí)間）

1設(shè)車(chē)輛到達(dá)客戶需求點(diǎn) 的時(shí)間為 ，先找滿足 的點(diǎn)，若有，則點(diǎn) 即為線路的關(guān)鍵點(diǎn)，且完成關(guān)鍵點(diǎn)任務(wù)后的可用時(shí)間為 ；否則轉(zhuǎn)下一步；

2 對(duì)于該線路中所有連接的點(diǎn)對(duì) ，尋找 的點(diǎn)，客戶需求點(diǎn) 即為該條線路的關(guān)鍵點(diǎn)，且車(chē)輛 的可用時(shí)間為 。

表1 動(dòng)態(tài)車(chē)輛路徑問(wèn)題需求點(diǎn)參數(shù)設(shè)置的符號(hào)表

車(chē)場(chǎng)

車(chē)輛 ，服務(wù)的客戶點(diǎn)數(shù)

時(shí)刻 ，關(guān)鍵點(diǎn)的集合

時(shí)刻 ，未完成任務(wù)點(diǎn)和新需求點(diǎn)的集合

時(shí)刻 ，所有關(guān)鍵點(diǎn)及中心車(chē)場(chǎng)的集合

時(shí)刻 ，所有未完成任務(wù)點(diǎn)、新需求點(diǎn)和中心車(chē)場(chǎng)的集合

時(shí)刻 ，所有關(guān)鍵點(diǎn)、未完成任務(wù)點(diǎn)以及新需求點(diǎn)的集合

時(shí)刻 ，所有關(guān)鍵點(diǎn)、中心車(chē)場(chǎng)、未完成任務(wù)點(diǎn)和新需求點(diǎn)集合

表2 參數(shù)以及相關(guān)變量表

車(chē)輛數(shù)

車(chē)輛的最大載重量

時(shí)刻，車(chē)輛 的累積載重量（包括關(guān)鍵點(diǎn)），如果車(chē)輛還在車(chē)場(chǎng)，則值為0

客戶點(diǎn) 的需求量

車(chē)輛從客戶點(diǎn) 到客戶點(diǎn) 的行駛時(shí)間

客戶點(diǎn) 最早開(kāi)始接受服務(wù)時(shí)間

客戶點(diǎn) 最晚開(kāi)始接受服務(wù)時(shí)間

在客戶點(diǎn) 的服務(wù)時(shí)間

車(chē)輛單位時(shí)間行駛成本

車(chē)輛在 之前到達(dá)客戶點(diǎn) 等待的單位時(shí)間成本

車(chē)輛在 之后到達(dá)客戶點(diǎn) 懲罰的單位時(shí)間成本

車(chē)輛到達(dá)客戶點(diǎn) 的時(shí)刻，其中 表示最晚一輛車(chē)返回車(chē)場(chǎng)0的時(shí)刻， 表示客戶點(diǎn) 到達(dá)車(chē)場(chǎng)的時(shí)刻。

1表示客戶點(diǎn) 的任務(wù)由車(chē)輛 來(lái)完成

0表示為其它

1表示車(chē)輛 從客戶點(diǎn) 行駛到客戶點(diǎn)

0表示為其它

該問(wèn)題的總支出成本包括固定發(fā)車(chē)成本、車(chē)輛行駛時(shí)間成本、等待時(shí)間機(jī)會(huì)成本、客戶懲罰成本，問(wèn)題要求是總成本最小。當(dāng)車(chē)輛接受任務(wù)進(jìn)行配送，固定發(fā)車(chē)成本必定發(fā)生，因此模型中暫不考慮。

（1）車(chē)輛行駛時(shí)間成本

以往的研究中大多以距離來(lái)計(jì)算配送成本，而現(xiàn)實(shí)中配送成本還有很多其他影響因素，即使從A點(diǎn)到B點(diǎn)距離很近，但是車(chē)輛行駛的時(shí)間可能會(huì)由于車(chē)流量、路況等因素的影響而產(chǎn)生延遲，因此本文根據(jù)經(jīng)驗(yàn)得出各個(gè)客戶需求點(diǎn)之間以及客戶需求點(diǎn)與車(chē)場(chǎng)之間的行駛時(shí)間和單位時(shí)間的配送成本，具體可以表示為：

，其中 表示單位時(shí)間的配送成本。

（2）等待時(shí)間機(jī)會(huì)成本

車(chē)輛配送中可能會(huì)沒(méi)有在客戶規(guī)定的時(shí)間窗內(nèi)到達(dá)客戶點(diǎn)進(jìn)行服務(wù)，如果車(chē)輛提前到達(dá)客戶點(diǎn) （ ），該文原載于中國(guó)社會(huì)科學(xué)院文獻(xiàn)信息中心主辦的《環(huán)球市場(chǎng)信息導(dǎo)報(bào)》雜志http：//www.ems86.com總第522期2013年第39期-----轉(zhuǎn)載須注名來(lái)源需要等待時(shí)間窗到了之后才能開(kāi)始服務(wù)，因此而產(chǎn)生的時(shí)間機(jī)會(huì)成本，具體可以表示為：

，其中 表示單位時(shí)間的機(jī)會(huì)成本。

（3）客戶懲罰時(shí)間成本

如果車(chē)輛超出客戶規(guī)定的時(shí)間窗到達(dá)客戶點(diǎn)，會(huì)因?yàn)樗拓浀臏?zhǔn)時(shí)性和時(shí)效性影響到客戶的滿意程度，即車(chē)輛晚到客戶點(diǎn) （ ），產(chǎn)生所謂的懲罰成本（即客戶等待車(chē)輛的成本），用下面公式表示為：

， 表示單位時(shí)間的客戶懲罰成本。

由以上分析我們可以將模型表示為：

（3-1）

（3-2）

（3-3）

（3-4）

（3-5）

（3-6）

（3-7）

（3-8）

（3-9）

（3-10）

該模型中，目標(biāo)函數(shù)（3-1）表示總運(yùn)輸成本最小，其中總運(yùn)輸成本 由三項(xiàng)成本構(gòu)成：第一項(xiàng)表示車(chē)輛在各地點(diǎn)間行駛所產(chǎn)生的線路成本，主要為燃料費(fèi)用，其值與車(chē)輛行駛的時(shí)間成正比；第二項(xiàng)表示如果車(chē)輛提前到達(dá)客戶點(diǎn) （ ），需要等待時(shí)間窗到了之后才能開(kāi)始服務(wù)，因此而產(chǎn)生的時(shí)間機(jī)會(huì)成本；第三項(xiàng)表示如果車(chē)輛晚到客戶點(diǎn) （ ），這樣會(huì)影響送貨的及時(shí)性和準(zhǔn)時(shí)性，影響客戶的滿意度，從而產(chǎn)生所謂的懲罰成本（即客戶等待車(chē)輛的成本）。這三項(xiàng)的單位成本分別為 。其中第一項(xiàng)的單位成本 比較容易通過(guò)計(jì)算獲得，而第二項(xiàng)的單位成本和第三項(xiàng)的單位成本 則主要根據(jù)企業(yè)情況，通過(guò)人工經(jīng)驗(yàn)制定，或通過(guò)不斷試算從而得到一個(gè)符合本企業(yè)實(shí)際的值。

式（3-2）車(chē)容量的限制，即每輛車(chē)在t時(shí)刻之后要服務(wù)的客戶的總的需求量不能超過(guò)該車(chē)輛的車(chē)容量減去已經(jīng)服務(wù)過(guò)的客戶需求量的差值；

式（3-3）客戶需求點(diǎn)與車(chē)輛的對(duì)應(yīng)關(guān)系，每個(gè)客戶需求點(diǎn)有且僅有一輛車(chē)為其服務(wù)；

式（3-4）為平衡式，到達(dá)客戶點(diǎn)提供服務(wù)的車(chē)輛在服務(wù)結(jié)束之后一定會(huì)從該點(diǎn)離開(kāi)，其值為1或0，即車(chē)輛或不訪問(wèn)該點(diǎn)，或訪問(wèn)一次；

式（3-5）為刪除構(gòu)成不完整配送路徑的解，約束配送的車(chē)輛在任何一個(gè)客戶需求點(diǎn)的子集中不形成回路。

式（3-6）相鄰客戶需求點(diǎn)間的時(shí)間約束，即當(dāng)車(chē)輛 對(duì)客戶點(diǎn) 服務(wù)結(jié)束后服務(wù)客戶需求點(diǎn) 時(shí)，則車(chē)輛到達(dá)客戶點(diǎn) 的時(shí)間等于開(kāi)始服務(wù)客戶點(diǎn) 的服務(wù)時(shí)間加上從客戶點(diǎn) 到客戶點(diǎn) 路上的行駛時(shí)間；

式（3-7）配送服務(wù)的車(chē)輛從配送中心的出發(fā)時(shí)間必須在配送中心工作時(shí)間窗開(kāi)始后；

式（3-8）最晚的配送車(chē)輛須在配送中心關(guān)閉前返回，該車(chē)輛可以晚于時(shí)間窗到達(dá)各客戶需求點(diǎn)；

式（3-9）、（3-10）為0、1決策變量。

工作時(shí)間內(nèi)，不同時(shí)刻的新客戶請(qǐng)求的加入，可以在時(shí)刻表的基礎(chǔ)上建立動(dòng)態(tài)車(chē)輛調(diào)度問(wèn)題模型，其中初始時(shí)刻的模型和傳統(tǒng)靜態(tài)模型一樣，配送中心是關(guān)鍵點(diǎn)，而所有初始需求構(gòu)成了未完成任務(wù)集合，此時(shí)的解是初始調(diào)度解。

4 總結(jié)

出于對(duì)實(shí)際應(yīng)用中各種不確定性的考慮，本文討論了在調(diào)度決策執(zhí)行過(guò)程中新的客戶需求不斷產(chǎn)生的環(huán)境下的動(dòng)態(tài)車(chē)輛路徑問(wèn)題，對(duì)預(yù)先的客戶請(qǐng)求進(jìn)行預(yù)先安排和優(yōu)化，并對(duì)新的客戶請(qǐng)求進(jìn)行實(shí)時(shí)處理，把接收到的動(dòng)態(tài)信息在信息明確的情況下轉(zhuǎn)化為靜態(tài)車(chē)輛路徑優(yōu)化問(wèn)題，并在傳統(tǒng)靜態(tài)車(chē)輛調(diào)度問(wèn)題的基礎(chǔ)上，以成本最小化為最終目標(biāo)，建立了基于時(shí)刻表的動(dòng)態(tài)車(chē)輛調(diào)度模型。

可以應(yīng)用到商品貨物以及郵件的速運(yùn)、公交車(chē)以及出租車(chē)的服務(wù)、零售業(yè)的配送、生產(chǎn)計(jì)劃以及緊急服務(wù)等各個(gè)領(lǐng)域。因其廣泛的應(yīng)用價(jià)值，動(dòng)態(tài)車(chē)輛路徑問(wèn)題必然是今后物流配送企業(yè)發(fā)展的方向。