動態車輛路徑優化問題

現代物流問題的眾多研究中，車輛路徑問題一直是焦點問題。車輛路徑優化后的配送作業不僅可以降低物流配送企業的物質消耗、節約成本，還可以提高客戶的滿意度和服務水平，最終提高企業的市場競爭力。該文在分析客觀世界動態需求特征的基礎上，對動態車輛路徑問題進行分析，并基于時刻表建立動態車輛路徑問題優化模型。

1引言

隨著信息技術的發展，物流已從傳統的運輸服務發展成為以信息技術和管理為核心的綜合物流系統。據統計，物流成本占產品銷售價格的75%左右。其中，運輸成本在整個物流成本中占有相當大的比例。因此，對物流配送車輛調度進行優化成為企業尤為關注的焦點。

以往對物流配送和車輛調度的研究當中，傳統的做法依據靜態配送車輛優化調度理論。但客觀世界存在著大量的不確定性，需要一種可以求解動態車輛路徑優化問題的方法。

2 動態車輛路徑問題的相關理論

動態車輛路徑問題的提出。車輛路徑問題是物流管理當中最為典型的問題，1959年由Dantzig 和 Ramser[2]提出之后立即引起了很大反響。理論上講，車輛路徑問題屬于組合優化問題，其對應的優化目標是在滿足基本約束條件的前提下，使得配送貨物的車輛的行駛總里程、使用的配送車輛數量、行駛時間的組合達到最小。

動態車輛路徑問題的定義。靜態車輛路徑問題中，在對物流配送路徑進行優化之前的相關信息（客戶、車輛、客戶請求、調度及其他相關信息等）是已知且固定的；而動態車輛路徑優化問題中的很多信息都是不確定且不可預知的，可能還會有部分信息是模糊的、隨機的，在進行路徑規劃時要根據實時信息對車輛路徑進行實時的規劃調整和優化。

3 動態車輛路徑問題模型

動態需求特征分析。車輛在配送的路程當中存在著大量的不確定性：如擁堵、惡劣天氣、車輛故障、客戶信息改變等，這都將直接影響配送車輛行駛時間或者速度的變化，導致等待甚至改變路線，進而造成車輛的調度成本的增加。這些不確定使優化調度變得復雜，但當信息一旦明確已知，就可以把動態車輛調度問題轉化為靜態車輛調度問題來求解。

為了充分研究動態車輛調度問題的動態性特性，這里引入兩個概念：關鍵點和時刻表。關鍵點是指在某個特定的時刻正在客戶點進行服務或者正在前往客戶需求點服務的配送車輛，每條配送行駛路線最多只有一個關鍵點。對已經服務過的客戶需求點暫不考慮，而關鍵點之后的未服務的客戶需求點稱為未分配點，在接收到新的請求信息，或者配送車輛路況發生改變時，應該首先及時、明確地知道當前關鍵點以及未分配點的信息。

下圖（圖1）通過一個簡單的實例清晰地展示了動態車輛路徑問題的相關特性。

圖1 時刻表和關鍵點示例圖

按照車輛的位置狀態，可以將所有客戶需求點的信息大致分為四類：預先安排已經完成服務的、正在進行服務或正在前往服務的路上，預先安排未進行服務的以及新的客戶請求。對于預先安排并已經完成服務的客戶點我們不再考慮。如圖1所示，時刻1的點1、2、4、5為正在進行服務的客戶需求點或者車輛正在前往服務客戶需求點的路上，這些點就是所謂的關鍵點，此時，車輛處于工作狀態中，該資源已經被占用。在時刻2，圖1右邊的點3、6為關鍵點。此時，新的需求點7也是我們考慮的。

基于時刻表的動態車輛路徑問題模型。動態車輛路徑問題的模型是建立在規定的工作時間內（即調度周期）的，而該模型選擇以每天的工作時間為時刻表，新的客戶請求產生的時刻，動態車輛路徑問題都會面對一個新的情況，當新的請求信息明確時，動態的調度問題即轉變為靜態。其中在確定的時刻 ，明確該時刻下的關鍵點以及該時刻之后的已經預先安排但還未進行服務的客戶點是很重要的。關鍵點的個數等于處于工作狀態中的配送車輛的數目，其判斷方法如下：（其中， 是車輛在客戶點 的服務時間）

1設車輛到達客戶需求點 的時間為 ，先找滿足 的點，若有，則點 即為線路的關鍵點，且完成關鍵點任務后的可用時間為 ；否則轉下一步；

2 對于該線路中所有連接的點對 ，尋找 的點，客戶需求點 即為該條線路的關鍵點，且車輛 的可用時間為 。

表1 動態車輛路徑問題需求點參數設置的符號表

車場

車輛 ，服務的客戶點數

時刻 ，關鍵點的集合

時刻 ，未完成任務點和新需求點的集合

時刻 ，所有關鍵點及中心車場的集合

時刻 ，所有未完成任務點、新需求點和中心車場的集合

時刻 ，所有關鍵點、未完成任務點以及新需求點的集合

時刻 ，所有關鍵點、中心車場、未完成任務點和新需求點集合

表2 參數以及相關變量表

車輛數

車輛的最大載重量

時刻，車輛 的累積載重量（包括關鍵點），如果車輛還在車場，則值為0

客戶點 的需求量

車輛從客戶點 到客戶點 的行駛時間

客戶點 最早開始接受服務時間

客戶點 最晚開始接受服務時間

在客戶點 的服務時間

車輛單位時間行駛成本

車輛在 之前到達客戶點 等待的單位時間成本

車輛在 之后到達客戶點 懲罰的單位時間成本

車輛到達客戶點 的時刻，其中 表示最晚一輛車返回車場0的時刻， 表示客戶點 到達車場的時刻。

1表示客戶點 的任務由車輛 來完成

0表示為其它

1表示車輛 從客戶點 行駛到客戶點

0表示為其它

該問題的總支出成本包括固定發車成本、車輛行駛時間成本、等待時間機會成本、客戶懲罰成本，問題要求是總成本最小。當車輛接受任務進行配送，固定發車成本必定發生，因此模型中暫不考慮。

（1）車輛行駛時間成本

以往的研究中大多以距離來計算配送成本，而現實中配送成本還有很多其他影響因素，即使從A點到B點距離很近，但是車輛行駛的時間可能會由于車流量、路況等因素的影響而產生延遲，因此本文根據經驗得出各個客戶需求點之間以及客戶需求點與車場之間的行駛時間和單位時間的配送成本，具體可以表示為：

，其中 表示單位時間的配送成本。

（2）等待時間機會成本

車輛配送中可能會沒有在客戶規定的時間窗內到達客戶點進行服務，如果車輛提前到達客戶點 （ ），該文原載于中國社會科學院文獻信息中心主辦的《環球市場信息導報》雜志http：//www.ems86.com總第522期2013年第39期-----轉載須注名來源需要等待時間窗到了之后才能開始服務，因此而產生的時間機會成本，具體可以表示為：

，其中 表示單位時間的機會成本。

（3）客戶懲罰時間成本

如果車輛超出客戶規定的時間窗到達客戶點，會因為送貨的準時性和時效性影響到客戶的滿意程度，即車輛晚到客戶點 （ ），產生所謂的懲罰成本（即客戶等待車輛的成本），用下面公式表示為：

， 表示單位時間的客戶懲罰成本。

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

（3-1）

（3-2）

（3-3）

（3-4）

（3-5）

（3-6）

（3-7）

（3-8）

（3-9）

（3-10）

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

式（3-2）車容量的限制，即每輛車在t時刻之后要服務的客戶的總的需求量不能超過該車輛的車容量減去已經服務過的客戶需求量的差值；

式（3-3）客戶需求點與車輛的對應關系，每個客戶需求點有且僅有一輛車為其服務；

式（3-4）為平衡式，到達客戶點提供服務的車輛在服務結束之后一定會從該點離開，其值為1或0，即車輛或不訪問該點，或訪問一次；

式（3-5）為刪除構成不完整配送路徑的解，約束配送的車輛在任何一個客戶需求點的子集中不形成回路。

式（3-6）相鄰客戶需求點間的時間約束，即當車輛 對客戶點 服務結束后服務客戶需求點 時，則車輛到達客戶點 的時間等于開始服務客戶點 的服務時間加上從客戶點 到客戶點 路上的行駛時間；

式（3-7）配送服務的車輛從配送中心的出發時間必須在配送中心工作時間窗開始后；

式（3-8）最晚的配送車輛須在配送中心關閉前返回，該車輛可以晚于時間窗到達各客戶需求點；

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

工作時間內，不同時刻的新客戶請求的加入，可以在時刻表的基礎上建立動態車輛調度問題模型，其中初始時刻的模型和傳統靜態模型一樣，配送中心是關鍵點，而所有初始需求構成了未完成任務集合，此時的解是初始調度解。

4 總結

出于對實際應用中各種不確定性的考慮，本文討論了在調度決策執行過程中新的客戶需求不斷產生的環境下的動態車輛路徑問題，對預先的客戶請求進行預先安排和優化，并對新的客戶請求進行實時處理，把接收到的動態信息在信息明確的情況下轉化為靜態車輛路徑優化問題，并在傳統靜態車輛調度問題的基礎上，以成本最小化為最終目標，建立了基于時刻表的動態車輛調度模型。

可以應用到商品貨物以及郵件的速運、公交車以及出租車的服務、零售業的配送、生產計劃以及緊急服務等各個領域。因其廣泛的應用價值，動態車輛路徑問題必然是今后物流配送企業發展的方向。