基于社會(huì)化庫(kù)存的多回程物流配送問(wèn)題的拉格朗日松弛算法

譚志龍，王 征，薛桂琴，王 新

(1.大連海事大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連 116026;2.大連海事大學(xué) 航運(yùn)經(jīng)濟(jì)與管理學(xué)院，遼寧 大連 116026)

0 引言

隨著零售業(yè)的不斷發(fā)展，網(wǎng)購(gòu)商品的可選范圍得到了極大的拓展，除傳統(tǒng)的需要多天配送的服裝鞋帽、家電數(shù)碼等商品外，線上線下相融合的本地商家進(jìn)行生鮮果蔬、日用百貨等生活快消品的配送也成為了網(wǎng)購(gòu)的一股新力量。這種配送方式依托地理上分散分布的多個(gè)商店實(shí)現(xiàn)庫(kù)存的社會(huì)化，通過(guò)運(yùn)力的合理調(diào)度，在顧客規(guī)定的時(shí)間內(nèi)完成從商家取貨并向顧客配送的物流任務(wù)。這種社會(huì)化的庫(kù)存對(duì)運(yùn)力的優(yōu)化調(diào)度提出了新要求，物流配送呈現(xiàn)出時(shí)間緊迫、取送一體化等特點(diǎn)。因此，如何在滿足顧客需求的前提下，以較低的成本完成社會(huì)化庫(kù)存的配送服務(wù)，是第三方物流公司必須解決的關(guān)鍵問(wèn)題。理論上，這類問(wèn)題可歸結(jié)為一類特殊的多回程混合取送車(chē)輛路徑問(wèn)題，是車(chē)輛路徑問(wèn)題(Vehicle Routing Problem，VRP)的一類變形，仍具有NP-hard復(fù)雜性。

多回程VRP是指配送車(chē)輛可在供貨點(diǎn)與顧客點(diǎn)之間往返多次，從而完成每個(gè)顧客的配送服務(wù)。該類問(wèn)題的代表性研究成果包括Hernandez等[1]的分支定價(jià)法、Nguyen等[2]的禁忌搜索算法、Cattaruzza等[3]的遺傳算法、Golden等[4]的適應(yīng)性記憶算法、Chbichib等[5]的構(gòu)建啟發(fā)式、Battarra等[6]的適應(yīng)性監(jiān)督算法、Azi等[7]的大鄰域搜索算法、以及國(guó)內(nèi)學(xué)者唐加福等[8]的精確算法、王征等[9]基于路徑池的算法等。然而，這些關(guān)于多回程VRP的研究通常只考慮一個(gè)供貨點(diǎn)，而在本文問(wèn)題中，貨物倉(cāng)儲(chǔ)被分散在了大量商店中，每個(gè)商店都是供貨點(diǎn)。這種分散的社會(huì)化庫(kù)存為車(chē)輛帶來(lái)了更多的路徑選擇，比現(xiàn)有研究中單供貨點(diǎn)、多回程的車(chē)輛調(diào)度問(wèn)題具有更多的路線選擇，因而解的搜索空間和復(fù)雜性顯著提升。

混合取送VRP是指配送車(chē)輛在配送時(shí)既可以取貨、又可以送貨，是一類取送一體化的VRP拓展問(wèn)題。其代表性成果包括Dumas等[10]的列生成方法、Nagy等[11]的基于強(qiáng)弱可行性的混合啟發(fā)式、Wassan等[12]的響應(yīng)式禁忌搜索、Zachariadis等[13]的基于適應(yīng)性記憶的方法、Subramanian等[14]的分支裁剪法、Zhang等[15]的分散搜索算法、Paraphantakul等[16]的蟻群算法、及Wang等[17]的混合啟發(fā)式等。上述文獻(xiàn)基本可以分為兩類問(wèn)題:①取貨點(diǎn)和送貨點(diǎn)一對(duì)一的問(wèn)題;②從中央倉(cāng)庫(kù)統(tǒng)一取貨送至顧客、同時(shí)又從各個(gè)顧客回收廢品再送至中央倉(cāng)庫(kù)的一對(duì)多對(duì)一的取送問(wèn)題。不同于上述兩類問(wèn)題，社會(huì)化庫(kù)存配送中的取貨點(diǎn)和送貨點(diǎn)屬于“多對(duì)多”的關(guān)系，每個(gè)商店可為多個(gè)顧客供貨，每個(gè)顧客也可以從多個(gè)商店購(gòu)貨，現(xiàn)有研究中的混合取送問(wèn)題并不具備上述特征。

拉格朗日松弛算法是將增加計(jì)算復(fù)雜度的約束添加到目標(biāo)函數(shù)中，是一種較好的求解組合優(yōu)化問(wèn)題的精確解算法[18]。傳統(tǒng)拉格朗日松弛算法的主要工作是求出問(wèn)題的下界，在有限時(shí)間內(nèi)所得結(jié)果雖與最優(yōu)解的目標(biāo)值相近，但一般為不可行解[19]。目前，拉格朗日松弛算法的應(yīng)用主要分為兩部分:①利用次梯度優(yōu)化不斷增長(zhǎng)問(wèn)題下界，直至找到問(wèn)題最優(yōu)解[20];②將傳統(tǒng)拉格朗日算法與啟發(fā)式算法相結(jié)合，在傳統(tǒng)拉格朗日松弛算法所得結(jié)果的基礎(chǔ)上，運(yùn)用一些啟發(fā)式規(guī)則使其可行化[21]。兩者各有優(yōu)劣，前者雖然可以確定所得結(jié)果為問(wèn)題最優(yōu)解，但求解時(shí)間過(guò)長(zhǎng);后者雖然可以得到問(wèn)題可行解，但在運(yùn)用啟發(fā)式規(guī)則時(shí)充滿了不確定性，無(wú)法確?？尚薪獾挠行?，求解效率難以保證。

基于前人的研究，本文將研究基于社會(huì)化庫(kù)存的帶時(shí)間窗多回程混合取送車(chē)輛路徑問(wèn)題(Multiple Trip Pickup and Delivery Vehicle Routing Problem with Time Windows，MTPDVRPTW)，并對(duì)傳統(tǒng)拉格朗日松弛算法進(jìn)行改進(jìn)，在保留其原有求解問(wèn)題下界優(yōu)勢(shì)的基礎(chǔ)上，為其注入了問(wèn)題上界求解的可行方法，通過(guò)不斷逼近問(wèn)題上下界，實(shí)現(xiàn)了對(duì)MTPDVRPTW 的有效求解。

1 問(wèn)題描述與模型構(gòu)建

1.1 問(wèn)題描述

在MTPDVRPTW 中，每個(gè)商店可為多個(gè)顧客提供商品，商店可被訪問(wèn)多次，每次訪問(wèn)都可能發(fā)生在不同時(shí)間，如何表達(dá)出商店被不同車(chē)輛、在不同時(shí)間的多次訪問(wèn)是建模的難點(diǎn)。一種建模的思路是根據(jù)時(shí)間將商店拷貝多次，同一商店拷貝后的每個(gè)點(diǎn)雖然具有相同的位置信息，但所代表的到達(dá)時(shí)間不同，車(chē)輛對(duì)同一點(diǎn)的多次訪問(wèn)可以被關(guān)聯(lián)到不同的拷貝點(diǎn)上[22]。建模示例如圖1所示，商店s1為顧客b1、b2供貨，顧客b2的最晚到達(dá)時(shí)間為20min時(shí)，每隔5min將車(chē)場(chǎng)、商店s1、顧客b1、b2復(fù)制一份，復(fù)制后的位置信息不變，但每點(diǎn)分別代表了不同的時(shí)間點(diǎn)，如點(diǎn)s11代表車(chē)輛在5分鐘時(shí)是否位于商店s1。在時(shí)間跨度較長(zhǎng)時(shí)，運(yùn)用該種建模思路復(fù)制后的點(diǎn)數(shù)量龐大，求解效率無(wú)法得到保證。另一種建模思路是根據(jù)商品數(shù)量，將商店與顧客進(jìn)行拷貝，拷貝后的商店點(diǎn)地理位置不變，復(fù)制后的商店只完成一個(gè)“顧客、訂單”對(duì)的服務(wù)[23]，建模示例如圖2所示，商店s1為顧客b1、b2供貨，在建模中不易表示到達(dá)顧客點(diǎn)時(shí)車(chē)輛的裝載情況，因此將商店s1根據(jù)所要服務(wù)的顧客點(diǎn)數(shù)量進(jìn)行拷貝，拷貝后商店點(diǎn)s11為顧客點(diǎn)b1提供貨物，商店s12為顧客點(diǎn)b2服務(wù)。復(fù)制后點(diǎn)的地理位置及其他信息不變，商店與顧客屬于一一映射關(guān)系，每個(gè)商店僅服務(wù)一個(gè)顧客，每個(gè)顧客也只需要一個(gè)商店的商品。假設(shè)現(xiàn)有n個(gè)顧客需求m個(gè)商店的貨物，顧客點(diǎn)的最晚到達(dá)時(shí)間為60min，顧客最多訂購(gòu)了3家商店的商品。在第一種建模思路下，每隔5min將顧客點(diǎn)與商店點(diǎn)拷貝一份，拷貝后的點(diǎn)數(shù)為12(m+n)。而在第二種建模思路下，復(fù)制后的商店與顧客總數(shù)不超過(guò)6max(m，n)，問(wèn)題規(guī)模遠(yuǎn)小于第一種建模思路，因此本文采用第二種建模思路對(duì)問(wèn)題進(jìn)行抽象化。

經(jīng)過(guò)抽象后，本文研究的問(wèn)題可用圖G=(N，A)表示。其中N為所有節(jié)點(diǎn)的集合，包括車(chē)場(chǎng)o，復(fù)制過(guò)后的商店點(diǎn)集合Ns，顧客點(diǎn)集合Nc;A為所有節(jié)點(diǎn)相互連接形成的弧的集合，使用cij表示兩節(jié)點(diǎn)之間的配送成本，用兩點(diǎn)間直線距離來(lái)表示。本文模型所用到的主要符號(hào)定義如下:xijk表示車(chē)輛k是否從點(diǎn)i行駛到點(diǎn)j，行駛則xijk=1，不行駛則;車(chē)場(chǎng)的自有車(chē)輛集合用K表示，自有車(chē)輛總數(shù)用V表示，車(chē)輛額定裝載量為Q，某時(shí)刻要完成n個(gè)顧客訂單的配送服務(wù)，配送車(chē)輛需從車(chē)場(chǎng)o出發(fā)，并最終返回車(chē)場(chǎng);訂單i所對(duì)應(yīng)的取貨點(diǎn)用si表示，商品重量為qi，到達(dá)時(shí)間為ai，訪問(wèn)i點(diǎn)后的車(chē)輛裝載為li;顧客訂單需求已知，服務(wù)時(shí)間窗為[ETi，LTi]，其中:ETi表示顧客訂單i的時(shí)間窗下界，到達(dá)時(shí)間早于ETi需等待;LTi表示顧客點(diǎn)i的時(shí)間窗上界，不允許出現(xiàn)晚于LTi的訪問(wèn)。

現(xiàn)實(shí)操作中，配送公司會(huì)對(duì)當(dāng)天訂單量進(jìn)行預(yù)測(cè)，并以此來(lái)分配車(chē)輛和騎手，一旦制定分配計(jì)劃，自有車(chē)輛在一般情況下都將被使用。若自有車(chē)輛無(wú)法完成全部顧客點(diǎn)的配送服務(wù)，需要利用第三方物流對(duì)未被訪問(wèn)的顧客點(diǎn)進(jìn)行配送，此時(shí)每單的配送成本固定為P，顧客點(diǎn)是否進(jìn)行第三方配送用0-1變量yj表示。問(wèn)題的目標(biāo)是成本最小化，成本由自有車(chē)輛的行駛成本和第三方物流配送所產(chǎn)生的成本兩部分組成。

1.2 模型構(gòu)建

基于以上問(wèn)題描述，建立了以成本最小化的多回程混合取送車(chē)輛路徑問(wèn)題模型MTPDVRPTW。建模過(guò)程中，對(duì)商店點(diǎn)進(jìn)行復(fù)制，車(chē)輛可以多次返回同一商店點(diǎn)，因此模型具備多回程的特性;且車(chē)輛同時(shí)具備取送貨能力，在商店點(diǎn)取貨后，再完成對(duì)應(yīng)顧客點(diǎn)的配送，模型具備取送一體化的特性。

其中:目標(biāo)函數(shù)(1)表示成本最小化，由自有車(chē)輛的行駛成本和第三方物流配送的成本構(gòu)成;約束(2)表示商店點(diǎn)與顧客點(diǎn)的訪問(wèn)次數(shù)限制;約束(3)表示商店點(diǎn)與顧客點(diǎn)是否需要第三方物流配送;約束(4)表示車(chē)輛需從車(chē)場(chǎng)出發(fā)，在完成配送服務(wù)后返回車(chē)場(chǎng);約束(5)為車(chē)輛流約束，確保車(chē)輛在進(jìn)入節(jié)點(diǎn)(非車(chē)場(chǎng)節(jié)點(diǎn))后一定從該節(jié)點(diǎn)離開(kāi);約束(6)和(7)確保顧客點(diǎn)與所對(duì)應(yīng)的取貨點(diǎn)必須被同一輛車(chē)訪問(wèn)，且僅在完成取貨點(diǎn)訪問(wèn)后才可訪問(wèn)顧客點(diǎn);約束(8)為節(jié)點(diǎn)到達(dá)時(shí)間的計(jì)算，其中M為一充分大的正數(shù);約束(9)為顧客點(diǎn)的訪問(wèn)時(shí)間限制;約束(10)為到達(dá)節(jié)點(diǎn)時(shí)的裝載量約束;約束(11)為確保車(chē)輛的裝載容量約束;約束(12)保證決策變量為0-1變量。

2 改進(jìn)的拉格朗日松弛算法

2.1 拉格朗日松弛算法

VRP求解算法主要分為啟發(fā)式算法和精確算法兩類。其中啟發(fā)式算法采用一定的規(guī)則在問(wèn)題可行域進(jìn)行隨機(jī)搜索，容易陷入局部最優(yōu)，無(wú)法確保所得結(jié)果的有效性，多用于大規(guī)模問(wèn)題的求解;精確算法的求解時(shí)間隨問(wèn)題規(guī)模的增長(zhǎng)而快速增長(zhǎng)，一般用于求解中小規(guī)模問(wèn)題，拉格朗日松弛是其中的代表性成果，是求解組合優(yōu)化NP-hard問(wèn)題的有效工具。

由于組合優(yōu)化問(wèn)題NP難的特性，求解最優(yōu)目標(biāo)值非常困難，解決該難點(diǎn)的有效方法就是計(jì)算問(wèn)題下界，通過(guò)比較所得可行解與問(wèn)題下界的差值來(lái)評(píng)價(jià)算法的有效性，而拉格朗日松弛算法是一種有效求解問(wèn)題下界的方法。拉格朗日松弛算法的優(yōu)點(diǎn)在于通過(guò)松弛某些約束，從而使得松弛問(wèn)題可被分解為多個(gè)相同的子問(wèn)題，僅需對(duì)子問(wèn)題求解一次即可得到原問(wèn)題下界，大大提高了下界的求解效率。在實(shí)際求解中，問(wèn)題由于某些原因很難直接求得最優(yōu)解，或者求解效率較差;而如果放松原問(wèn)題的一些約束，其求解難度將大大降低，從而在可接受的時(shí)間內(nèi)完成求解。這些導(dǎo)致求解難度增大的約束通常被稱為難約束。在本文模型中，難約束為約束(2)，即商店點(diǎn)與顧客點(diǎn)的訪問(wèn)次數(shù)限制，引入拉格朗日乘子λj對(duì)其進(jìn)行松弛，由于始終為非負(fù)值，松弛過(guò)后的拉格朗日松弛模型目標(biāo)如式(13)所示，滿足約束(3)～約束(12):

拉格朗日乘子λj反映了服務(wù)顧客的成本，且在一般情況下為正數(shù)。因此，對(duì)于任意給定的λ=(λ1，λ2，...，λn)T，拉格朗日函數(shù)值都是原問(wèn)題的下界，因而構(gòu)建拉格朗日對(duì)偶問(wèn)題max(ZLR(λ))，得到拉格朗日松弛模型的最大值ZLD，即可以求得原問(wèn)題一個(gè)較優(yōu)的下界。

為方便表示，令

顯然，式(16)為線性分段的凹函數(shù)，且并不可微。而次梯度優(yōu)化方法是求解不可微凹函數(shù)的極大化問(wèn)題的較好方法。次梯度是指針對(duì)x*，對(duì)于?x∈Rn，使得不等式f(x)≤f(x*+dT(x-x*))成立的向量d。換言之，對(duì)于凹函數(shù)而言，在點(diǎn)x*的次梯度為通過(guò)此點(diǎn)，并且始終位于凹函數(shù)之下的直線的斜率。在本文問(wèn)題中，集合U={uj|j=1，2，…，m}即為拉格朗日乘子為λ時(shí)的一個(gè)次梯度。本文建立的總體算法流程如下:

步驟1將拉格朗日對(duì)偶問(wèn)題分解為相同的車(chē)輛數(shù)個(gè)子問(wèn)題;對(duì)拉格朗日乘子λ，原問(wèn)題上界Zub，下界Zlb進(jìn)行初始化。

步驟2求解子問(wèn)題，計(jì)算此時(shí)的拉格朗日函數(shù)值ZLR(λk+1)，更新原問(wèn)題下界Zlb。

步驟3根據(jù)所求子問(wèn)題最優(yōu)解計(jì)算次梯度，更新拉格朗日乘子若原問(wèn)題下界在β1代內(nèi)未得到更新，β的值減半。

步驟4以γ的概率基于次短路的優(yōu)化思想求解子問(wèn)題，搜索原問(wèn)題可行解，并更新原問(wèn)題上界Zub;

步驟5若原問(wèn)題上界與下界的差值小于范圍β2或者達(dá)到最大迭代次數(shù)，停止迭代，將現(xiàn)有最優(yōu)可行解視為原問(wèn)題最優(yōu)解。反之，重復(fù)步驟2～步驟4。

2.2 基于次短路的子問(wèn)題求解算法

拉格朗日松弛模型的目標(biāo)函數(shù)整理后可得:

本文基于動(dòng)態(tài)規(guī)劃的思想，采用改進(jìn)的標(biāo)號(hào)法求解子問(wèn)題。傳統(tǒng)算法的思想對(duì)每個(gè)點(diǎn)進(jìn)行標(biāo)號(hào)，用以表示從車(chē)場(chǎng)起始點(diǎn)到該點(diǎn)的路徑，記為π。π由(m，t，l，s，c)5部分構(gòu)成，其中:m表示此路徑訪問(wèn)的上一個(gè)點(diǎn);t表示到達(dá)點(diǎn)i并做好裝卸貨準(zhǔn)備的時(shí)間;l表示完成點(diǎn)i后的車(chē)輛裝載量;根據(jù)在完成點(diǎn)i訪問(wèn)后車(chē)輛的現(xiàn)有裝載情況，s表示車(chē)輛后續(xù)必須訪問(wèn)的顧客點(diǎn)集合;c表示訪問(wèn)完此點(diǎn)的路徑成本。假設(shè)π與π'為同一點(diǎn)的不同標(biāo)號(hào)，若滿足條件式(19)，則認(rèn)為π支配π'，使用?符號(hào)表示支配。

但該標(biāo)號(hào)方法只能得到子問(wèn)題的最優(yōu)解，由于車(chē)輛是同質(zhì)的，所有子問(wèn)題的求解結(jié)果相同。這種情況下，所得子問(wèn)題求得的訪問(wèn)路徑一般無(wú)法覆蓋所有顧客點(diǎn)，即無(wú)法得到原問(wèn)題的可行解。而且由于覆蓋點(diǎn)較少，直接通過(guò)啟發(fā)式方法將其進(jìn)行可行化的效率并不高，無(wú)法實(shí)現(xiàn)問(wèn)題上下界的快速逼近，求解效率差。針對(duì)傳統(tǒng)標(biāo)號(hào)法的上述缺點(diǎn)，本文在子問(wèn)題求解過(guò)程中引入了次短路的優(yōu)化思想，在對(duì)商店與顧客點(diǎn)進(jìn)行標(biāo)號(hào)時(shí)，接受劣于最優(yōu)標(biāo)號(hào)一定范圍內(nèi)的次優(yōu)標(biāo)號(hào)，從而實(shí)現(xiàn)了問(wèn)題上界的有效求解，加快了問(wèn)題上下界的逼近速度，具有較好的求解性能。

定理1隨著次梯度的更新，各點(diǎn)間的成本定價(jià)不斷減小，原問(wèn)題最優(yōu)解中的每條訪問(wèn)路徑的reduce cost會(huì)不斷減小，且各路徑成本的最大reduce cost差在不斷下降，并逐漸逼近于此時(shí)子問(wèn)題的最短路徑。

證明為方便表示，假設(shè)最優(yōu)解由R條路徑組合而成，用表示第k代r條路徑的reduce cost。由于在最優(yōu)解中每點(diǎn)被訪問(wèn)且僅被訪問(wèn)一次，若在第k代求得的最短路徑為ri，則除第i條路徑訪問(wèn)點(diǎn)之外的點(diǎn)均未被訪問(wèn)，根據(jù)次梯度的更新法則，點(diǎn)與未訪問(wèn)點(diǎn)之間的成本定價(jià)會(huì)減小。此時(shí)，未訪問(wèn)路徑的reduce cost將減小，直至發(fā)現(xiàn)比成本更低的路徑，以此實(shí)現(xiàn)最優(yōu)解中每條路徑的reduce cost的不斷縮小。此外，在更新次梯度時(shí)，由于更新的步長(zhǎng)不斷減小，reducecost的降低速度一直在減緩，故最優(yōu)解中的各路徑成本差將逐漸縮小。

因此，在問(wèn)題求解過(guò)程中，以一定的概率采取次短路的優(yōu)化思想，接受劣于最短路徑一定范圍內(nèi)的路徑，即使無(wú)法覆蓋原問(wèn)題最優(yōu)解中的所有路徑，所得的路徑也會(huì)包含原問(wèn)題最優(yōu)解的一部分，訪問(wèn)的顧客點(diǎn)也比較多，對(duì)其進(jìn)行可行化的效率也較高。綜上所述，本文在求解子問(wèn)題時(shí)，以一定的概率采用式(20)的標(biāo)號(hào)支配法則，使用?符號(hào)表示支配。

在這種支配法則下，可以求得成本劣于最優(yōu)路徑一定范圍內(nèi)的路徑。在算法運(yùn)行中，應(yīng)根據(jù)求取目標(biāo)選擇支配法則，按照下述動(dòng)態(tài)規(guī)劃算法流程進(jìn)行求解:

步驟1從車(chē)場(chǎng)出發(fā)，為所有商店點(diǎn)進(jìn)行標(biāo)號(hào)，并將除車(chē)場(chǎng)以外的點(diǎn)加入集合E中。

步驟2從E中選取一點(diǎn)i，將其從E中刪除，對(duì)其余點(diǎn)進(jìn)行標(biāo)號(hào)，若標(biāo)號(hào)滿足車(chē)輛載重約束、顧客時(shí)間窗約束、取貨后才能送貨的約束，且訪問(wèn)后已裝載商品至少有一可行配送方案，轉(zhuǎn)至步驟3。

步驟3將標(biāo)號(hào)與已存標(biāo)號(hào)進(jìn)行比較，若存在可支配標(biāo)號(hào)，刪除此標(biāo)號(hào);若此標(biāo)號(hào)可支配已存標(biāo)號(hào)，進(jìn)行取代，并將此點(diǎn)加入集合E中;若此標(biāo)號(hào)與已存標(biāo)號(hào)不存在支配關(guān)系，將其加入此點(diǎn)的標(biāo)號(hào)集合，并將此點(diǎn)加入集合E。

步驟4當(dāng)標(biāo)號(hào)中的載重量為0時(shí)，對(duì)車(chē)場(chǎng)o'進(jìn)行標(biāo)號(hào)。若采用的為次短路策略，接受劣于最短路徑一定范圍內(nèi)的路徑。

步驟5重復(fù)步驟2～步驟4，直至集合E為空集，選取車(chē)場(chǎng)的標(biāo)號(hào)，此時(shí)得到子問(wèn)題的解。

上述方法使用傳統(tǒng)標(biāo)號(hào)法求取子問(wèn)題的最短路，保留了傳統(tǒng)拉格朗日算法求取問(wèn)題下界的優(yōu)勢(shì)，并以一定概率采用次短路的優(yōu)化思想尋求問(wèn)題上界的有效求取，根據(jù)問(wèn)題上下界進(jìn)行拉格朗日乘子的更新，具有較快的收斂速度。這種次短路的優(yōu)化思想為傳統(tǒng)的拉格朗日松弛算法注入了獲得可行解上界的能力，使得該算法在求取下界的同時(shí)能夠快速得到高質(zhì)量的上界，從而實(shí)現(xiàn)了問(wèn)題上下界的并行求解，為快速求得問(wèn)題最優(yōu)解或高質(zhì)量可行解提供了途徑。

3 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證本文模型的合理性及改進(jìn)拉格朗日算法的有效性，基于標(biāo)準(zhǔn)Solomon算例構(gòu)建了顧客訂單數(shù)不同的算例，采用MATLAB 2014a編程平臺(tái)對(duì)設(shè)計(jì)的改進(jìn)朗格朗日松弛算法進(jìn)行編碼實(shí)現(xiàn)，并將算法求解結(jié)果與CPLEX求解器及利用次梯度優(yōu)化的傳統(tǒng)拉格朗日松弛算法進(jìn)行了對(duì)比。本文所有實(shí)驗(yàn)均在i5CPU、8 GB內(nèi)存的計(jì)算機(jī)上運(yùn)行。

3.1 算例與參數(shù)

MTPDVRPTW 不同于傳統(tǒng)的帶時(shí)間窗的車(chē)輛路徑問(wèn)題，因此將該領(lǐng)域標(biāo)準(zhǔn)的Solomon算例進(jìn)行了改進(jìn)，使其適用于本文的問(wèn)題，算例選取與具體改進(jìn)工作如下:

(1)選用的算例類型 商店一般存在配送范圍的限制，且配送范圍不會(huì)太大，一般為相鄰的人口集聚地。這是由于配送費(fèi)用與配送范圍相關(guān)，配送范圍越大，配送費(fèi)用越高，而顧客與商店對(duì)于配送費(fèi)用敏感性較高。這種情況下，商店和顧客往往是成簇出現(xiàn)的，這與Solomon算例中的C 類算例非常相似。本文以C類算例為基礎(chǔ)進(jìn)行了改進(jìn)，在Solomon算例中選取了V個(gè)顧客簇，從這些顧客簇中隨機(jī)選取了商店點(diǎn)與顧客點(diǎn)，并生成了兩者的對(duì)應(yīng)關(guān)系。

(2)時(shí)間窗設(shè)置 同城物流配送公司一般為顧客提供的送達(dá)時(shí)間為時(shí)間點(diǎn)的形式，但在實(shí)際情況中，在早于或晚于送達(dá)時(shí)間點(diǎn)一定范圍的時(shí)間窗內(nèi)送達(dá)均不會(huì)引起顧客滿意度的大幅下降，從而也不會(huì)出現(xiàn)退貨的情況。物流配送公司偏好時(shí)間跨度大的時(shí)間窗，這有利于配送者根據(jù)實(shí)際情況對(duì)配送路線進(jìn)行調(diào)整，而顧客偏好時(shí)間跨度小的時(shí)間窗，從而確保送達(dá)時(shí)間的可靠性。綜合考慮兩者，本文隨機(jī)生成了顧客點(diǎn)的送達(dá)時(shí)間，并根據(jù)顧客點(diǎn)的時(shí)間窗跨度設(shè)置顧客點(diǎn)的時(shí)間窗范圍，確保物流配送公司既可以對(duì)配送路線進(jìn)行小范圍調(diào)動(dòng)，又確保了顧客的滿意度。

(3)車(chē)輛裝載容量的設(shè)置 現(xiàn)有同城配送主要由電動(dòng)車(chē)與摩托車(chē)完成，裝載能力十分有限，另外顧客訂購(gòu)生活快消品通常是為了滿足未來(lái)一段時(shí)間內(nèi)的消耗，訂購(gòu)的數(shù)量較多。綜上考慮，設(shè)置車(chē)輛額定裝載量Q=30，并在[7，12]的區(qū)間內(nèi)隨機(jī)生成了各顧客訂單所需要的商品重量。

此外，在參數(shù)設(shè)置上，本文拉格朗日松弛算法的參數(shù)設(shè)置為α=1.2，γ=0.2，β1=5，終止條件為問(wèn)題上下界誤差率β2 不超過(guò)5%。

3.2 算例求解及分析

為驗(yàn)證算法的有效性，本文分別構(gòu)建了顧客訂單數(shù)為15、20、25、30、35、40的算例，相同訂單數(shù)的算例平均運(yùn)行時(shí)間如圖3所示。由圖3可知，顧客訂單數(shù)的規(guī)模對(duì)于問(wèn)題求解時(shí)間的影響極大，在訂單數(shù)逐漸增加時(shí)，Cplex和本文算法的求解時(shí)間都會(huì)上升，但本文算法求解時(shí)間的上升幅度明顯低于Cplex，問(wèn)題規(guī)模越大，兩種方法求解時(shí)間的差距越大。這是由拉格朗日松弛算法自身的特性決定的，由于本文在利用拉格朗日松弛算法求得下界的同時(shí)，也會(huì)得到問(wèn)題的高質(zhì)量的上界，這十分有利于問(wèn)題上下界差距的縮小，從而極大地減少了問(wèn)題的求解時(shí)間。

因?yàn)镸TPDVRPTW 的NP難特性，Cplex求解器很難在有限的時(shí)間內(nèi)求得最優(yōu)解，所以針對(duì)每個(gè)算例設(shè)置了兩個(gè)終止條件:①問(wèn)題上下界誤差小于5%;②達(dá)到所設(shè)置的最大運(yùn)行時(shí)間。滿足兩者之一即終止，輸出當(dāng)前得到的最優(yōu)可行解。改進(jìn)的拉格朗日松弛算法和Cplex的求解結(jié)果如表1所示?？梢园l(fā)現(xiàn)，改進(jìn)算法所求得的上下界仍存在一定的誤差，但與CPLEX 求解器的求解結(jié)果進(jìn)行對(duì)比，本文算法的求解速度和求解質(zhì)量均優(yōu)于CPLEX求解器，體現(xiàn)了本文算法較好的性能。

由于傳統(tǒng)的拉格朗日松弛算法在可接受時(shí)間內(nèi)并不能得到問(wèn)題的可行解，無(wú)法提供原問(wèn)題上界。而本文算法不僅保留了傳統(tǒng)算法求取下界的優(yōu)勢(shì)，還提供了一種較好的求取問(wèn)題上界的方法。為了進(jìn)一步觀察在算例計(jì)算過(guò)程中問(wèn)題上下界的變化趨勢(shì)，本文針對(duì)上述算例在算法執(zhí)行過(guò)程中的每一次迭代中都記錄了上界和下界，如圖4所示為算例4的上下界逼近圖，其他算例的上下界變化趨勢(shì)與圖4基本一致。如圖4可見(jiàn)，在本文算法的執(zhí)行過(guò)程中，問(wèn)題的上下界不斷逼近，最終得到了高質(zhì)量的上界，即問(wèn)題的可行解。

表1 改進(jìn)算法與CPLEX求解結(jié)果表

為了確定參數(shù)設(shè)置的有效性，在α=1.2的前提下，使得γ在區(qū)間[0.1，1.0]選取了不同的數(shù)值，隨機(jī)選取了算例4與算例7進(jìn)行求解，不同γ值時(shí)的求解時(shí)間如圖5所示?？梢园l(fā)現(xiàn)，當(dāng)γ=0.2時(shí)，求解時(shí)間最短(分別為75 s，186 s)，說(shuō)明了本文參數(shù)設(shè)置的有效性。另外，隨著γ的增加，求解時(shí)間總體呈上升的趨勢(shì)，這是由于本文的次短路方法雖然可以較好地構(gòu)建原問(wèn)題上界，但在子問(wèn)題求解過(guò)程中，由于接受了更多的標(biāo)號(hào)點(diǎn)，導(dǎo)致子問(wèn)題求解時(shí)間比傳統(tǒng)算法稍慢，若僅采用次短路的方法進(jìn)行問(wèn)題求解，下界提升較慢。本文采用了一定的概率使用次短路方法構(gòu)建問(wèn)題上界，既可以較快地找到可行解，又保證了問(wèn)題下界的更新速度，因而具有較好的性能。另一方面，從圖4也可以看出，如果不采用次短路的方法(γ=0)，傳統(tǒng)拉格朗日松弛算法在1000 s內(nèi)均無(wú)法得到可行解，消耗的時(shí)間將遠(yuǎn)遠(yuǎn)超過(guò)本文改進(jìn)的拉格朗日松弛算法。

4 結(jié)束語(yǔ)

本文針對(duì)帶有社會(huì)化庫(kù)存特征的帶時(shí)間窗多回程混合取送同城物流配送問(wèn)題，建立了混合整數(shù)模型，并針對(duì)傳統(tǒng)拉格朗日松弛算法無(wú)法有效求解問(wèn)題上界的缺陷，采用次短路的優(yōu)化思想構(gòu)建了原問(wèn)題上界。該思想為傳統(tǒng)的拉格朗日松弛算法注入了獲取可行解上界的能力，使得該算法在求取下界的同時(shí)能夠快速得到高質(zhì)量的上界，從而實(shí)現(xiàn)上下界的并行求解，為快速求得問(wèn)題最優(yōu)解或高質(zhì)量可行解提供了途徑。計(jì)算實(shí)驗(yàn)表明，本文算法的求解速度和求解質(zhì)量均優(yōu)于CPLEX 求解器，從而體現(xiàn)了本文算法較好的性能，也證明了模型的合理性和算法的有效性。

本文研究中的模型是針對(duì)確定性問(wèn)題而建立，未考慮配送服務(wù)當(dāng)中的一些不確定因素影響，如服務(wù)時(shí)間的不確定性、行駛時(shí)間不確定性等。隨著即時(shí)配送市場(chǎng)規(guī)模的不斷擴(kuò)大，物流配送中的不確定性對(duì)于現(xiàn)有調(diào)度方式將是一個(gè)巨大的挑戰(zhàn)，這些問(wèn)題將在未來(lái)的研究中予以深入考慮。