前言

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

目錄

• 背景介紹和問題性質

• 模型建立

• BPC技術簡介

• 相關研究及問題變式

• 參考文獻

1 背景介紹和問題性質

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

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

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

當然，如果客戶需量求小于車的容量，因為客戶的需求可拆分（split，即一次送貨量小于客戶需求），物流公司也可能獲得經濟上的收益。舉個例子。

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

雖然SDVRPTW是VRPTW對約束的松弛，但是前者模型的建立和算法的設計卻更加復雜。因為一旦客戶允許被訪問多次，那我們很難在頂點用唯一的變量分別表示該客戶每次接受服務的配送量和服務時間，這無疑為模型定義和算法帶來極大的挑戰。

所以有必要剖析SDVRPTW的性質，為復雜的問題求解提供幫助。對于任意行駛成本和行駛時間均滿足三角不等式關系的SDVRPTW實例，存在一個最優解具備以下幾個性質：

性質1：對解中任意兩條路線，它們共同訪問的客戶數目不超過1個。

性質2：每一條連接兩個客戶點的邊最多被正向或反向經過一次。

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

例如當0表示depot，送貨給拆分需求的客戶1和2時，則允許存在兩條0-1-0的路線，但不允許0-1-2-0和0-2-1-0同時存在，因為此時違反了性質1和性質2。

2 模型建立

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

因為模型在求解的時候會先進行松弛，為了使模型下界更好，通常會引進有效不等式，所以需要以下符號定義，假設U是客戶集合N的一個子集。

額外的符號說明如下：

綜上建立如下arc flow模型：

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

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

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

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

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

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

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

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

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

3 BPC技術簡介

首先我們對上文提到的arc-flow模型進行轉換。因為arc-flow模型雖然可以非常恰當地描述SDVRPTW模型，但是松弛后的下界比較差，不利于算法的收斂，而將模型轉化為set partitioning模型后再松弛，可以得到更好的下界。轉化后的模型稱為master problem（MP），需要下列的符號定義：

注：Corollary 1為前文提到的性質2

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

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

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

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

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

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

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

接下來我們基于上圖，代入到SDVRPTW模型的求解進行闡述。從圖片右上方開始，我們首先構造一個初始的分支定界樹的結點，并將該結點加入到搜索隊列。當搜索隊列不為空時，對隊列頭結點開始迭代求解。

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

綜上建立如下Subproblem模型：

其中，

本文的Subproblem是一個有界背包問題，這里Desaulniers（2010）采用labeling algorithm進行精確求解。當找不到檢驗數為負的列（路徑），則停止列生成得到當前RLMP的最優解，對應算法流程圖的LP solution，否則添加找到的負列到RLMP中，繼續調用列生成迭代。

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

1. 如果改進后的下界大于等于當前最優上界，則節點被剪枝；

2. 如果改進后的下界小于當前最優上界，且為整數解，則更新為當前最優上界；

3. 如果改進后的下界小于當前最優上界，但不是整數解，則通過一系列branching decision對節點進行分支，得到的結點加入到搜索隊列等待后續搜索。

當搜索隊列為空，即所有搜索節點都被搜索完畢后時，算法停止，框架下界值即為最優解。

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

4 相關研究及問題變式

Archetti et al. (2011)在Dsaulniers（2010）模型的基礎上改進了BPC算法。因為使用精確算法求解Subproblem比較慢，所以作者先用Tabu Search尋找負檢驗數的列，如果找不到再調用labeling algorithm，同時引進了更多類型的Cuts改善下界，使用啟發式separation algorithm尋找違反的有效不等式。以上技術都加快了BPC對SDVRPTW的求解速度。

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

Luo et al.（2017）研究了SDVRPTW with linear weight-related cost，在這個問題中，每單位距離的行駛成本是車輛載重的線性函數。本文的labeling algorithm更加高效，雖然每個標簽的定義都包含了檢驗數與車輛載重之間的函數關系，因此每個頂點可能生成的標簽數量將會是Desaulniers（2010）的三倍，但因為使用了一對多的dominance rule，所以最后保留下來的標簽數量將會變少，且性質更優，這也得益于作者提出了一個dominance graph。

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

5 參考文獻

[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] 舒勝男. 求解多周期質檢員排期問題的精確算法設計[D]. 武漢：華中科技大學. 2017