考慮空重箱轉(zhuǎn)換的港口集裝箱甩掛運(yùn)輸問題研究

徐世達(dá), 何雯晴, 靳志宏

(大連海事大學(xué) 交通運(yùn)輸工程學(xué)院,遼寧 大連 116026)

0 引言

集裝箱作為一種高效流通的標(biāo)準(zhǔn)化運(yùn)運(yùn)載單元，被廣泛應(yīng)用在現(xiàn)代物流運(yùn)輸系統(tǒng)中。近年來，國內(nèi)港口集裝箱吞吐量呈現(xiàn)出逐年上升的良好態(tài)勢[1]。港口內(nèi)陸集裝箱運(yùn)輸(Inland Container Transport, ICT)主要研究港口、內(nèi)陸堆場和客戶間的集裝箱卡車運(yùn)輸調(diào)度問題。內(nèi)陸集疏運(yùn)環(huán)節(jié)的集卡運(yùn)輸在為客戶提供門到門服務(wù)的同時面臨高昂的單位運(yùn)輸成本，因此為了在激烈競爭的市場環(huán)境中處于有利地位，企業(yè)管理者需要在提升貨運(yùn)周轉(zhuǎn)率的同時有效降低運(yùn)輸成本[2]。

隨著運(yùn)輸裝備的發(fā)展，車輛動力部分和載重部分可進(jìn)行分離的甩掛運(yùn)輸車輛被廣泛應(yīng)用在港口集裝箱運(yùn)輸實(shí)踐中。Xue等[3]將此類問題定義為局部集裝箱托運(yùn)問題(Local Container Drayage Problem, LCDP)，并通過對比分析表明，采用甩掛運(yùn)輸模式能夠有效降低任務(wù)等待時間和服務(wù)成本。

集裝箱的重掛任務(wù)屬于起止點(diǎn)(Origin-Destination, OD)確定性的運(yùn)輸需求，其運(yùn)輸路線固定且不可拆分的特點(diǎn)決定了相關(guān)研究主要集中在降低重掛任務(wù)之間牽引車空駛的銜接成本部分。馬華偉等[4,5]分別采用了模擬退火算法和禁忌搜索算法對多車單掛情形的甩掛運(yùn)輸問題進(jìn)行了研究。Song等[6]將空重箱任務(wù)相互獨(dú)立的甩掛運(yùn)輸問題轉(zhuǎn)化為一類基于DAOV圖的帶有時間窗約束的非對稱車輛路徑問題，并設(shè)計分支定價算法求解。楊珍花等[7]將上一決策期的重掛車輛轉(zhuǎn)化為本決策期的空掛車輛資源，提出空掛OD不確定的空重掛車聯(lián)合調(diào)度問題并采用兩階段算法求解。

受到港口堆場堆存能力以及空箱保有量等條件的限制，往往要求單個決策周期內(nèi)所有運(yùn)出的重集裝箱必須以空集裝箱的形式返還給堆場，這種空重箱狀態(tài)轉(zhuǎn)換的特點(diǎn)使得集裝箱在單個決策期內(nèi)同時具有空箱和重箱兩種屬性與運(yùn)輸任務(wù)。張建同等[8]基于上述研究提出了基于交換箱(Swap Body)的甩箱運(yùn)輸模式，決策變量中除訪問順序外還設(shè)置了集卡到達(dá)時間和集卡離開時間，設(shè)計了考慮訪問序列限制的蟻群算法，但所提出的路徑切割方法只適用于空、重箱任務(wù)同屬一輛集卡服務(wù)的問題。Xue等[9]采用牽引車和掛車可分離的甩掛運(yùn)輸模式對空重箱轉(zhuǎn)化問題進(jìn)行了研究，建立了混合整數(shù)規(guī)劃模型并采用改進(jìn)的最大最小蟻群算法進(jìn)行求解。

谷首更等[10]建立了整數(shù)規(guī)劃模型進(jìn)行求解，但對于各個運(yùn)輸任務(wù)都設(shè)定了時間窗并作為參數(shù)輸入，當(dāng)問題規(guī)模擴(kuò)大時，任務(wù)間沖突的時間窗可能導(dǎo)致無法搜索可行解。

通過上述分析可知，現(xiàn)有的研究在處理港口集裝箱甩掛運(yùn)輸?shù)目罩叵滢D(zhuǎn)化問題時，大多以牽引車訪問順序、到達(dá)時間和離開時間為決策變量建立混合整數(shù)規(guī)劃模型進(jìn)行求解，主要通過優(yōu)化節(jié)點(diǎn)訪問時間的方法來解決空重箱轉(zhuǎn)化所產(chǎn)生的運(yùn)輸任務(wù)訪問順序約束。然而，當(dāng)問題規(guī)模逐漸擴(kuò)大時，混合整數(shù)規(guī)劃問題的求解時間呈現(xiàn)爆炸性的指數(shù)增長。因此，本文針對此類問題提出了基于前置任務(wù)訪問約束的方法，以牽引車任務(wù)序列訪問順序和安排任務(wù)數(shù)量為決策變量建立了整數(shù)規(guī)劃模型，根據(jù)所建立數(shù)學(xué)模型的特點(diǎn)設(shè)計了基于集群選擇的改進(jìn)蟻群算法進(jìn)行問題求解，并通過數(shù)值試驗(yàn)證明所提出模型和算法的有效性。

1 問題描述與相關(guān)定義

考慮空重箱轉(zhuǎn)換的港口集裝箱甩掛運(yùn)輸問題與傳統(tǒng)的集卡運(yùn)輸模式以及其他甩掛運(yùn)輸模式相比，最主要的特點(diǎn)在于充分利用甩掛運(yùn)輸減少車輛等待時間的特點(diǎn)，以達(dá)到單周期內(nèi)空重集裝箱的狀態(tài)轉(zhuǎn)換以及回收的目的。為進(jìn)一步闡述本文研究問題的特點(diǎn)，在問題描述之前首先給出如下定義：

(1)定義1:運(yùn)輸需求

客戶節(jié)點(diǎn)所提出的集裝箱運(yùn)輸需求，而不是傳統(tǒng)甩掛運(yùn)輸中提出重掛運(yùn)輸任務(wù)。運(yùn)輸需求可以細(xì)分為送貨人到港口重箱堆場的進(jìn)港客戶需求和港口重箱堆場的出港需求。每個客戶節(jié)點(diǎn)可以具有多項不同類型的運(yùn)輸需求。

(2)定義2:集裝箱任務(wù)

客戶的每項運(yùn)輸需求都可以拆分為兩項相互關(guān)聯(lián)的集裝箱任務(wù)。其中進(jìn)港客戶需求可拆分為送空箱任務(wù)(DE)和取重箱任務(wù)(PF)，出港客戶需求可拆分為送重箱任務(wù)(DF)和取空箱任務(wù)(PE)，上述各類集裝箱任務(wù)對應(yīng)的牽引車運(yùn)輸操作如表1所示。

表1 集裝箱任務(wù)的牽引車運(yùn)輸操作

通過表1中牽引車的運(yùn)輸操作可知，送箱類任務(wù)(DE, DF)的終點(diǎn)均為客戶節(jié)點(diǎn)，由于裝卸條件的限制通常采用甩箱又甩掛的操作模式；而取箱類任務(wù)(PF, PE)的終點(diǎn)為集裝箱堆場，則可通過集裝箱作業(yè)設(shè)備實(shí)現(xiàn)甩箱不甩掛操作模式。

(3)定義3：銜接任務(wù)

表示兩項集裝箱任務(wù)之間牽引車所需要完成的銜接任務(wù)。不同任務(wù)之間牽引車的銜接運(yùn)輸操作如表2所示：

(4)定義4：前置任務(wù)

結(jié)合甩掛運(yùn)輸?shù)牟僮魈攸c(diǎn)，當(dāng)送箱任務(wù)完成后牽引車可獨(dú)立離開并進(jìn)行其他運(yùn)輸任務(wù)，當(dāng)貨物裝卸完成后由其他牽引車完成取箱任務(wù)。由于裝卸任務(wù)時間的限制，取箱任務(wù)的最早開始時間應(yīng)為送箱任務(wù)交付時間與該集裝箱拆箱任務(wù)時間的總和。綜上，我們定義每項任務(wù)需求所拆分的送箱任務(wù)為取箱任務(wù)的前置任務(wù)。

結(jié)合上述定義，港口集裝箱甩掛運(yùn)輸問題可以描述如下：在某一港口的區(qū)域范圍內(nèi)具有掛車中心、重箱堆場和空箱堆場三項基礎(chǔ)設(shè)施。在該港口的內(nèi)陸腹地中具有一定數(shù)量的客戶節(jié)點(diǎn)，針對客戶節(jié)點(diǎn)的進(jìn)港需求和出港需求，牽引車需要在滿足前置任務(wù)約束的情況下完成每項運(yùn)輸需求的空重箱運(yùn)輸任務(wù)，且兩項運(yùn)輸任務(wù)可以由不同的牽引車進(jìn)行服務(wù)。由于客戶節(jié)點(diǎn)往往不具有大型集裝箱吊裝作業(yè)設(shè)備，因此在客戶節(jié)點(diǎn)采用同時甩下半掛車和集裝箱的“甩箱又甩掛模式”，在港口的空重箱堆場采用只甩下集裝箱的“甩箱不甩掛模式”。如表2所示，牽引車在完成兩項集裝箱任務(wù)的銜接任務(wù)過程中，可能由于當(dāng)前牽引車狀態(tài)限制導(dǎo)致需要前往掛車中心完成“單獨(dú)牽引車”或“牽引車+半掛車”的狀態(tài)轉(zhuǎn)換。

表2 銜接任務(wù)的牽引車運(yùn)輸操作

本問題主要解決的是所有集裝箱任務(wù)在滿足前置任務(wù)約束的前提下，在當(dāng)前決策期內(nèi)均被完成, 并最小化牽引車調(diào)用數(shù)量和銜接任務(wù)行駛距離。

3 帶有前置任務(wù)訪問約束的整數(shù)規(guī)劃模型

3.1 模型假設(shè)

假設(shè)1牽引車只能同時拖掛一輛半掛車，車輛狀態(tài)又可細(xì)分為：“牽引車+半掛車”、“牽引車+半掛車+空箱”和“牽引車+半掛車+重箱”三類。

假設(shè)2假設(shè)牽引車在不同車輛狀態(tài)時速度相同，且保持恒定速度運(yùn)輸。

假設(shè)3不考慮集裝箱、掛車、牽引車之間的設(shè)備尺寸匹配問題。

假設(shè)4掛車與空集裝箱調(diào)用數(shù)量無限制。

3.2 參數(shù)設(shè)置

C:運(yùn)輸節(jié)點(diǎn)集合，C={0,1,2,…,P}，其中0表示掛車中心，1表示重箱堆場，2表示空箱堆場，3,4,…,M表示客戶節(jié)點(diǎn)。

K:牽引車數(shù)量。

k:牽引車編號,k∈{1,2,…,K}。

R:集裝箱任務(wù)集合，R=DE∪PF∪DF∪PE，其中DE表示送空箱任務(wù)集合，PF表示取重箱任務(wù)集合，DF表示送重箱任務(wù)集合，PE表示取空箱任務(wù)集合。

g(i)表示任務(wù)i的前置任務(wù)。 (i∈PE,g(i)∈DE;i∈PE,g(i)∈DF)。

CF:牽引車固定調(diào)用成本。

Cd:牽引車的單位時間運(yùn)輸成本。

τi:集裝箱任務(wù)的執(zhí)行時間，以送空箱任務(wù)(DE)為例，執(zhí)行時間=提取空箱時間+運(yùn)往客時間+空箱和掛車甩掛時間(i∈R)。

tij:集裝箱任務(wù)i和集裝箱任務(wù)j之間銜接任務(wù)所需服務(wù)時間。以送重箱任務(wù)(DF)和送空箱任務(wù)(DE)之間的銜接任務(wù)為例，銜接時間=從DF的客戶點(diǎn)前往掛車中心時間+提取掛車時間+從掛車中心前往空箱堆場時間(i,j∈R)。

T:每輛牽引車的最長工作時間。

3.3 決策變量與衍生變量

(1)決策變量:

(1)

Nk:牽引車k所安排的運(yùn)輸任務(wù)數(shù)量。

Nk∈{0,1,…,|R|}

(2)

(2)衍生變量：

(3)

Ti:集裝箱任務(wù)i的完成時間。

(4)

3.4 帶有前置任務(wù)訪問約束的整數(shù)規(guī)劃模型

(1)目標(biāo)函數(shù):

(5)

模型的目標(biāo)函數(shù)由兩部分構(gòu)成，第一部分表示牽引車調(diào)用成本，主要受牽引車調(diào)用數(shù)量影響；第二部分表示牽引車運(yùn)輸成本。由于集裝箱任務(wù)的OD具有確定性，當(dāng)所有任務(wù)都被服務(wù)時這些重掛運(yùn)輸任務(wù)的成本為固定值，因此第二部分的牽引車運(yùn)輸成本僅計算集裝箱任務(wù)之間銜接任務(wù)的運(yùn)輸成本。模型的優(yōu)化目標(biāo)在于降低牽引車調(diào)用數(shù)量和銜接任務(wù)的運(yùn)輸距離進(jìn)而使總運(yùn)輸成本最低。

(2)約束條件

(6)

(7)

(8)

(9)

(10)

Tg(i)≤Ti-τi,?i∈PF,g(i)∈DE

(11)

Tg(j)≤Tj-τj,?j∈PF,g(j)∈DE

(12)

(13)

Nk∈{0,1,2,…,|R|},?k∈K

(14)

其中式(6)表示所有集裝箱任務(wù)均被安排到不同的牽引車中；式(7)表示每個集裝箱任務(wù)只安排給一輛牽引車在一次運(yùn)輸任務(wù)中完成；式(8)表示客戶節(jié)點(diǎn)處任務(wù)流量守恒約束；式(9)表示每輛牽引車必須從掛車中心出發(fā)并最終返回，且調(diào)用牽引車總數(shù)量不能超過掛車中心的最大車輛數(shù)；式(10)表示牽引車工作時間限制，完成所有集裝箱任務(wù)和銜接任務(wù)時間的總和不能超過牽引車最長工作時間；式(11)和式(12)表示前置任務(wù)約束，即第二階段任務(wù)的開始時間必須大于其前置任務(wù)的完成時間；式(13)和式(14)表示變量取值約束。

4 基于集群選擇的改進(jìn)蟻群算法

蟻群算法(Ant Colony Optimization, ACO)最早由Dorigo等人提出，該算法的概率選擇操作能夠始終保證算法在可行解空間內(nèi)進(jìn)行迭代尋優(yōu)，因此被廣泛應(yīng)用在車輛路徑問題(Vehicle Routing Problem, VRP)及其拓展問題中[11～14]。

對于本文所研究的考慮空重箱轉(zhuǎn)化的港口集裝箱甩掛運(yùn)輸問題，每個客戶點(diǎn)的運(yùn)輸需求被拆分為空箱任務(wù)和重箱任務(wù)兩部分，需要對每個客戶點(diǎn)在滿足前置約束的前提下進(jìn)行兩次訪問。同時集合甩掛運(yùn)輸?shù)奶攸c(diǎn)，兩次運(yùn)輸服務(wù)可以由不同的牽引車完成。這就需要算法在解的生成過程中能夠準(zhǔn)確的表述出前置任務(wù)的完成情況，而現(xiàn)有蟻群算法無法有效的處理這種多路徑之間相互影響的情況，因此本文提出了基于集群選擇的蟻群算法(ACO with Cluster Select, CSACO)，主要對蟻群算法的編碼方式和概率選擇操作進(jìn)行了改進(jìn)。

4.1 任務(wù)時間矩陣與變維數(shù)矩陣編碼

任務(wù)時間矩陣的初始階段形式如圖1所示，該矩陣是一個N×2維矩陣，第一行表示集裝箱任務(wù)編號，第二行表示對應(yīng)任務(wù)的最早可開始時間。為方便表述，本文將奇數(shù)列任務(wù)設(shè)為偶數(shù)列任務(wù)的前置任務(wù)。在初始階段，奇數(shù)列任務(wù)作為前置任務(wù)可開始時間均為0，偶數(shù)列任務(wù)由于前置任務(wù)沒有完成，可開始時間設(shè)為一個充分大的正數(shù)M。

圖1 任務(wù)時間矩陣初始形式

當(dāng)前置任務(wù)1完成后，任務(wù)時間矩陣更新形式如圖2所示。任務(wù)1被牽引車選擇后可開始時間立刻更新為另一個充分大的正數(shù)MM，防止單個任務(wù)被多輛牽引車選擇。同時，對應(yīng)的二階段任務(wù)可開始時間更新為任務(wù)1的完成時間T1，計算方法見式(4)。

圖2 任務(wù)時間矩陣更新后形式

算法的解的編碼結(jié)構(gòu)如圖3所示，該編碼由一個K×max(Nk)維矩陣構(gòu)成，其中max(Nk)表示所有牽引車安排任務(wù)的最大值。由于矩陣的維數(shù)隨著決策變量的變化而變化，因此稱之為變維數(shù)矩陣編碼。編碼中元素表示集裝箱任務(wù)編號，每一行包含元素個數(shù)為該輛牽引車k所安排的運(yùn)輸任務(wù)數(shù)量Nk。當(dāng)Nk=0時，即編號為k的牽引車未被調(diào)用，該行的所有元素編碼為0。

4.2 基于集群選擇的概率選擇操作

由于每個客戶可能具有多項運(yùn)輸需求，即多項進(jìn)港、出港的集裝箱運(yùn)輸任務(wù)，因此在牽引車在進(jìn)行路徑選擇時除了需要考慮任務(wù)之間銜接時間之外，還受客戶點(diǎn)剩余任務(wù)數(shù)量的影響?？蛻酎c(diǎn)可以視作具有多項集裝箱運(yùn)輸任務(wù)的任務(wù)集群，因此本文設(shè)計了基于集群選擇的概率選擇操作模式。首先，本文設(shè)計了節(jié)點(diǎn)剩余任務(wù)矩陣和車輛狀態(tài)矩陣，如圖3和圖4所示：

節(jié)點(diǎn)剩余任務(wù)矩陣由一個P×4維矩陣構(gòu)成，行表示客戶點(diǎn)編號i，對應(yīng)列的元素表示該客戶節(jié)點(diǎn)不同類型運(yùn)輸任務(wù)的剩余量Taski。設(shè)cj表示任務(wù)j所對應(yīng)的客戶節(jié)點(diǎn)，則Taski=|{j|cj=i}|。在初始階段，PF和PE作為二階段任務(wù)數(shù)量為0。隨著牽引車運(yùn)輸路線的安排，DE和DF類型任務(wù)完成后，會在PF和PE類型列中更新剩余任務(wù)數(shù)量。

圖3 節(jié)點(diǎn)剩余任務(wù)矩陣

車輛狀態(tài)矩陣由一個k維數(shù)組構(gòu)成，表示各輛牽引車完成最后一個集裝箱運(yùn)輸任務(wù)后的車輛狀態(tài)。矩陣內(nèi)元素由0-1元素構(gòu)成。其中0表示“單獨(dú)牽引車”狀態(tài)，元素1表示“牽引車+半掛車”狀態(tài)。

結(jié)合上述的節(jié)點(diǎn)剩余任務(wù)矩陣和車輛狀態(tài)矩陣，牽引車路徑第n次決策的基于集群選擇的概率選擇操作可以描述如下：

Step1對于當(dāng)前牽引車k運(yùn)輸路徑的最后一個集裝箱任務(wù)節(jié)點(diǎn)i,計算該任務(wù)對應(yīng)客戶節(jié)點(diǎn)c(i)到剩余任務(wù)矩陣中有需求的客戶節(jié)點(diǎn)的行駛時間。

Step2根據(jù)任務(wù)時間矩陣，判斷各個有需求客戶節(jié)點(diǎn)所包含集裝箱任務(wù)是否可行。若任務(wù)可行，則將該任務(wù)放在可行集合J(n)中。

任務(wù)可行性根據(jù)任務(wù)可開始時間和添加該任務(wù)后是否超過牽引車最長工作時間進(jìn)行判斷。

由于一個客戶節(jié)點(diǎn)可能存在多項進(jìn)港、出港任務(wù)，因此一個客戶點(diǎn)可能會在可行集合中添加多項任務(wù)。

Step3遍歷結(jié)束后生成可行集合J(n)。若J(n)=?，則對應(yīng)以下兩種情況：1)所有集裝箱任務(wù)均被完成；2)當(dāng)前牽引車剩余可服務(wù)時間不足以完成任何一項運(yùn)輸任務(wù)。此時把掛車中心0加入到路徑中，此輛牽引車路徑搜索結(jié)束。若J(n)≠0，進(jìn)行節(jié)點(diǎn)選擇操作。

Step4計算集裝箱任務(wù)節(jié)點(diǎn)i到可行集合J(n)中所有集裝箱任務(wù)的轉(zhuǎn)移概率，如式(15)所示:

(15)

(16)

(17)

式(15)表示第n次決策時，牽引車k的下一集裝箱任務(wù)為j的轉(zhuǎn)移概率。主要受軌跡強(qiáng)度τ(i,j)、能見度η(i,j)和傾向任務(wù)數(shù)ω(i,j)影響。

軌跡強(qiáng)度τ(i,j)受蟻群信息素濃度影響，更新函數(shù)為τn+1(i,j)=ρτn(i,j)+Δτ(i,j)。

式(16)表示能見度系數(shù)，由任務(wù)所在集群的客戶節(jié)點(diǎn)間距離表示，其中d[g(i),g(j)]表示集裝箱任務(wù)i所在客戶節(jié)點(diǎn)g(i)和集裝箱任務(wù)j所在客戶節(jié)點(diǎn)g(j)之間的運(yùn)輸距離。

式(17)表示傾向任務(wù)數(shù)，即任務(wù)j所在客戶節(jié)點(diǎn)在牽引車當(dāng)前車輛狀態(tài)更傾向選擇服務(wù)的任務(wù)數(shù)量。其中φ(k)=0表示車輛狀態(tài)為“單獨(dú)牽引車”，為了避免返回掛車中心切換車輛狀態(tài)，傾向任務(wù)為PE和PF類型集裝箱任務(wù)。PE(j)和PF(j)分別表示任務(wù)j所在節(jié)點(diǎn)剩余取空箱任務(wù)數(shù)和取重箱任務(wù)數(shù)；φ(k)=1表示車輛狀態(tài)為“牽引車+半掛車，傾向任務(wù)類型為DE和DF。DF(j)和DF(j)分別表示任務(wù)j所在節(jié)點(diǎn)剩余送空箱任務(wù)數(shù)和送重箱任務(wù)數(shù)。

Step6根據(jù)集裝箱任務(wù)的選擇情況對任務(wù)時間矩陣、節(jié)點(diǎn)剩余任務(wù)矩陣、車輛狀態(tài)矩陣等相關(guān)任務(wù)信息進(jìn)行更新。

5 仿真實(shí)驗(yàn)與結(jié)果分析

為了進(jìn)一步證明本文基于前置任務(wù)訪問約束所建立的整數(shù)規(guī)劃模型的有效性，在此與文獻(xiàn)10[10]中任務(wù)時間作為參數(shù)的整數(shù)規(guī)劃模型和文獻(xiàn)9[9]中任務(wù)時間作為決策變量的混合整數(shù)規(guī)劃模型在最優(yōu)解、求解時間等方面進(jìn)行對比分析。同時，將本文所提出的基于集群選擇的蟻群算法與其他優(yōu)化算法進(jìn)行求解效率和穩(wěn)定性方面的對比分析。

5.1 算例1:整數(shù)規(guī)劃模型與混合整數(shù)規(guī)劃模型對比分析

本部分的算例采用CPLEX商用求解軟件(version 12.9)在英特爾酷睿i5處理器(2.5GHz)、4.0GB內(nèi)存、64位Windows 10操作系統(tǒng)的個人計算機(jī)上運(yùn)行，對三個數(shù)學(xué)模型在不同客戶點(diǎn)數(shù)量、不同算例規(guī)模的算例中采用相同的運(yùn)算環(huán)境進(jìn)行求解分析，對比結(jié)果如表3所示。表中任務(wù)時間作為參數(shù)的數(shù)學(xué)模型是以牽引車各階段任務(wù)的訪問情況作為決策變量，任務(wù)時間作為決策變量的數(shù)學(xué)模型則是采用任務(wù)之間銜接情況和任務(wù)開始時間作為決策變量，建立一個混合整數(shù)規(guī)劃模型求解。

在小規(guī)模算例中，三個數(shù)學(xué)模型均能夠在可接受的時間內(nèi)求得問題的最優(yōu)解。隨著問題規(guī)模的擴(kuò)大，由于不同客戶需求的時間窗沖突的可能性增加，只能夠通過牽引車?yán)@行或增加牽引車數(shù)量的方式滿足所有客戶需求。在精確解求解時間方面，在本文提出的基于前置訪問約束整數(shù)規(guī)劃模型中，雖然前置訪問約束使得模型中的約束條件數(shù)量大于上述模型，但由于除任務(wù)數(shù)量變量Nk之外其他決策變量均為0-1變量，沒有明顯的增加模型的求解時間。通過對求解時間的對比分析，本文提出的模型在不同算例中平均節(jié)約28%的運(yùn)算時間。

因此，本文所提出的基于前置任務(wù)約束的整數(shù)規(guī)劃模型能夠?qū)Υ祟悊栴}進(jìn)行準(zhǔn)確的表達(dá)，同時在精確解的求解時間方面優(yōu)于現(xiàn)有的混合整數(shù)規(guī)劃模型。

表3 整數(shù)規(guī)劃模型與混合整數(shù)規(guī)劃模型求解對比分析

5.2 算例2:算法性能分析

為了進(jìn)一步分析本文所提出的基于集群選擇的改進(jìn)蟻群算法(CSACO)的求解效率和有效性，在相同規(guī)模的數(shù)值算例中，分別與CPLEX和遺傳算法(GA)的求解結(jié)果進(jìn)行對比分析，如表4所示。由于CPLEX在求解大規(guī)模算例時難以在可接受時間范圍內(nèi)獲得問題的最優(yōu)解，因此對于30規(guī)模以上的數(shù)值算例，表中CPLEX的最優(yōu)解為5小時內(nèi)算法搜索的最優(yōu)解下界。

通過對表4中的數(shù)據(jù)對比分析可知，在小規(guī)模算例中遺傳算法與本文所提出的CSACO算法均能夠搜索到問題的最優(yōu)解，并且算法運(yùn)行時間明顯低于商用求解器CPLEX的計算耗時。隨著問題規(guī)模的擴(kuò)大，GA算法雖然在運(yùn)行時間方面優(yōu)于CSACO算法，但對最優(yōu)解的搜索能力較弱，同時算法穩(wěn)定性較差。這是由于CSACO算法利用了蟻群算法的特點(diǎn)，通過概率選擇操作生成的解的方式能夠保證算法始終在可行解空間內(nèi)進(jìn)行迭代尋優(yōu)。同時，本文通過添加任務(wù)時間矩陣、剩余任務(wù)矩陣以及轉(zhuǎn)移概率中的牽引車傾向任務(wù)數(shù)w(k,j)的方式，避免大量不可行解計算的同時加速了算法的迭代。

表4 算法性能分析

因此，基于集群算法操作的改進(jìn)蟻群算法(CSACO)可以在較快的時間中以良好的穩(wěn)定性求得此類問題的最優(yōu)解。

6 結(jié)論

本文針對港口集裝箱甩掛運(yùn)輸問題開展了相關(guān)研究，結(jié)合甩掛運(yùn)輸?shù)奶攸c(diǎn)在不同運(yùn)輸節(jié)點(diǎn)處分別采用甩箱不甩掛和甩箱又甩掛的操作模式。同時，通過甩掛運(yùn)輸實(shí)現(xiàn)了單個決策周期內(nèi)集裝箱空重狀態(tài)的轉(zhuǎn)化以及回收問題，提出帶有前置任務(wù)訪問約束的整數(shù)規(guī)劃模型。通過構(gòu)造牽引車最大任務(wù)數(shù)量以及銜接任務(wù)內(nèi)容兩個決策變量，避免了數(shù)學(xué)模型中出現(xiàn)非整數(shù)決策變量，進(jìn)而提升了精確解的搜索時間和求解規(guī)模。同時，結(jié)合問題的特點(diǎn)設(shè)計了基于集群選擇的改進(jìn)蟻群算法，通過引入節(jié)點(diǎn)剩余任務(wù)矩陣的方式提收斂性以及搜索速度。數(shù)值試驗(yàn)結(jié)果表明，本文所提出的蟻群算法能夠在較短的時間內(nèi)以良好的穩(wěn)定性獲得更好的最優(yōu)解。

針對文中所提到的取空箱任務(wù)(PE)，本文的研究采用的運(yùn)輸策略是統(tǒng)一運(yùn)回空箱堆場進(jìn)行調(diào)度，而在實(shí)際作業(yè)中，由重箱轉(zhuǎn)化的空箱亦可作為一種資源在客戶點(diǎn)之間流動?？紤]客戶點(diǎn)間空箱流動的空重箱聯(lián)合調(diào)運(yùn)問題將在后續(xù)研究中展開，由于前置任務(wù)約束的特點(diǎn)，第一階段任務(wù)完成時間的不確定導(dǎo)致第二階段任務(wù)的開始時間和起始點(diǎn)不能在決策期開始前確定，因此可歸結(jié)為一類OD流完全不確定的空箱調(diào)運(yùn)問題。需要對數(shù)學(xué)模型和算法進(jìn)行進(jìn)一步的優(yōu)化。