基于改進(jìn)分支定價(jià)法的車輛路徑優(yōu)化研究

呂欣昊

（山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590）

0 引言

全球物流產(chǎn)業(yè)相關(guān)數(shù)據(jù)顯示，快遞平均單價(jià)持續(xù)走低，配送成本增加，導(dǎo)致企業(yè)利潤(rùn)空間進(jìn)一步被壓縮。雖然末端配送距離不足整個(gè)運(yùn)輸距離的5%，花費(fèi)的時(shí)長(zhǎng)卻占據(jù)了整個(gè)快遞業(yè)務(wù)時(shí)長(zhǎng)的45%，這不僅影響著物流配送的最終成本還直接決定了客戶的購(gòu)物體驗(yàn)。末端配送的目的是在保證滿足客戶需求的前提下，最小化配送的總成本。為了追求更低的配送成本，就要進(jìn)一步提高解的質(zhì)量。

為了追求更低的配送成本，就要進(jìn)一步提高解的質(zhì)量。學(xué)術(shù)界不滿足于啟發(fā)式算法帶來的近似解，開始從多個(gè)角度運(yùn)用精確算法對(duì)末端配送優(yōu)化問題進(jìn)行了研究并取得了相應(yīng)的成果。Desrochers[1]等在1988年采用標(biāo)簽算法研究了SPPTW（The Shortest Path Problem With Time Windows）問題，成功處理了2500個(gè)節(jié)點(diǎn)和250000條弧的車輛路徑問題。1992年 Desrochers[2]又依托標(biāo)簽算法結(jié)合列生成研究了VRPTW（The Vehicle Routing Problem With Time Windows）問題，即分支定價(jià)算法的雛形。Augerat[3]在 1998年從分支切割的角度研究了 CVRP（The Capacitated Vehicle Routing Problem）問題，構(gòu)建出可以識(shí)別違反有效不等式的算法。精確算法開始由初始應(yīng)用階段轉(zhuǎn)變到提高效率階段。2006年Irnich[4]采用K循環(huán)消除成功解決了帶資源約束的最短路徑問題，得出 2K≤ 時(shí)提升算法效率最高的結(jié)論。2006年Chabrier[5]等對(duì)更大規(guī)模的CVRP問題進(jìn)行研究，提出了新的優(yōu)勢(shì)規(guī)則，結(jié)果表明新優(yōu)勢(shì)規(guī)則的提出，可大幅度減少了動(dòng)態(tài)規(guī)劃算法中標(biāo)簽的數(shù)量。此后研究者又開始根據(jù)問題本身的屬性特點(diǎn)，通過調(diào)整精確算法的結(jié)構(gòu)來提高效率。2011年Toth[6]等結(jié)合CVRP問題的特點(diǎn)，設(shè)計(jì)了離散的方案。Desaulniers[7]在 2016年采用分支定價(jià)算法解決了 SDVRPTW（The Split-delivery Vehicle Routing Problem With Time Windows）問題，成功處理了504個(gè)DSVRPT基本算例中的176個(gè)。2016年揭婉晨[8]運(yùn)用分支定價(jià)算法處理多車型電動(dòng)汽車車輛問題。2017年Spliet[9]結(jié)合TWAVRP問題的特點(diǎn)，設(shè)計(jì)了相應(yīng)的分支定價(jià)模型來處理不同概率下的客戶需求。隨著處理效率的提升，精確算法已經(jīng)可以處理更大規(guī)模，更加復(fù)雜情況下的車輛路徑優(yōu)化問題。2018年Qie He[10]從具有凸節(jié)點(diǎn)成本的角度指出不便成本對(duì)配送成本影響的重要性，采用分支切割定價(jià)算法驗(yàn)證了不便成本會(huì)對(duì)車輛路徑規(guī)劃的影響。2018年P(guān)essozai[11]為異構(gòu)車輛路徑提出了一種新的 BCP（Branch-Cut-and- Price）算法，解決了200個(gè)客戶節(jié)點(diǎn)的VRP變體問題。2018年Bulh?es[12]從最小延遲問題(MLP)的角度提出了一個(gè)新的MLP分支定價(jià)算法。目前以分支定價(jià)算法為精確算法的代表，其改進(jìn)工作也主要集中在優(yōu)化標(biāo)簽規(guī)則方面，較少的考慮分支階段對(duì)算法性能的影響。在分支階段，以往的基于{0,1}的分支策略會(huì)造成分支定界樹的嚴(yán)重不平衡，這使得算法在運(yùn)行的時(shí)候，分支定界樹中會(huì)出現(xiàn)某條分支過長(zhǎng)而另一條分支會(huì)很短，進(jìn)而影響二叉樹的尋優(yōu)效率。基于這個(gè)問題本文提出了一種新的分支策略來改進(jìn)分支定價(jià)方案，通過維持分支定界樹平衡性從而提升效率。本文使用改進(jìn)后分支定價(jià)算法處理考慮（1）客戶的時(shí)間窗，（2）車輛的里程，（3）車輛的載重，（4）等待成本，（5）運(yùn)輸成本五種約束條件下的車輛路徑問題。通過與原有分支策略進(jìn)行對(duì)比，驗(yàn)證改進(jìn)算法在求解效率上的優(yōu)越性。

1 多約束條件下車輛路徑問題模型的建立

1.1 問題描述

某物流公司在某地有一個(gè)物流倉(cāng)庫(kù)負(fù)責(zé)給本地區(qū)的一定數(shù)量的客戶提供配送服務(wù)，倉(cāng)庫(kù)配送車輛數(shù)量充足且車型相同。車輛一開始都從配送中心出發(fā)，最終都需要返回配送中心。配送中心和客戶都有一個(gè)時(shí)間窗。每輛車必須在客戶給定時(shí)間窗截止時(shí)間前到達(dá)并在時(shí)間窗最早時(shí)間后進(jìn)行服務(wù)，這里強(qiáng)制在時(shí)間窗內(nèi)進(jìn)行服務(wù)即強(qiáng)時(shí)間窗約束。如果車輛早于時(shí)間窗口到達(dá)需要等待并計(jì)算成本，在倉(cāng)庫(kù)等待不計(jì)算等待成本。假設(shè)車輛具有里程約束，從配送中心出發(fā)的車輛為滿電狀態(tài)，在配送區(qū)域設(shè)有一定數(shù)量的充電站可以供車輛充電。假設(shè)車輛具有載重約束，一輛車服務(wù)總的客戶需求不能超過其車輛的載重約束。每個(gè)客戶都要被服務(wù)且只能被服務(wù)一次，每個(gè)客戶具有相同的服務(wù)時(shí)間。

1.2 模型建立

建立一個(gè)有向圖G(A,N)，圖中的詳細(xì)變量說明如下。

表1 符號(hào)說明Tab.1 Symbol description

通過 Danizig-Wolfe分解獲得松弛后的受限的主問題模型如下。關(guān)于Danizig-Wolfe分解更詳細(xì)的分解過程請(qǐng)參考Vanderbeck和Savelsbergh (2006)[13]的論文。

公式（1）是目標(biāo)函數(shù)。公式（2）要求每個(gè)客戶至少需要被訪問一次。公式（3）表示變量rx為非負(fù)數(shù)。這里RR′?，R′是R的子集并且初始化狀態(tài)是每個(gè)客戶單獨(dú)分配一輛車。

2 算法設(shè)計(jì)

本節(jié)根據(jù)第1節(jié)中建立的RMP模型使用改進(jìn)的分支定價(jià)和動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)對(duì)問題的求解。第一步將通過定價(jià)策略對(duì)R′擴(kuò)展，第二步提出新的分支策略，第三步運(yùn)用動(dòng)態(tài)規(guī)劃算法安排充電站位置以完成對(duì)最終車輛路徑問題的求解。

2.1 基于標(biāo)簽規(guī)則的定價(jià)策略

對(duì)RMP求解后，獲得了每個(gè)客戶節(jié)點(diǎn)關(guān)于約束（2）的對(duì)偶變量。根據(jù)這個(gè)值來安排合適的列插入RMP中，組成新的RMP。尋找合適的列稱為定價(jià)問題，是列生成算法中的核心問題之一。為了挑選合適的列進(jìn)入RMP，需要計(jì)算可行路徑集合中路徑的邊際成本，邊際成本的值決定該列是否可以插入到 RMP，邊際成本的值和 RMP求解后生成的對(duì)偶變量有關(guān)。具體的邊際成本公式如下所示：

根據(jù)列生成算法的定義，將具有負(fù)的邊際成本路線添加到RMP中。在執(zhí)行定價(jià)之前需要組建可行路徑集合R，采用的方式為2006年Chabrier提出的標(biāo)簽算法。優(yōu)勢(shì)規(guī)則的運(yùn)用將顯著減少了節(jié)點(diǎn)中標(biāo)簽的數(shù)量。以50客戶節(jié)點(diǎn)為例，正常循環(huán)會(huì)產(chǎn)生502個(gè)標(biāo)簽，通過使用上述優(yōu)勢(shì)規(guī)則后，實(shí)際產(chǎn)生到配送中心標(biāo)簽數(shù)量卻只有 3598個(gè)（取決于具體的算例）。當(dāng)R中沒有發(fā)現(xiàn)負(fù)檢驗(yàn)數(shù)的路線時(shí)，對(duì)RMP進(jìn)行分支操作。

2.2 雙重禁用的分支策略

分支策略是依靠分支定界樹執(zhí)行的操作，目的是獲得最優(yōu)的整數(shù)解。分支策略好壞決定了獲取上界的速度。傳統(tǒng)的分支策略是對(duì)所有的弧計(jì)算其弧流量ijf，選擇一條弧流量大于0且小于1的弧ije。一個(gè)分支禁止使用該弧的路線，另一個(gè)分支必須使用包含該弧的路線，但這種效率被證明效率非常低，很容易造成分支定界樹的不平衡，其中 xr=1分支下的節(jié)點(diǎn)數(shù)量遠(yuǎn)遠(yuǎn)大于 xr= 0 的數(shù)量。針對(duì)這個(gè)問題，本文提出了新的分支策略平衡分支定界樹的兩側(cè)的分支。描述如下：

圖1 分支規(guī)則Fig.1 Branching rule

2.3 基于優(yōu)勢(shì)充電站的動(dòng)態(tài)規(guī)劃策略

充電站的安排是找到滿足里程約束并且不影響客戶配送時(shí)間的最小數(shù)量。規(guī)則如下：

（1）找到一條路徑中各條弧（i, j）之間距離最近的充電站作為優(yōu)勢(shì)充電站。

（2）將每條弧擁有的優(yōu)勢(shì)充電站組合為一個(gè)集合。

（3）通過動(dòng)態(tài)規(guī)劃算法搜索該集合，要求使用充電站的次數(shù)最少，同時(shí)需要滿足車輛的里程約束且不違反該路線的時(shí)間窗約束。

3 算例分析

3.1 實(shí)例數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)采用某大件物流配送中心 50個(gè)客戶訂單及其相關(guān)數(shù)據(jù)，所采用的數(shù)據(jù)集中提供了車輛的數(shù)量、載重、里程、充電時(shí)間、行駛成本、行駛速度等車輛信息。還有客戶的位置（經(jīng)緯度）、服務(wù)時(shí)間、貨物重量、時(shí)間窗等信息。此外還包含轄區(qū)內(nèi)100個(gè)充電站的位置信息，這里使用距離為歐式距離。

3.2 程序的運(yùn)行環(huán)境

表2 運(yùn)行環(huán)境Tab.2 Operating environment

3.3 運(yùn)行結(jié)果及分析

下表展示了在使用改進(jìn)的分支策略和基于{0,1}分支策略處理4組數(shù)據(jù)所獲得計(jì)算時(shí)間。

表3 50個(gè)節(jié)點(diǎn)計(jì)算時(shí)間表Tab.3 50 node calculation schedule

通過上表中數(shù)據(jù)可以看到對(duì)于兩個(gè)分支都獲得同樣的結(jié)果，證明了改進(jìn)分支策略的正確性。4組數(shù)據(jù)改進(jìn)后的分支策略的運(yùn)行時(shí)間都低于基于{0,1}的分支策略，說明改進(jìn)的分支策略確實(shí)取得了一定的效果，平均的效率提升在12%左右。實(shí)際在程序的運(yùn)行過程中，基于{0,1}的分支策略需要判斷ije禁用和使用兩種情況，而改進(jìn)的分支策略只需判斷ije禁用這一種情況，所以在這段對(duì)弧判斷的時(shí)間上，改進(jìn)的分支策略執(zhí)行時(shí)間只有基于{0,1}分支策略的一半。改進(jìn)的分支策略所生成的分支定界樹的深度也明顯小于基于{0,1}分支策略，可以更快的獲得問題的解。改進(jìn)后的分支策略更加相比之前的策略在計(jì)算4組數(shù)據(jù)時(shí)間上更加穩(wěn)定。基于{0,1}分支策略對(duì)同樣規(guī)模的4組數(shù)據(jù)計(jì)算時(shí)間相差較大，也是因?yàn)榛趝0,1}分支策略會(huì)依據(jù)數(shù)據(jù)的特點(diǎn)生成不同的不平衡二叉樹從使得計(jì)算效率的不穩(wěn)定，而改進(jìn)的分支策略能更好的避免這種情況。

下圖是最終的路線規(guī)劃圖，其中0和51表示倉(cāng)庫(kù)，1～50表示客戶，大于51表示充電站。

圖2 最終50客戶節(jié)點(diǎn)路線圖Fig.2 Final 50 customer node roadmap

4 結(jié)論

本文充分考慮了強(qiáng)時(shí)間窗約束、載重約束、里程約束下的車輛配送路徑研究，并提出了改進(jìn)的分支定價(jià)算法。改進(jìn)的分支定價(jià)算法針對(duì)分支階段基于{0,1}分支策略不能維持二叉樹平衡而導(dǎo)致的效率低下問題，提出了可維持二叉樹平衡新的分支策略，保持了分支定界樹的平衡性同時(shí)也加快求解速度。實(shí)驗(yàn)所采用的數(shù)據(jù)相對(duì)于以往研究的數(shù)據(jù)更難以處理，以此測(cè)試改進(jìn)的分支策略和基于{0,1}分支策略在尋優(yōu)能力和算法穩(wěn)定性方面的表現(xiàn)。

運(yùn)用對(duì)照實(shí)驗(yàn)的方法，在保證處理數(shù)據(jù)和定價(jià)策略相同的條件下，對(duì)兩種不同的分支策略分別進(jìn)行實(shí)驗(yàn)。對(duì)照實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)的分支定價(jià)方案對(duì)于客戶需求種類多、時(shí)間窗緊、位置分布均勻的復(fù)雜情況有更好的處理效果。同時(shí)本文也考慮了車輛的里程約束，可以更好的指導(dǎo)車輛在實(shí)際生產(chǎn)過程中的路徑規(guī)劃。改進(jìn)的分支定價(jià)算法在求解車輛路徑問題的效率和穩(wěn)定性方面的良好性能，為今后的分支定價(jià)算法研究[14-18]做參考。