李昆鵬 ,孫欣蕊 ,劉騰博 ,李文莉

(1.華中科技大學(xué) 管理學(xué)院,武漢 430074;2.武漢紡織大學(xué) 管理學(xué)院,武漢 430200)

隨著消費(fèi)者生活水平的提高以及移動(dòng)終端設(shè)備的普及,網(wǎng)絡(luò)購物已經(jīng)成為一種流行趨勢(shì)。截至2019年6月,中國網(wǎng)絡(luò)購物的用戶規(guī)模達(dá)6.39億人,滲透率達(dá)74.8%,網(wǎng)購需求的爆發(fā)式增長為快遞業(yè)的發(fā)展注入了新的活力,2019年人均快遞業(yè)務(wù)量達(dá)72.3件,同比增長13.7%。然而,隨著當(dāng)代生活節(jié)奏不斷加快,公眾時(shí)間日益趨于碎片化,消費(fèi)者對(duì)商品交付的時(shí)效性和準(zhǔn)時(shí)性提出了更高的標(biāo)準(zhǔn),不僅要求商品在更短時(shí)間內(nèi)送達(dá),而且希望送貨時(shí)間更準(zhǔn)確。在多元化、差異化的市場(chǎng)環(huán)境驅(qū)動(dòng)下,2016年京東上線“京準(zhǔn)達(dá)”增值服務(wù),通過在下單環(huán)節(jié)為顧客提供多個(gè)可選的具體配送時(shí)段,將收貨時(shí)間精確至2 h,以滿足不同消費(fèi)群體的便利性需求。隨后,天貓、蘇寧相繼在各自物流系統(tǒng)中推出“準(zhǔn)時(shí)達(dá)”“定時(shí)達(dá)”服務(wù)。由此可見,各大電商企業(yè)開始重視末端物流體系建設(shè),并將“精準(zhǔn)配送、按時(shí)送貨”作為主要目標(biāo),從而進(jìn)一步提升客戶滿意度。然而,配送時(shí)段的精細(xì)化將導(dǎo)致運(yùn)行成本的增加,面對(duì)人力資源短缺和配送資源有限的雙重挑戰(zhàn),如何在滿足送貨時(shí)間要求的同時(shí)控制物流成本,成為當(dāng)前電商企業(yè)在最后一公里訂單交付環(huán)節(jié)亟待解決的難題。

電商企業(yè)采用供應(yīng)商-配送中心-末端網(wǎng)點(diǎn)-客戶的運(yùn)輸網(wǎng)絡(luò)模式對(duì)訂單進(jìn)行配送,其運(yùn)作流程如圖1所示。

圖1 商品配送網(wǎng)絡(luò)

在此模式的末端配送環(huán)節(jié)中,裝載訂單貨物的多輛支線貨車通常在不同時(shí)間點(diǎn)到達(dá)末端網(wǎng)點(diǎn),隨后末端網(wǎng)點(diǎn)對(duì)到達(dá)的訂單貨物利用電車安排最后一站的配送。對(duì)于到達(dá)末端網(wǎng)點(diǎn)的每件訂單貨物均有對(duì)應(yīng)的訂單可得時(shí)間,即該訂單貨物可以進(jìn)行最后一站配送的時(shí)間點(diǎn)。與此同時(shí),在配送企業(yè)提供的“精準(zhǔn)配送”服務(wù)中,每個(gè)訂單均有消費(fèi)者要求的貨物送達(dá)時(shí)間窗。通常末端網(wǎng)點(diǎn)的快遞人員采用集中配送方式對(duì)訂單貨物進(jìn)行最后一站的配送。然而,隨著消費(fèi)者對(duì)物流服務(wù)質(zhì)量要求的不斷提高,商品送達(dá)時(shí)間被劃分得更加細(xì)致,集中配送顯然已無法滿足客戶的時(shí)間要求。因此,為實(shí)現(xiàn)在提供準(zhǔn)時(shí)配送服務(wù)的同時(shí)減少運(yùn)營成本,末端網(wǎng)點(diǎn)必須考慮如下兩個(gè)問題:訂單貨物到達(dá)后立刻安排配送還是等待其他訂單貨物到達(dá)后共同配送;如何在滿足客戶時(shí)間窗要求的條件下規(guī)劃車輛配送路線?；诖?本文在考慮訂單可得時(shí)間和客戶時(shí)間窗的情況下,以最小化總配送距離為目標(biāo)對(duì)末端網(wǎng)點(diǎn)的訂單貨物制定最后一站的配送方案。根據(jù)電商末端配送特點(diǎn),將本文所研究問題提煉為考慮訂單可得時(shí)間和客戶時(shí)間窗的車輛路徑問題(Vehicle Routing Problem with Time Window with Release Dates,VRPTWRD)。

目前,僅有國外較少學(xué)者對(duì)基于訂單可得時(shí)間的車輛路徑問題進(jìn)行了相關(guān)研究,而國內(nèi)關(guān)于此類問題的研究極少。在求解方法上,由于本文所研究的VRPTWRD 具有嚴(yán)格的NP-Hard屬性,對(duì)其進(jìn)行精確求解難度相當(dāng)大,國內(nèi)外學(xué)者主要采用啟發(fā)式算法得到近似最優(yōu)解。在啟發(fā)式算法方面的研究有:Johar等[1]研究了考慮訂單完成時(shí)間和訂單交付截止時(shí)間的車輛路徑問題,提出變鄰域搜索算法;Johar等[2]研究了單機(jī)生產(chǎn)中考慮訂單交付截止日期的協(xié)調(diào)調(diào)度問題,提出變鄰域搜索算法;Cattaruzza等[3]考慮時(shí)間窗和訂單完成時(shí)間研究可多次配送的車輛路徑問題,并設(shè)計(jì)了一種文化基因算法;Liu 等[4]通過給定訂單生產(chǎn)順序研究了訂單可得時(shí)間已知的車輛路徑問題,采用禁忌搜索算法求解并設(shè)計(jì)拉格朗日算法計(jì)算下界;Shelbourne等[5]對(duì)傳統(tǒng)車輛路徑和調(diào)度問題進(jìn)行延伸,在經(jīng)典問題基礎(chǔ)上考慮訂單可得時(shí)間和訂單交付截止時(shí)間,設(shè)計(jì)了一種路徑鏈接算法;Archetti等[6]考慮訂單可得時(shí)間對(duì)單個(gè)車輛多次配送的車輛路徑問題進(jìn)行研究,并提出迭代局部搜索算法;Archetti等[7]考慮隨機(jī)訂單可得時(shí)間的動(dòng)態(tài)旅行商問題,該問題是一個(gè)馬爾科夫決策過程,以配送時(shí)間和等待時(shí)間總和最小為目標(biāo)提出隨機(jī)模型和確定模型,通過再優(yōu)化方法求解;Soman等[8]考慮訂單可得時(shí)間、配送截止時(shí)間和不同類型車隊(duì)的車輛路徑問題,以使庫存成本、配送成本、延誤成本和延遲交貨成本總和最小為目標(biāo)建立混合整數(shù)模型,并用離散搜索算法求解;Zhen等[9]考慮訂單可得時(shí)間以及時(shí)間窗的多倉庫多次配送車輛路徑問題,提出混合整數(shù)模型,并設(shè)計(jì)了混合粒子群優(yōu)化算法和混合遺傳算法;Li等[10]考慮訂單可得時(shí)間、時(shí)間窗及產(chǎn)品和服務(wù)同步車輛路徑問題,提出了自適應(yīng)大鄰域搜索算法。在精確算法求解方面的研究有:Archetti等[11]考慮訂單交付截止日期研究了多階段車輛路徑問題,提出3種模型并針對(duì)每種模型設(shè)計(jì)有效不等式及分支切割算法;Archetti等[12]研究了基于訂單可得時(shí)間的車輛路徑問題的兩個(gè)變體:考慮訂單交付的截止日期并以最小化總配送距離為目標(biāo)構(gòu)建模型;以最小化總配送時(shí)間為目標(biāo)建立數(shù)學(xué)模型;此外,還指出,當(dāng)客戶分布結(jié)構(gòu)呈線性或星型時(shí),可采用動(dòng)態(tài)規(guī)劃方法在多項(xiàng)式時(shí)間內(nèi)求解;Reyes等[13]分析了基于訂單可得時(shí)間和訂單交付截止時(shí)間的車輛路徑問題的復(fù)雜性,并采用動(dòng)態(tài)規(guī)劃方法對(duì)提出的兩個(gè)子問題進(jìn)行求解:客戶分布呈半直線結(jié)構(gòu)的單車配送路徑優(yōu)化問題;客戶分布呈半直線結(jié)構(gòu)且車容不限的車輛路徑問題。

綜上所述,相關(guān)文獻(xiàn)在求解方法上多局限于啟發(fā)式算法,對(duì)精確求解算法的研究較少,如何衡量啟發(fā)式算法獲得的解與最優(yōu)解的差距一直是一個(gè)難題。此外,僅有的精確算法研究均在客戶分布特殊(直線分布或星型分布)條件下進(jìn)行求解,無法適用于客戶位置通常呈現(xiàn)分散性分布的實(shí)際情況?；诖?本文考慮分散式客戶布局,設(shè)計(jì)精確算法研究考慮客戶時(shí)間窗的電商末端配送路徑問題。首先,提出線性的數(shù)學(xué)模型,再通過考慮問題特征,對(duì)基礎(chǔ)模型進(jìn)行改進(jìn),即提出改進(jìn)數(shù)學(xué)模型;然后,設(shè)計(jì)改進(jìn)分支切割算法對(duì)模型求解,為加快算法的收斂速度,不僅提出兩種加速不等式,即容量不等式和多星不等式,通過基于不等式的分離算法提升目標(biāo)函數(shù)的下界,而且通過構(gòu)造方法得到可行解以提升目標(biāo)函數(shù)值的上界;最后,利用實(shí)際數(shù)據(jù)算例比較兩種線性規(guī)劃模型的適用性,通過實(shí)驗(yàn)測(cè)試分析本文提出的有效不等式對(duì)算法的影響,并對(duì)精確算法的可行性和有效性進(jìn)行驗(yàn)證。

1 模型建立

考慮訂單可得時(shí)間和客戶時(shí)間窗的電商末端配送問題屬于VRP 的擴(kuò)展,在此構(gòu)建兩種線性數(shù)學(xué)模型。首先,構(gòu)建該問題的非線性數(shù)學(xué)模型,再對(duì)該模型進(jìn)行線性化處理;然后,基于客戶需求量、訂單可得時(shí)間和客戶時(shí)間窗等要求,在線性基礎(chǔ)模型基礎(chǔ)上,考慮裝載能力約束和時(shí)間窗約束,從而構(gòu)建改進(jìn)數(shù)學(xué)模型,以減少最優(yōu)解的搜索空間。

1.1 問題描述及假設(shè)條件

本文研究的VRPTWRD 可描述為:末端網(wǎng)點(diǎn)覆蓋區(qū)域內(nèi)有n個(gè)客戶,共配備K輛車對(duì)這些客戶的訂單貨物進(jìn)行配送,每個(gè)客戶訂單不僅有訂單貨物送達(dá)客戶的時(shí)間窗要求,而且有訂單貨物通過支線運(yùn)輸?shù)竭_(dá)末端網(wǎng)點(diǎn)的訂單可得時(shí)間,即可安排車輛進(jìn)行末端配送的時(shí)間。因此,基于客戶時(shí)間窗和訂單可得時(shí)間,以車輛總行駛距離最小為目標(biāo),在滿足客戶時(shí)間窗、配送車輛最大裝載能力及最長工作時(shí)間等約束下,決策車輛與客戶的服務(wù)關(guān)系,并對(duì)車輛訪問客戶的配送路線進(jìn)行規(guī)劃,使所有客戶的商品需求能在相應(yīng)時(shí)間窗內(nèi)送達(dá)。

為方便建模,考慮如下假設(shè):

(1)所有車輛同質(zhì)且行駛速度相同。

(2)不考慮商品在末端網(wǎng)點(diǎn)的分揀時(shí)間。

(3)客戶的需求量在車輛最大裝載量范圍內(nèi)。

(4)每輛車進(jìn)行單次配送。

(5)每個(gè)客戶僅由一輛車單次訪問。

1.2 數(shù)字符號(hào)及解釋

模型中涉及的符號(hào)及解釋:

N={0,1,…,n,n+1}——節(jié)點(diǎn)集合,其中0和n+1表示同一末端網(wǎng)點(diǎn)節(jié)點(diǎn),即車輛的起點(diǎn)和終點(diǎn)

Nc={1,2,…,n}——客戶節(jié)點(diǎn)集合

V={0,1,…,K-1}——車輛集合

dij——節(jié)點(diǎn)i～j的行駛距離

tij——車輛服務(wù)節(jié)點(diǎn)i的時(shí)間與從節(jié)點(diǎn)i～j的行駛時(shí)間之和,即服務(wù)節(jié)點(diǎn)i的時(shí)間包含在行駛時(shí)間tij內(nèi)

Q——車輛最大裝載量

T——車輛最長工作時(shí)間

qi——客戶i的貨物量

ri——客戶i的訂單可得時(shí)間

[Ei,Li]——客戶i的時(shí)間窗限制,Ei和Li分別表示客戶i要求車輛對(duì)其服務(wù)的最早開始時(shí)間和最遲結(jié)束時(shí)間

M——非負(fù)的極大值

模型中涉及的變量及解釋:

——0-1變量,等于1表示車輛k從節(jié)點(diǎn)i行駛至節(jié)點(diǎn)j,否則為0

——0-1變量,等于1表示客戶j被車輛k服務(wù),否則為0

DTk——非負(fù)變量,車輛k從網(wǎng)點(diǎn)出發(fā)開始配送的時(shí)間

ATk——非負(fù)變量,車輛k完成配送任務(wù)后返回網(wǎng)點(diǎn)的時(shí)間

Ai——非負(fù)變量,車輛到達(dá)客戶i的時(shí)間

Bi——非負(fù)變量,車輛服務(wù)客戶i的時(shí)間

1.3 基礎(chǔ)數(shù)學(xué)模型

1.3.1 模型構(gòu)建

目標(biāo)函數(shù)式(1)表示車輛的總行駛距離最小;式(2)、(3)表示所有車輛從網(wǎng)點(diǎn)出發(fā)完成配送任務(wù)后返回網(wǎng)點(diǎn);式(4)表示每個(gè)客戶只能被一輛車訪問;式(5)表示車輛裝載量不超過最大裝載能力;式(6)、(7)為車輛流平衡約束;式(8)、(9)表示每輛車開始配送的時(shí)間大于等于所服務(wù)客戶的訂單可得時(shí)間,且該時(shí)間不能超過最長工作時(shí)間限制;式(10)表示客戶實(shí)際被服務(wù)時(shí)間為車輛到達(dá)時(shí)間與要求最早開始服務(wù)時(shí)間的較大值,即若車輛提前到達(dá)則等待至最早開始服務(wù)時(shí)間;式(11)表示客戶被服務(wù)時(shí)間不能超過其要求的最遲結(jié)束時(shí)間;式(12)、(13)描述了Aj與Bi+tij的關(guān)系,當(dāng)車輛k從客戶節(jié)點(diǎn)i行駛至客戶節(jié)點(diǎn)j時(shí),車輛k到達(dá)節(jié)點(diǎn)j處的時(shí)間等于車輛k開始服務(wù)客戶i的時(shí)間與兩節(jié)點(diǎn)間的旅行時(shí)間之和,即Aj=Bi+tij;當(dāng)車輛k未從節(jié)點(diǎn)i行駛至節(jié)點(diǎn)j時(shí),因?yàn)镸是一個(gè)非負(fù)的極大值,所以有Bi+tij-M<0,Bi+tij+M>M,故式(12)、(13)恒成立。式(14)表示當(dāng)車輛k從末端網(wǎng)點(diǎn)節(jié)點(diǎn)0行駛至客戶節(jié)點(diǎn)i時(shí),保證了車輛服務(wù)客戶i的時(shí)間大于等于車輛離開節(jié)點(diǎn)0的時(shí)間和從節(jié)點(diǎn)0到客戶i的行駛時(shí)間的總和;當(dāng)車輛k未從末端網(wǎng)點(diǎn)節(jié)點(diǎn)0行駛至客戶節(jié)點(diǎn)i時(shí),因?yàn)镸是一個(gè)非負(fù)的極大值,所以有DTk+t0i-M<0,故式(14)依然成立。式(15)表示當(dāng)車輛k從客戶節(jié)點(diǎn)i行駛至客戶節(jié)點(diǎn)j時(shí),保證了車輛服務(wù)客戶節(jié)點(diǎn)j的時(shí)間大于等于車輛服務(wù)客戶節(jié)點(diǎn)i的時(shí)間和從客戶節(jié)點(diǎn)i～j的行駛時(shí)間的總和;當(dāng)車輛k未從客戶節(jié)點(diǎn)i行駛至客戶節(jié)點(diǎn)j時(shí),因?yàn)镸是一個(gè)非負(fù)的極大值,所以有Bi+tij-M<0,故式(15)依然成立。式(16)表示當(dāng)車輛k從客戶節(jié)點(diǎn)i行駛至末端網(wǎng)點(diǎn)節(jié)點(diǎn)n+1時(shí),保證了車輛服務(wù)客戶節(jié)點(diǎn)j的時(shí)間大于等于車輛服務(wù)客戶節(jié)點(diǎn)i的時(shí)間和從客戶節(jié)點(diǎn)i～j的行駛時(shí)間的總和;當(dāng)車輛k未從客戶節(jié)點(diǎn)i行駛至末端網(wǎng)點(diǎn)節(jié)點(diǎn)n+1時(shí),因?yàn)镸是一個(gè)非負(fù)的極大值,所以有Bi+ti,n+1-M<0,故式(16)依然成立。由此,式(14)～(16)確定了任意一輛車k服務(wù)節(jié)點(diǎn)的序列,繼而阻止了子回路出現(xiàn)的情況。式(17)表示車輛完成配送任務(wù)后返回到末端網(wǎng)點(diǎn)的時(shí)間不能超過其最長工作時(shí)間限制。式(18)表示當(dāng)車輛k從節(jié)點(diǎn)0處出發(fā)開始配送后訪問的第1個(gè)節(jié)點(diǎn)是客戶i時(shí),車輛k離開節(jié)點(diǎn)0的時(shí)間和到達(dá)客戶i處的時(shí)間關(guān)系滿足Ai≥DTk+t0i;當(dāng)車輛k從節(jié)點(diǎn)0處出發(fā)開始配送后訪問的第1個(gè)節(jié)點(diǎn)不是客戶i時(shí),因?yàn)镸是一個(gè)非負(fù)的極大值,所以有DTk+t0i-M<0,從而松弛了Ai的下界。式(19)、(20)表示0-1變量,式(21)～(23)表示非負(fù)變量。

1.3.2 時(shí)間窗約束線性化 因VRPTWRD 考慮客戶的硬時(shí)間窗限制,要求車輛必須在時(shí)間窗內(nèi)服務(wù)客戶,如果車輛在客戶的時(shí)間窗之前到達(dá),則需等待至客戶要求的最早開始時(shí)間,表示為約束式(10),即Bi=max{Ai,Ei},?i∈Nc。由于該約束為非線性形式,導(dǎo)致式(1)～(23)無法利用CPLEX 求解,故引入0-1 變量u0i,?i∈N{0,n+1}對(duì)式(10)進(jìn)行線性化處理,將式(10)替換為如下約束:

根據(jù)式(24)～(29),當(dāng)u0i=1時(shí),表示車輛到達(dá)時(shí)間大于客戶要求的最早開始服務(wù)時(shí)間,則到達(dá)時(shí)間即為實(shí)際開始服務(wù)時(shí)間,即Bi=Ai;當(dāng)u0i=0時(shí),表示到達(dá)時(shí)間小于最早開始服務(wù)時(shí)間,則配送車輛在客戶處等待直至客戶要求的最早開始時(shí)間再進(jìn)行服務(wù),即Bi=Ei。

由此得到本文線性基礎(chǔ)數(shù)學(xué)模型:

s.t.式(2)～(9),式(11)～(29)

1.4 改進(jìn)數(shù)學(xué)模型

由于本文所研究問題的高度復(fù)雜性,實(shí)驗(yàn)表明,當(dāng)數(shù)據(jù)規(guī)模不斷增大時(shí),CPLEX 求解基礎(chǔ)模型運(yùn)算時(shí)間非常長。為實(shí)現(xiàn)高效求解,從車輛裝載能力和客戶配送時(shí)間需求兩方面考慮,對(duì)基礎(chǔ)模型進(jìn)行改進(jìn),從而提高模型求解效率,并在3.2節(jié)將其與本文“基礎(chǔ)模型”進(jìn)行比較性分析。

1.4.1 車輛裝載能力約束 如果任意兩個(gè)客戶的總需求量大于車輛的裝載能力,則它們不能由同一輛車進(jìn)行配送,從而下列約束是有效的,即:

表示需求量大于0.5 倍車輛最大裝載量的客戶集合,符合該條件的客戶數(shù)為|V1|,顯然,該集合中任意兩個(gè)客戶不能由同一輛車進(jìn)行配送。因此,|V1|個(gè)客戶可分配給|V1|輛車。首先,將每一個(gè)客戶點(diǎn)j∈V1預(yù)先分配給固定的車輛k∈V,即存在如下形式:

其次,令

表示滿足客戶點(diǎn)j所在車輛k的容量約束的客戶集合,則有:

其中:式(33)表示客戶j所在車輛k的裝載量不超過它的裝載能力;式(34)、(35)表示如果存在客戶i滿足qi+qj>Q時(shí),則客戶i、j不能由同一車輛訪問。

最后,令

1.4.2 客戶點(diǎn)的時(shí)間窗約束 若存在滿足條件Ei+tij>Lj的客戶i,j∈N{0,n+1},則同一輛車不能先后訪問客戶i和客戶j;否則,客戶j無法在規(guī)定的時(shí)間窗內(nèi)被服務(wù)。因此,有

從而得到本文線性優(yōu)化數(shù)學(xué)模型:

s.t.式(2)～(9),式(11)～(37)

2 改進(jìn)分支切割算法

2.1 初始解生成

為在保證找到最優(yōu)解的前提下,盡可能地減小搜索空間以提高搜索效率,本文提出了一種改進(jìn)的分支切割算法求解考慮訂單可得時(shí)間和客戶時(shí)間窗的車輛路徑規(guī)劃問題。首先采用構(gòu)造啟發(fā)式算法得到一個(gè)可行解s,然后對(duì)可行解的每條行駛路線進(jìn)行局部優(yōu)化,從而得到一個(gè)較優(yōu)的初始解s0,將其作為目標(biāo)函數(shù)值的上界s。

2.1.1 構(gòu)造啟發(fā)式算法 構(gòu)造啟發(fā)式算法過程如下:令v表示第v輛車的路線;Nv為第v輛車已訪問的客戶集合;客戶點(diǎn)ev為Nv中被訪問的最后一個(gè)客戶點(diǎn);Cv為第v輛車基于ev可插入的下一個(gè)客戶的集合;W為未被訪問的客戶集合。初始化v=0,Cv=?,Nv={0},ev=0,W=Nc。

步驟1判斷W是否為空集?,若是,則停止運(yùn)行。

步驟2從集合W中尋找滿足如下3個(gè)條件的客戶,將其添加到Cv:

(1)該客戶未被訪問;

(2)將該客戶插入到第v條路徑中,滿足車輛裝載量約束;

(3)將該客戶插入到第v條路徑中,車輛到達(dá)客戶的時(shí)間不超過該客戶被訪問的最遲時(shí)間。

步驟3如果Cv=?,檢測(cè)是否所有客戶都已被訪問,若是,則停止運(yùn)行并輸出結(jié)果;否則,令v=v+1,Cv=?,Nv={0},返回步驟2。

步驟4如果Cv≠?,則選取客戶j'=arg min(cjv)j∈Cv,將其添加至Nv中,并標(biāo)記j'為已被訪問狀態(tài),ev=j'。令W=W{j'},返回步驟1。

在上述過程中,cjv為評(píng)估函數(shù),用來選取車輛將要訪問的下一個(gè)客戶。對(duì)于車輛v,當(dāng)前已確定的最后一個(gè)訪問客戶ev,Sev,v為車輛v開始服務(wù)客戶ev的時(shí)間,tev,j為客戶ev、j之間的行駛時(shí)間,兩者之和為車輛v從客戶ev行使到客戶j的實(shí)際時(shí)間Ajv,Ej和Lj分別為客戶j要求的最早和最遲服務(wù)時(shí)間,客戶j滿足實(shí)際到達(dá)時(shí)間與最早服務(wù)時(shí)間之間的差值為Tjv,計(jì)算方法為

通?？紤]兩種度量方法來評(píng)估插入的客戶j:第1種方法是考慮距離dev,j;第2 種方法是考慮Tjv。然而,為了平衡dev,j和Tjv,評(píng)估函數(shù)cjv考慮兩種方法的加權(quán),即

2.1.2 可行解的局部優(yōu)化 在得到可行解集合的基礎(chǔ)上,對(duì)集合中任意可行解s進(jìn)行局部優(yōu)化,從而獲得一個(gè)較優(yōu)的初始解?？尚薪鈙包含|V|條路線。首先,令Ck表示可行解s中車輛k訪問的客戶集合,|Ck|為車輛k訪問的客戶數(shù),則{C1,…,Ck}為s中所有行駛路線對(duì)應(yīng)的客戶集合。

考慮到可行解s中的路線可能不是最優(yōu)路線,利用CPLEX 求解模型式(39)～(47)對(duì)每條路線重新優(yōu)化,從而獲得一個(gè)較優(yōu)初始解s0,將其作為目標(biāo)函數(shù)值的上界。Ck(0≤k≤K-1)為車輛k服務(wù)的客戶集合。為構(gòu)建單條路徑優(yōu)化模型,引入0-1變量wij,如果車輛從節(jié)點(diǎn)i行駛至節(jié)點(diǎn)j,則wij=1;否則,wij=0。非負(fù)變量ti,表示訪問客戶i的時(shí)間,

其中:式(39)表示車輛k的總配送距離最小;式(40)、(41)表示車輛k從末端網(wǎng)點(diǎn)出發(fā)完成配送任務(wù)后返回末端網(wǎng)點(diǎn);式(42)表示每個(gè)屬于Ck的客戶僅被車輛k訪問一次;式(43)為車輛流平衡約束;式(44)表示車輛服務(wù)客戶時(shí)間滿足客戶的時(shí)間窗要求;式(45)描述了車輛k開始服務(wù)節(jié)點(diǎn)j∈Ck的時(shí)間tj和車輛k開始服務(wù)節(jié)點(diǎn)i∈Ck的時(shí)間ti之間的關(guān)系,當(dāng)車輛k先后連續(xù)訪問節(jié)點(diǎn)i、j時(shí),車輛開始服務(wù)節(jié)點(diǎn)i的時(shí)間ti和車輛開始服務(wù)節(jié)點(diǎn)j的時(shí)間tj之間的關(guān)系,則tj≥ti+tij;當(dāng)車輛k未從節(jié)點(diǎn)i行駛至節(jié)點(diǎn)j時(shí),因?yàn)镸是一個(gè)非負(fù)的極大值常量,所以有ti+tij-M<0,故式(45)恒成立。式(46)、(47)分別為0-1變量和非負(fù)變量約束。

2.2 切割面的產(chǎn)生

由于VRPTWRD 的線性松弛模型包含式(1)～(9)、式(11)～(17)、式(20)～(37)以及式(18)、(19)的松弛:0≤≤1,?i,j∈N,?k∈V;0≤≤1,?j∈N,?k∈V,故相較于原始模型,線性松弛模型的可行域(包含整數(shù)可行解和小數(shù)可行解)更大。分支切割算法是基于線性松弛模型的可行域而設(shè)計(jì)的,并最終獲得原始模型的最優(yōu)解。因此,為得到原始模型的最優(yōu)解,需要利用切割面割去松弛模型可行域中的小數(shù)可行解?；诖?根據(jù)問題特征,本節(jié)考慮容量不等式和多星不等式,并設(shè)計(jì)相應(yīng)的算法生成切割面。

2.2.1 容量不等式切割面產(chǎn)生 令S?Nc表示客戶集合=NS為S的余集,r(S)為S中客戶最少需要的車輛數(shù)。對(duì)于任意可行解,每個(gè)客戶不僅被一輛車單次訪問,而且滿足運(yùn)輸流的平衡;每輛車從末端網(wǎng)點(diǎn)0出發(fā),完成配送任務(wù)后返回末端網(wǎng)點(diǎn)n+1。因此,令

表示一個(gè)端點(diǎn)在S中、一個(gè)端點(diǎn)在中的邊的集合,則配送車輛經(jīng)過集合E中邊的個(gè)數(shù)至少為2r(S),可由如下形式表示:

由于r(S)的計(jì)算涉及裝箱問題,而裝箱問題屬于NP難問題。為了計(jì)算簡(jiǎn)便,考慮r(S)的下界代替r(S),從而有

在分支切割算法對(duì)應(yīng)的枚舉搜索樹中的每個(gè)節(jié)點(diǎn)處,令z*為當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的松弛模型最優(yōu)解。當(dāng)z*是小數(shù)解時(shí),z*不是原模型的最優(yōu)解,則需要考慮切割面切割掉z*。切割面的生成方法就是尋找被z*所違反的有效不等式,而被z*所違反的有效不等式是基于z*構(gòu)造的加權(quán)無向圖得到的。構(gòu)造加權(quán)無向圖G*的方法[15]為:G*=(N,E*),其中,N=Nc∪{0,n+1}是節(jié)點(diǎn)集合,

G*中每條邊[i,j]∈E*的權(quán)值為。由于在VRPTWRD 的任意一個(gè)可行解中,車輛均從節(jié)點(diǎn)0出發(fā),在完成配送任務(wù)后回到節(jié)點(diǎn)n+1,以及每個(gè)客戶節(jié)點(diǎn)被一輛車有且僅訪問一次,故G*是連通的[15],并且連通分圖個(gè)數(shù)為1。由此可知,若G*有多個(gè)連通分圖,則z*是不可行解。

為描述尋找被z*所違反的容量不等式的方法,首先,根據(jù)式(49)和G*,對(duì)于?S?Nc,定義

當(dāng)f(S)<0時(shí),就確定一個(gè)被z*所違反的容量不等式:

其次,定義圖G*的連通分支G(C)*=表示,其中,C?N,

最后,確定所考慮的被z*違反的容量不等式個(gè)數(shù)的最大值maxN。通過實(shí)驗(yàn)測(cè)試發(fā)現(xiàn),由于在節(jié)點(diǎn)搜索樹的子節(jié)點(diǎn)處考慮分支比考慮添加切割面的效果更好,故考慮在根節(jié)點(diǎn)處尋找較多的被z*所違反的容量不等式,在子節(jié)點(diǎn)處尋找較少的被z*所違反的容量不等式。因此,令maxN表示確定的容量不等式個(gè)數(shù)的最大值,如果當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn),則maxN=100;否則,maxN=8。在此基礎(chǔ)上,通過如下方法(6個(gè)步驟)確定被z*所違反的容量不等式,即得到切割面。

步驟1首先計(jì)算當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的加權(quán)無向圖G*連通分支。

步驟2如果加權(quán)無向圖G*存在p(≥1)個(gè)連通子圖G(Ci)*,Ci?Nc,?i∈{1,2,…,p},則對(duì)任意=0,從而

因此違反式(49)。由此可以確定p個(gè)被z*所違反的容量不等式

步驟3如果G*是連通的,則令j表示客戶點(diǎn)數(shù),l表示確定的違反z*的容量不等式的個(gè)數(shù),并初始化為:j=1,l=0。

步驟4從客戶集合Nc中選取包含j個(gè)元素的所有子集,…,(q為子集個(gè)數(shù))。

步驟5對(duì)每個(gè)子集,計(jì)算是否小于等于-0.2。如果≤-0.2,則確定一個(gè)被z*所違反的容量不等式

并且l=l+1;如果l>maxN,則停止。

步驟6令j=j+1,如果j<|N|-2,返回步驟4;否則,終止算法。

2.2.2 多星不等式切割面產(chǎn)生 多星不等式由Araque等[14]針對(duì)CVRP提出的,即考慮S?Nc,具有如下形式:

稱S?Nc為核,T?N({0}∪S)為衛(wèi)星,α、β和γ是依賴于|S|和|T|的常量。

本文研究的問題是在CVRP的基礎(chǔ)上,考慮了訂單可得時(shí)間和時(shí)間窗等特性,因此,式(50)同樣適用于本問題。又因?yàn)長etchford等[15]表明多面體程序可以生成式(50)的所有形式,并且提出了基于多面體程序的切割面方法,通過實(shí)驗(yàn)證明具有很好的效果[11]。鑒于此,采用Letchford等提出的方法尋找違反的多星不等式。對(duì)搜索樹的根節(jié)點(diǎn),限制每次迭代添加到松弛模型中的多星不等式不超過100;對(duì)于子節(jié)點(diǎn),限制每次迭代添加到松弛模型中的多星不等式的個(gè)數(shù)不超過8。

2.3 分支策略

2.4 基于改進(jìn)的分支切割算法的求解流程

由于初步試驗(yàn)(3.2節(jié))表明改進(jìn)的數(shù)學(xué)模型可以減少最優(yōu)解的搜索空間,從而加快求解速度,故本文改進(jìn)的分支切割算法基于改進(jìn)數(shù)學(xué)模型采取如下步驟:

步驟1初始化。根據(jù)2.1節(jié)得到初始解z0,zbest表示目標(biāo)最優(yōu)解,zbest←z0。令Φ表示活躍節(jié)點(diǎn)的集合,當(dāng)前活躍節(jié)點(diǎn)t為根節(jié)點(diǎn)0,并將其添加到Φ。

步驟2求解2.3節(jié)中的改進(jìn)數(shù)學(xué)模型,得到解z*t。

步驟3若為不可行解,則令Φ←Φ{t},轉(zhuǎn)至步驟6。

步驟4若為整數(shù)可行解,且

步驟5若為小數(shù)可行解,且當(dāng)前活躍節(jié)點(diǎn)t為根節(jié)點(diǎn),根據(jù)2.2節(jié),確定切割面。若存在被所違反的有效不等式,則將其添加到模型中,重新求解;否則,轉(zhuǎn)至步驟7。

步驟6節(jié)點(diǎn)選擇。若Φ為空集,則算法停止;否則,根據(jù)下界最優(yōu)策略[16]選擇一個(gè)節(jié)點(diǎn)t進(jìn)行求解,令Φ←Φ{t},返回步驟3。

步驟7分支。從|?j∈{0,n+1},?k∈V}中選取一個(gè)對(duì)應(yīng)解為小數(shù)解的變量進(jìn)行分支,生成兩個(gè)子節(jié)點(diǎn),將它們添加到Φ。

3 數(shù)值實(shí)驗(yàn)及分析

本節(jié)基于某末端網(wǎng)點(diǎn)的實(shí)際配送情況,生成測(cè)試算例,對(duì)提出的改進(jìn)的分支數(shù)學(xué)模型切割算法進(jìn)行一系列測(cè)試,并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。首先,說明數(shù)據(jù)來源及相應(yīng)參數(shù),然后通過與基礎(chǔ)模型比較分析改進(jìn)數(shù)學(xué)模型的效果;其次,分析算法中提出的容量不等式和多星不等式的求解性能;最后,對(duì)CPLEX 與改進(jìn)分支切割算法求解結(jié)果進(jìn)行比較性分析,以此驗(yàn)證本文算法的有效性。所有測(cè)試均在同一環(huán)境中進(jìn)行,操作系統(tǒng)為64位Windows 10,運(yùn)行內(nèi)存為8 GB,CPU 為Intel(R)Core(TM)i5-6200U,主頻為2.3 GHz,采用CPLEX 作為模型求解器,啟發(fā)式算法采用C++編譯。

3.1 測(cè)試算例及參數(shù)

實(shí)際中每天都會(huì)有多輛運(yùn)輸車到達(dá)末端網(wǎng)點(diǎn),并且對(duì)于當(dāng)日到達(dá)的貨物通常不能在第二天進(jìn)行配送。因此,隨機(jī)選取一天中某時(shí)段內(nèi)的配送信息獲取客戶具體位置,再利用地圖軟件得到末端網(wǎng)點(diǎn)及所有客戶的位置(客戶的經(jīng)度和緯度),從而計(jì)算任意兩個(gè)客戶點(diǎn)之間的距離。在此基礎(chǔ)上,構(gòu)造8組不同客戶規(guī)模的算例進(jìn)行測(cè)試,每種規(guī)模均隨機(jī)生成5個(gè)算例,共40個(gè)算例,各項(xiàng)實(shí)驗(yàn)參數(shù)如表1所示(U[a,b]表示服從[a,b]的均勻分布)。

表1 實(shí)驗(yàn)參數(shù)

3.2 改進(jìn)模型性能測(cè)試

為評(píng)估在改進(jìn)數(shù)學(xué)模型中加入車輛裝載能力約束和客戶時(shí)間窗約束的必要性,采用優(yōu)化軟件CPLEX 分別對(duì)基礎(chǔ)模型和改進(jìn)數(shù)學(xué)模型進(jìn)行求解,表2所示為CPLEX 在1 h內(nèi)對(duì)兩種模型的測(cè)試結(jié)果。第1列為算例名稱,例如:“25_1”表示客戶數(shù)為25的第1個(gè)算例;第2～5列是求解基礎(chǔ)模型后的結(jié)果,第6～9列是求解改進(jìn)的數(shù)學(xué)模型后的結(jié)果;UB和LB 分別表示求解得到的上界和下界;Time表示運(yùn)行時(shí)間(s);Gap表示上下界所形成的百分比差距,將其作為求解質(zhì)量的評(píng)價(jià)標(biāo)準(zhǔn),計(jì)算公式為:Gap=(100%)×(UB-LB)/UB。

表2結(jié)果表明:

(1)在規(guī)定運(yùn)行時(shí)間內(nèi),相比于基礎(chǔ)數(shù)學(xué)模型,改進(jìn)的數(shù)學(xué)模型可以得到兩個(gè)小規(guī)模算例的最優(yōu)解,說明對(duì)基礎(chǔ)模型進(jìn)行優(yōu)化可有效縮短求解時(shí)間。同時(shí)也可推斷出,若增加運(yùn)行時(shí)間,改進(jìn)的數(shù)學(xué)模型可獲得最優(yōu)解。

(2)對(duì)于上下界之間的差距,由圖2可知,在相同求解時(shí)間內(nèi),優(yōu)化模型所得上下界之間的差距明顯較小,且在小規(guī)模算例中能夠求得最優(yōu)解。

圖2 數(shù)學(xué)模型與優(yōu)化模型的上下界Gap值比較

(3)對(duì)于兩種模型在相同時(shí)間內(nèi)得到的下界,計(jì)算可知,改進(jìn)數(shù)學(xué)模型在運(yùn)行1 h內(nèi)能將下界平均提高23.8%,求解能力更強(qiáng)。綜上所述,由于CPLEX 求解時(shí)間隨著數(shù)據(jù)規(guī)模的增大呈指數(shù)型增長,非常有必要加入合適的約束以提高求解效率,而本文所提出的改進(jìn)模型能夠有效減少搜索空間、加快求解速度,具有一定的科學(xué)性。

3.3 有效不等式性能測(cè)試

為分析在改進(jìn)分支切割算法中所提出的有效不等式對(duì)目標(biāo)值下界的提升效果,考慮在搜索樹的根節(jié)點(diǎn)處添加不同的有效不等式,并比較它們對(duì)根節(jié)點(diǎn)處下界值的影響,表3所示為CPLEX 在1 h內(nèi)的運(yùn)行結(jié)果。第1列為算例名稱,第2列表示在搜索樹的根節(jié)點(diǎn)處求解優(yōu)化模型的下界結(jié)果,第3列表示基于改進(jìn)數(shù)學(xué)模型僅加入容量不等式(Capacity)的下界值,第4列表示基于改進(jìn)數(shù)學(xué)模型僅加入多星不等式(Multistar)的下界值,第5 列表示將兩種不等式(Full)均加入改進(jìn)數(shù)學(xué)模型的下界值,第6～8列表示相比于求解M2得到的下界,加入容量不等式、多星不等式等情形下得到的下界分別提升的Gap值。

表3 有效不等式結(jié)果比較

表3結(jié)果表明:

(1)對(duì)于3種處理方式下的Gap值,由圖3可知,在搜索樹的根節(jié)點(diǎn)處同時(shí)考慮容量不等式和多星不等式方式下幾乎所有算例(除40_1)均得到最好的Gap值。

圖3 不同處理方式的Gap值比較

(2)對(duì)于3種處理方式下的平均下界,由圖4可知,在搜索樹的根節(jié)點(diǎn)處,相比于求解模型下的平均下界,3種處理方式均能不同程度地提高搜索樹根節(jié)點(diǎn)處的下界。此外,同時(shí)考慮兩種不等式具有最好的平均下界。綜上所述,容量不等式和多星不等式均可有效提高下界,減少搜索空間;相比于容量不等式,多星不等式的效果較好;在搜索樹的根節(jié)點(diǎn)處,相比于單獨(dú)考慮一種有效不等式的添加策略,同時(shí)考慮兩種不等式是最好的不等式添加策略。因此,在改進(jìn)的分支切割算法中,在搜索樹的節(jié)點(diǎn)處將同時(shí)考慮容量不等式和多星不等式作為添加策略。

圖4 不同處理方式的平均下界值

3.4 改進(jìn)分支切割算法效果測(cè)試

為驗(yàn)證算法的求解效果,采用3.1節(jié)生成的40個(gè)算例進(jìn)行測(cè)試,并將其結(jié)果與CPLEX 求解改進(jìn)數(shù)學(xué)模型的結(jié)果進(jìn)行比較。設(shè)定每個(gè)算例的最大允許測(cè)試時(shí)間為1 h,兩種方法的計(jì)算結(jié)果如表4所示。其中:CPLEX 表示優(yōu)化模型求解結(jié)果;UB、LB和Time分別表示獲得的上界、下界和求解時(shí)間;Gap表示上下界之間的百分比差異;粗體表示在規(guī)定時(shí)間內(nèi)找到了問題的最優(yōu)解;“*”表示均得到最優(yōu)解但所耗費(fèi)求解時(shí)間相對(duì)較短。

表4 改進(jìn)分支切割算法與CPLEX默認(rèn)分支切割算法的比較結(jié)果

為了從整體比較兩種方法的求解效果,按照客戶規(guī)模不同對(duì)表5結(jié)果進(jìn)行匯總。如表5所示,包括兩種方法得到的最優(yōu)解數(shù),每種客戶規(guī)模所包含5個(gè)算例的平均Gap值及平均求解時(shí)間。

表5 兩種方法求解結(jié)果總結(jié)

根據(jù)上述計(jì)算結(jié)果,由表4可知,對(duì)40個(gè)算例在規(guī)定的1 h內(nèi)求解,改進(jìn)分支切割算法能夠獲得33個(gè)算例的最優(yōu)解,而CPLEX 只能得到13個(gè)算例的最優(yōu)解;對(duì)于此13個(gè)算例,改進(jìn)的分支切割算法同樣能獲得最優(yōu)解,并且求解時(shí)間相對(duì)較短的算例數(shù)達(dá)到10個(gè);針對(duì)改進(jìn)分支切割算法未在規(guī)定時(shí)間內(nèi)獲得最優(yōu)解的7個(gè)算例,由Gap可知所獲得上下界之間的差距均在8%內(nèi),若增加運(yùn)行時(shí)間將很快得到最優(yōu)解。由表5可知,對(duì)于小規(guī)模算例(n=25),兩種方法均可在較短時(shí)間內(nèi)得到最優(yōu)解,但隨著客戶規(guī)模的增大,CPLEX 默認(rèn)的分支切割算法只能獲得個(gè)別算例的最優(yōu)解,且耗費(fèi)時(shí)間很長,而改進(jìn)分支切割算法仍能在較短時(shí)間內(nèi)得到最優(yōu)解。當(dāng)客戶數(shù)達(dá)到55、60時(shí),兩種方法均存在無法獲得最優(yōu)解的情況,但改進(jìn)分支切割算法所得上下界之間的差距明顯小于CPLEX 求解結(jié)果。此外,改進(jìn)分支切割算法可以得到33個(gè)算例的最優(yōu)解,而CPLEX則對(duì)大規(guī)模算例無能為力。綜上所述,CPLEX 默認(rèn)的分支切割算法求解線性規(guī)劃模型,對(duì)于小規(guī)模問題能夠在短時(shí)間內(nèi)獲得最優(yōu)解,但在求解大規(guī)模問題時(shí)通常求解時(shí)間過長甚至無法求解;而改進(jìn)分支切割算法能夠在保證求解質(zhì)量的同時(shí)有效減少求解時(shí)間,且對(duì)于大規(guī)模的算例,能夠在合理時(shí)間內(nèi)獲得近似最優(yōu)解,可為相關(guān)問題的啟發(fā)算法提供很好的下界。

4 結(jié)語

本文考慮訂單可得時(shí)間和客戶時(shí)間窗的電商末端配送路徑問題不僅對(duì)提高城市末端配送效率具有重要的現(xiàn)實(shí)意義,而且對(duì)車輛路徑問題(VRP)進(jìn)行擴(kuò)展具有重要的理論意義。根據(jù)電商末端配送特點(diǎn)和客戶的配送需求構(gòu)建了基礎(chǔ)數(shù)學(xué)模型,并對(duì)其進(jìn)行線性化處理。同時(shí),為減少解的搜索空間,根據(jù)問題特性,即車輛的裝載能力和客戶配送需求,構(gòu)建了優(yōu)化數(shù)學(xué)模型。此外,設(shè)計(jì)了包含分離有效不等式算法的改進(jìn)分支切割算法對(duì)模型進(jìn)行提升。最后,基于實(shí)際算例,通過兩種模型的對(duì)比,表明優(yōu)化數(shù)學(xué)模型具有很強(qiáng)的實(shí)用性。通過與CPLEX 默認(rèn)的分支切割算法對(duì)比,體現(xiàn)了改進(jìn)的分支切割算法的優(yōu)越性和必要性。所設(shè)計(jì)的模型對(duì)提高城市末端配送提供了較好的解決思路,與此同時(shí),對(duì)于小規(guī)模算例,所提出的精確算法可為城市末端配送系統(tǒng)的路線優(yōu)化提供新的思路方法;對(duì)于大規(guī)模算例,已有研究多設(shè)計(jì)啟發(fā)式算法進(jìn)行求解,所提出的算法可作為評(píng)估末端配送系統(tǒng)優(yōu)化路線方案優(yōu)劣的工具。

本文考慮了訂單可得時(shí)間和客戶時(shí)間窗的電商末端配送問題的車輛單次配送情況。然而,在實(shí)際中,末端網(wǎng)點(diǎn)的車輛可以進(jìn)行多次配送。因此,車輛多次配送下考慮訂單可得時(shí)間和客戶時(shí)間窗的電商末端配送問題的精確算法將是下一步的研究方向。