師欣欣，陳樹(shù)國(guó)，馬 弘，鄧明榮

(1.浙江大學(xué)管理學(xué)院，浙江 杭州 310058；2．國(guó)網(wǎng)浙江省電力有限公司，浙江 杭州 310007;3.浙江大學(xué)工程師學(xué)院，浙江 杭州 310015)

1 引言

伴隨著互聯(lián)網(wǎng)經(jīng)濟(jì)的蓬勃發(fā)展，網(wǎng)上購(gòu)物成為人們消費(fèi)活動(dòng)的重要組成部分，國(guó)內(nèi)對(duì)快遞的配送需求也呈現(xiàn)爆發(fā)式增長(zhǎng)態(tài)勢(shì)。2019年，中國(guó)快遞服務(wù)企業(yè)業(yè)務(wù)量累計(jì)完成630億余件，其中農(nóng)村快遞增速比城市高近10個(gè)百分點(diǎn)[1]。支線鎮(zhèn)際的快遞配送是影響配送整體效率和服務(wù)水平的重要環(huán)節(jié)，快遞的大規(guī)模和高時(shí)效性特點(diǎn)為支線鎮(zhèn)際配送問(wèn)題提出新的要求和挑戰(zhàn)。與此同時(shí)，隨著新能源汽車在續(xù)航、充電時(shí)間等方面的表現(xiàn)日益提升，將電動(dòng)汽車引入支線鎮(zhèn)際快遞配送成為可能，并將有助于物流行業(yè)綠色經(jīng)濟(jì)的發(fā)展。本文主要對(duì)電動(dòng)汽車在城鎮(zhèn)快遞配送中的路徑規(guī)劃進(jìn)行研究，并提出與之相適應(yīng)的分支定價(jià)算法求解該問(wèn)題。

本文以支線鎮(zhèn)際快遞配送系統(tǒng)為研究對(duì)象，給定運(yùn)營(yíng)周期內(nèi)城鎮(zhèn)之間的快遞配送需求，要求結(jié)合電動(dòng)車輛自身屬性，決策車輛的行駛路徑和充電地點(diǎn)及時(shí)長(zhǎng)，在滿足所有運(yùn)輸需求的前提下，最小化總運(yùn)輸成本。由于Kerivin等[2]證明了SPDPR問(wèn)題(the Splittable Pickup and Delivery Problem with Reloads)的復(fù)雜度為NP-hard，本文的研究問(wèn)題較SPDPR問(wèn)題附加考慮了多種車型以及電動(dòng)車輛的相關(guān)特性，使得SPDPR問(wèn)題成為了本文研究問(wèn)題的一個(gè)特例，因而本文研究問(wèn)題的復(fù)雜度亦為NP-hard。

已有的與城際、鎮(zhèn)際快遞配送應(yīng)用相關(guān)的研究，大多圍繞啟發(fā)式算法和智能優(yōu)化算法展開(kāi)。Smilowitz等[3]在運(yùn)輸模型中將航空配送系統(tǒng)的剩余運(yùn)力納入考慮之中，利用割平面法計(jì)算問(wèn)題下界，并提出一個(gè)高效的線性規(guī)劃取整算法獲得問(wèn)題可行解。Li等[4]則在有資源管理約束的服務(wù)網(wǎng)絡(luò)設(shè)計(jì)中考慮到異車型的問(wèn)題。該研究將原問(wèn)題分解為2個(gè)子問(wèn)題，并利用禁忌搜索不斷指導(dǎo)和調(diào)整2個(gè)子問(wèn)題的求解。在精確求解算法方面，Andersen等[5]針對(duì)鐵路運(yùn)輸系統(tǒng)設(shè)計(jì)與之對(duì)應(yīng)的分支定價(jià)算法，對(duì)小規(guī)模和中等規(guī)模問(wèn)題實(shí)現(xiàn)了高效求解。但是，由于研究對(duì)象為鐵路運(yùn)輸系統(tǒng)，模型并未涉及多車型、倉(cāng)儲(chǔ)管理、充電樁管理等本文研究所必須要考慮的問(wèn)題。

分支定價(jià)作為精確求解整數(shù)規(guī)劃問(wèn)題中的經(jīng)典算法，已經(jīng)被廣泛應(yīng)用于車輛路徑規(guī)劃、網(wǎng)絡(luò)設(shè)計(jì)和背包問(wèn)題等各個(gè)研究領(lǐng)域中[6 - 8]。在本文的研究問(wèn)題中，分支定價(jià)算法的應(yīng)用要求對(duì)電動(dòng)車輛建立基于路徑的數(shù)學(xué)模型，和經(jīng)典的基于邊構(gòu)建的模型相比，該模型提供了更優(yōu)的問(wèn)題下界，同時(shí)規(guī)避了車輛之間建模對(duì)稱性所帶來(lái)的困擾，有利于問(wèn)題的高效求解。針對(duì)不同的應(yīng)用場(chǎng)景，分支定價(jià)算法框架中的分支策略、子問(wèn)題求解策略、割平面策略和強(qiáng)化策略等部分都需要完成有針對(duì)性的算法設(shè)計(jì)?；谏鲜鲅芯?，本文針對(duì)電動(dòng)汽車在鎮(zhèn)際快遞配送的路徑規(guī)劃這一問(wèn)題提出相應(yīng)的分支定價(jià)算法，給出有利于平衡搜索樹(shù)的分支策略，結(jié)合割平面策略，用Java語(yǔ)言進(jìn)行了實(shí)現(xiàn)。在實(shí)驗(yàn)部分，將分支定價(jià)算法與求解器和經(jīng)典的啟發(fā)式算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的可行性和有效性。

2 問(wèn)題描述與模型建立

在鎮(zhèn)際快遞配送系統(tǒng)中，某2個(gè)城鎮(zhèn)中轉(zhuǎn)站之間每隔一段時(shí)間會(huì)產(chǎn)生一批新的快遞運(yùn)輸需求，即需要將一定數(shù)量快遞包裹在規(guī)定的時(shí)間窗內(nèi)從城鎮(zhèn)中轉(zhuǎn)站1送達(dá)城鎮(zhèn)中轉(zhuǎn)站2。在運(yùn)輸車輛資源有限的情況下，為進(jìn)一步節(jié)約運(yùn)輸成本，降低車輛空駛率，本文規(guī)定該配送系統(tǒng)支持以下2種運(yùn)輸規(guī)則：

(1)同一批貨物可以以任意數(shù)量被分裝在不同的車輛上進(jìn)行運(yùn)輸。

(2)每個(gè)城鎮(zhèn)中轉(zhuǎn)站配有倉(cāng)庫(kù)，可以臨時(shí)存放貨物，貨物在中轉(zhuǎn)站可以選擇更換運(yùn)輸車輛。

在時(shí)間維度，與文獻(xiàn)[5]相同，本文假設(shè)快遞運(yùn)輸需求和車輛路徑都具有周期性重復(fù)的特點(diǎn)。所有快遞運(yùn)輸需求的時(shí)間窗長(zhǎng)度不超過(guò)一個(gè)運(yùn)營(yíng)周期，每輛運(yùn)輸車的配送路徑要求在一個(gè)運(yùn)營(yíng)周期形成環(huán)路。通過(guò)圖1中的運(yùn)輸方案來(lái)說(shuō)明該假設(shè)。在該實(shí)例中，運(yùn)營(yíng)周期為10 h。表1列舉了5批待完成運(yùn)輸需求的信息，其中需求D1的貨物數(shù)量為30，需要從城鎮(zhèn)中轉(zhuǎn)站2運(yùn)往城鎮(zhèn)中轉(zhuǎn)站3，在某個(gè)配送周期內(nèi)，最早取貨時(shí)刻為1，要在當(dāng)前配送周期的時(shí)刻5之前送達(dá)。注意到需求D3、D4和D5的最晚送達(dá)時(shí)刻小于或等于最早取貨時(shí)刻，此時(shí)最晚送達(dá)時(shí)刻所在周期指相對(duì)于最早取貨時(shí)刻所在周期的下一個(gè)運(yùn)營(yíng)周期，即允許需求的時(shí)間窗跨越周期。在圖1中，2輛電動(dòng)汽車完成了D1到D5的運(yùn)輸需求。載重量為50的車輛1在1時(shí)刻從城鎮(zhèn)2出發(fā)，途徑城鎮(zhèn)3、城鎮(zhèn)4，到達(dá)城鎮(zhèn)中轉(zhuǎn)站4后在其充電樁充電1 h并空閑等待3 h后從城鎮(zhèn)4出發(fā)返回城鎮(zhèn)2。載重量為20的車輛2在1時(shí)刻從城鎮(zhèn)5出發(fā)，途徑城鎮(zhèn)3、城鎮(zhèn)1、城鎮(zhèn)2、城鎮(zhèn)1,在一個(gè)周期后返回城鎮(zhèn)5。需求D3被拆分成2批(數(shù)量為10和20)進(jìn)行運(yùn)輸，數(shù)量為10的貨物首先由車輛2運(yùn)送至城鎮(zhèn)中轉(zhuǎn)站2的倉(cāng)庫(kù)存放4 h后由車輛1運(yùn)往目的地城鎮(zhèn)3。

為了更好地描述問(wèn)題，與文獻(xiàn)[9]類似，本文選擇在時(shí)空網(wǎng)絡(luò)(Time-Space Network)上構(gòu)建模型。在時(shí)空網(wǎng)絡(luò)中，原配送網(wǎng)絡(luò)中的每一個(gè)城鎮(zhèn)中轉(zhuǎn)站以及每一條邊在每一個(gè)時(shí)刻均有一個(gè)備份，使得時(shí)空網(wǎng)絡(luò)中的每個(gè)點(diǎn)和邊既定位空間也定位時(shí)間。如圖2所示，網(wǎng)絡(luò)中共包含2類邊，運(yùn)輸邊和等候邊。運(yùn)輸邊代表快遞包裹或電動(dòng)汽車實(shí)際的空間位置轉(zhuǎn)移，等候邊代表快遞包裹在倉(cāng)庫(kù)存放等候或者電動(dòng)汽車在某中轉(zhuǎn)站充電或者等候。注意到由于問(wèn)題具有周期性，在周期末尾的邊會(huì)循環(huán)指向周期開(kāi)始，代表進(jìn)入下一個(gè)新的運(yùn)營(yíng)周期。

Table 1 Delivery demand example

Figure 1 An example of transportation solution

Figure 2 Time-space network

2.1 符號(hào)說(shuō)明

記G(N,A)代表時(shí)空網(wǎng)絡(luò)。假設(shè)每一個(gè)城鎮(zhèn)中轉(zhuǎn)站配有固定數(shù)量的充電樁。N代表時(shí)空網(wǎng)絡(luò)中點(diǎn)的集合，A代表時(shí)空網(wǎng)絡(luò)中的邊集，包括運(yùn)輸邊集E和等候邊集H，記為A=E∪H。將整個(gè)時(shí)間周期劃分為離散的時(shí)刻T={1,2,…,Tmax}，對(duì)于實(shí)際的物理中轉(zhuǎn)站集合L，有N=L×T={lt|l∈L,t∈T}，其中l(wèi)t代表t時(shí)刻的中轉(zhuǎn)站l。定義s(o,d)∈S為一個(gè)運(yùn)輸服務(wù)，它包含了時(shí)空網(wǎng)絡(luò)中從中轉(zhuǎn)站o到中轉(zhuǎn)站d的所有時(shí)刻的運(yùn)輸邊的集合。

2.2 模型構(gòu)建

Table 2 Notation list

(1)

(2)

(3)

(4)

(5)

(6)

(7)

zτ∈N,?τ∈θ

(8)

約束(2)保證所有運(yùn)輸需求都在規(guī)定的時(shí)間窗內(nèi)被滿足。約束(3)限制在所有的運(yùn)輸邊上，貨物總量不得超過(guò)車輛的總載重量。約束(4)代表每個(gè)中轉(zhuǎn)站l最多派出車型為p的汽車數(shù)量為ubpl。約束(5)保證了每個(gè)中轉(zhuǎn)站的倉(cāng)庫(kù)在各時(shí)刻容納的快遞貨物量不超出其容量限制。所以，對(duì)于時(shí)空網(wǎng)絡(luò)中的每一個(gè)點(diǎn)lt∈N，將從該點(diǎn)出發(fā)的等候邊上的所有非終點(diǎn)貨物流相加，計(jì)為存放在當(dāng)前倉(cāng)庫(kù)的總貨物量。dk為需求k的實(shí)際目的城鎮(zhèn)。這里，為了簡(jiǎn)化模型中可能涉及的倉(cāng)庫(kù)存儲(chǔ)成本，本文假設(shè)當(dāng)快遞被送達(dá)目的城鎮(zhèn)的中轉(zhuǎn)站時(shí)，它即刻從該中轉(zhuǎn)站分撥至快遞貨物目的地具體地址附近，而不再占用中轉(zhuǎn)站的倉(cāng)儲(chǔ)資源。約束(6)限制每個(gè)中轉(zhuǎn)站同時(shí)充電的最大車輛數(shù)。

3 分支定價(jià)算法設(shè)計(jì)

為了獲得更高質(zhì)量的LP松弛值，并且消除基于車輛構(gòu)建模型中車輛同質(zhì)所引起的對(duì)稱性問(wèn)題[10]，本文選擇基于路徑構(gòu)建模型。這相當(dāng)于對(duì)經(jīng)典的基于邊構(gòu)建的模型進(jìn)行Dantizg-Wolfe分解[11]，模型中會(huì)包含大量車輛路徑?jīng)Q策變量。對(duì)于該模型，列生成算法有助于求解其LP松弛問(wèn)題(zτ松弛為實(shí)數(shù)變量)。算法主要在受限主問(wèn)題RMP(Restricted Master Problem)和子問(wèn)題之間協(xié)調(diào)計(jì)算。為了檢查RMP中的解對(duì)于主問(wèn)題MP(Master Problem)是否已經(jīng)最優(yōu)，子問(wèn)題將被求解。在本文算法中，每一個(gè)中轉(zhuǎn)站l和每一種車型p均對(duì)應(yīng)于其中一個(gè)子問(wèn)題。將列生成算法應(yīng)用在分支定界搜索樹(shù)中的每個(gè)節(jié)點(diǎn)，即為分支定價(jià)算法，算法流程如圖3所示。

Figure 3 Flow chart of the branch and price algorithm

3.1 受限主問(wèn)題RMP

3.2 分支策略

在分支定價(jià)算法中，本文采用了3種分支策略，分別是服務(wù)分支策略、子問(wèn)題服務(wù)分支策略和運(yùn)輸邊分支策略。3種分支策略的執(zhí)行優(yōu)先權(quán)依次遞減。當(dāng)?shù)玫侥矻P實(shí)數(shù)解時(shí)，首先考慮是否可以執(zhí)行服務(wù)分支策略，如果不滿足條件，則繼續(xù)檢查是否可以執(zhí)行子問(wèn)題服務(wù)分支策略，最后檢查運(yùn)輸邊分支策略。運(yùn)輸邊分支策略可以保證最終得到可行解。

3.2.1 服務(wù)分支策略

服務(wù)分支策略針對(duì)所有子問(wèn)題的某一服務(wù)s(o,d)∈S來(lái)進(jìn)行分支，即所有電動(dòng)車輛提供服務(wù)s(o,d)的數(shù)量之和需要為整數(shù)。服務(wù)s(o,d)為包含了時(shí)空網(wǎng)絡(luò)中所有時(shí)刻從中轉(zhuǎn)站o到d的運(yùn)輸邊集合。本文通過(guò)向RMP中加入以下相對(duì)應(yīng)的約束來(lái)進(jìn)行分支操作。

(9)

(10)

3.2.2 子問(wèn)題服務(wù)分支策略

同服務(wù)分支策略類似，子問(wèn)題服務(wù)分支策略針對(duì)某一子問(wèn)題的某一服務(wù)s(o,d)∈S來(lái)進(jìn)行分支，即從某中轉(zhuǎn)站l∈L出發(fā)，第p∈P種電動(dòng)車輛提供服務(wù)s(o,d)的數(shù)量之和需要為整數(shù)。RMP中對(duì)應(yīng)的分支約束如下所示：

(11)

(12)

3.2.3 運(yùn)輸邊分支策略

在運(yùn)輸邊分支策略中，檢查每個(gè)子問(wèn)題中電動(dòng)車輛走過(guò)某一運(yùn)輸邊的數(shù)量和是否為整數(shù)，若存在非整數(shù)，同樣選取小數(shù)部分最接近預(yù)先設(shè)點(diǎn)值的一條運(yùn)輸邊a∈E進(jìn)行分支。該分支對(duì)應(yīng)于RMP中的約束(13)和(14)。運(yùn)輸邊分支策略可以保證最終的解為可行解，但它往往會(huì)造成搜索樹(shù)2個(gè)分支的不平衡，本文將它放在分支策略中的最后來(lái)保證解的可行性。

(13)

(14)

3.3 割平面策略

在該問(wèn)題中，本文還使用了普遍應(yīng)用于服務(wù)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題的強(qiáng)限制約束(Strong Forcing Constraint)。由于該強(qiáng)制約束數(shù)量眾多，本文將其作為割平面策略，只在適當(dāng)?shù)臅r(shí)候采用并將其加入到RMP中。由式(15)可看出，每一條運(yùn)輸邊和每一批運(yùn)輸需求均對(duì)應(yīng)于一個(gè)強(qiáng)限制約束。

(15)

3.4 子問(wèn)題

物流配送中電動(dòng)汽車在很多方面具有與傳統(tǒng)汽車不同的特征[12]。本文假設(shè)電動(dòng)汽車通過(guò)在中轉(zhuǎn)站的充電樁充電來(lái)進(jìn)行能量供給，且采用部分充電模式，充電的最小時(shí)間單位同時(shí)空網(wǎng)絡(luò)。假設(shè)充電時(shí)間和充電可供行駛里程成線性關(guān)系，單位時(shí)間充電可供電動(dòng)汽車行駛里程為g。為方便起見(jiàn)，將電動(dòng)汽車的電池容量同樣用行駛里程來(lái)衡量，假設(shè)所有車輛的電池容量為Power。

(16)

(17)

(18)

(19)

(2)當(dāng)考慮在點(diǎn)i充電時(shí)，對(duì)于以點(diǎn)i為首的等候邊(i,j)∈H，生成下列新標(biāo)簽：

(20)

(21)

(22)

其中，chargeMark表示該路徑處有充電行為。

在本文的列生成算法中，針對(duì)特定子問(wèn)題中的每個(gè)出發(fā)時(shí)刻，求出其最短路徑，若機(jī)會(huì)成本為負(fù)則將該最短路徑變量加入RMP中進(jìn)行下一輪求解。

3.5 強(qiáng)化策略

在本文提出的分支定價(jià)算法中，每隔一定數(shù)目節(jié)點(diǎn)的LP問(wèn)題被求解后，會(huì)使用一次強(qiáng)化策略。首先統(tǒng)計(jì)出2個(gè)變量，cycleSet和lpColumnCount,其中，cycleSet代表當(dāng)前列生成算法產(chǎn)生過(guò)的所有路徑變量構(gòu)成的集合，lpColumnCount代表上述路徑變量對(duì)在所有節(jié)點(diǎn)LP最優(yōu)解中的值的和。接下來(lái)以lpColumnCount為依據(jù)對(duì)cycleSet中的路徑變量進(jìn)行篩選，識(shí)別cycleSet中的關(guān)鍵路徑變量并將其加入求解器，有利于強(qiáng)化策略在短時(shí)間獲得更高質(zhì)量的可行解。

(23)

至此，計(jì)算出所有組組內(nèi)路徑變量之間的距離并將其存儲(chǔ)在cyclePairList中。在圖4所示算法(其中包含了本文提出的路徑變量篩選算法)中，我們?cè)O(shè)置targetSize為將路徑變量集合篩選后的目標(biāo)集合大小。路徑變量篩選算法根據(jù)lpCoumnCount提供的信息篩選出對(duì)問(wèn)題求解關(guān)鍵的路徑變量集合并輸出該集合。

Figure 4 Flow chart of the intensification strategy

4 數(shù)值實(shí)驗(yàn)與分析

本節(jié)中的數(shù)值實(shí)驗(yàn)在安裝了CentOS Linux 7，配置了Intel Pentium 3.5 GHz處理器與16 GB內(nèi)存的PC機(jī)上完成。使用Java 1.8實(shí)現(xiàn)了分支定價(jià)算法，并使用IBM ILOG CPLEX 12.6.1求解LP與MIP問(wèn)題。源代碼已上傳至github網(wǎng)站(https://github.com/JAIMX/ESNDRC/tree/dev/paper)。在實(shí)驗(yàn)部分，首先針對(duì)小規(guī)模算例將分支定價(jià)算法同直接用求解器求解做對(duì)比，以探究分支定價(jià)算法在精確求解小規(guī)模算例方面的性能。其次針對(duì)中等規(guī)模用例，使用分支定價(jià)算法和基于列生成的啟發(fā)式算法來(lái)求解并進(jìn)行比較，以探究分支定價(jià)算法對(duì)中等規(guī)模問(wèn)題的求解效果。

4.1 算例說(shuō)明

從文獻(xiàn)[5]的實(shí)驗(yàn)數(shù)據(jù)中挑選了數(shù)據(jù)集1～12，其中5組小規(guī)模數(shù)據(jù)集構(gòu)成測(cè)試算例1～5，其允許在有限時(shí)間內(nèi)枚舉出所有可能的路徑τ并將其對(duì)應(yīng)變量加入求解器中求解。7組中等規(guī)模數(shù)據(jù)集中，每組又加入了2個(gè)隨機(jī)生成的數(shù)據(jù)集以構(gòu)成測(cè)試算例6～12。

將各算例的規(guī)?？偨Y(jié)如表3所示。數(shù)據(jù)生成時(shí)，對(duì)于每一個(gè)中轉(zhuǎn)站，保證車輛固定使用成本隨著車輛容量增大而增加。根據(jù)每組算例的具體規(guī)模，在保證有可行解的前提下，相關(guān)參數(shù)的區(qū)間取值如表4所示。

Table 3 Problem instance sizes

Table 4 Parameters values

4.2 小規(guī)模數(shù)據(jù)求解

針對(duì)小規(guī)模算例1～算例5，本文將所有可能的路徑變量枚舉出加入求解器CPLEX進(jìn)行求解，并將其結(jié)果和分支定價(jià)算法的結(jié)果作對(duì)比。2種算法的求解時(shí)間限制均設(shè)置為2 h。分支定價(jià)算法中，按照節(jié)點(diǎn)的下界大小進(jìn)行節(jié)點(diǎn)選擇，優(yōu)先搜索下界最低的節(jié)點(diǎn)，有助于更快地找到小規(guī)模算例的最優(yōu)解。割平面策略只應(yīng)用在父節(jié)點(diǎn)進(jìn)行分支操作后下界沒(méi)有提升的節(jié)點(diǎn)中，并且相應(yīng)的約束會(huì)保留在當(dāng)前節(jié)點(diǎn)。強(qiáng)化策略中，設(shè)置每求解10個(gè)節(jié)點(diǎn)使用一次強(qiáng)化策略，targetSize設(shè)置為1 000。表5展示了分支定價(jià)算法和求解器對(duì)小規(guī)模算例求解的結(jié)果。

在表5中，|θ|列表示所有可能路徑變量的數(shù)量，本文將該數(shù)量的路徑變量全部加入到求解器CPLEX中直接求解原MIP問(wèn)題。由表5可看出，分支定價(jià)算法在5組算例中的4組找到最優(yōu)解并證明了是全局最優(yōu)。求解器CPLEX則在算例1和算例5中找到了最優(yōu)解，然而對(duì)所有小規(guī)模算例都無(wú)法證明最優(yōu)性。盡管在其他相關(guān)研究[4]中，求解器在提升下界方面有很好的表現(xiàn)，但在該問(wèn)題中，相比于求解器，分支定價(jià)算法總是具有更佳的提升下界的表現(xiàn)?？傮w來(lái)說(shuō)，在精確求解小規(guī)模問(wèn)題方面，相比于求解器直接求解，分支定價(jià)算法在尋找可行解和提升下界方面都具有更好的表現(xiàn)。

Table 5 Comparison of results on small instances of the branch and price algorithm and the CPLEX MIP solver

4.3 中等規(guī)模數(shù)據(jù)求解

在求解中等規(guī)模算例時(shí)，如果使用不加強(qiáng)化策略的分支定價(jià)算法，絕大多數(shù)算例甚至無(wú)法在2 h內(nèi)找到任何一個(gè)可行解，該實(shí)驗(yàn)事實(shí)表明了強(qiáng)化策略的必要性。為了進(jìn)一步驗(yàn)證分支定價(jià)算法結(jié)合強(qiáng)化策略的高效性，本文將其與效果表現(xiàn)良好的常用算法——基于列生成的啟發(fā)式算法進(jìn)行比較。

使用分支定價(jià)算法和基于列生成的啟發(fā)式算法對(duì)算例6～12中共14組中等規(guī)模數(shù)據(jù)進(jìn)行了測(cè)試，求解時(shí)間均為2 h。基于列生成的啟發(fā)式算法的主要思路是使用列生成算法對(duì)原問(wèn)題對(duì)應(yīng)的LP問(wèn)題進(jìn)行求解，并將求解過(guò)程中生成的所有路徑變量加入求解器，求解僅包含該部分列變量的MIP問(wèn)題。在分支定價(jià)算法中，由于本文的求解目標(biāo)不再是全局最優(yōu)，有限時(shí)間內(nèi)的最優(yōu)解往往由強(qiáng)化策略搜索得到。強(qiáng)化策略中，本文設(shè)置每求解2個(gè)節(jié)點(diǎn)使用一次強(qiáng)化策略，targetSize設(shè)置為1 000。表6顯示了2種算法對(duì)中等規(guī)模數(shù)據(jù)的測(cè)試結(jié)果。

在表6中，強(qiáng)化策略|θ|表示獲得最優(yōu)解時(shí)加入求解器中的路徑變量數(shù)。 基于列生成的啟發(fā)式算法中的|θ|列表示加入求解器中路徑變量數(shù)。在14組測(cè)試結(jié)果中，分支定價(jià)算法在12組數(shù)據(jù)上的表現(xiàn)都要優(yōu)于基于列生成的啟發(fā)式算法。注意到由于算例10運(yùn)營(yíng)周期為50，2個(gè)算法在2 h之內(nèi)無(wú)法對(duì)原問(wèn)題的LP問(wèn)題求得最優(yōu)解，所以未顯示下界和最優(yōu)間隔，僅對(duì)2個(gè)算法的最優(yōu)解進(jìn)行比較。另一方面，不同測(cè)試用例之間的最優(yōu)間隔百分比的值相差較大，這主要和各部分成本之間的比例構(gòu)成有關(guān)。由表6結(jié)果可以看出，相比于經(jīng)典的基于列生成的啟發(fā)式算法，分支定價(jià)算法在中等規(guī)模問(wèn)題上具有更好的表現(xiàn)，可以有效解決該規(guī)模的問(wèn)題。

Table 6 Comparison of results on medium instances of the branch and price algorithm and the CG-based heuristic algorithm

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

本文針對(duì)電動(dòng)汽車支持的鎮(zhèn)際快遞配送系統(tǒng)建立基于路徑變量的數(shù)學(xué)模型。模型構(gòu)建在具有周期性的時(shí)空網(wǎng)絡(luò)之中，同時(shí)考慮到車輛資源、倉(cāng)儲(chǔ)資源和充電樁資源的管理問(wèn)題。本文針對(duì)該模型提出了分支定價(jià)算法。分支策略有利于削弱由時(shí)間離散化導(dǎo)致的對(duì)稱性問(wèn)題，子問(wèn)題中的標(biāo)簽算法為列生成算法的主問(wèn)題提供支持部分充電的電動(dòng)汽車路徑變量。分支策略和割平面策略的組合有助于實(shí)現(xiàn)對(duì)小規(guī)模數(shù)據(jù)的精確求解。強(qiáng)化策略通過(guò)篩選路徑變量并利用求解器的高效性，幫助算法在求解中等規(guī)模問(wèn)題時(shí)找到高質(zhì)量可行解。實(shí)驗(yàn)對(duì)比了分支定價(jià)算法和CPLEX求解器在精確求解小規(guī)模問(wèn)題上的表現(xiàn)，以及與基于列生成的啟發(fā)式算法對(duì)比了在中等規(guī)模問(wèn)題中的表現(xiàn)，結(jié)果表明了分支定價(jià)算法在精確求解和啟發(fā)式求解方面的高效性。因?yàn)樵跁r(shí)空網(wǎng)絡(luò)上構(gòu)建模型，時(shí)間離散化會(huì)造成問(wèn)題規(guī)模的迅速擴(kuò)增，加大問(wèn)題的求解復(fù)雜度，后續(xù)的研究可以考慮探究上述問(wèn)題在時(shí)空網(wǎng)絡(luò)的子網(wǎng)絡(luò)中實(shí)現(xiàn)精確求解的可能性[13]，以期擴(kuò)大問(wèn)題求解規(guī)模。