需求可拆分電動汽車車輛路徑問題及其改進分支定價算法研究

揭婉晨 侍 穎 楊 珺 楊 超

(1. 浙江財經(jīng)大學信息管理與人工智能學院；2. 廣東財經(jīng)大學國際商學院；3. 華中科技大學管理學院)

1 研究背景

由于政府的大力支持、人民社會環(huán)境意識的提高和部分城市道路燃油車限行政策的影響，越來越多的企業(yè)相繼開始使用電動汽車來進行物流配送[1]。例如，德國郵政國際快遞于2016年5月宣布，集團開始批量生產(chǎn)StreetScooter電動車用于替換現(xiàn)有的3萬輛傳統(tǒng)汽車。UPS于2016年與比亞迪合作，欲逐步將其車隊升級為電動汽車。同時，中國郵政、順豐快遞等物流行業(yè)領(lǐng)跑者也先后購入電動汽車進行物流配送。然而，電動汽車含有電量約束，它需要在站點進行充電或者換電以延長其行駛里程。根據(jù)發(fā)改委發(fā)布的相關(guān)文件，我國到2020年的充換電設(shè)備需要滿足500萬輛電動汽車的需要[2]。電動汽車換電的操作時間小于10分鐘，大大小于充電時間，并且被換下來的低電量電池可以在晚上低谷電價時批量充電，節(jié)約了充電成本，因此，換電是延長電動汽車行駛里程的重要方案。此外，在現(xiàn)實生活的多數(shù)場景中，客戶的貨物需求量往往較大，而電動汽車的載重量相對較小，經(jīng)常會出現(xiàn)客戶需求量大于車輛最大載重的情況。由此，客戶需求允許被拆分，能被多輛車分別配送，充分利用電動汽車的裝載能力，探討需求可以被拆分運輸?shù)碾妱悠嘨RP顯得十分必要。

在現(xiàn)有的理論研究成果中，暫未發(fā)現(xiàn)同時考慮電動汽車配送和客戶需求可拆分相關(guān)的研究，但有單獨考慮電動汽車車輛路徑問題(electric vehicle routing problem，EVRP)和需求可以被拆分運送的車輛路徑問題(split delivery VRP，SDVRP)的研究?；诳蛻粜枨蟛豢刹鸱值募僭O(shè)條件，許多學者研究了EVRP的相關(guān)問題，并對其作了綜述，包括車隊構(gòu)成與規(guī)模、車輛路徑和最優(yōu)路徑3個部分[3]。YANG等[4]提出了電動汽車換電站選址路徑問題，研究在電池續(xù)航里程約束下，同時規(guī)劃換電站位置和電動汽車的行駛方案。SCHIFFER等[5]在充電站選址路徑問題中，考慮了電動汽車可以選擇部分充電或全部充電，以及時間窗約束，模型的目標函數(shù)不僅最小化行駛距離，還最小化電動汽車的數(shù)量和充電站的數(shù)量。LIAO等[6]研究了電動汽車游覽問題，該問題的目標是在給定的公路網(wǎng)中找到出行時間最短的路線。在現(xiàn)有電動汽車路徑相關(guān)的研究中，大都采用啟發(fā)式算法求解。HOF等[7]采用擴展自適應(yīng)變鄰域算法求解換電站選址路徑問題；SCHIFFER等[8]提出基于動態(tài)規(guī)劃的自適應(yīng)大鄰域搜索算法，求解換電站的選址路徑問題。在精確算法方面，DESAULNIERS等[9]提出分支定價切割算法，得到含時間窗的電動汽車車輛路徑問題的4種變式問題的最優(yōu)解；揭婉晨等[10]通過分支定價方法，研究了在時間窗約束下的EVRP。

在SDVRP方面，DROR等[11]首先提出了SDVRP，它是傳統(tǒng)VRP的一種擴展，允許客戶需求被拆分配送，充分利用了車輛的剩余載重，大大提高了車輛的利用率，更加符合現(xiàn)如今的物流態(tài)勢。在該問題的求解算法上，最早采用精確算法的主要有ARCHETTI等[12]及DROR等[13]。其中，DROR等[13]首先提出了SDVRP的一種弧流公式，并給出了一類新的有效不等式進行求解。接著，更多精確算法被提出用來求解SDVRP，主要有截平面法[14]、最短路徑法[15]、列生成法[16]等。此外，該問題的啟發(fā)式方法主要有局部搜尋[11, 17]、禁忌搜尋[18～20]、進化算法[21]、混合元啟發(fā)式方法[22]以及PSO算法[23]等。關(guān)于SDVRP及其擴展問題還可參考綜述性文獻[24,25]。國內(nèi)對SDVRP的研究較少，近年來相關(guān)的研究有：陳靖等[26]考慮了車輛運載能力限制與客戶產(chǎn)品新鮮度要求，對生鮮品的物流集配問題進行建模；王旭坪等[27]構(gòu)建多約束條件下的同時集送車輛路徑優(yōu)化模型，滿足了實際物流配送中客戶對不同車型及服務(wù)時間的多樣化需求；徐東洋等[28]考慮了多車場、多車型、多貨品、客戶間供需未匹配和取送貨需求可任意拆分等因素，研究取送貨車輛路徑問題；卿東升等[29]研究了滿載需求可拆分車輛路徑規(guī)劃問題，并采用粒子群算法求解。

總結(jié)已有文獻可以發(fā)現(xiàn)：①VRP研究中大都假設(shè)客戶需求不可分割，但這種假設(shè)與現(xiàn)實的物流配送場景不太符合，還會降低車輛的利用率，無法保證整個優(yōu)化結(jié)果的適用性，所以研究SDVRP具有現(xiàn)實指導意義；②由于燃油車在部分城市道路上受限行政策影響，和其在配送過程中產(chǎn)生的環(huán)境污染問題，同時考慮到油價的增長，引入電動汽車到物流配送中順應(yīng)了時代的發(fā)展趨勢。鑒于此，研究需求可拆分的電動汽車車輛路徑問題，顯得十分必要。此外，現(xiàn)有SDVRP和EVRP的求解算法，僅分別圍繞需求拆分策略和換電充電策略進行算法設(shè)計，因此，同時實現(xiàn)兼顧這兩類因素和協(xié)同這兩種策略的算法也顯得非常必要。本研究擬將EVRP與SDVRP相結(jié)合，研究E-SDVRP，并建立其相應(yīng)的數(shù)學規(guī)劃模型；運用基于列生成的分支定價算法對問題進行分解，推導出復雜的定價子問題目標函數(shù)，并設(shè)計相應(yīng)的標簽算法求解該問題的最優(yōu)解。

2 問題概述和建模

2.1 問題概述

在圖G=(C∪R∪{0},A)中，C為客戶點集合，R為換電站集合，弧(i,j)∈A。考慮通過電動汽車從配送中心出發(fā)，給相應(yīng)的顧客運輸貨品，每個顧客的需求可以被拆分，由多輛車共同配送，每輛車最多為同一個客戶點配送一次。客戶點i的貨物需求量為qi；dij表示i點到點j的距離；cij表示電動汽車從點i到點j的行駛花費；換電站的位置已知，每次換電的費用為cB；K表示電動汽車集合，從配送中心出發(fā)的電動汽車的電量是滿的，電動汽車的最大行駛里程(電池的最大容量)為B，最大載重量為Q。本研究的目標函數(shù)為使系統(tǒng)總配送成本最小。

2.2 建模

表1 E-SDVRP模型構(gòu)建中的變量和參數(shù)

該模型描述如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

j∈R∪C∪{n+1}，i≠j，k∈K；

(11)

(12)

(13)

j∈R∪C∪{n+1}，i≠j，k∈K；

(14)

(15)

(16)

xijk∈{0,1}，?k∈K，(i,j)∈A。

(17)

其中，目標函數(shù)(1)表示最小化物流系統(tǒng)的總配送成本，包括電動汽車的行駛成本和換電成本；式(2)表示電動汽車運輸給客戶點i的貨物量之和等于該點的需求量；式(3)是上文“k-分割圈”屬性的數(shù)學表達；式(4)為電動汽車的數(shù)量約束；式(5)和式(6)確保每條路徑弧的均衡；式(7)表示非負約束和車輛的載重限定；式(8)保證xijk與變量ωik的一致性；式(9)體現(xiàn)了車輛到達換電站時的載重量等于車輛離開換電站時的載重量；式(10)表示電動汽車到達客戶點時的貨物量減去離開該客戶點時的貨物量，為這輛車給該客戶點的配送量；式(11)表示電動汽車貨物流量的約束；式(12)表示電動汽車離開配送中心或換電站時，電池為滿電狀態(tài)；式(13)表示電動汽車到達和離開客戶點時，電量相等；式(14)表示電動汽車離開點i和到達點j的電量約束；式(15)表示電動汽車k到達和離開點i時的電量在0到B之間；式(16)表示電動汽車k到達和離開點i時，車輛的載重量在0到Q之間；式(17)表示決策變量的0-1約束。

3 Danzig-Wolfe分解

以上數(shù)學模型通過Dantzig-Wolfe分解的方法可以分為主問題模型和子問題模型。

3.1 主問題模型

主問題模型構(gòu)建如下：

(18)

(19)

(20)

(21)

θr∈{0,1}，?r∈Rm；

(22)

θr∈Z，?r∈Rs。

(23)

表2 主問題模型中的變量和參數(shù)

其中，目標函數(shù)(18)與函數(shù)(1)一致，計算系統(tǒng)的最小總配送成本；式(19)～式(21)與式(2)～式(4)的效用一致；式(22)及式(23)為0-1約束和整數(shù)約束。

3.2 子問題模型

根據(jù)對偶原理，可以定義子問題模型中的相關(guān)變量：πi表示式(19)的對偶變量，當i∈R時，πi=0；當i∈C時，πi表示配送客戶的需求量；ρij表示式(20)的對偶變量，且ρij=ρji；β表示式(21)的對偶變量，則子問題模型構(gòu)建如下：

(24)

(25)

(26)

(27)

(28)

(29)

(30)

(31)

?i∈R∪C∪{0}，j∈R∪C∪{n+1}，i≠j；

(32)

(33)

ωi≥0，ωi∈Z，?i∈C；

(34)

xij∈{0,1}，?(i,j)∈A。

(35)

其中，目標函數(shù)(24)表示尋找非負檢驗數(shù)最小的路徑；式(25)～式(35)與式(5)～式(17)一致，保證子問題搜索的路徑滿足流量平衡、載重量、電量和需求可拆分約束。

4 模型求解

4.1 動態(tài)規(guī)劃算法

4.2 分支策略與整數(shù)解

5 實驗計算與分析

本部分使用的計算機核心參數(shù)為4核CPU，2.50GHz主頻，8GB內(nèi)存，算法采用單線程的JAVA代碼實現(xiàn)。

5.1 實驗數(shù)據(jù)

5.2 實驗結(jié)果與對比分析

5.2.1模型及算法的驗證分析

本研究將式(1)～式(17)轉(zhuǎn)化為CPLEX程序來評估最優(yōu)解的準確性。該部分使用IBM ILOG CPLEX 12.7求解該問題的10組小規(guī)模算例。如果CPLEX在3 600秒內(nèi)沒有得到全局最優(yōu)解，則給出當前最優(yōu)解。接著，把求得的結(jié)果與改進分支定價算法的計算結(jié)果作比較，測試結(jié)果見表3。由表3可見，CPLEX和改進分支定價算法的計算結(jié)果大致相同，模型及算法的準確性得以證明。

表3 小規(guī)模算例結(jié)果

5.2.2較大規(guī)模實驗結(jié)果

為了驗證E-SDVRP的求解算法具有一定的實用性，本研究進行了大規(guī)模實驗數(shù)據(jù)的算法測試。算法在解決較大規(guī)模E-SDVRP的實例數(shù)據(jù)與實驗結(jié)果見表4。

表4 較大規(guī)模算例結(jié)果

實驗結(jié)果表明：問題規(guī)模變大，求解時間隨之增加，本研究改進的分支定價算法都能在不同規(guī)模的數(shù)據(jù)集下求解現(xiàn)實場景的E-SDVRP，并得到問題的解，說明該算法的一般實用性。求解時間的增加與實驗數(shù)據(jù)本身和問題復雜度相關(guān)，這可以通過一些數(shù)據(jù)預處理(如客戶區(qū)域劃分等)操作，保證算法運行時間在可接受的時間范圍內(nèi)。

5.2.3相關(guān)因素靈敏度分析

最大載重量和最大行駛里程是電動汽車最核心的兩個指標參數(shù)，最大載重量的增加會導致車輛單位距離行駛成本的增加，最大行駛里程的增加會導致?lián)Q電成本的增加，進而直接影響本研究模型的計算結(jié)果。由此，本研究將在最大載重量和最大行駛里程中考慮上述兩種成本，分析參數(shù)變化對結(jié)果的影響。

為了保證實驗的一般性，本研究在較大規(guī)模算例中選取5組算例進行測試，分別命名為A、B、C、D和E。該組算例數(shù)據(jù)匯總后的情況為：客戶點數(shù)量為50，換電站數(shù)量為20，車輛數(shù)量為13，電動汽車的最大載重量分別為25、28、21、25、27，電池的最大行駛里程為291.15。

(1)電動汽車的最大載重量Q與單位行駛成本cij為了研究電動汽車的最大載重量和行駛成本對計算結(jié)果的影響，將最大載重量設(shè)為相對初始值逐漸增加0%、25%、50%、75%和100%，單位距離的行駛成本根據(jù)實驗數(shù)據(jù)的設(shè)定原則相應(yīng)地進行變化，實驗結(jié)果見表5。

表5 電動汽車最大載重量和行駛成本的靈敏度分析

實驗結(jié)果表明：客戶需求被拆分的數(shù)量和電動汽車的數(shù)量，隨著最大載重量和行駛成本的逐漸增加，呈減少的趨勢。當其最大載重量增加到一定程度后，客戶的需求不需要拆分，可以一次配送即能滿足，問題將轉(zhuǎn)化為電動汽車的VRP問題。在網(wǎng)路拓撲結(jié)構(gòu)和最大行駛里程已確定的情況下，電動汽車最大載重量的增加，將導致拆分的需求可以選擇最近的電動汽車進行配送，配送里程會相應(yīng)地減少，或者電動汽車可能借助附近的換電站增長行駛里程來服務(wù)更多的客戶點，導致整體配送車輛數(shù)量的減少，經(jīng)過換電站的數(shù)量增加。但因為行駛里程成本占總成本的比重比較大，單位距離行駛成本的增加，會導致整體配送成本呈現(xiàn)逐漸增長的趨勢。

(2)電池的最大行駛里程B與單次換電成本cB參考上述參數(shù)設(shè)置方法，將B設(shè)為相對初始值逐步增長0%、25%、50%、75%和100%，換電成本cB根據(jù)實驗數(shù)據(jù)的設(shè)定原則相應(yīng)地進行變化，實驗結(jié)果見表6。

表6 電動汽車最大行駛里程和換電成本的靈敏度分析

實驗結(jié)果表明：電動汽車經(jīng)過換電站的數(shù)量和所需的車輛數(shù)量，隨著電池的最大行駛里程和換電成本的逐漸增加，呈減少的趨勢；而配送總費用因為換電成本的增加和配送里程的減少之間的平衡，出現(xiàn)上下波動的情況。當其最大行駛里程增加到一定程度后，車輛經(jīng)過換電站的數(shù)量將減少，客戶需求被分割配送的數(shù)量將在訪問換電站數(shù)量變少時呈現(xiàn)增多的趨勢，然后再呈現(xiàn)比較平穩(wěn)的趨勢。相對于需求不可拆分場景，需求可拆分的場景通過拆分客戶需求配送多次的方式，能夠減少車輛的數(shù)量，提高車輛滿載率。實驗中，電池的最大行駛里程的增加會讓電動汽車可以服務(wù)更多的客戶點，由于車輛數(shù)量和整體載重量的限制，會選擇更加合適的電動汽車進行拆分配送，特別是當經(jīng)過一個換電站，能夠服務(wù)更遠的客戶，會導致車輛數(shù)量的減少，原來從車場出發(fā)服務(wù)客戶的車輛，直接在最大載重量的限制下由換電站出發(fā)的車輛去服務(wù)更多的客戶，整體配送里程也跟著降低。同時，電池的最大行駛里程的增加導致途徑的換電站數(shù)量減少時，減少的換電費用會觸發(fā)新的需求拆分進行調(diào)整，可能導致原有配送路線進行大的調(diào)整和客戶需求拆分數(shù)量增長。

6 結(jié)語

本研究探討E-SDVRP，建立了相應(yīng)的數(shù)學模型，并根據(jù)該問題客戶需求可分割和電動汽車有行駛里程和車輛數(shù)量限制等特點，設(shè)計了相應(yīng)的求解算法。此外，基于某大型電商網(wǎng)站的真實案例數(shù)據(jù)，驗證了本研究改進的分支定價算法可以有效地加速算法求解。對該問題的重要參數(shù)做了靈敏度分析，發(fā)現(xiàn)最大載重量增加相對于最大行駛里程增加，對總成本的影響會更大一些。

進一步的研究可以從以下兩點著手：①在求解算法中加入啟發(fā)式算法，以求解更大規(guī)模的算例；②更多地考慮物流企業(yè)的實際配送情況，把路網(wǎng)的不確定性加入到模型中，研究路網(wǎng)不確定性的情境下客戶需求可分割的電動汽車車輛路徑問題。