帶時間窗偏好的同時配集貨且需求可拆分車輛路徑問題

范厚明, 任曉雪, 劉 浩

(大連海事大學(xué) 交通運輸工程學(xué)院,遼寧 大連 116026)

0 引言

帶時間窗偏好的同時配集貨且需求可拆分車輛路徑問題(Split Delivery Vehicle Routing Problem with Simultaneous Delivery and Pick-up and Time Windows Preference, SDVRPSDPTWP)是綜合考慮了同時配集貨需求可拆分車輛路徑問題(Split Delivery Vehicle Routing Problem with Simultaneous Delivery and Pick-up, SDVRPSDP)和帶時間窗偏好的同時配集貨車輛路徑問題(Vehicle Routing Problem with Simultaneous Delivery and Pick-up and Time Windows Preference, VRPSDPTWP)而展開的研究。該研究涉及現(xiàn)實中普遍存在的物流配送問題，如：醫(yī)藥公司分批次配送并回收過期藥物；區(qū)域物流分揀中心向各小區(qū)、高校配送快件的同時會收取寄件，由于快件數(shù)量多，且送、取件的時間要求不同，會出現(xiàn)多次對一個客戶進行配送并收取快件的情況等。

有關(guān)SDVRPSDP的研究：Casazza等[1,2]設(shè)計了分支-定價算法求解SDVRPSDP問題。Chen等[3]設(shè)計了基于運輸效率的啟發(fā)式算法和變鄰域搜索算法求解SDVRPSDP問題。Haddad等[4]提出了基于大鄰域搜索的元啟發(fā)式算法和分支-定價算法求解SDVRPSDP問題。Hennig等[5]研究了原油船的SDVRPSDP問題，設(shè)計了兩種可替換的路徑流模型進行求解。Hernández-Pérez等[6]設(shè)計了分支-切割算法求解SDVRPSDP問題，該問題中客戶可作為臨時中間點，用于貨物的配送以及收集。Abdi等[7]研究的是只拆分配貨需求的SDVRPSDP問題，設(shè)計了四種元啟發(fā)式算法進行求解。

有關(guān)VRPSDPTW的研究：Aziez等[8]研究了帶有時間窗的多收集-單配送的車輛路徑問題，設(shè)計了分支-切割算法進行求解。Goeke[9]研究了電車的VRPSDPTW問題，設(shè)計了禁忌搜索算法進行求解。Gy?rgyi等[10]研究了不確定時間窗的隨機和動態(tài)配集貨車輛路徑問題，設(shè)計了兩個啟發(fā)式算法進行求解。Veenstra等[11]研究了帶時間窗和裝卸作業(yè)的配集貨車輛路徑問題，并設(shè)計了分支-定價-切割算法進行求解。Wang等[12]研究了VRPSDPTW問題，設(shè)計了并行模擬退火算法進行求解。Li等[13]設(shè)計了自適應(yīng)大鄰域搜索算法求解VRPSDPTW問題。

目前，關(guān)于SDVRPSDPTWP的研究成果還沒有。通過文獻梳理可見，以下幾個方面有待更深入的研究：(1)大多求解算法在生成客戶排列時僅考慮客戶間的空間距離，沒有考慮時間距離；(2)大多研究假設(shè)配送車輛統(tǒng)一固定時刻出發(fā)，而不是根據(jù)客戶要求確定車輛最優(yōu)出發(fā)時間；(3)部分研究設(shè)置了固定拆分閾值，分析不同拆分閾值對路徑規(guī)劃的影響，但拆分閾值很難合理確定。

1 SDVRPSDPTWP模型建立

1.1 參數(shù)定義

1.2 客戶時間窗偏好

若車輛在客戶i的規(guī)定時間窗[ETi,LTi]內(nèi)到達，客戶i的滿意度始終為最高值1，且沒有時間懲罰成本；若車輛在時間窗[EETi,ETi]和[LTi,ELTi]內(nèi)到達，到達時間偏離客戶規(guī)定時間窗越大，滿意度越低，時間懲罰成本越大；若車輛在EETi和ELTi處到達，客戶i的滿意度為最低值0，時間懲罰成本為最高值；若車輛在EETi之前到達，需要等待，直到EETi才可以開始服務(wù)，客戶滿意度為0，時間懲罰成本為最高值；若車輛在ELTi之后到達，客戶i拒絕接受服務(wù)，滿意度為0，時間懲罰成本為無窮。

時間懲罰成本為車輛到達時間的隸屬度函數(shù)。客戶滿意度和時間懲罰成本的計算公式如下:

(1)

(2)

1.3 油耗成本

車輛的油耗與車輛的載重成線性關(guān)系[14]，本文假設(shè)z1是車輛空載時的油耗率，z2是車輛滿載時的油耗率，c0是單位油耗成本。若車輛k服務(wù)的客戶序列為Vk={e,f,s,y},Vk∈V0，當車輛k服務(wù)完客戶e,f,s后，其實時載重量Qsyk=Qefk-df+pf-ds+ps，Qefk是車輛k服務(wù)完客戶e后駛向客戶f的裝載量，Qsyk是車輛k服務(wù)完客戶s后駛向客戶y的裝載量。車輛k從客戶s到客戶y的油耗率以及油耗成本如式(3)、(4)所示:

zsyk=z1+(z2-z1)Qsyk/Q

(3)

csyk=c0zsyklsyxsyk

(4)

1.4 數(shù)學(xué)模型

基于以上所述，本文建立的模型如下:

(5)

(24)

其中，式(5)最小化總配送成本，包括派遣成本、理貨成本、時間窗懲罰成本及油耗成本；式(6)表示從配送中心派出的車輛數(shù)不能多于實際擁有數(shù)量；式(7)表示車輛服務(wù)完客戶點后必須離開；式(8)表示每個客戶最少被服務(wù)一次；式(9)和(10)保證客戶被車輛服務(wù)時一定有路徑與其連接；式(11)表示車輛從配送中心被派出，完成相應(yīng)服務(wù)后必須返回配送中心；式(12)表示車輛,k服務(wù)客戶j前后的車輛負載平衡約束；式(13)和(14)表示每個客戶的配集貨需求量都得到滿足；式(15)和(16)表示任一輛車對其路徑上的任一客戶點的配、集貨量都不超過其需求量；式(17)計算車輛的服務(wù)時間；式(18)計算車輛k從客戶i到達客戶j的時刻；式(19)表示客戶滿意度最低為ω；式(20)表示兩決策變量之間的關(guān)系；式(21)表示車輛k到達客戶j的時間必須小于客戶j的最晚服務(wù)開始時間且不小于0；式(22)表示車輛的載重量約束；式(23)和(24)為決策變量屬性。

2 混合遺傳變鄰域搜索算法

本文設(shè)計了混合遺傳變鄰域搜索算法(Hybrid Genetic-Variable Neighborhood Search Algorithm, HG-VNSA)求解建立的模型，具體操作步驟如下：

Step1設(shè)置參數(shù)。

Step2生成初始種群。

首先用最近鄰插入法生成一條染色體；然后用Logistic映射方程生成初始種群；最后把用最近鄰插入法生成的染色體放在用Logistic映射方程生成的初始種群的前面，成為種群規(guī)模為pop_size的初始種群成。

Step3利用插入法生成車輛路徑。

Step4計算所有染色體的適應(yīng)度值。

Step5搜索當代種群中的最優(yōu)染色體，若當前最優(yōu)解優(yōu)于歷史最優(yōu)解，則接受該染色體，否則，拒絕。

Step6本文采用0-1Exchange、1-1Exchange、2-OPT三種鄰域操作改進當前解(具體鄰域操作見2.6節(jié))。本文還設(shè)計了以下兩種自適應(yīng)搜索策略：

(1)自適應(yīng)鄰域搜索次數(shù)

Si=「ε1·max_gen+?ε2·max_gen·(gen/max_gen)1/2」?

(2)自適應(yīng)鄰域搜索范圍

Sr=「β1·n+?β2·n·(gen/max_gen)1/2」?,

β1+β2≤1,β1,β2≠0

其中，max_gen是預(yù)設(shè)的最大迭代次數(shù)，?x」表示取不大于x的最大整數(shù)，「x?表示取不小于x的最小整數(shù)。

Step7若解改進了，則返回第一個鄰域結(jié)構(gòu)繼續(xù)進行搜索，否則執(zhí)行下一個鄰域結(jié)構(gòu)進行搜索，直到最后一個鄰域結(jié)構(gòu)仍未找到改進解時，搜索終止。

Step8輸出最優(yōu)解。

Step9結(jié)束。

2.1 考慮時空距離的初始種群的生成

2.1.1 時空距離的定義與度量

本文將空間距離和時間距離歸一化處理，計算公式如式(26)所示。

(25)

(26)

2.1.2 初始種群的生成及編解碼方式

(1)采用最近鄰插入法。選擇模糊時間窗窄且EETi小的客戶，若存在多個，則從中選擇距離配送中心最近的客戶作為第一個客戶，然后根據(jù)時空距離采用最近鄰插入法將其余客戶依次加入到客戶排列中。

(2)利用混沌系統(tǒng)的內(nèi)在隨機性，用Logistic映射方程進行迭代，生成初始種群，Logistic映射方程如式(27)所示:

xi+1=wxi(1-xi),i=1,2,3,…

(27)

其中xi代表第i時刻種群的狀態(tài)，xi∈[0,1]，w是控制參數(shù)，w∈(3.5699456,4]。

具體的編碼方式如圖1所示。

圖1 編解碼方式示意圖

2.2 適應(yīng)度函數(shù)

染色體的適應(yīng)度函數(shù)fi可以表示為:

fi=1/Ci

(28)

其中，Ci為染色體i的目標函數(shù)值。

2.3 選擇操作

確定式采樣選擇策略的具體步驟如下:

Step1計算種群中每條染色體在下一代種群中的期望生存數(shù)目Fi:

(29)

其中，fi是染色體i的適應(yīng)度值，pop_suze是種群規(guī)模。

2.4 拆分準則

2.5 時間優(yōu)化策略

本文提出確定車輛最優(yōu)出發(fā)時間的時差推移法(Time Difference Pass Method, TDPM)，給出以下定義：

定義1任一可行路徑做任何調(diào)整都會造成路徑在時間上的不可行或降低客戶滿意度，該路徑稱為緊路徑。其確定方法如下：

(1)記錄可行路徑中車輛在客戶規(guī)定時間窗之前到達客戶點，客戶點的個數(shù)ne，車輛在客戶規(guī)定時間窗之后到達客戶點，客戶點的個數(shù)nl。

(2)可行路徑中每個客戶點的可能調(diào)整量可由式(30)進行計算，若ce·min{Δti}·ne≤cl·min{Δti}·nl，即ce·ne≤cl·nl，則該可行路徑為緊路徑。

(30)

2.6 變鄰域搜索策略

本文采用的鄰域結(jié)構(gòu)為N={N1,N2,…,Ng,…}，首先讓個體i從N1開始擾動，若未找到改進解，則執(zhí)行N2；否則，令x=x′，并返回N1重新開始擾動，若到最后一個鄰域結(jié)構(gòu)仍未找到改進解，則停止搜索。本文的變鄰域操作是0-1Exchange、1-1Exchange和2-OPT：

(1)0-1Exchange：分為線路內(nèi)0-1Exchange和線路間0-1Exchange。隨機選擇客戶i和客戶j，將客戶i插入到客戶j的后面。

(2)1-1Exchange：分為線路內(nèi)1-1Exchange和線路間1-1Exchange。隨機選擇客戶i和客戶j，交換客戶i和客戶j的位置。

(3)2-OPT：分為線路內(nèi)2-OPT和線路間2-OPT。隨機選擇客戶i和客戶j，若客戶i和客戶j不同路，通過交換路徑中部分邊使其相鄰，組成新的路徑。

3 算例驗證及結(jié)果分析

本文參數(shù)設(shè)置如下：最大迭代次數(shù)max_gen=100～1000，種群規(guī)模pop_size=20～100，自適應(yīng)鄰域搜索次數(shù)參數(shù)ε1=0.01～0.5，ε2=0.01～0.02，自適應(yīng)鄰域搜索范圍參數(shù)β1=0.1～0.15，β2=0.2～0.4，控制系數(shù)w=4，時空距離參數(shù)a1=0.5，a2=0.5，α1=2.5，α2=0.95，α3=4.2。

3.1 VRPTW算例驗證

實驗1采用Solomon[15]的VRPTW標準算例進行實驗，文獻[16～19]的求解結(jié)果見表1和附表1。表1中“BKS”表示算例的已知最優(yōu)解，“L”表示本文HG-VNSA的求解結(jié)果，“N”表示使用車輛數(shù)輛，“%Dve”表示本文HG-VNSA的求解結(jié)果相較于已知最優(yōu)解的計算偏差。將Solomon計算的結(jié)果作為標準，把其他算法計算的結(jié)果進行“標準化”，即附表1中“rate”的數(shù)據(jù)均為與Solomon計算結(jié)果的比值，“Mean”表示各算例的比值平均值。

表1：HG-VNSA求出4個算例的已知最優(yōu)解，與已知最優(yōu)解的偏差最大為0.97%，最小為0.17%，均小于1%。分析結(jié)果表明HG-VNSA能夠有效求解小規(guī)模VRPTW算例，具有較強的尋優(yōu)能力。

附表1：HG-VNSA的比值平均值為5.23，均小于SMA、RMPC、AVNS、Modified ACS。分析結(jié)果表明HG-VNSA的可行性和有效性。

表1 小規(guī)模VRPTW算例對比結(jié)果

3.2 SDVRP算例驗證

實驗2選取文獻[20]中的算例進行實驗，文獻[20～22]的求解結(jié)果見表2，本文HG-VNSA算法求出的最優(yōu)路徑見表3，其中“Best”表示各算法求出的最優(yōu)解，“Mean”表示各算法求出的平均解，“CPU”表示各算法運行10次的平均運行時間,“R(loads)”表示行駛路徑(各路徑中各客戶需求滿足量)，“L”表示車輛行駛距離。

表2：HG-VNSA在10次計算結(jié)果中均求出最優(yōu)解，具有較強的穩(wěn)定性。HG-VNSA算法求出的平均值相較于其他算法最大改進了6.49%，最小改進了2.63%。

表2 不同算法的求解結(jié)果對比

表3 HG-VNSA算法求出的最優(yōu)路徑

3.3 VRPSDPTW算例驗證

實驗3文獻[23]對Solomon[15]的VRPTW標準算例進行了擴展。本文選取擴展后的算例進行實驗，文獻[23]的求解結(jié)果見表4，文獻[23～26]的求解結(jié)果見附表2。將Wang[23]采用GA計算的結(jié)果作為標準，把其他算法計算的結(jié)果進行“標準化”，即附表2中“”的數(shù)據(jù)均為與GA計算結(jié)果的比值。

表4：Cplex求出4個算例的最優(yōu)解，GA和HG-VNSA也求出這4個算例的最優(yōu)解。其余5個算例中，只有算例“RCdp2504”和“RCdp2507”，HG-VNSA的求解結(jié)果與GA相同，其余3個算例所求最優(yōu)解與GA最大偏差0.30%，最小偏差0.09%。分析結(jié)果表明HG-VNSA具有較強的尋優(yōu)能力。

附表2：p-SA求出6個算例的已知最好解，其中RCdp201改進最大。DCS求出9個算例的已知最好解，其中RCdp201改進最大，且有2個算例求出的最優(yōu)解少使用一輛車。IGAFSA求出3個算例的已知最好解，其中RCdp208改進最大，且有3個算例求出的最優(yōu)解少使用一輛車。HG-VNSA求出8個算例的已知最好解，其中RCdp205改進最大，且有3個算例求出的最優(yōu)解少使用一輛車。從“”的數(shù)據(jù)可以看出：HGVNSA的比值平均值均小于p-SA、DCS、IGAFSA。分析結(jié)果表明HGVNSA能夠有效求解VRPSDPTW大規(guī)模算例，驗證了HGVNSA的可行性和有效性。

表4 VRPSDPTW中小規(guī)模算例對比結(jié)果

3.4 SDVRPSDP算例驗證

實驗4選取文獻[27]的數(shù)據(jù)進行實驗，結(jié)果見表5。

表5：需求允許拆分策略下的求解結(jié)果優(yōu)于需求不允許拆分。在需求允許拆分策略下進行求解，HG-VNSA求出的最優(yōu)解比蟻群算法少使用1輛車，且行駛距離縮短了0.05%。

表5 SDVRPSDP算例對比結(jié)果

3.5 SDVRPSDPTWP算例驗證

實驗5對3.3節(jié)中的VRPSDPTW標準算例進行修改，生成SDVRPSDPTWP算例。修改如下：EETi=ETi-60,ELTi=LTi+60，客戶最低滿意度ω=0.5，單位時間處理ξ=5單位的貨物，單位時間等待成本ce=2，單位時間延誤成本cl=3，單位理貨成本cd=25，車輛的額定載重Q=200，單位派遣成本ck=100，空載油耗率z1=0.15，滿載油耗率z2=0.23，油價co=6.5。實驗結(jié)果見附表3，其中“C”為最優(yōu)路徑的總配送成本，“CPU”為程序運行時間。

附表3：使用枚舉法只能求出算例規(guī)模為5和10的算例的最優(yōu)解，使用HG-VNSA1和HG-VNSA2也能求出這些算例的最優(yōu)解，在求解客戶規(guī)模為10的算例時，使用HG-VNSA1和HG-VNSA2用時較少。本文設(shè)計的時間優(yōu)化策略在總配送成本方面最大改進了19.653%，最小改進了0.001%，只有算例“RCdp203-15”使用時間優(yōu)化策略前后的求解結(jié)果一樣。

4 結(jié)論

本文對SDVRPSDPTWP進行了研究，主要結(jié)論如下：

(1)為各客戶設(shè)置不同的拆分服務(wù)量，避免了客戶需求量差異過大，拆分閾值設(shè)置不合理的情況。

(2)在算法設(shè)計中，根據(jù)客戶間的時空距離采用最近鄰插入法生成客戶排列，生成高質(zhì)量的初始解。

(3)設(shè)計了時間優(yōu)化策略，調(diào)整車輛的派出時間，盡可能避免在客戶規(guī)定時間窗外到達，降低時間窗懲罰成本。

(4)設(shè)計了混合遺傳變鄰域搜索算法，利用變鄰域搜索算法的深度搜索能力優(yōu)化算法；提出自適應(yīng)搜索策略，避免算法陷入局部最優(yōu)。(5)多組實驗表明本文模型及算法求解SDVRPSDPTWP問題的有效性。