周 紅，朱 瑾

（上海海事大學(xué)物流科學(xué)與工程研究院,上海 201306）

0 引言

自主駕駛無(wú)人跨運(yùn)車(chē)(Autonomous Straddle Carrier，ASC)是一種應(yīng)用在自動(dòng)化集裝箱碼頭上的移動(dòng)機(jī)器人，依靠人工智能技術(shù)能夠?qū)崿F(xiàn)自主定位、自主導(dǎo)航、面對(duì)突發(fā)狀況能夠做出智能決策，并且能夠自主規(guī)劃出集裝箱水平運(yùn)輸?shù)淖顑?yōu)路徑[1]。AGV與ASC都是自動(dòng)化集裝箱碼頭上的水平運(yùn)輸車(chē)輛，主要的區(qū)別在于ASC不需要與岸橋和自動(dòng)軌道吊直接交互，可以獨(dú)立完成集裝箱的裝卸工作，裝卸效率高。ASC的車(chē)輛路徑問(wèn)題就是為每臺(tái)ASC尋找一條可行且高效的路徑，使ASC完成一系列的集裝箱轉(zhuǎn)運(yùn)工作。由于涉及到的作業(yè)量大、ASC數(shù)量多且碼頭環(huán)境復(fù)雜，ASC車(chē)輛路徑問(wèn)題受到越來(lái)越多的關(guān)注。

基于ASC作業(yè)的獨(dú)立性，可以將ASC車(chē)輛路徑問(wèn)題建模為帶硬時(shí)間窗的同時(shí)取送貨問(wèn)題（PDPTW）。關(guān)于車(chē)輛路徑問(wèn)題的求解算法，已經(jīng)有許多學(xué)者進(jìn)行了深入研究。例如，姚錦寶等[2]用改進(jìn)的蟻群算法對(duì)同時(shí)取貨送貨車(chē)輛路徑問(wèn)題進(jìn)行求解，賈方方等[3]采用改進(jìn)的粒子群優(yōu)化算法對(duì)同時(shí)取貨送貨車(chē)輛路徑問(wèn)題進(jìn)行求解，陳秀娟等[4]用改進(jìn)的蟻群算法求解了逆向物流中的車(chē)輛路徑問(wèn)題，武小平等[5]設(shè)計(jì)遺傳算法求解了不確定配送條件下的車(chē)輛路徑問(wèn)題。文獻(xiàn)[6，7]提出了基于禁忌搜索和導(dǎo)引式局部搜索的混合式啟發(fā)式算法求解同時(shí)取貨送貨問(wèn)題，文獻(xiàn)[8]提出一種混合遺傳算法求解了帶硬時(shí)間窗的車(chē)輛路徑問(wèn)題，但這些方法都是基于近似的方法，能夠得到可行解但并不是最優(yōu)解。近年來(lái)關(guān)于VRP及其一系列變體問(wèn)題的研究大都將其轉(zhuǎn)化為大規(guī)模整數(shù)規(guī)劃問(wèn)題來(lái)求解。在精確算法的相關(guān)研究中，最基本的方法為分支定界算法，雖然能夠從理論上保證在有限時(shí)間內(nèi)獲得最優(yōu)解，但在實(shí)際計(jì)算中存在著計(jì)算耗時(shí)巨大的情況。Desrosiers等[9]首次提出將列生成算法與分支定界算法結(jié)合起來(lái)對(duì)車(chē)輛路徑問(wèn)題進(jìn)行求解，Barnhart等[10]將其命名為分支定價(jià)算法。文獻(xiàn)[11]針對(duì)自動(dòng)化集裝箱碼頭ASC的車(chē)輛路徑問(wèn)題，以車(chē)輛運(yùn)輸成本最低為目標(biāo)建立優(yōu)化模型，提出了一種基于分支定界和列生成算法的精確算法，但在模型中沒(méi)有考慮ASC的載荷量約束，并且子問(wèn)題的求解依賴(lài)于主問(wèn)題的對(duì)偶變量，每次迭代需要重新對(duì)子問(wèn)題建模，影響算法的求解效率。文獻(xiàn)[12]提出了ASC車(chē)輛路徑問(wèn)題的多目標(biāo)優(yōu)化模型，用分支定價(jià)算法求解，并與單目標(biāo)車(chē)輛路徑問(wèn)題對(duì)比，驗(yàn)證了多目標(biāo)模型的有效性和靈活性。車(chē)輛路徑問(wèn)題的子問(wèn)題通常是帶資源約束的最短路徑問(wèn)題（ESPPRC）。文獻(xiàn)[13]提出了K循環(huán)消除方法提高對(duì)子問(wèn)題松弛問(wèn)題下界的約束。文獻(xiàn)[14，15]分別提出了標(biāo)簽算法和列生成算法，并應(yīng)用到車(chē)輛路徑問(wèn)題中，標(biāo)簽算法通過(guò)迭代過(guò)程對(duì)標(biāo)簽逐步修正，可以在搜索過(guò)程中刪除大量標(biāo)簽，提高算法效率，用列生成算法求解了ESPPRC的松弛問(wèn)題。文獻(xiàn)[16]引入了子集-行不等式，極大地改進(jìn)了分支定價(jià)算法中每個(gè)節(jié)點(diǎn)的下界，但增加了定價(jià)問(wèn)題的復(fù)雜性。文獻(xiàn)[17]提出了一種基于隱枚舉法的精確求解方法，極大地縮小了搜索空間。

在分支定價(jià)算法的框架中設(shè)計(jì)合理的加速策略以提高車(chē)輛路徑問(wèn)題中定價(jià)子問(wèn)題的求解效率仍然是目前的研究熱點(diǎn)?；诖?，本文以最小化ASC總行駛距離為目標(biāo)，考慮ASC的載荷量以及每個(gè)作業(yè)點(diǎn)的時(shí)間窗和需求量等因素，建立帶硬時(shí)間窗的ASC車(chē)輛路徑問(wèn)題的混合整數(shù)規(guī)劃模型，并改進(jìn)分支定價(jià)算法求解模型，即將脈沖算法嵌入列生成算法提高子問(wèn)題的求解效率。最后通過(guò)求解不同規(guī)模的算例驗(yàn)證了模型和算法的有效性，并對(duì)影響算法效率的相關(guān)因素進(jìn)行了靈敏度分析。

1 問(wèn)題描述與數(shù)學(xué)模型

1.1 問(wèn)題描述

ASC車(chē)輛路徑問(wèn)題可以描述為將集裝箱的運(yùn)輸任務(wù)分配給ASC，以滿(mǎn)足每個(gè)作業(yè)點(diǎn)（提箱點(diǎn)/卸箱點(diǎn)）的時(shí)間窗約束、ASC的載荷量約束和ASC的數(shù)量約束。假設(shè)前一個(gè)任務(wù)的卸箱點(diǎn)為后一個(gè)任務(wù)的提箱點(diǎn)，并以最小化ASC總行駛距離為目標(biāo)函數(shù)，將ASC車(chē)輛路徑問(wèn)題建模為帶硬時(shí)間窗的同時(shí)取送貨問(wèn)題（PDPTW）。

為符合PDPTW的數(shù)學(xué)框架，簡(jiǎn)化搜索空間結(jié)構(gòu)，首先根據(jù)自動(dòng)化集裝箱碼頭的堆場(chǎng)環(huán)境圖構(gòu)建ASC-PDPTW運(yùn)輸網(wǎng)絡(luò)，用有向圖G=（P，A）表示，由作業(yè)點(diǎn)集P={0，1，2，...，n，n+1} 和弧集A組成，作業(yè)點(diǎn)0和n+1表示車(chē)場(chǎng)，n+1為虛擬節(jié)點(diǎn)，代表終點(diǎn)，定義節(jié)點(diǎn)n到n+1的距離為0，其他n個(gè)作業(yè)點(diǎn)集記為N={1，2，...，n}。ASC的集合記為V={1，2，...，k}，每個(gè)作業(yè)點(diǎn)i（i∈N）都有給定的需求量di、所需的作業(yè)時(shí)間si和時(shí)間窗[ai，bi]，ai，bi分別表示該作業(yè)的最早開(kāi)始時(shí)間和最晚開(kāi)始時(shí)間，ASC早到必須等待，但不能在最晚作業(yè)時(shí)間bi之后到達(dá)。其中車(chē)場(chǎng)的時(shí)間窗[a0，b0]=[an+1，bn+1]表示作業(yè)完成的周期。ASC的最大載荷量為q，tij表示ASC從作業(yè)點(diǎn)i行駛到作業(yè)點(diǎn)j(i，j∈N)的行駛時(shí)間，cij表示ASC訪問(wèn)運(yùn)輸網(wǎng)絡(luò)中每個(gè)弧段的成本（行駛距離）。

假設(shè)q，ai，bi，di，cij均為非負(fù)整數(shù)，tij，si為正整數(shù)。引入兩個(gè)決策變量x和s，對(duì)每個(gè)弧段(i，j)和每一輛車(chē)k，定義

其中i≠j，i≠n+1，j≠0，sik定義為車(chē)輛k在i點(diǎn)開(kāi)始作業(yè)的時(shí)間，若k不在i點(diǎn)作業(yè)則sik無(wú)意義，本文假設(shè)a0=0，即對(duì)于所有的ASC均有s0k=0。

本文所解決的問(wèn)題是改進(jìn)分支定價(jià)算法求解ASC最優(yōu)行駛路徑，在各個(gè)作業(yè)點(diǎn)的時(shí)間窗內(nèi)完成所有的運(yùn)輸任務(wù)，并使得ASC總行駛距離最短。

1.2 數(shù)學(xué)模型

以最小化ASC總行駛距離為目標(biāo)建立ASC-PDPTW混合整數(shù)規(guī)劃模型。

其中約束條件(7)可以線(xiàn)性化為：

Mij是一個(gè)很大的常數(shù)，可以縮小到max{bi+tij-aj}，{i，j}∈A。

式(1)表示最小化ASC總行駛距離，式(2)保證每個(gè)作業(yè)點(diǎn)只能被一輛ASC訪問(wèn)且僅訪問(wèn)一次，式(3)表示每輛ASC的載荷量不能超過(guò)q，式(4)～式(6)確保每輛ASC由車(chē)場(chǎng)出發(fā)，依次完成作業(yè)后仍回到車(chē)場(chǎng)，式(7)表示ASC從作業(yè)點(diǎn)i行駛到作業(yè)點(diǎn)j的時(shí)間約束，式(8)表示ASC到達(dá)作業(yè)點(diǎn)的時(shí)間必須滿(mǎn)足時(shí)間窗約束，式(9)表示若第k輛ASC從i行駛到j(luò)，則xijk=1，否則為0，式(10)給出了ASC數(shù)量上限。

2 模型分解

建立的模型中只有賦值約束(2)是車(chē)輛耦合約束，其余的約束條件均分別處理各ASC。因此可以將模型化為具有對(duì)角結(jié)構(gòu)的線(xiàn)性規(guī)劃問(wèn)題，然后用列生成算法求解，從Dantzig-Wolf分解原理出發(fā)，將模型分解為帶資源約束的最短路徑定價(jià)子問(wèn)題和變量數(shù)目很大的主問(wèn)題。

2.1 ASC-PDPTW主問(wèn)題

設(shè)Ω為車(chē)輛k(k∈V)的可行路徑集合，隨著問(wèn)題規(guī)模的增大，可行路徑的數(shù)目呈現(xiàn)爆炸式增長(zhǎng)，因此不能把所有的可行路徑都在模型中顯性的表示出來(lái)。本文從單純形法的理論出發(fā)，將問(wèn)題轉(zhuǎn)化為求解滿(mǎn)足約束的若干條可行路徑，并使得目標(biāo)函數(shù)值最小。主問(wèn)題即為包含這若干條可行路徑的集合劃分問(wèn)題。

設(shè)Ω為車(chē)輛k(k∈V)的可行路徑集合，二進(jìn)制決策變量xkijp=1表示車(chē)輛k在它的可行路徑集合中的路徑p(p∈Ω)中從i到j(luò)，否則為0，ykp表示車(chē)輛k是否經(jīng)過(guò)路徑p，則有：

通過(guò)xkijp可以定義一條路徑的花費(fèi)為；車(chē)輛k訪問(wèn)客戶(hù)點(diǎn)i的次數(shù)為aki，?k∈V,?i∈N,?p∈Ω。

在列生成算法中，并不是所有的列都顯性的表達(dá)出來(lái)，主問(wèn)題的列集合僅限于已經(jīng)生成的列，在所有可行路徑集合中找到滿(mǎn)足條件和目標(biāo)函數(shù)的路徑Ω'，稱(chēng)為受限主問(wèn)題(Restricted Master Problem，RMP)。RMP的模型表示如下：

2.2 ASC-ESPPRC定價(jià)子問(wèn)題

ASC車(chē)輛路徑問(wèn)題的子問(wèn)題是帶資源約束的最短路徑問(wèn)題（ASC-ESPPRC），是NP難問(wèn)題。為了找到向RMP可行路徑集Ω'中添加的路徑，ASC-ESPPRC定價(jià)子問(wèn)題是在考慮約束(3)至(9)的條件下最小化可行路徑的節(jié)約成本，由原問(wèn)題分解得到的模型為：

3 改進(jìn)的分支定價(jià)算法

本文從包含部分路徑的RMP出發(fā)，采用脈沖算法求解ASC-ESPPRC定價(jià)子問(wèn)題，將子問(wèn)題的解為負(fù)的列加入RMP重新求解，如此迭代直到子問(wèn)題的解為非負(fù)則得到了RMP的最優(yōu)解。將得到的解采用弧分支策略得到最優(yōu)整數(shù)解。圖1是改進(jìn)分支定價(jià)算法（Improved branch-andprice algorithm，IBP）的流程圖。

圖1 IBP算法流程圖

3.1 脈沖算法

脈沖算法是通過(guò)對(duì)已得到的部分路徑遞歸搜索，在擴(kuò)展過(guò)程中部分路徑所包含的節(jié)點(diǎn)會(huì)被不斷擴(kuò)展到最終作業(yè)點(diǎn)或剪枝不滿(mǎn)約束條件的路徑。良好的定界策略能夠大大縮小搜索空間，提高算法的求解效率，脈沖算法過(guò)程中包含三個(gè)不同的剪枝策略。圖2為脈沖算法流程圖。

圖2 脈沖算法流程圖

3.1.1 符號(hào)說(shuō)明

G：訪問(wèn)作業(yè)節(jié)點(diǎn)（路徑）有向圖；

ns：脈沖算法的起始節(jié)點(diǎn)；

ne：脈沖算法的終止節(jié)點(diǎn)；

S：當(dāng)前節(jié)點(diǎn)的路徑信息；

S*：獲得的最優(yōu)路徑；

r(S)：當(dāng)前路徑節(jié)約成本的累加和；

q(S)：當(dāng)前路徑載荷量的累加和；

t(S)：行駛到當(dāng)前路徑花費(fèi)的時(shí)間；

Δ：定界算法中時(shí)間變化步長(zhǎng)；

[tu，td]：定界過(guò)程的時(shí)間范圍；

ASC每行駛到一個(gè)節(jié)點(diǎn)，就會(huì)運(yùn)行脈沖算法進(jìn)行遞歸搜索。執(zhí)行上述三個(gè)不同的剪枝策略嘗試縮小搜索空間，最后到達(dá)節(jié)點(diǎn)ne的脈沖包含了從ns到ne的所有信息。

3.1.2 脈沖算法流程

針對(duì)ASC-ESPPRC定價(jià)子問(wèn)題，求解過(guò)程可以分為兩個(gè)階段。首先通過(guò)定界（Bound）算法計(jì)算出到達(dá)每個(gè)節(jié)點(diǎn)的最低成本（cost），該過(guò)程稱(chēng)為定界。然后運(yùn)行脈沖（Pulse）算法進(jìn)行路徑搜索。此時(shí)通過(guò)定界算法得到的每個(gè)節(jié)點(diǎn)的最低成本用于剪枝，能夠去掉不好的路徑。

求解過(guò)程如圖3所示。a)～d)將當(dāng)前獲得的部分路徑S、當(dāng)前路徑節(jié)約成本r(S)、當(dāng)前載荷量累加和q(S)和當(dāng)前花費(fèi)的時(shí)間t(S)初始化。e)運(yùn)行定界算法確定ASC行駛到各個(gè)節(jié)點(diǎn)時(shí)的最低成本，如3.2.2所述。f)執(zhí)行脈沖過(guò)程。通過(guò)不同的剪枝策略得到最優(yōu)路徑S*，如3.2所述。最后輸出最優(yōu)路徑。

圖3 脈沖算法

3.2 脈沖過(guò)程剪枝策略

脈沖過(guò)程主要包括三個(gè)剪枝策略：

If_Feasible：用于檢查ASC行駛到當(dāng)前節(jié)點(diǎn)時(shí)是否滿(mǎn)足約束條件；

Check_Bound：用于檢查到達(dá)當(dāng)前節(jié)點(diǎn)時(shí)的cost是否小于等于通過(guò)Bound算法求得的最低cost，若不是則該條路徑被剪枝；

Rollback：用于回溯操作，即檢查是否有滿(mǎn)足三角不等式的節(jié)點(diǎn)，使得比原來(lái)的路徑成本更低，若有則原來(lái)的路徑被剪枝。

脈沖剪枝策略的執(zhí)行過(guò)程如圖4所示，其中Ψ+(ni)表示從當(dāng)前節(jié)點(diǎn)出發(fā)后的入度節(jié)點(diǎn)。

圖4 脈沖剪枝策略

3.2.1 檢查約束剪枝策略

當(dāng)ASC到達(dá)當(dāng)前節(jié)點(diǎn)時(shí)，首先檢查是否滿(mǎn)足模型的約束條件，即時(shí)間窗約束，載荷量約束以及完成任務(wù)的周期約束。運(yùn)行If_Feasible剪枝策略，當(dāng)行駛到節(jié)點(diǎn)ni時(shí)檢查是否形成循環(huán)、是否超出載荷量q以及是否違反時(shí)間窗約束。若其中任何一個(gè)不滿(mǎn)足，這條路徑為不可行路徑，將被剪枝。

為檢查當(dāng)前路徑是否有循環(huán)，本文設(shè)置一個(gè)標(biāo)記函數(shù)標(biāo)記在當(dāng)前路徑中已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)，若訪問(wèn)過(guò)則該部分路徑被剪枝。對(duì)于載荷量約束，若ASC在行駛到下一節(jié)點(diǎn)時(shí)載荷量超出，則該部分路徑被剪枝。對(duì)于時(shí)間窗約束，若ASC在bi后到達(dá)則該部分路徑被剪枝，若在ai前到達(dá)則需要等待到ai才可以作開(kāi)始作業(yè)。

3.2.2 定界剪枝策略

定界算法用于求解ASC行駛到不同節(jié)點(diǎn)時(shí)，在不同最晚到達(dá)時(shí)間下的最低成本，最終得到ASC在不同時(shí)間到達(dá)該點(diǎn)的成本矩陣。定義為邊界值的上界，隨著路徑的變化更新，運(yùn)行定界算法后得到每個(gè)節(jié)點(diǎn)ni∈N在當(dāng)前的時(shí)間t(S)下的最小節(jié)約成本，記為。定界算法的執(zhí)行過(guò)程如圖5所示。最低成本矩陣記為，其中為達(dá)到最低成本時(shí)的時(shí)間。

圖5 定界策略

tu是訪問(wèn)車(chē)場(chǎng)的時(shí)間窗上界，Δ是非負(fù)的時(shí)間步長(zhǎng)，訪問(wèn)節(jié)點(diǎn)的最晚到達(dá)時(shí)間從tM開(kāi)始每次減少一個(gè)時(shí)間步長(zhǎng)，直到減小到td。即當(dāng)訪問(wèn)節(jié)點(diǎn)ni時(shí)，首先設(shè)置到達(dá)該節(jié)點(diǎn)的最晚到達(dá)時(shí)間為t(S)=tM-Δ，求得的最優(yōu)解為當(dāng)前最小節(jié)約成本的下界。若此時(shí)t(S)≠td，則繼續(xù)設(shè)置該節(jié)點(diǎn)的最晚到達(dá)時(shí)間為t(S)=tu-Δ，計(jì)算最優(yōu)解。此后的過(guò)程重復(fù)上述操作，直到當(dāng)前訪問(wèn)節(jié)點(diǎn)的t(S)=td。此時(shí)得到不同節(jié)點(diǎn)在不同最晚到達(dá)時(shí)間下的最小成本矩陣。

3.2.3 回溯剪枝策略

由于脈沖算法是通過(guò)遞歸的方式尋找路徑，因此采用深度優(yōu)先搜索尋找路徑節(jié)點(diǎn)。深度優(yōu)先搜索的缺點(diǎn)是選擇了分支定界樹(shù)上的分支后必須遍歷完，但不一定得到最優(yōu)解，此時(shí)需要返回重新搜索。本文采用回溯策略，在獲得部分路徑的最后一個(gè)節(jié)點(diǎn)就執(zhí)行回溯操作，尋找是否有更優(yōu)的路徑，若有則替換當(dāng)前最優(yōu)部分路徑。如圖6所示，假設(shè)有部分路徑Ssi從節(jié)點(diǎn)ns出發(fā)到達(dá)ni，然后訪問(wèn)節(jié)點(diǎn)nl，最終到達(dá)nk?；厮菁糁Σ呗詴?huì)在重新判斷到達(dá)終點(diǎn)前選擇的節(jié)點(diǎn)，S'SK為回溯操作后可選擇的另一條路徑，由Ssi直接擴(kuò)展到節(jié)點(diǎn)ni，不經(jīng)過(guò)nl直接到達(dá)nk。此時(shí)需要進(jìn)一步判斷路徑S'SK是否滿(mǎn)足以下約束：1)S'SK?SSK；2)t(S'SK)≤t(SSK)；3)r(S'SK)≤r(SSK)；4)q(S'SK)≤t(SSK)。

圖6 回溯剪枝策略示意圖

由上述分析易知，約束1)，4)顯然滿(mǎn)足，因此只需要判斷約束2)，3)是否滿(mǎn)足。若滿(mǎn)足則用S'SK替換SSK，即原路徑被剪枝。

3.3 列生成算法與整數(shù)解

由列生成求解得到的RMP的最優(yōu)解可以是整數(shù)或浮點(diǎn)數(shù)，若為整數(shù)則與當(dāng)前上界相比較，小于當(dāng)前上界則更新上界值并剪枝。對(duì)于浮點(diǎn)數(shù)解，若小于當(dāng)前上界則在求得的變量中選擇最接近0.5的變量進(jìn)行分支，得到兩條路徑S1和S2，S1中包括弧段(i，j)，S2不經(jīng)過(guò)i點(diǎn)到達(dá)j，刪除當(dāng)前節(jié)點(diǎn)同時(shí)將分支節(jié)點(diǎn)加入分支定界搜索樹(shù)。若大于當(dāng)前上界則不需要分支。

4 實(shí)驗(yàn)結(jié)果分析

本實(shí)驗(yàn)使用Eclipse JDK 4.3.0版本，在Java多線(xiàn)程中調(diào)用Cplex求解模型，實(shí)現(xiàn)了本文IBP算法。進(jìn)行實(shí)驗(yàn)的計(jì)算機(jī)參數(shù)為Inter(R) Core(TM)i5-8250U CPU @ 1.60GHz 1.80GHz。

實(shí)驗(yàn)首先在Solomon標(biāo)準(zhǔn)測(cè)試集中選取5組小規(guī)模算例，分別用分支定界算法和IBP算法求解，并用本文IBP算法求解得到了部分較大規(guī)模Gehring&Homberger算例的最優(yōu)解，同時(shí)對(duì)影響算法效率的相關(guān)因素進(jìn)行靈敏度分析。

4.1 對(duì)比實(shí)驗(yàn)及小規(guī)模算例測(cè)試結(jié)果

在Eclipse中編寫(xiě)分支定界算法，調(diào)用Cplex求解小規(guī)模算例，并與改進(jìn)的分支定價(jià)算法求解結(jié)果對(duì)比。從Solomon標(biāo)準(zhǔn)測(cè)試集中選取5組小規(guī)模算例進(jìn)行測(cè)試，測(cè)試結(jié)果如表1所示。圖7為相同規(guī)模下傳統(tǒng)分支定界算法與IBP算法求解時(shí)間的對(duì)比。

表1 分支定界算法IBP算法小規(guī)模算例結(jié)果對(duì)比

圖7 分支定界算法與IBP算法效率對(duì)比

通過(guò)表1可以看出兩個(gè)算法求解的ASC行駛總距離基本吻合，平均誤差小于1，且IBP算法求解時(shí)間比分支定界算法平均值短11.37s。通過(guò)圖7更可直觀看出，隨著問(wèn)題復(fù)雜程度的上升，IBP算法效率高于分支定界算法。

選取不同類(lèi)型的算例測(cè)試算法的有效性。C類(lèi)算例表示作業(yè)點(diǎn)集中在部分區(qū)域，R類(lèi)算例表示作業(yè)點(diǎn)隨機(jī)分布，RC類(lèi)算例表示作業(yè)點(diǎn)既有集中分布、也有隨機(jī)分布的。表2為改進(jìn)的分支定價(jià)算法在不同測(cè)試集下的計(jì)算結(jié)果。表3列出了三類(lèi)算例的部分ASC車(chē)輛行駛路徑。

表2 改進(jìn)的分支定價(jià)算法求解結(jié)果

表3 IBP算法求解部分算例路徑

由表2、表3可得，隨著問(wèn)題規(guī)模的增加，迭代次數(shù)不斷增加，即子問(wèn)題求解次數(shù)增加。求解時(shí)間R類(lèi)＜RC類(lèi)＜C類(lèi)，即作業(yè)點(diǎn)越分散計(jì)算時(shí)間越短。作業(yè)點(diǎn)數(shù)量相同條件下，隨機(jī)分布的R類(lèi)算例，路徑數(shù)比C類(lèi)算例和RC類(lèi)算例多，每條路徑中訪問(wèn)的作業(yè)點(diǎn)數(shù)量少，需要的ASC數(shù)量多，C類(lèi)算例中每條路徑的作業(yè)點(diǎn)數(shù)目分配較均勻，所需的ASC數(shù)量較少。即作業(yè)點(diǎn)越分散求解時(shí)間越短，但所需ASC數(shù)量越多。

4.2 較大規(guī)模算例求解結(jié)果

在Gehring&Homberger數(shù)據(jù)集中選取了7組較大規(guī)模的C類(lèi)算例求解，作業(yè)點(diǎn)規(guī)模為200、400、600，設(shè)置可接受的最大求解時(shí)間為2小時(shí)，定界策略中的時(shí)間步長(zhǎng)。實(shí)驗(yàn)結(jié)果如表4所示。

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

由表4可得，IBP算法能夠用于求解一些較大規(guī)模的ASC車(chē)輛路徑問(wèn)題，并且能在不同規(guī)模算例和可接受的時(shí)間范圍內(nèi)求得最優(yōu)解。問(wèn)題規(guī)模與求解時(shí)間成正比，但得到的可行路徑數(shù)目與求解時(shí)間不一定成正比，這與算例本身的數(shù)據(jù)復(fù)雜程度有關(guān)。可行路徑少的算例中每條路徑的作業(yè)點(diǎn)較多，ASC的利用率較低；可行路徑多的算例中ASC利用率較高。

4.3 靈敏度分析

在IBP算法中，子問(wèn)題求解過(guò)程中定界策略對(duì)求解效率起關(guān)鍵作用，另外ASC的載荷量也會(huì)直接影響求解結(jié)果。因此分析定界策略中不同時(shí)間步長(zhǎng)與不同ASC載荷量對(duì)算法求解效率的影響。為保證實(shí)驗(yàn)的一般性，從Solomon標(biāo)準(zhǔn)測(cè)試集中選取6組作業(yè)點(diǎn)規(guī)模相同的算例進(jìn)行實(shí)驗(yàn)。分別分析定界策略中不同的時(shí)間步長(zhǎng)和ASC不同載荷量對(duì)算法求解效率的影響。

1）定界策略的時(shí)間步長(zhǎng)

為研究不同時(shí)間步長(zhǎng)下的定界策略對(duì)算法的效率影響，在其他參數(shù)不變的條件下，每組算例依次設(shè)置步長(zhǎng)為4、8、12、16、20進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果如表5所示。

表5 不同時(shí)間步長(zhǎng)靈敏度分析

由表5縱向來(lái)看，隨著算例規(guī)模的增加和問(wèn)題本身復(fù)雜程度的上升，算法的求解時(shí)間不斷增加，但都能夠在0.5小時(shí)內(nèi)得到最優(yōu)解；橫向來(lái)看，上述6個(gè)算例從Δ=4增加到Δ=20，算法求解時(shí)間逐漸減少，求解效率分別提升了36%、48%、40%、16.4%、69%和42.7%。驗(yàn)證了時(shí)間步長(zhǎng)對(duì)算法效率的影響，時(shí)間步長(zhǎng)越大得到的成本矩陣規(guī)模越小，求解時(shí)間越短。

2）ASC不同的載荷量

為研究ASC在不同載荷量下對(duì)實(shí)驗(yàn)結(jié)果的影響，選取6組算例進(jìn)行測(cè)試，在其他參數(shù)不變的情況下，設(shè)置可接受的求解時(shí)間為2小時(shí)以?xún)?nèi)，分別設(shè)置ASC載荷量為200、400、600、800和1000進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果如表6所示。

表6 ASC不同載荷量靈敏度分析

由表6 可得，對(duì)于數(shù)據(jù)簡(jiǎn)單的小規(guī)模算例，如c101.100和c102.100，不同載荷量下得到的最優(yōu)路徑相同，隨著ASC載荷量的增加，求解時(shí)間呈減少趨勢(shì)，最大差值為1.487s和4.757s，ASC不同載荷量對(duì)求解時(shí)間的影響小于5s。對(duì)于數(shù)據(jù)較復(fù)雜的算例，如c201.100和c221.200，q＜600時(shí)無(wú)法在可接受時(shí)間范圍內(nèi)得到最優(yōu)解，q≥600時(shí)能得到最優(yōu)解，在q=600時(shí)求解時(shí)間最短，此后得到的路徑數(shù)趨于穩(wěn)定，即隨著ASC載荷量的增大，最優(yōu)解趨于穩(wěn)定。對(duì)于較大規(guī)模算例，如c121.200和c221.200，c121.200在不同載荷量下得到最優(yōu)解的時(shí)間差值小于6s，c122.200由q=400增加到q=600時(shí)得到最優(yōu)解，隨著q的增加求解時(shí)間基本穩(wěn)定。由上述分析可得，ASC載荷量越大算法的求解效率越高，對(duì)于數(shù)據(jù)簡(jiǎn)單的算例對(duì)求解時(shí)間的影響小于7s，對(duì)于數(shù)據(jù)復(fù)雜的算例，ASC達(dá)到一定的載荷量后得到的最優(yōu)路徑趨于穩(wěn)定。驗(yàn)證了ASC不同載荷量對(duì)算法效率的影響，且不同的算例能夠求得最優(yōu)的ASC載荷量。

5 結(jié)語(yǔ)

本文建立了自動(dòng)化集裝箱碼頭ASC-PDPTW混合整數(shù)規(guī)劃模型，提出了一種求解ASC車(chē)輛路徑問(wèn)題改進(jìn)的分支定價(jià)算法。用脈沖算法求解定價(jià)子問(wèn)題并嵌入分支定價(jià)算法框架中，定界過(guò)程中包含三種剪枝策略，用于有效縮小解搜索空間，提高求解效率。設(shè)計(jì)了小規(guī)模算例的對(duì)比實(shí)驗(yàn)；求解并分析了較大規(guī)模算例的實(shí)驗(yàn)結(jié)果，并進(jìn)一步對(duì)不同的時(shí)間步長(zhǎng)和ASC載荷量進(jìn)行靈敏度分析。作業(yè)點(diǎn)在20至100內(nèi)小規(guī)模算例的求解時(shí)間比傳統(tǒng)分支定界算法平均提高11.37s；作業(yè)點(diǎn)在200至600的較大規(guī)模算例能夠在可接受時(shí)間范圍內(nèi)求得最優(yōu)解，即該算法不僅能夠更加快速的求解小規(guī)模算例，也能夠在可接受時(shí)間范圍內(nèi)求解一些較大規(guī)模算例。在靈敏度分析中，隨著定界策略中時(shí)間步長(zhǎng)增加到20，求解效率平均提高42.01%；隨著ASC載荷量的增加，對(duì)于數(shù)據(jù)簡(jiǎn)單的算例得到的最優(yōu)解基本穩(wěn)定，對(duì)于數(shù)據(jù)復(fù)雜的算例，載荷量越大求解效率越高，在達(dá)到最優(yōu)載荷量后最優(yōu)路徑不再變化，求解時(shí)間會(huì)增加。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所建立模型的可行性，提出的IBP算法能夠有效提高求解ASC最優(yōu)行駛路徑的效率。