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

符 卓，劉 文，邱 萌

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

?

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

符 卓，劉 文，邱 萌

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

目前，尚未看到直接研究需求依訂單拆分VRP、或帶軟時間窗的需求可拆分VRP的文獻(xiàn)。但上述相關(guān)的研究成果為開展這方面的研究提供了可借鑒的理論和方法?；谏鲜龇治觯疚闹饕芯繋к洉r間窗的需求依訂單拆分車輛路徑問題(Vehicle Routing Problem with Soft Time Windows and Split Deliveries by Order，VRPSTWSDO)及其求解算法。以純送貨情形為背景，對單車場、單車型的VRPSTWSDO特點進(jìn)行描述和分析，建立相應(yīng)的數(shù)學(xué)模型，提出求解的禁忌搜索算法，并構(gòu)造測試算例對其進(jìn)行測試運算和比較分析。

2 問題表述

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

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

K為所需的車輛數(shù)；

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為到達(dá)客戶點i的時間；

tis為客戶點i的服務(wù)時間；

e為提前到達(dá)客戶點i并開始服務(wù)的懲罰系數(shù)；

f為延遲到達(dá)客戶點i并開始服務(wù)的懲罰系數(shù)。

定義變量如下：

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

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

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

模型假設(shè)：

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

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

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

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

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

MinK

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

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

(9)

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

3 禁忌搜索算法設(shè)計

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

與使用其他現(xiàn)代啟發(fā)式算法求解優(yōu)化問題一樣，使用禁忌搜索算法來求解問題時需要在其基本通用框架內(nèi)，結(jié)合所要求解的問題進(jìn)行一些具體設(shè)計。

3.1 初始解

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

本文選擇采用隨機方式生成初始解，并參考文獻(xiàn)[44]中算法設(shè)計的策略，通過鄰域結(jié)構(gòu)、禁忌規(guī)則、參數(shù)設(shè)置等針對性的設(shè)計來降低禁忌搜索對初始解的敏感性，增強禁忌搜索算法的尋優(yōu)能力。

3.2 解的表示方式

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

3.3 鄰域結(jié)構(gòu)

為增強算法的搜索能力，本算法采用混合鄰域結(jié)構(gòu)，即隨機選擇以下點操作或訂單操作對當(dāng)前解的鄰域進(jìn)行搜索。

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

3.4 解的評價

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

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

3.5 禁忌規(guī)則

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

3.6 算法描述

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

iter為當(dāng)前的迭代步數(shù)；

max-iter為最大的迭代步數(shù)；

cons-iter表示當(dāng)前最好解保持不變的當(dāng)前連續(xù)迭代步數(shù)；

max-cons-iter表示當(dāng)前最好解保持不變的最大連續(xù)迭代步數(shù)；

cand-list當(dāng)前解的候選解數(shù)量；

max-cand-list最大的候選解數(shù)量。

算法終止條件：當(dāng)前最好解保持不變達(dá)到給定的max-cons-iter，或總迭代次數(shù)達(dá)到max-iter，則終止搜索進(jìn)程。

算法流程框架如下：

步驟1：隨機產(chǎn)生一個初始可行解，并將其作為當(dāng)前解和當(dāng)前最好解。

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

步驟3：轉(zhuǎn)入鄰域搜索，隨機選取所要進(jìn)行的鄰域變換。

步驟4：將所挑選的鄰域變換作用于當(dāng)前解，并將產(chǎn)生的新解放入候選解集中。

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

步驟6：若cand-list<=max-cand-list，則轉(zhuǎn)步驟3，否則，轉(zhuǎn)下一步。

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

步驟8：若新的最佳候選解優(yōu)于當(dāng)前的最好解，則更新當(dāng)前最好解，并置cons-iter為0，否則，cons-iter的值加1；其中，若出現(xiàn)車輛數(shù)減少的可行解，則直接將其置為當(dāng)前解和當(dāng)前最好解，iter的值加1，并置cons-iter為0。

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

4 測試結(jié)果及其比較

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

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

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

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

表1 算法結(jié)果與比較

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

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

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

本次計算RC101算例結(jié)束后得出最終解的路徑規(guī)劃情況如表3所示。需求未被拆分的客戶點，則直接用該客戶點編號來表示。需求被拆分的客戶點，則在該客戶點編號后，用括號詳細(xì)羅列出被運送訂單貨物量，如表中加粗?jǐn)?shù)字所示。編號中間用“-”連接。比如最終解中第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的三個訂單由此線路服務(wù)。

表3 算例RC101最終解路徑規(guī)劃情況

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

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

5 結(jié)語

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

[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]. 上海：同濟大學(xué)，2006.

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

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

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

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

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

[22] 楊亞璪，靳文舟，郝小妮，等. 求解集送貨可拆分車輛路徑問題的啟發(fā)式算法[J]. 華南理工大學(xué)學(xué)報，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]. 中國管理科學(xué)，2007, 15(6):78-83.

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

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

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

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

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

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

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

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

[35] 祁文祥，陸志強，孫小明. 帶軟時間窗的集貨與送貨多車輛路徑問題節(jié)約算法[J]. 交通運輸工程學(xué)報，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] 劉光遠(yuǎn)，賀一，溫萬惠. 禁忌搜索算法及應(yīng)用[M]. 北京：科學(xué)出版社，2014.

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

[43] 李進(jìn)，傅培華，李修琳，等. 低碳環(huán)境下的車輛路徑問題及禁忌搜索算法研究[J]. 中國管理科學(xué)，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

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

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

O221；F253.4

A