VRP算法學(xué)習(xí)

title: VRP算法學(xué)習(xí)
author: Chen Yanbo
mathjax: true
date: 2019-04-13 14:41:48
tags:

列生成

介紹

列生成算法是求解大規(guī)模整數(shù)規(guī)劃問題的優(yōu)化算法，其理論基礎(chǔ)由Danzig 等于1960 年提出，1995年Desrochers等將列生成算法實(shí)際應(yīng)用到駕駛員調(diào)度及VRP問題中。目前，列生成已經(jīng)被成功應(yīng)用于多個(gè)領(lǐng)域列生成求解過程中，將整數(shù)規(guī)劃問題線性松弛后成為 主問題MP（Master Problem）。鑒于變量規(guī)模較大，初始時(shí)只考慮小部分變量，構(gòu)造 限制主問題RMP（Restricted Master Problem），通過求解受限主問題的最優(yōu)解，獲得線性規(guī)劃的對(duì)偶變量，并在構(gòu)造網(wǎng)絡(luò)中尋找可以使目標(biāo)函數(shù)優(yōu)化的新變量，并將之加入到受限主問題中再次進(jìn)行求解，如此迭代，直到無法尋找到可使目標(biāo)函數(shù)優(yōu)化的變量，得到松弛問題的最優(yōu)解。如果解為整數(shù)，則為原問題的最優(yōu)解，如果存在非整數(shù)解，則需要進(jìn)行分支定界尋找整數(shù)解。

算法

(1)主問題與初始可行解
\begin{align}
&\min \sum_{j \in J} c_j \lambda_j\
s.t \quad &\sum_{j \in J} a_j \lambda_j\geq b \
& \lambda\geq 0,j \in J
\end{align}
這是一個(gè)通用的線性規(guī)劃模型，其中集合J代表所有的列（column）。MP的對(duì)偶變量用非負(fù)向量\pi來表示，根據(jù)對(duì)偶理論，我們希望找到一個(gè)j\in J能夠使得c_j=cj-\pi^T a_j的值最小。
(2)受限主問題求解及對(duì)偶變量
當(dāng)|J|的值很大時(shí)，這種直接定價(jià)（pricing）的方法運(yùn)算成本很高。所以考慮取一個(gè)合理的子集j'\in J來操作，用 間接枚舉（implicit enumeration）的方法來計(jì)算 檢驗(yàn)成本（reduced cost），得到限制主問題。假設(shè)\lambda和\pi分別是當(dāng)前RMP的原始最優(yōu)解和對(duì)偶最優(yōu)解，給定一個(gè)集合A，它由列（column）a_j,j\in J組成，目標(biāo)函數(shù)的成本系數(shù)c_j可以通過關(guān)于a_j的函數(shù)式c計(jì)算得到，由此得到子問題的檢驗(yàn)成本

\begin{align}
c^=\min {c(a)-\pi^T a|a\in A}
\end{align}

(3)問題求解，生成新列

對(duì)于上面的檢驗(yàn)成本，如果c \geq 0 ，且不存在負(fù)的c_j,j\in J 那么就說明限制主問題的解\lambda 就是主問題的最優(yōu)解。若c^ \geq 0 向RMP添加來自子問題的最優(yōu)解，并且不斷對(duì)RMP進(jìn)行重新優(yōu)化（re-optimizing）。當(dāng)處理有限集合A時(shí)，列生成算法是精確的（即現(xiàn)實(shí)問題都是精確的）。有限集合A 時(shí)，列生成算法是精確的（即現(xiàn)實(shí)問題都是精確的）。

分枝定界法

介紹

對(duì)于 整數(shù)規(guī)劃間題(IP),當(dāng)直接求解它比較困難時(shí)，可以采用“分而治之"(divide and conquer)的策略，先將可行域分割成一些小的集合，然后，在較小的集合上求解相應(yīng)目標(biāo)函數(shù)的最優(yōu)值，并將結(jié)果集成在一起生成原問題的最優(yōu)解。值得指出的是，在求解較小集合對(duì)應(yīng)的子問題時(shí)，還可以利用分而治之的策略進(jìn)行分析此外，可以采取多種措施對(duì)子問題進(jìn)行分析，例如可以估計(jì)子問題最優(yōu)值的某個(gè)界，將它與已經(jīng)知道的原間題的可行目標(biāo)值進(jìn)行比較，如果能夠斷定子問題無法獲得更好的可行目標(biāo)值，那么就不需要對(duì)子問題進(jìn)行精確地求解。這就是 分枝定界法(branch and bound method)的基本思想。

算法

（1）初始化
令整數(shù)規(guī)劃子問題表示為C={{IP}},S_0=S最優(yōu)值的上界z_0=\infty,下界z_{ip}=-\infty。

（2）最優(yōu)性檢驗(yàn)
若C=\emptyset，則當(dāng)z_{ip}=-\infty時(shí)，可行域S=\emptyset; 當(dāng)z_{ip}>-\infty時(shí)，滿足z_{ip}= C^Tx^0的點(diǎn)x^0是(IP)的最優(yōu)解，算法停止。

（3）分枝與松弛
從C中取出一個(gè)子問題(IP;)，并求解它的松弛形式(RP')若松弛問題(RP;)存在最優(yōu)解，則記其最優(yōu)解為x_{rp}，對(duì)應(yīng)的最優(yōu)值為z_{rp}

剪枝
(4.1)若z_{rp}^{i}\leq z_{ip}，則轉(zhuǎn)(2)。(有時(shí)，并不需要真正求出松弛間題的最優(yōu)值，在對(duì)偶間題得到的對(duì)偶目標(biāo)值接近或者小于z_{ip}時(shí)即可判斷該條件是否滿足）

(4.2)若z_{rp} \not \in S^i，則轉(zhuǎn)(5)。

(4.3)若z_{rp} \in S^i，并且c^Tx_{rp}^{i}>z_{ip}，則置z_{ip}=c^Tx_{rp}^{i},x^0=x_{rp}^{i}，并且從C中刪除所有的上界的分枝，轉(zhuǎn)(5)。

（5）分割
生成S_i的一個(gè)分割{S^{ij}}_{j=1}^k增加到C中，并且置z^{ij}=z_{rp}^{i},j=1,\dots ,k，轉(zhuǎn)(2)。

運(yùn)用列生成和分支定界法求解VRP問題

模型

基于集劃分(Set Partitioning,SP)或 集覆蓋(Set Covering,SC)的模型廣泛運(yùn)用于CVRP問題中。這個(gè)公式最初是由Balinski和Quandt提出的。為了便于求解，這部分的VRP 問題假設(shè)為此種模型。設(shè)G=(N,R) 的所有路徑節(jié)點(diǎn)的集合，對(duì)應(yīng)于可行的路徑，每條路徑都有一個(gè)相關(guān)的成本c_r，令a_ir表示顧客i經(jīng)過路徑r的次數(shù)。CVRP的擴(kuò)展模型為：

\begin{align}
&\min \sum_{r \in \Omega } c_r \lambda_r\
s.t \quad &\sum_{r \in \Omega } a_{ir} \lambda_r=1 \
& \sum_{r \in \Omega}\lambda_r=|K|\
& \lambda_r \in {0,1}
\end{align}

限制主問題

對(duì)于上面的模型，對(duì)公式(3.4)進(jìn)行線性松弛。根據(jù)列生成的理論，可以得到限制主問題的模型：

\begin{align}
&\min \sum_{r \in R' } c_r \lambda_r\
s.t \quad &\sum_{r \in R' } a_{ir} \lambda_r=1 \
& \sum_{r \in R'}\lambda_r=|K|\
& 0\leq \lambda_r\leq 1,\forall r \in R'
\end{align}

其中，R'\in \Omega，僅包含已經(jīng)計(jì)算的路徑。

問題求解，生成新列

限制主問題的初始解選定為只包含一個(gè)顧客的路徑，即depot-i-depot。求解這個(gè)限制主問題，得到限制主問題的最優(yōu)解，最優(yōu)解的目標(biāo)函數(shù)值作為新的檢驗(yàn)成本（reduced cost），如果檢驗(yàn)成本小于零，說明非最優(yōu)解，則將這個(gè)限制主問題的解作為一列加入到限制主問題中，重新求解新的限制主問題。如此循環(huán)直至檢驗(yàn)成本非負(fù)。

若存在非整數(shù)解，則進(jìn)行分枝定界

通過反復(fù)迭代，若不再有檢驗(yàn)成本c^<0的路徑產(chǎn)生，則表明主問題已經(jīng)達(dá)到最優(yōu)解，如果解為整數(shù)，則為原問題的最優(yōu)解；如果解為小數(shù)，則應(yīng)為原規(guī)劃問題的下界，需要應(yīng)用分枝定界法，尋找原問題的最優(yōu)解.通過對(duì)邊的0-1分枝重新構(gòu)造其所對(duì)應(yīng)的有向網(wǎng)絡(luò)，并應(yīng)用列生成進(jìn)行求解，直到找到最優(yōu)整數(shù)解為止。

(1)設(shè)置變量f_{up}=\infty

(2)任意選定邊(i,j)\in R，執(zhí)行R={r-(i,j)}，并對(duì)邊(i,j)進(jìn)行分枝：

(3)(i,j)=0，構(gòu)造網(wǎng)絡(luò)，刪掉邊(i,j)，應(yīng)用列生成進(jìn)行求解。若解為整數(shù)，且目標(biāo)函數(shù)值f_{RMP}< f_{up}，則更新f_{up} =f_{RMP}；若解為非整數(shù)，且f_{RMP}\geq f_{up}，則舍棄此分枝并返回(2)；若解為非整數(shù)，且f_{RMP}< f_{up}，則返回(2)繼續(xù)分枝。

(4)(i,j)=1，構(gòu)造網(wǎng)絡(luò)，刪掉邊(i,z)，其中z={N-j}，應(yīng)用列生成法進(jìn)行求解.若解為整數(shù)，且目標(biāo)值f_{RMP}< f_{up}，則更新為f_{up}= f_{RMP}；若解為非整數(shù)，且f_{RMP} \geq f_{up}，則舍棄此分枝并返回(2)；若解為非整數(shù)，且f_{RMP}< f_{up}，則返回(2)繼續(xù)分枝。

算法求解流程

整個(gè)求解的流程如下：首先建立一個(gè)Set Partitioning的CVRP模型，對(duì)約束條件進(jìn)行線性松弛，得到主問題的限制主問題。對(duì)限制主問題進(jìn)行求解后，更新新的檢驗(yàn)成本，若檢驗(yàn)成本大于零，說明該解有提升的空間，則將這個(gè)限制主問題的解作為一列加入限制主問題中更新得到新的問題，重新求解，直到檢驗(yàn)成本為負(fù)。若此時(shí)得到的最優(yōu)解不是整數(shù)，則該最優(yōu)解為問題的下界，通過分枝定界法繼續(xù)進(jìn)行求解，得到一個(gè)最優(yōu)的整數(shù)解。算法的流程圖如下：
[圖片上傳失敗...(image-6dc698-1555141349024)]

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容