前言

今天為大家介紹需求可拆分的帶時(shí)間窗車輛路徑問題（Split Delivery Vehicle Routing Problem with Time Window，簡稱SDVRPTW ）。而求解技術(shù)是精確算法之王中王——分支定價(jià)割平面法（Branch-Price-Cut，簡稱BPC），因?yàn)閲鴥?nèi)少有這類型算法的介紹，今天小編就給大家分享一下咯。

目錄

• 背景介紹和問題性質(zhì)

• 模型建立

• BPC技術(shù)簡介

• 相關(guān)研究及問題變式

• 參考文獻(xiàn)

1 背景介紹和問題性質(zhì)

傳統(tǒng)的VRPTW一般假設(shè)每個(gè)客戶的需求量小于車輛的最大載重，所以一輛車可以一次性滿足客戶的需求。VRPTW的介紹見下面推文：

干貨|十分鐘快速掌握CPLEX求解VRPTW數(shù)學(xué)模型（附JAVA代碼及CPLEX安裝流程）

在實(shí)際生活中，客戶需求也可能會(huì)大于車輛的最大載重，在要求一輛車至多訪問客戶一次的條件下，就需要多輛車服務(wù)同一個(gè)客戶，于是誕生了SDVRPTW。

當(dāng)然，如果客戶需量求小于車的容量，因?yàn)榭蛻舻男枨罂刹鸱郑╯plit，即一次送貨量小于客戶需求），物流公司也可能獲得經(jīng)濟(jì)上的收益。舉個(gè)例子。

假設(shè)客戶1、2、3的需求分別為3,4,3；每個(gè)客戶離depot 0的距離都是20，客戶之間的距離都是2；每輛車的最大載重為5；則VRP的最優(yōu)解（左圖）為3輛車，總距離為120；SDVRP的最優(yōu)解（右圖）為2輛車，總距離為84。

雖然SDVRPTW是VRPTW對(duì)約束的松弛，但是前者模型的建立和算法的設(shè)計(jì)卻更加復(fù)雜。因?yàn)橐坏┛蛻粼试S被訪問多次，那我們很難在頂點(diǎn)用唯一的變量分別表示該客戶每次接受服務(wù)的配送量和服務(wù)時(shí)間，這無疑為模型定義和算法帶來極大的挑戰(zhàn)。

所以有必要剖析SDVRPTW的性質(zhì)，為復(fù)雜的問題求解提供幫助。對(duì)于任意行駛成本和行駛時(shí)間均滿足三角不等式關(guān)系的SDVRPTW實(shí)例，存在一個(gè)最優(yōu)解具備以下幾個(gè)性質(zhì)：

性質(zhì)1：對(duì)解中任意兩條路線，它們共同訪問的客戶數(shù)目不超過1個(gè)。

性質(zhì)2：每一條連接兩個(gè)客戶點(diǎn)的邊最多被正向或反向經(jīng)過一次。

性質(zhì)3：每條路線中的客戶都至多被訪問一次。

例如當(dāng)0表示depot，送貨給拆分需求的客戶1和2時(shí)，則允許存在兩條0-1-0的路線，但不允許0-1-2-0和0-2-1-0同時(shí)存在，因?yàn)榇藭r(shí)違反了性質(zhì)1和性質(zhì)2。

2 模型建立

模型建立引用Desaulniers（2010）提出的arc-flow模型，符號(hào)定義決定直接使用原文展示，不然總覺得詞不達(dá)意。

因?yàn)槟Ｐ驮谇蠼獾臅r(shí)候會(huì)先進(jìn)行松弛，為了使模型下界更好，通常會(huì)引進(jìn)有效不等式，所以需要以下符號(hào)定義，假設(shè)U是客戶集合N的一個(gè)子集。

額外的符號(hào)說明如下：

綜上建立如下arc flow模型：

• 目標(biāo)函數(shù)(1)表示最小化車輛行駛成本；

• 約束(2)確保每個(gè)客戶的需求得到滿足;

• 約束(3)-(6)雖然是多余的約束，但是可以加強(qiáng)模型松弛的效果，其中（3）表示訪問客戶需要的最小車輛數(shù)；（4）表示共調(diào)度的車輛數(shù)；（5）表示共調(diào)度的車輛數(shù)的上下界；（6）表示k-path不等式；

• 約束(7)由性質(zhì)2每條邊至多經(jīng)過一次得到，關(guān)于arc的有效不等式，也是為了加強(qiáng)模型松弛效果；

• 約束(8)-(10)定義了路徑的結(jié)構(gòu)，從depot 0出發(fā)，最后回到depot n+1；

• 約束(11)-(12)確保不違反每個(gè)客戶的時(shí)間窗；

• 約束(13)確保不違反車輛的最大載重約束；

• 約束(14)表示如果車輛訪問了客戶，則有相應(yīng)的配送量，且不得超過該客戶的總需求；

• 約束(15)為決策變量的取值約束。

3 BPC技術(shù)簡介

首先我們對(duì)上文提到的arc-flow模型進(jìn)行轉(zhuǎn)換。因?yàn)閍rc-flow模型雖然可以非常恰當(dāng)?shù)孛枋鯯DVRPTW模型，但是松弛后的下界比較差，不利于算法的收斂，而將模型轉(zhuǎn)化為set partitioning模型后再松弛，可以得到更好的下界。轉(zhuǎn)化后的模型稱為master problem（MP），需要下列的符號(hào)定義：

注：Corollary 1為前文提到的性質(zhì)2

綜上建立如下set partitioning模型（MP）：

• 目標(biāo)函數(shù)(16)表示最小化車輛行駛成本；

• 約束(17)-(22)等價(jià)于約束(2)-(7)；

• 約束(23)確保MP的決策變量θ_rw非負(fù)；

• 約束(24)和(27)分別表示路徑θ_r和弧y_ij與決策變量的關(guān)系；

• 剩余約束為變量的取值約束。

但MP的不足在于包含大量的變量（路徑），為了解決這個(gè)問題，可以利用分支定價(jià)割平面算法（BPC）進(jìn)行處理，下面介紹的技術(shù)框架也是由Desaulniers（2010）提出的。BPC是分支定界法的一種延伸，其外部調(diào)用分支定界法的框架，在分支定界樹（Branch）的每個(gè)結(jié)點(diǎn)上通過列生成（Price）求解set partitioning模型的線性松弛來得到該節(jié)點(diǎn)的下界，并通過引入有效不等式（Cut）改善下界。下圖引用自舒勝男的碩士論文（見文獻(xiàn)6），流程圖詳細(xì)解釋了算法的框架細(xì)節(jié)。

接下來我們基于上圖，代入到SDVRPTW模型的求解進(jìn)行闡述。從圖片右上方開始，我們首先構(gòu)造一個(gè)初始的分支定界樹的結(jié)點(diǎn)，并將該結(jié)點(diǎn)加入到搜索隊(duì)列。當(dāng)搜索隊(duì)列不為空時(shí)，對(duì)隊(duì)列頭結(jié)點(diǎn)開始迭代求解。

對(duì)MP進(jìn)行松弛，構(gòu)造一個(gè)求解表達(dá)式(16)-(20)和(23)的約束線性主問題（Restricted linear master problem，RLMP），RLMP雖然與松弛后的MP（稱為LMP）有相同的約束，但是只包含了部分有限的決策變量。然后開始列生成迭代。通過前面推文的復(fù)習(xí)，我們知道在列生成過程中，核心就是通過定義求解Subproblem（也有叫pricing problem），尋找除了RLMP包含的變量外，LMP是否還存在負(fù)檢驗(yàn)數(shù)的變量θ_rw。Subproblem的符號(hào)定義如下：

綜上建立如下Subproblem模型：

其中，

本文的Subproblem是一個(gè)有界背包問題，這里Desaulniers（2010）采用labeling algorithm進(jìn)行精確求解。當(dāng)找不到檢驗(yàn)數(shù)為負(fù)的列（路徑），則停止列生成得到當(dāng)前RLMP的最優(yōu)解，對(duì)應(yīng)算法流程圖的LP solution，否則添加找到的負(fù)列到RLMP中，繼續(xù)調(diào)用列生成迭代。

將上述過程最終得到的LP solution作為當(dāng)前分支定界樹節(jié)點(diǎn)的下界，并通過引進(jìn)違反的有效不等式作為Cuts，加入到當(dāng)前RLMP的約束中，再調(diào)用列生成過程改進(jìn)下界，直到找不到違反的Cuts時(shí)停止列生成迭代，得到改進(jìn)后的下界，則算法需要判斷以下三種情況：

1. 如果改進(jìn)后的下界大于等于當(dāng)前最優(yōu)上界，則節(jié)點(diǎn)被剪枝；

2. 如果改進(jìn)后的下界小于當(dāng)前最優(yōu)上界，且為整數(shù)解，則更新為當(dāng)前最優(yōu)上界；

3. 如果改進(jìn)后的下界小于當(dāng)前最優(yōu)上界，但不是整數(shù)解，則通過一系列branching decision對(duì)節(jié)點(diǎn)進(jìn)行分支，得到的結(jié)點(diǎn)加入到搜索隊(duì)列等待后續(xù)搜索。

當(dāng)搜索隊(duì)列為空，即所有搜索節(jié)點(diǎn)都被搜索完畢后時(shí)，算法停止，框架下界值即為最優(yōu)解。

小聲吐槽：以上步驟希望讀者結(jié)合前言的推文回顧，仔細(xì)閱讀，定可以對(duì)其他涉及BPC的論文進(jìn)行舉一反三。小編也是學(xué)了很久才搞明白。

4 相關(guān)研究及問題變式

Archetti et al. (2011)在Dsaulniers（2010）模型的基礎(chǔ)上改進(jìn)了BPC算法。因?yàn)槭褂镁_算法求解Subproblem比較慢，所以作者先用Tabu Search尋找負(fù)檢驗(yàn)數(shù)的列，如果找不到再調(diào)用labeling algorithm，同時(shí)引進(jìn)了更多類型的Cuts改善下界，使用啟發(fā)式separation algorithm尋找違反的有效不等式。以上技術(shù)都加快了BPC對(duì)SDVRPTW的求解速度。

Salani and Vacca（2011）研究了discrete SDVRPTW，在這個(gè)問題中，客戶的需求為一系列可以分別配送的離散物品，且在客戶點(diǎn)的服務(wù)時(shí)間正比于配送量。因?yàn)檫@個(gè)特征，前文提到的性質(zhì)不再有效，比如實(shí)例的解允許兩條路徑有超過一個(gè)相同客戶是分批交貨的。

Luo et al.（2017）研究了SDVRPTW with linear weight-related cost，在這個(gè)問題中，每單位距離的行駛成本是車輛載重的線性函數(shù)。本文的labeling algorithm更加高效，雖然每個(gè)標(biāo)簽的定義都包含了檢驗(yàn)數(shù)與車輛載重之間的函數(shù)關(guān)系，因此每個(gè)頂點(diǎn)可能生成的標(biāo)簽數(shù)量將會(huì)是Desaulniers（2010）的三倍，但因?yàn)槭褂昧艘粚?duì)多的dominance rule，所以最后保留下來的標(biāo)簽數(shù)量將會(huì)變少，且性質(zhì)更優(yōu)，這也得益于作者提出了一個(gè)dominance graph。

Archett et al.（2011）首次用BPC解決SDVRP，即問題去掉了對(duì)客戶時(shí)間窗的約束。模型和算法都與Desaulniers（2010）相似，主要區(qū)別是在求解Subproblem時(shí)，將每個(gè)客戶點(diǎn)轉(zhuǎn)化為一系列該客戶可能配送量的點(diǎn)，再利用labeling algorithm求解時(shí)將變得簡單，但因此算法的效率也極大的取決于客戶需求的規(guī)模。

5 參考文獻(xiàn)

[1] Desaulniers G (2010) Branch-and-price-and-cut for the split delivery vehicle routing problem with time windows. Oper.

Res. 58(1):179–192.

[2] Archetti C, Bouchard M, Desaulniers G (2011) Enhanced branch and price and cut for vehicle routing with split deliveries and time windows. Transportation Sci. 45(3):285–298.

[3] Salani M, Vacca I (2011) Branch and price for the vehicle routing problem with discrete split deliveries and time windows. Eur. J. Oper. Res. 213(3):470–477.

[4] Luo Z, Qin H, Zhu W, Lim A (2017) Branch and price and cut for the split-delivery vehicle routing problem with time windows and linear weight-related cost. Transportation Sci. 51(2):668–687.

[5] Archetti C, Bianchessi N, Speranza MG (2011) A column generation approach for the split delivery vehicle routing problem. Networks. 58(4):241–254.

[6] 舒勝男. 求解多周期質(zhì)檢員排期問題的精確算法設(shè)計(jì)[D]. 武漢：華中科技大學(xué). 2017