帶軟時間窗的需求依訂單拆分車輛路徑問題及其禁忌搜索算法

符 卓，劉 文，邱 萌

(中南大學交通運輸工程學院，湖南 長沙 410075)

?

帶軟時間窗的需求依訂單拆分車輛路徑問題及其禁忌搜索算法

符 卓，劉 文，邱 萌

(中南大學交通運輸工程學院，湖南 長沙 410075)

需求可拆分車輛路徑問題是車輛路徑問題中的重要類型，又可分為需求可任意(按計量單位)拆分和需求依訂單拆分兩種子類型，在配送車輛路徑優化等實際問題中有著廣泛的應用背景。綜合考慮客戶需求依訂單拆分和客戶對于被服務時間的要求，本文針對帶軟時間窗的需求依訂單拆分車輛路徑問題及其優化算法進行研究。建立了問題的數學模型，設計了求解的禁忌搜索算法，以Solomn 標準算例為基礎構造算例對算法進行測試，并將求解結果與相關文獻中的結果進行比較。結果表明，算法收斂性較好，為解決該類問題提供了一種方法。

車輛路徑問題；需求依訂單拆分；軟時間窗；禁忌搜索算法

1 引言

物流配送線路確定問題是物流配送管理中的核心問題之一，通常都歸結為車輛路徑問題(Vehicle Routing Problem, VRP)來研究。VRP的一般描述是：對一系列給定的客戶點(送貨點或取貨點)，確定適當的車輛行駛路線，使車輛從車場出發，有序地對客戶進行服務，并在滿足一定的約束條件下(如車輛載重量、客戶需求量、時間窗限制等)，使總運輸成本達到最小(如使用車輛數最少、車輛行駛總距離最短等)。目前大部分有關VRP的研究工作，都是針對每個客戶點的需求只能由一輛車來完成，即需求不可拆分的問題類型。

在實際的配送中，有時會允許對客戶需求進行拆分，并由多輛車分別運送，以便充分利用車輛裝載能力和降低車輛行駛成本。這類問題被稱之為需求可拆分的車輛路徑問題。1989年，Dror和Trudeau[1]首先對其最基本類型，即需求可拆分的純送貨VRP(Split Delivery Vehicle Routing Problem, SDVRP)開展研究。在已有的需求可拆分車輛路徑問題研究中，都是以客戶點需求可被任意拆分(即按計量單位拆分)為背景。在實際工作中，客戶的一份訂單中有時包含有多件貨物，且是不可以拆分運送的，必須將一份訂單中的貨物裝在同一輛車上運送，即此情形下拆分客戶點需求時，不能拆分某一具體訂單，只能按訂單進行拆分。因此，以需求依訂單拆分為應用背景進一步研究需求可拆分VRP很有必要。

此外，客戶有時會對貨物送達的時間區間提出要求，該時間區間通常稱之為時間窗。根據該時間窗的要求是嚴格的，還是允許有所偏離但要支付相應的懲罰，又可相應地分為硬時間窗和軟時間窗。在未特別指出時，硬時間窗通常簡稱為時間窗。顯然，若某個客戶的時間窗不能被違反(是硬的)，則也可通過將有偏離時應支付的懲罰設為無窮大來限制。由此可見，硬時間窗類型實際上是軟時間類型的一種特殊情形。正如Fu Zhuo等[2]所歸納，將客戶的時間窗要求按“軟”的來處理有很多好處：

(1)許多實際問題并不要求將時間窗設置得非常精確。因此，時間窗實質上通常就是軟的。

(2)在實際中，往往也不可能精確地確定車輛的行駛時間。

(3)將時間窗設置為軟的，可以使車輛使用數和車輛的總行駛里程獲得較大節省。

(4)軟時間窗模型更一般化，且包含了硬時間窗的要求。因此，為求解軟時間窗模型設計的算法，通過適當加大偏離時間窗時的懲罰值即可用于求解帶硬時間窗的問題。

(5)在某些實例中，按硬時間窗的要求來求解時可能不存在可行解，而按軟時間窗來處理時總存在可行解。例如當可調配的車輛數較少時，就有可能不存在滿足所有客戶硬時間窗要求的可行解，此情形下，按軟時間窗來處理時總能提供可行解，只是到達某些客戶點的時間有所偏離其所期望的時間窗。

(6)軟時間窗模型還可以用來對車輛使用費用和滿足客戶時間窗要求(即服務質量)之間的背反關系進行權衡。

自從Dror和Trudeau[1]首先對需求可拆分VRP開展研究以來，已經有越來越多的學者從事該領域的研究工作。Dror等[3-5]論證了需求可拆分可提高車輛裝載率，并且節省車輛總成本。Archetti等[6-7]分析了需求可拆分的VRP的計算復雜性。Jin Mingzhou等[8-11]則研究了求解需求可拆分VRP的整數規劃算法。Archetti等[12-15]提出了求解需求可拆分VRP的禁忌搜索算法。國內近年也有學者開展該領域的研究工作。謝毅[16]利用禁忌搜索算法和遺傳算法分別求解了需求可拆分的VRP。孟凡超等[17]用禁忌搜索算法對需求可拆分的VRP進行了求解，并對算法進行了改進。陸琳等[18-22]也從不同角度對需求可拆分VRP做了一些相關研究。

Pankratz等[23-25]將需求可拆分VRP與時間窗結合，提出了相應的啟發式算法。侯立文等[26]使用最大最小螞蟻算法求解了帶時間窗的需求可拆分VRP，并通過放大Solomn標準算例檢驗了算法的有效性。馬華偉等[27]則對帶多時間窗的需求可拆分VRP進行研究，并提出一個求解的改進蟻群算法。相對而言，針對傳統的需求不可拆分VRP與時間窗結合的研究成果更多一些。如李寧等[28-30]使用粒子群算法對帶時間窗VRP進行了求解。汪勇[31]研究采用協同進化遺傳算法對帶時間窗的VRP進行了求解。潘立軍等[32-33]分別提出了求解帶時間窗取送貨問題的遺傳算法和求解帶時間窗VRP的時差插入檢測法。賓松等[34]和祁文祥等[35]則涉及帶軟時間窗的問題類型。而Fu Zhuo等[2]則將軟時間窗的主要類型歸納為6種，并提出了一個可求解各種軟時間窗類型的VRP的一體化禁忌搜索算法。

目前，尚未看到直接研究需求依訂單拆分VRP、或帶軟時間窗的需求可拆分VRP的文獻。但上述相關的研究成果為開展這方面的研究提供了可借鑒的理論和方法。基于上述分析，本文主要研究帶軟時間窗的需求依訂單拆分車輛路徑問題(Vehicle Routing Problem with Soft Time Windows and Split Deliveries by Order，VRPSTWSDO)及其求解算法。以純送貨情形為背景，對單車場、單車型的VRPSTWSDO特點進行描述和分析，建立相應的數學模型，提出求解的禁忌搜索算法，并構造測試算例對其進行測試運算和比較分析。

2 問題表述

VRPSTWSDO是指一組車輛從車場出發，訪問其需求量和希望得到服務的時間窗已知的各客戶點，在訪問客戶點時允許到達客戶點開始服務的時間有所偏離其時間窗要求，但必須給予相應的懲罰。當客戶需求大于車輛的剩余載重時，進行拆分運輸，但不可以分割該客戶點某一具體訂單，最終達到既不超過車輛載重，又最優化載重率的效果。問題的優化目標是確定合理的運輸路線，在滿足車輛裝載能力和行駛距離限制的前提下，最小化所使用的車輛數、車輛行駛距離(時間)和時間窗偏離量，且滿足所有客戶點的需求。其中，最小化車輛數為第一優化目標，最小化車輛行駛時間和時間窗偏離量為第二優化目標。

設車場編號為1，客戶點編號分別為2,3,…,N；

K為所需的車輛數；

Ci為客戶點i的需求量，由R個訂單組成；Ci=Ci1+Ci2+…+Cir+…+CiR，Cir為客戶點i的第r個訂單，每個訂單不可拆分，r為需求點i的訂單編號，r=1,2,…,R；

w為車輛裝載能力，且Ci

L為每條線路的最大長度(行駛時間)；

yki表示第k輛車為客戶點i配送的貨物量；

ai為客戶點i時間窗的最早時間；

bi為客戶點i時間窗的最晚時間；

tij為客戶點i到客戶點j的行駛時間；

ti為到達客戶點i的時間；

tis為客戶點i的服務時間；

e為提前到達客戶點i并開始服務的懲罰系數；

f為延遲到達客戶點i并開始服務的懲罰系數。

定義變量如下：

xijk=1，表示車輛k從客戶點i行駛到客戶點j；否則，xijk=0。

hkir=1，表示車輛k運輸客戶點i的第r個訂單的貨物；否則，hkir=0。

如果客戶點i和客戶點j在同一線路上，且服務客戶點i之后馬上服務客戶點j，那么tj=ti+tis+tij。

模型假設：

(1)兩點間的行駛時間是對稱的，即tij=tji；

(2)點與點之間的行駛時間符合三角不等式，即tik+tkj>tij；

(3)所有的車輛從車場出發，完成一趟任務后，必須返回車場；

(4)每個客戶點的需求必須滿足，但可以由一輛及以上車輛來滿足。

根據上述描述，帶軟時間窗的需求依訂單拆分的車輛路徑問題的數學模型可以描述為：

MinK

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

yki=hki1Ci1+hki2Ci2+…+hkirCir,i=2,3,…,N;k=1,2,…,K

(9)

式(1)是第一優化目標，最小化車輛使用數；式(2)是第二優化目標，最小化車輛行駛成本和時間窗偏離；式(3)為線路長度限制；式(4)為車輛裝載能力限制；式(5)、(6)表示每個客戶點至少被訪問一次，且需求均得到滿足；式(7)表示流量守恒，即進入某客戶點的車輛數和離開該客戶點的車輛數相等；式(8)表示當且僅當車輛經過某客戶點時，該客戶點才能得到服務；式(9)表示客戶點i的需求可以拆分，但每個訂單不可拆分。

3 禁忌搜索算法設計

Dror等[36]和Archetti等[37]用各自的方法證明了需求依訂單拆分VRP是NP-Hard 問題。本文研究的VRPSTWSDO是需求依訂單拆分VRP的延伸，也是NP-Hard問題。禁忌搜索算法作為一種全局性鄰域搜索亞啟發式算法，適用于本文所設計NP-Hard 問題模型的求解。已有研究中，Gendreau等[38]和Cordeau等[39]分別對求解VRP的一些現代啟發式算法，如模擬退火、禁忌搜索、遺傳算法、蟻群算法和神經網絡等進行了較為全面的綜述。根據他們的分析，總體來說，禁忌搜索是目前求解VRP的較為有效的方法。另外，Ho和Haugland[40]研究帶硬時間窗的需求可拆分車輛路徑問題，相較于本文的軟時間窗約束，約束條件更嚴格。Fu Zhuo等[2]研究帶軟時間窗的需求不可拆分的車輛路徑問題，相較于本文的需求可拆分，約束條件也更嚴格。兩篇文獻應用禁忌搜索算法均較好地解決了所研究的問題。所以本研究選擇設計禁忌搜索算法來求解該問題。

與使用其他現代啟發式算法求解優化問題一樣，使用禁忌搜索算法來求解問題時需要在其基本通用框架內，結合所要求解的問題進行一些具體設計。

3.1 初始解

禁忌搜索算法對初始解有較強的依賴性，好的初始解可使禁忌搜索在解空間中搜索到好的解，而較差的初始解則會降低禁忌搜索的收斂速度。一般來講，求解某個具體問題時，可用其他算法生成高質量的初始解，再用禁忌搜索求解，以提高搜索的質量和效率。當然也可以采用一定的策略來降低禁忌搜索對初始解的敏感性[41]。傅少川等[42-43]分別采用了貪婪算法和最鄰近貪心算法生成高質量的初始解，較好地求解了所研究問題。Fu Zhuo等[44]則采用隨機方式生成初始解，并通過設計混合鄰域搜索和設置當前最好解選擇機制等來降低禁忌搜索對初始解的敏感性，也較好地求解了所研究問題。

本文選擇采用隨機方式生成初始解，并參考文獻[44]中算法設計的策略，通過鄰域結構、禁忌規則、參數設置等針對性的設計來降低禁忌搜索對初始解的敏感性，增強禁忌搜索算法的尋優能力。

3.2 解的表示方式

在鄰域搜索過程中，本文采用客戶點編號和客戶點中被滿足的訂單相對應排列的方式表示線路。用Cir表示某條線路經過客戶點i并配送了該點第r個訂單的貨物。比如某條線路的排列(1C21C22C31C331)，表示客戶點2的第1、2兩個訂單，客戶點3的第1、3兩個訂單均由此條線路配送。每條線路均由1開始，在經過若干個客戶點之后，由1結束，表示每輛車從車場出發并在完成任務后回到車場。

3.3 鄰域結構

為增強算法的搜索能力，本算法采用混合鄰域結構，即隨機選擇以下點操作或訂單操作對當前解的鄰域進行搜索。

隨機選取兩條線路R1和R2，將其客戶點合并排列在一起，再進行相關操作。例如挑選到R1=(1C63C61C23C411)，R2=(1C72C33C32C521)，則合并排列為S=(1C63C61C23C411C72C33C32C521)。不考慮此排列中的第一個和最后一個“1”，從排列中隨機選取兩個訂單q1和q2(加下劃線表示)，其中將中間的“1”(車場)按只有一個訂單的客戶點處理。

3.4 解的評價

解的評價主要反映兩方面的內容，一是解的目標函數值，二是解是否可行。 若某條路徑中配送總量超過車輛裝載能力w，或者車輛總行駛時間超過最長時間限制L，則該路徑方案不可行。

該算法設計為可接受導致不可行解的變換，產生可行解和不可行解的混合，以便通過不可行解的過渡，對鄰域空間進行充分搜索，找到更好的可行解，避免過早陷入局部最優。因此，將解的評價設為E=P1K+P2(Z+pM)，其中，P1、P2表示優先級，即P1>>P2，是定性的概念，不賦予任何具體數值。因此并不意味著目標之間的任何折衷，只表示每個目標的優先級。這樣能夠保證算法在求解時以最小化車輛使用數為第一優化目標，以最小化車輛行駛時間作為第二優化目標。M為當前解對應的配送路徑方案的不可行路徑條數，p為每條不可行路徑的懲罰權重。若一個解是可行的，則M=0。p[50,2000]，開始時等于200，并通過一個自調整參數來加權，每隔10次迭代測試一次，若前面的10個解是可行的，則將其除以2；若所有的10個解都是不可行的，則將其乘以2。

3.5 禁忌規則

本算法選取定值15作為禁忌期(禁忌長度)。構造了一個(N×N)的矩陣作為禁忌表，以記錄禁忌對象的禁忌情況。如果進行了點操作(操作(1)、(2)、(3))，則將被操作客戶點i和j的禁忌情況存入(N×N)矩陣的元素(i,j)中。如果進行了訂單操作(操作(4)、(5)))，則找到被操作訂單q1和q2所屬客戶點i和j，將禁忌情況存入(N×N)矩陣的元素(i,j)中。每迭代一次，都要將禁忌表中其他被禁忌對象的禁忌期減去1，直至為0止。

3.6 算法描述

為了描述方便，定義以下變量：

iter為當前的迭代步數；

max-iter為最大的迭代步數；

cons-iter表示當前最好解保持不變的當前連續迭代步數；

max-cons-iter表示當前最好解保持不變的最大連續迭代步數；

cand-list當前解的候選解數量；

max-cand-list最大的候選解數量。

算法終止條件：當前最好解保持不變達到給定的max-cons-iter，或總迭代次數達到max-iter，則終止搜索進程。

算法流程框架如下：

步驟1：隨機產生一個初始可行解，并將其作為當前解和當前最好解。

步驟2：初始化禁忌表，置iter和cons-iter為0。

步驟3：轉入鄰域搜索，隨機選取所要進行的鄰域變換。

步驟4：將所挑選的鄰域變換作用于當前解，并將產生的新解放入候選解集中。

步驟5：cand-list的值加1。

步驟6：若cand-list<=max-cand-list，則轉步驟3，否則，轉下一步。

步驟7：若存在優于當前最好解的禁忌解，則解禁該解，并作為最佳候選解；若所有候選解都被禁忌，則解禁其中的最佳候選解；否則，從候選解集中選擇非禁忌的最佳候選解；并置新的最佳候選解為當前解，iter的值加1。

步驟8：若新的最佳候選解優于當前的最好解，則更新當前最好解，并置cons-iter為0，否則，cons-iter的值加1；其中，若出現車輛數減少的可行解，則直接將其置為當前解和當前最好解，iter的值加1，并置cons-iter為0。

步驟9：若iter<=max-iter，且cons-iter<=max- cons-iter，則轉步驟3；否則，終止算法。

4 測試結果及其比較

本文以國際上通用的Solomn[25]標準算例中的17個算例為基礎，將各客戶點的需求量隨機分解為由1-5個訂單組成，從而形成可用于測試本算法的算例。本算法使用Matlab7.11.0編程，并在CPU為Core(TM)i3雙核處理器(2.40GHz)，內存2GB的微機上實現。

國內外對于需求依訂單拆分的車輛路徑問題研究較少，目前沒有可直接對比的結果。故本文選取Ho和Haugland[40]和Fu等[2]中的第2種軟時間窗類型(Type 2 of VRPSTW)的結果進行間接比較。兩篇對比文獻相較于本文約束條件更嚴格。因此，理論上而言，本文中兩個優化目標的優化結果應小于或等于該兩文獻中的計算結果。

本算法中對于參數e，f的設定，需要根據實際應用中客戶對于被服務時間要求程度來設定，本文設定e=f=0.2來測算算例。對于參數max-cand-list，max-cons-iter和max-iter的設定，經過多次求解算例，測試比較，設定參數值如下：max-cand-list=200，max-cons-iter= 4000，max-iter=20000。每個算例計算5次，選取其中的最好解與兩篇文獻中的最好結果做比較。計算結果和對比文獻結果如表1所示。

計算結果表明，(1)對于測試算例，本文所得結果均優于或等于兩篇文獻的計算結果，達到了預期效果。(2)本文研究問題為帶軟時間窗，就是在有所偏離部分時間窗的基礎上，最小化車輛行駛時間，亦達到基本要求。

表1 算法結果與比較

以表1中算例RC101為例，進一步說明本文算例的構造、所設計禁忌搜索算法計算得到的最終解、以及算法的收斂性等情況。

開始計算算例RC101時，各客戶點的需求量被隨機分解為由1-5個訂單組成，訂單生成情況如表2所示(其中0代表該訂單不存在)。

表2 算例RC101各客戶點的訂單生成情況

本次計算RC101算例結束后得出最終解的路徑規劃情況如表3所示。需求未被拆分的客戶點，則直接用該客戶點編號來表示。需求被拆分的客戶點，則在該客戶點編號后，用括號詳細羅列出被運送訂單貨物量，如表中加粗數字所示。編號中間用“-”連接。比如最終解中第1條線路為1-66(10, 1, 2)-91-70-89-79-74-80-61-56-1，則表示此線路中，包含客戶點66, 91, 70, 89, 79，74，80，61，56，其中，只有客戶點66被拆分，且貨物量為10、1和2的三個訂單由此線路服務。

表3 算例RC101最終解路徑規劃情況

至于本文所設計禁忌搜索算法的收斂情況，以本次計算算例RC101時，迭代過程中解的評價值E的變化情況為例說明，如圖1所示。由圖可知，算法收斂速度較快，收斂性較好。

圖1 本次運算RC101算例時解的評價值E的變化情況

5 結語

本文研究帶軟時間窗的需求依訂單拆分車輛路徑問題及其禁忌搜索算法，并進行了編程實現。以 Solomn標準算例為基礎構造算例對算法進行測試，并將求解結果與相關文獻中的結果進行比較，表明所得結果優于目前約束條件更為嚴格的車輛路徑問題的結果，且算法收斂性較好，達到了基本要求。為求解帶軟時間窗的需求依訂單拆分車輛路徑問題提供了一種求解算法。

[1] Dror M, Trudeau P. Savings by split delivery routing[J]. Transportations Science, 1989, 23(2):141-145.

[2] Fu Zhuo, Eglese R, Li L Y O. A unified tabu search algorithm for vehicle routing problems with soft time windows[J]. Journal of the Operational Research Society, 2008, 59(5):663-673.

[3] Dror M, Trudeau P. Split delivery routing[J]. Naval Research Logistics, 1990, 37(3):383-402.

[4] Archetti C, Savelsbergh M W, Grazia Speranza M. To split or not to split: That is the question[J]. Transportation Research Part E: Logistics and Transportation Review, 2008,44(1):114-123.

[5] Archetti C, Savelsbergh M W, Speranza M G. Worst-case analysis for split delivery vehicle routing problems[J]. Transportation Science, 2006, 40(2): 226-234.

[6] Archetti C, Feillet D, Gendreau M, et al. Complexity of the VRP and SDVRP[J]. Transportation Research Part C: Emerging Technologies, 2011,19(5):741-750.

[7] Archetti C, Mansini R, Speranza M G. Complexity and reducibility of the split delivery problem[J]. Transportation Science, 2005,39(2):182-187.

[8] Jin Mingzhou, Liu Kai, Eksioglu B. A column generation approach for the split delivery vehicle routing problem[J]. Operations Research Letters, 2008, 36(2): 265-270.

[9] Chen S8, Golden B, Wasil E. The split delivery vehicle routing problem: Applications, algorithms, test problems, and computational results[J]. Networks, 2007,49(4): 318-329.

[10] Salani M, Vacca I. Branch and price for the vehicle routing problem with discrete split deliveries and time windows[J]. European Journal of Operational Research, 2011, 213(3):470-477.

[11] Archetti C, Bianchessi N, Speranza M G. Branch-and-cut algorithms for the split delivery vehicle routing problem[J]. European Journal of Operational Research, 2014, 238(3): 685-698.

[12] Archetti C, Speranza M G, Hertz A. A tabu search algorithm for the split delivery vehicle routing problem[J]. Transportation Science, 2006, 40(1):64-73.

[13] Aleman R E, Hill R R. A tabu search with vocabulary building approach for the vehicle routing problem with split demands[J]. International Journal of Metaheuristics, 2010, 1(1):55-80.

[14] Berbotto L, García S, Nogales F J. A randomized granular tabu search heuristic for the split delivery vehicle routing problem[J]. Annals of Operations Research, 2014, 222(1):153-173.

[15] Campos V, Corberán A, Mota E. A scatter search algorithm for the split delivery vehicle routing problem[M]//Fin R A,Rothlauf F. Advances in Computational Intelligence in Transport, Logistics, and Supply Chain Management,Berlin-Heidelberg:Springer,2008:137-152.

[16] 謝毅. 需求可拆分的物流車輛路線問題研究[D]. 上海：同濟大學，2006.

[17] 孟凡超，陸志強，孫小明. 需求可拆分車輛路徑問題的禁忌搜索算法[J]. 計算機輔助工程，2010, 9(1):78-83.

[18] 陸琳. 不確定信息車輛路徑問題及其智能算法研究[M]. 北京：科學出版社，2010.

[19] 李三彬，柴玉梅，王黎明. 需求可拆分的開放式車輛路徑問題的研究[J]. 計算機工程，2011, 37(6):168-171.

[20] 劉旺盛，楊帆，李茂青，等. 需求可拆分車輛路徑問題的聚類求解算法[J]. 控制與決策，2012, 27(4):535-540.

[21] 劉旺盛，黃娟. 需求可拆分的車輛路徑問題的分段求解[J]. 集美大學學報，2011, 16(1):38-44.

[22] 楊亞璪，靳文舟，郝小妮，等. 求解集送貨可拆分車輛路徑問題的啟發式算法[J]. 華南理工大學學報，2010, 38(3):58-62.

[23] Pankratz G. A grouping genetic algorithm for the pickup and delivery problem with time windows[J].OR Spectrum,2005,27(1): 21-41.

[24] Frizzell P W, Gi In J W. The split delivery vehicle scheduling problem with time windows and grid network distances[J]. Computers & Operational Research, 1995, 22(6): 655-667.

[25] Solomn M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2): 254-265.

[26] 侯立文，譚家美，趙元. 求解帶時間窗的客戶需求可分條件下的車輛路徑問題[J]. 中國管理科學，2007, 15(6):78-83.

[27] 馬華偉, 葉浩然, 夏維. 允許分割配送的多時間窗車輛調度問題的改進蟻群算法求解[J]. 中國管理科學，2012, 20(S1):43-47.

[28] 李寧，鄒彤，孫德寶. 帶時間窗車輛路徑問題的粒子群算法[J]. 系統工程理論與實踐，2004, 24(4):134-140.

[29] 吳耀華，張念志. 帶時間窗車輛路徑問題的改進粒子群算法研究[J]. 計算機工程與應用，2010, 46(15): 345-349.

[30] 馬炫，彭芃，劉慶. 求解帶時間窗車輛路徑問題的改進粒子群算法[J]. 計算機工程與應用，2009, 45(27): 679-684.

[31] 汪勇，丁凡，吳志華. 協同進化遺傳算法求解帶時間窗的車輛路徑問題[J]. 統計與決策，2010, (10):76-87.

[32] 潘立軍,符卓. 求解帶時間窗取送貨問題的遺傳算法. 系統工程理論與實踐, 2012, 32 (1):120-126.

[33] 潘立軍,符卓. 求解帶時間窗車輛路徑問題的時差插入檢測法. 系統工程理論與實踐, 2012, 32(2):319-322.

[34] 賓松，符卓. 求解帶軟時間窗的車輛路徑問題的改進遺傳算法[J]. 系統工程，2003, 21(6):79-85.

[35] 祁文祥，陸志強，孫小明. 帶軟時間窗的集貨與送貨多車輛路徑問題節約算法[J]. 交通運輸工程學報，2010, 10(2):99-103.

[36] Dror M, Laporte G, Trudeau P. Vehicle routing with split deliveries[J]. Discrete Applied Mathematics,1994, 50(3): 239-254.

[37] Archetti C, Mansini R, Speranza M G. Complexity and reducibility of the skip delivery problem[J]. Transportation Science, 2005, 39(2): 182-187.

[38] Gendreau M, Laporte G, Potvin J Y. Metaheuristics for the Capacitated VRP[M]//Toth P, Vigo D. The vehicle routing problem. Philadelphia, PA: SIAM Monographs on Discrete Mathematics and Applications, 2002:129-154.

[39] Cordeau J F, Gendreau M, Laporte G, et al. A guide to vehicle routing heuristics[J]. Journal of the Operational Research Society, 2002, 53(5): 512-522.

[40] Ho S C, Haugland D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J]. Computers & Operations Research, 2004, 31(12):1947-1964.

[41] 劉光遠，賀一，溫萬惠. 禁忌搜索算法及應用[M]. 北京：科學出版社，2014.

[42] 傅少川，胡夢飛，唐方成. 禁忌搜索算法在單分配多樞紐輻射式物流網絡中的應用[J]. 中國管理科學，2012, 20(3)：145-151.

[43] 李進，傅培華，李修琳，等. 低碳環境下的車輛路徑問題及禁忌搜索算法研究[J]. 中國管理科學，2015, 23(10)：98-106.

[44] Fu Zhuo, Eglese R, Li L Y O. A new tabu search heuristic for the open vehicle routing problem[J]. Journal of the Operational Research Society, 2005, 56(3):267-274.

A Tabu Search Algorithm for the Vehicle Routing Problem with Soft Time Windows and Split Deliveries by Order

FU Zhuo, LIU Wen, QIU Meng

(School of Traffic and Transportation Engineering, Central South University, Changsha 410075,China)

As an important type of vehicle routing problem, split delivery vehicle routing problem, which can be divided into two subtypes, split deliveries without restriction (by unit) and split deliveries by order, has broad applications such as distribution vehicle routing optimization and so on. In most of the present research of split delivery vehicle routing problem, customers’ demands can be split without restrictions. However, in practical, sometimes a customer order consists of several cargos and could not be split during deliveries. So the cargos in the same order can only be delivered by the same vehicle. In that condition, customers’ demands can be split in orders while a specific order could not be split. In addition, more and more customers have time window requirement during the distribution process. Considering this two respects, the vehicle routing problem with soft time windows and split deliveries by the order and its optimization algorithm are presented. The problem allows that the same customer can be serviced by multiple vehicles and the customer demand can be split but not split a specific order. Customers can be served either in the specified time windows or out of the time windows with according punishment. A mixed integer programming model for the problem is constructed and a tabu search algorithm for the model is proposed. The proposed algorithm was coded and tested on the problems which are based on the benchmark problems generated by Solomn. The computational results are compared with the ones in related literatures. It shows that the algorithm converges well and effectively solves the problem.

vehicle routing problem；split deliveries by order；Soft time windows；tabu search algorithm

1003-207(2017)05-0078-09

10.16381/j.cnki.issn1003-207x.2017.05.010

2015-12-14；

2016-05-12

國家自然科學基金資助項目(71271220)

符卓(1960-)，男(漢族)，中南大學交通運輸工程學院，教授，博士，博士生導師,研究方向：物流系統優化，E-mail: zhfu@csu.edu.cn.

O221；F253.4

A