甩箱模式下考慮多箱型任務(wù)組合的集卡調(diào)度優(yōu)化

靳志宏，黃穎，張佳藝，徐世達(dá)

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

0 引言

在港口集裝箱集散過程中，公路運(yùn)輸因其便捷快速且能提供門到門服務(wù)的優(yōu)勢，在堆場與客戶間的集疏運(yùn)作業(yè)中發(fā)揮重要作用。但這種運(yùn)輸作業(yè)距離較短、運(yùn)輸頻率高，以及有大量往返的短途運(yùn)輸，不僅會(huì)加劇港區(qū)內(nèi)擁堵現(xiàn)象，還會(huì)產(chǎn)生高額運(yùn)輸成本。因此，在不斷發(fā)展港口集裝箱運(yùn)輸業(yè)的同時(shí)，運(yùn)輸成本和運(yùn)輸資源調(diào)用的問題也引起關(guān)注。

在運(yùn)輸集裝箱時(shí)，根據(jù)車輛是否在客戶點(diǎn)等待集裝箱裝卸作業(yè)，將運(yùn)輸模式分為傳統(tǒng)模式、甩掛模式及甩箱模式。在甩掛模式下，牽引車到達(dá)客戶點(diǎn)后甩下集裝箱與掛車，可繼續(xù)執(zhí)行其他任務(wù)，以提高車輛運(yùn)輸效率，降低運(yùn)輸成本[1]。HE 等[2]在研究港口堆場與內(nèi)陸客戶間的牽引車調(diào)度問題時(shí)，考慮集裝箱的空重箱轉(zhuǎn)化過程，并加入牽引車作業(yè)過程中的碳排放成本，以達(dá)到提高運(yùn)輸效率并減少環(huán)境污染的效果。彭勇等[3]針對(duì)交換箱的甩掛運(yùn)輸牽引車調(diào)度優(yōu)化問題進(jìn)行了研究。靳志宏等[4]對(duì)比了滾裝甩掛新船型的運(yùn)輸模式與傳統(tǒng)船型運(yùn)輸模式，建立滾裝甩掛碼頭牽引車調(diào)度模型。

與甩掛模式類似，甩箱模式下集裝箱通過獨(dú)立支架可脫離集卡底盤獨(dú)立放置在客戶裝卸區(qū)，更方便快速。XUE 等[5]研究甩箱模式下的集卡調(diào)度問題，證明甩箱模式能有效減少15.26%的成本，并且隨著裝卸時(shí)間增加，優(yōu)勢更加明顯。SONG 等[6]的研究中，集裝箱在卸載完成后產(chǎn)生的空箱需要送回堆場，建立混合整數(shù)規(guī)劃模型并利用分支定價(jià)精確算法進(jìn)行求解。張建同等[7]研究了類似情況下，基于甩箱模式的港口集卡路徑優(yōu)化問題，通過數(shù)值實(shí)驗(yàn)發(fā)現(xiàn)，在客戶與堆場間位置較為集中時(shí)，集卡的使用數(shù)量和集卡總作業(yè)時(shí)間明顯減少。

在多樣化的貨運(yùn)市場中，集裝箱尺寸繁多，并以20 ft和40 ft為主。集卡通過特殊底盤裝置一次能攜帶兩個(gè)20 ft 的集裝箱或者一個(gè)40ft 的集裝箱。在單個(gè)周期內(nèi)，進(jìn)口集裝箱在卸載完成后需要以空箱的形式運(yùn)回堆場，而出口集裝箱需要提供空箱裝載貨物。對(duì)于這種空重狀態(tài)轉(zhuǎn)化特點(diǎn)，將空箱與重箱任務(wù)進(jìn)行組合，能夠有效緩解由于進(jìn)出口貿(mào)易不對(duì)稱所產(chǎn)生的空箱資源緊缺現(xiàn)象。在此背景下，ZHANG 等[8]和FUNKE 等[9]同時(shí)考慮不同箱型空箱和重箱任務(wù)的組合運(yùn)輸，限制運(yùn)輸過程中集卡攜帶的集裝箱數(shù)量，在甩箱模式下，分別以集卡的總行駛時(shí)間和距離最小化為目標(biāo)，建立調(diào)度優(yōu)化模型。MAHBOOBEH等[10]為研究等待模式和分離模式下車隊(duì)規(guī)模不同和集裝箱尺寸不同情況下的集裝箱運(yùn)輸問題，提出了一個(gè)廣義模型，并利用現(xiàn)實(shí)案例進(jìn)行求解。

從上述分析中可以發(fā)現(xiàn)，現(xiàn)有研究將20 ft 和40 ft 的集裝箱運(yùn)輸任務(wù)在集卡單次運(yùn)輸行程中進(jìn)行組合時(shí)，未考慮到空重箱的轉(zhuǎn)化過程和任務(wù)訪問順序，因?yàn)樵谠O(shè)計(jì)集裝箱的空重轉(zhuǎn)化過程時(shí)，單次運(yùn)輸途中集卡的狀態(tài)變化與任務(wù)的匹配過程變得難以解決。因此，本文充分結(jié)合空重箱狀態(tài)轉(zhuǎn)化和多箱型任務(wù)組合的特點(diǎn)，研究甩箱模式下的集卡調(diào)度優(yōu)化問題。

1 問題描述

在港口與內(nèi)陸客戶組成的運(yùn)輸網(wǎng)絡(luò)中，運(yùn)輸公司為具有不同箱型的進(jìn)出口集裝箱運(yùn)輸需求的客戶點(diǎn)提供服務(wù)。在單周期內(nèi)，所有的進(jìn)出口集裝箱任務(wù)具有送和取兩階段的任務(wù)特性，因此，客戶的20 ft和40 ft集裝箱運(yùn)輸需求可進(jìn)一步細(xì)分，如表1所示。

表1 集裝箱運(yùn)輸任務(wù)Table 1 Container transportation tasks

在行駛過程中，集卡在到達(dá)客戶點(diǎn)后，進(jìn)行甩箱作業(yè)，之后集裝箱在客戶處完成空重轉(zhuǎn)化過程。為了減少由于往返堆場而產(chǎn)生的不必要行駛，收貨人處卸載完畢的空箱可以直接送往托運(yùn)人客戶處。所有集裝箱任務(wù)的執(zhí)行操作只包含在客戶點(diǎn)進(jìn)行的甩箱和提箱過程。而在堆場以及客戶之間的運(yùn)輸過程包含在兩個(gè)集裝箱任務(wù)之間的銜接任務(wù)中，銜接任務(wù)的確定需要結(jié)合集卡狀態(tài)與任務(wù)需求。集裝箱任務(wù)作業(yè)流程如圖1所示。

圖1 集裝箱任務(wù)作業(yè)流程Fig.1 Container task transportation process

1 個(gè)簡單的有向運(yùn)輸網(wǎng)絡(luò)圖G=(N,A)，其中，N={1,2,3} 為任務(wù)集合，A為銜接任務(wù)集合。當(dāng)20 ft 取重箱任務(wù)1 和2 與40 ft 取重箱任務(wù)3 組合時(shí)，由于集卡執(zhí)行完任務(wù)1和2后處于滿載狀態(tài)，因此，銜接任務(wù)(2，3)的內(nèi)容為返回堆場交付當(dāng)前車上集裝箱，隨后，前往任務(wù)3 客戶處。集卡當(dāng)前狀態(tài)決定集卡當(dāng)前任務(wù)與下個(gè)任務(wù)的銜接任務(wù)行駛距離以及銜接時(shí)間。簡單的多箱型集疏運(yùn)任務(wù)如圖2所示。

圖2 多箱型集疏運(yùn)任務(wù)運(yùn)輸示意Fig.2 Example of multi-size container collection and distribution tasks

甩箱模式下，考慮多箱型任務(wù)組合與重空轉(zhuǎn)化的集卡調(diào)度問題屬于非對(duì)稱旅行商問題。由于對(duì)進(jìn)出口任務(wù)進(jìn)行拆分，所以，每個(gè)提箱任務(wù)都有與之對(duì)應(yīng)的前置送箱任務(wù)。提箱任務(wù)需要在其前置任務(wù)已經(jīng)執(zhí)行，并且對(duì)應(yīng)的集裝箱已經(jīng)裝卸完成之后才能開始執(zhí)行，當(dāng)集卡提前到達(dá)時(shí)將會(huì)產(chǎn)生等待時(shí)間。在行駛過程中，集卡狀態(tài)的動(dòng)態(tài)變化增大了問題的求解復(fù)雜性。因此，本文將在保證單周期內(nèi)所有集裝箱任務(wù)都被完成的情況下，考慮任務(wù)的前置任務(wù)約束以及集卡狀態(tài)與不同箱型任務(wù)需求的匹配程度，以集卡啟用成本、行駛以及等待過程中的成本最小化為目標(biāo)建立數(shù)學(xué)模型，在考慮到集裝箱的空重轉(zhuǎn)化過程時(shí)，拆分港口不同箱型進(jìn)出口集裝箱任務(wù)，并引入前置任務(wù)約束。最后，根據(jù)模型特點(diǎn)設(shè)計(jì)基于不可行弧過濾策略的蟻群算法求解問題。

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

2.1 模型假設(shè)

(1)集卡停放于車場，并在初次執(zhí)行任務(wù)時(shí)由車場出發(fā)，執(zhí)行完所有任務(wù)后返回車場；

(2)堆場堆存足夠數(shù)量的空箱；

(3)所有客戶點(diǎn)具備甩箱裝備；

(4)集卡1 次最多能攜帶2 個(gè)20 ft 的集裝箱或者1個(gè)40 ft的集裝箱。

2.2 符號(hào)設(shè)置

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

K——集卡集合，K={1,…,k,…,|K|}，k∈K；

N——所有任務(wù)集合，N={0,1,…,i,…,j,…,|N|}，其中，{0}為集卡出發(fā)以及返回的虛擬任務(wù)，N1=N{0}，i,j∈N；

N1——除去虛擬任務(wù)的任務(wù)集合，N1=，其中為N1中取空箱的任務(wù)子集合，且為取20 ft空箱任務(wù)集合，為取40 ft取空箱任務(wù)集合，類似地，N1(DF)、N1(DE)、N1(PF)分別為送重箱、送空箱、取重箱的任務(wù)子集合；

S——任務(wù)集合N的子集，S?N；

m——集卡在港口提和交20 ft 集裝箱時(shí)間，2m為集卡在港口提和交40 ft集裝箱時(shí)間；

n——集卡在客戶點(diǎn)提和交20 ft集裝箱時(shí)間，2n為集卡在客戶點(diǎn)提和交40 ft集裝箱時(shí)間；

T——集卡的最大工作時(shí)間；

c1——集卡單位啟用成本；

c2——集卡單位行駛成本；

c3——集卡單位等待成本；

M——充分大的正整數(shù)；

ξi——任務(wù)i中集裝箱箱型，ξi={1,2}，其中，20 ft 集裝箱任務(wù)對(duì)應(yīng)ξi=1，40 ft 集裝箱任務(wù)對(duì)應(yīng)ξi=2；

ti——任務(wù)i的執(zhí)行時(shí)間；

tij——任務(wù)i到任務(wù)j的行駛時(shí)間，，其中，dij為任務(wù)i、j的銜接距離，v為集卡行駛速度，?i,j∈N1，?k∈K；

ωi——任務(wù)i的前置任務(wù)；

pi——任務(wù)i的集裝箱裝卸時(shí)間。

(2)狀態(tài)變量

αik——集卡執(zhí)行任務(wù)i的離港剩余箱位數(shù)量，αik={0,1,2}；

βik——集卡執(zhí)行任務(wù)i的當(dāng)前使用箱位數(shù)量，βik={0,1,2}；

——集卡執(zhí)行任務(wù)i時(shí)集卡攜帶20 ft空箱數(shù)量，{0,1,2}；

——集卡執(zhí)行任務(wù)i時(shí)集卡攜帶40 ft空箱數(shù)量，{0,1}；δijk——與集卡當(dāng)前狀態(tài)以及任務(wù)j的需求相關(guān)，δijk={0,1}。

(3)決策變量

xijk——當(dāng)集卡k連續(xù)執(zhí)行任務(wù)i和j時(shí)，xijk=1，否則xijk=0；

yik——當(dāng)集卡k執(zhí)行任務(wù)i時(shí)，yik=1，否則yik=0；

zi——任務(wù)i的開始時(shí)間。

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

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

目標(biāo)函數(shù)由3 部分組成，第1 部分表示集卡的使用成本，與集卡的啟用數(shù)量相關(guān)；第2 部分是集卡的行駛成本，包括任務(wù)銜接時(shí)的行駛成本和當(dāng)任務(wù)與集卡狀態(tài)不匹配時(shí)前往堆場交付所有當(dāng)前車上任務(wù)時(shí)的行駛成本；第3部分是集卡提前到達(dá)任務(wù)起點(diǎn)時(shí)集裝箱裝卸未完成所產(chǎn)生的等待成本。模型的目的是使3部分成本總和最小化。

(2)約束條件

式(2)限制所有任務(wù)只能由一輛車提供服務(wù)。式(3)限制啟用集卡數(shù)不能超過最大集卡數(shù)。式(4)表示若集卡被啟用，必須執(zhí)行起始任務(wù)。式(5)表示集卡不存在從一個(gè)任務(wù)出發(fā)又返回到同一個(gè)任務(wù)的情況。式(6)和式(7)限制任務(wù)被執(zhí)行時(shí)一定有1輛集卡對(duì)任務(wù)進(jìn)行訪問并且離開。式(8)表示任務(wù)只能被集卡訪問一次。式(9)是任務(wù)節(jié)點(diǎn)流量守恒約束。式(10)為回路消除約束。式(11)限制第一個(gè)任務(wù)的開始時(shí)間不能早于到達(dá)時(shí)間。式(12)限制集卡執(zhí)行最后一個(gè)任務(wù)必須有足夠的時(shí)間返回虛擬任務(wù)節(jié)點(diǎn)。式(13)為兩個(gè)任務(wù)之間的銜接時(shí)間約束。式(14)為前置任務(wù)約束。式(15)限制任務(wù)開始時(shí)間范圍。式(16)為相關(guān)決策變量取值約束。

本文研究問題中，由于集卡狀態(tài)隨所執(zhí)行任務(wù)不斷變化，需詳細(xì)說明集卡執(zhí)行任務(wù)過程中剩余箱位和空箱資源變化情況，集卡的初始箱位和相關(guān)參數(shù)的取值范圍為

集卡每執(zhí)行完1次提箱和送箱任務(wù)后，車上剩余箱位數(shù)和所攜帶空箱個(gè)數(shù)都會(huì)發(fā)生相應(yīng)變化，從而影響δijk的取值。對(duì)于?i∈N，?k∈K，若j∈N1(PF)?N1(PE)，δijk的取值僅與當(dāng)前箱位βik有關(guān)，且僅在βik≥ξj時(shí)，δijk=0。而當(dāng)j∈N1(DE)時(shí)，首先，需要考慮車上所帶空箱資源情況，以為例，若0，且αik≤ξj或者βik≤ξj時(shí)，δijk=1；其余情況下，δijk=0。對(duì)于?k∈K，?i∈N，集卡行駛過程中的箱位數(shù)變化情況為

車上攜帶空箱資源的變化情況為

由于本文所建立的集卡調(diào)度模型中，前置任務(wù)約束和集卡箱位的限制導(dǎo)致問題難以用Cplex求解器直接進(jìn)行求解，因此，僅利用小規(guī)模算例對(duì)模型進(jìn)行簡單驗(yàn)證。選取任務(wù)規(guī)模以及比例為8(4-4)的算例，其中，0為出發(fā)以及返回的虛擬任務(wù)，{1，2，3，4，5，6，7，8}為任務(wù)集合，奇數(shù)任務(wù)為偶數(shù)任務(wù)的前置任務(wù)，利用Cplex 求解調(diào)度結(jié)果如圖3所示。使用集卡數(shù)量為1，顯示集卡調(diào)度方案為0→1→5→3→2→7→4→6→8→0，目標(biāo)函數(shù)最優(yōu)解為205.08，驗(yàn)證模型有效。

圖3 求解結(jié)果Fig.3 Solve results

3 基于不可行弧過濾策略的蟻群算法

蟻群算法作為一種概率性算法對(duì)求解車輛調(diào)度問題(VRP)具有一定的優(yōu)越性。然而，在較為復(fù)雜問題的求解過程中，容易出現(xiàn)死循環(huán)、收斂過早或者出現(xiàn)局部最優(yōu)解的情況。在本文研究的考慮箱型組合和重空箱轉(zhuǎn)化的集卡調(diào)度優(yōu)化問題中，進(jìn)出口任務(wù)拆分的空箱和重箱任務(wù)可以分配給不同的集卡，在此種情況下，同時(shí)考慮集卡調(diào)度和前置任務(wù)限制時(shí)，難以用傳統(tǒng)的蟻群算法求出可行的解決方案。因此，本文設(shè)計(jì)了基于不可行弧過濾策略的蟻群算法求解問題，關(guān)鍵設(shè)計(jì)如下。

(1)解的編碼形式

本文的解編碼由1個(gè)m0×n0的變維矩陣構(gòu)成，其維數(shù)隨著集卡任務(wù)安排的變化而不斷變化。在解編碼中，m0為集卡的使用數(shù)量，n0為1輛集卡執(zhí)行的最大任務(wù)數(shù)，編碼中每行元素代表集卡k所執(zhí)行的任務(wù)。解的編碼如圖4所示。

圖4 解的編碼Fig.4 Solution code

(2)不可行弧過濾策略

在利用蟻群算法解決集卡調(diào)度問題時(shí)，蟻群需要遍歷當(dāng)前所有潛在運(yùn)輸弧。潛在運(yùn)輸弧由所有可用集卡的當(dāng)前已執(zhí)行任務(wù)與未被訪問的任務(wù)組成。在本文所研究的問題中，集卡的調(diào)度問題還需要考慮前置任務(wù)、集卡剩余箱位數(shù)及集卡最大行駛時(shí)間限制，導(dǎo)致潛在運(yùn)輸弧中存在部分明顯無法滿足這些限制的不可行弧。不可行弧的存在將會(huì)大大增加算法的計(jì)算復(fù)雜性和計(jì)算時(shí)間，因此，針對(duì)本文所研究問題的特點(diǎn)，提出一種不可行弧過濾策略，過濾準(zhǔn)則如下：

①任務(wù)j的前置任務(wù)ωj已經(jīng)被服務(wù)；

②集卡k的離港箱位滿足任務(wù)j所需條件；

③加入任務(wù)j后，集卡k有足夠的時(shí)間返回出發(fā)點(diǎn)。

同時(shí)滿足上述3種條件時(shí)，潛在弧被判定為可行弧。圖5給出了1組任務(wù)集合和當(dāng)前任務(wù)執(zhí)行情況。設(shè)定每個(gè)奇數(shù)任務(wù)為后一偶數(shù)任務(wù)的前置任務(wù)。從集卡1，2，3的末尾任務(wù)0，4，0為當(dāng)前集卡任務(wù)起始節(jié)點(diǎn)，與未訪問的任務(wù)進(jìn)行銜接組成潛在弧。在未訪問的任務(wù)中，僅有任務(wù)2的前置任務(wù)被訪問，而集卡2 在執(zhí)行完任務(wù)2 后沒有足夠的時(shí)間返回堆場，且當(dāng)前的離港剩余容量不滿足任務(wù)5所需箱位要求。不可行弧過濾策略的具體操作如圖6所示。

圖5 任務(wù)編碼以及當(dāng)前任務(wù)執(zhí)行情況Fig.5 Task code and task execution

圖6 不可行弧過濾Fig.6 Infeasible arc filtering strategy

(3)狀態(tài)轉(zhuǎn)移

在蟻群算法中，螞蟻需要根據(jù)當(dāng)前被訪問節(jié)點(diǎn)到所有可能的下個(gè)訪問節(jié)點(diǎn)的轉(zhuǎn)移概率來選擇下個(gè)任務(wù)訪問節(jié)點(diǎn)。在過濾不可行弧之后，需要計(jì)算每條可行弧的轉(zhuǎn)移概率，任務(wù)節(jié)點(diǎn)i到可行任務(wù)節(jié)點(diǎn)j的轉(zhuǎn)移概率為

式中：i、j屬于可行弧集；pij為螞蟻從任務(wù)i轉(zhuǎn)移到任務(wù)j的概率；ηij=1/ΔZ為能見度系數(shù)，ΔZ由集卡啟用、行駛以及等待的總成本表示；τij為可行弧(i,j)上的信息素濃度；a為信息啟發(fā)式因子；b為期望啟發(fā)式因子。

同時(shí)，為了提高蟻群算法的搜索性能，防止陷入局部最優(yōu)解，使用以下3個(gè)不同的選擇策略提高算法性能。

① 精英策略，選擇轉(zhuǎn)移概率pij最大的弧(i,j)。

②隨機(jī)策略，從可行弧中隨機(jī)選擇弧(i,j)。

③輪盤賭策略，每個(gè)弧的被選擇概率對(duì)應(yīng)于其轉(zhuǎn)移概率pij。

(4)信息素更新

在蟻群算法尋優(yōu)過程中，多條路徑上的信息素濃度不相上下時(shí)會(huì)干擾螞蟻的選擇，影響算法的性能。最大最小螞蟻系統(tǒng)(Max-Min Ant System，MMAS)能夠有效避免傳統(tǒng)蟻群算法的收斂速度和陷入局部最優(yōu)的情況。MMAS 更新策略中，首先，通過加強(qiáng)全局最優(yōu)和當(dāng)前最優(yōu)路徑的信息素濃度，有效改善算法收斂速度；其次，對(duì)每條路徑的信息素濃度設(shè)定變化的最大值和最小值，避免存在信息素濃度過高或過低而產(chǎn)生的局部最優(yōu)解；最后，通過將信息素濃度設(shè)置成最大值，減緩路徑信息素濃度的揮發(fā)。具體步驟如下：

Step 1 選擇一個(gè)解。

Step 2 從解的編碼中隨機(jī)選取元素不都為0 的一行，按順序提取所有非零任務(wù)序號(hào)，例如，7→1→8。

Step 3 確定集卡執(zhí)行任務(wù)的子序列，例如，0→7，7→1，1→8，8→0。

Step 4 如果該螞蟻的目標(biāo)值優(yōu)于當(dāng)前最優(yōu)解，則采用MMAS策略更新子序列的信息素(信息素更新量為Q/ΔZ。其中，ΔZ為目標(biāo)函數(shù)數(shù)值，Q為信息素更新值)；否則，更新每個(gè)螞蟻的整個(gè)子序列信息素。

Step 5 重復(fù)Step 2～Step 4，直到Step 1 中的所有集卡任務(wù)子序列信息素濃度更新。

基于上述主要環(huán)節(jié)，基于不可行弧過濾策略的蟻群算法流程如圖7所示，其中，Niter為迭代次數(shù)，Aant為螞蟻編號(hào)。

圖7 基于不可行弧過濾策略的蟻群算法流程Fig.7 Flow chart of ant colony algorithm based on infeasible arc filtering strategy

4 數(shù)值試驗(yàn)與結(jié)果分析

4.1 算例生成和參數(shù)設(shè)置

本文基于Solomon 標(biāo)準(zhǔn)數(shù)據(jù)集隨機(jī)生成任務(wù)規(guī)模數(shù)不同的算例。在算例生成過程中，對(duì)所有箱型的進(jìn)出口集裝箱任務(wù)進(jìn)行拆分，并設(shè)定奇數(shù)任務(wù)為偶數(shù)任務(wù)的前置任務(wù)。將所有進(jìn)出口任務(wù)隨機(jī)分配給抽取的客戶點(diǎn)，保證每個(gè)客戶點(diǎn)都有任務(wù)。每個(gè)生成的任務(wù)包含有任務(wù)起點(diǎn)、任務(wù)終點(diǎn)、任務(wù)類型、前置任務(wù)、裝卸時(shí)間及任務(wù)占用箱位等信息。具體算例設(shè)置如表2所示。數(shù)值實(shí)驗(yàn)的相關(guān)參數(shù)如表3所示。

表2 算例設(shè)置Table 2 Example settings

表3 參數(shù)設(shè)置Table 3 Parameter settings

在利用基于不可行弧過濾策略的蟻群算法求解問題時(shí)，分別將每種規(guī)模的算例獨(dú)立運(yùn)行10次，并記錄目標(biāo)函數(shù)的最小值與均值。實(shí)驗(yàn)過程中，當(dāng)達(dá)到預(yù)設(shè)的最大迭代次數(shù)時(shí)，算法停止迭代，輸出當(dāng)前最優(yōu)解。為了選取合適的迭代次數(shù)進(jìn)行后續(xù)的實(shí)驗(yàn)，對(duì)前10個(gè)算例分別進(jìn)行多次實(shí)驗(yàn)，并記錄相應(yīng)的最優(yōu)解迭代次數(shù)，最優(yōu)解的迭代次數(shù)統(tǒng)計(jì)情況如圖8所示。

圖8 最優(yōu)解的迭代次數(shù)分布Fig.8 Iteration times of optimal solution

在10 個(gè)算例中，得到最優(yōu)解的迭代次數(shù)在0～50、51～100 及101～200 之間的占比分別為6%，10%，21%，且集中在前期的小規(guī)模算例中，在算例規(guī)模逐步增大時(shí)，部分實(shí)驗(yàn)產(chǎn)生最優(yōu)解的迭代次數(shù)增加。在所有的算例中，迭代次數(shù)在500以內(nèi)的占比76%，而迭代次數(shù)在501～1000 內(nèi)的占比24%。迭代次數(shù)的增加可能會(huì)使得一部分大規(guī)模算例尋得更優(yōu)解，同時(shí)，也會(huì)大幅增加算法的求解時(shí)間，影響算法性能。因此，為了更好地進(jìn)行后續(xù)實(shí)驗(yàn)，并凸顯算法性能，設(shè)定算法最大迭代次數(shù)為500。

4.2 甩箱模式和傳統(tǒng)模式實(shí)驗(yàn)結(jié)果對(duì)比分析

為驗(yàn)證甩箱模式運(yùn)用在多箱型集裝箱運(yùn)輸過程中的優(yōu)越性，利用本文的算法分別求解甩箱模式和傳統(tǒng)模式下的多箱型集裝箱運(yùn)輸作業(yè)總成本。兩種模式下的求解結(jié)果和運(yùn)行時(shí)間如表4所示。甩箱模式與傳統(tǒng)模式的總成本的結(jié)果以及甩箱模式下多次求解的最優(yōu)值與均值結(jié)果如圖9所示，其中，GAP1 為甩箱模式與傳統(tǒng)模式的最優(yōu)值差值，GAP1=100%×(最優(yōu)值2-最優(yōu)值1)/最優(yōu)值2；GAP2 為甩箱模式下最優(yōu)值與均值的差值，GAP2=100%×(均值-最優(yōu)值1)/均值。

結(jié)合表4和圖9可以發(fā)現(xiàn)，傳統(tǒng)模式下，由于進(jìn)出口集裝箱任務(wù)拆分后的兩個(gè)任務(wù)必須前后完成，減少了算法求解的復(fù)雜性，因此，在任務(wù)規(guī)模增加時(shí)，甩箱模式下的求解時(shí)間大于傳統(tǒng)模式的求解時(shí)間。采用甩箱模式進(jìn)行多箱型集裝箱運(yùn)輸作業(yè)的集卡運(yùn)輸總成本遠(yuǎn)遠(yuǎn)低于傳統(tǒng)模式下的集卡運(yùn)輸總成本。相比較傳統(tǒng)模式，甩箱模式由于大幅降低了集卡在客戶等待裝卸的時(shí)間，總成本平均減少45.10%。甩箱模式通過減少集卡等待裝卸的時(shí)間，能夠大幅提高集卡的利用率，并減少等待所產(chǎn)生的高額等待成本。

表4 兩種模式的求解結(jié)果和求解時(shí)間Table 4 Results and solving time of two modes

圖9 結(jié)果比較Fig.9 Result comparison

從表4的結(jié)果進(jìn)一步發(fā)現(xiàn)，任務(wù)規(guī)模相同，兩種箱型的任務(wù)比例不同時(shí)，其對(duì)應(yīng)的目標(biāo)函數(shù)值存在一定差異。為研究兩種箱型的任務(wù)比例對(duì)目標(biāo)函數(shù)的影響，選取任務(wù)規(guī)模為32的算例，改變20 ft與40 ft集裝箱任務(wù)的比例，任務(wù)比例不同的情況下算法求解的結(jié)果如圖10所示。

由圖10可知，隨著20 ft 集裝箱任務(wù)比例的增加，集卡執(zhí)行任務(wù)的總成本也存在不同程度的降低。由于在多箱型集裝箱運(yùn)輸過程中，集卡1次最多可攜帶1 個(gè)40 ft 的集裝箱或者2 個(gè)20 ft 的集裝箱，1 個(gè)集裝箱對(duì)應(yīng)1 個(gè)任務(wù)，因此，當(dāng)20 ft 集裝箱任務(wù)增多時(shí)，集卡車上1 次所攜帶的任務(wù)加倍，提高了集卡的利用效率，也減少了部分重復(fù)往返堆場與客戶之間的行程。因此，在港口多箱型集裝箱集疏運(yùn)過程中，20 ft 集裝箱任務(wù)占總?cè)蝿?wù)比例越多，一車多箱的優(yōu)勢更能發(fā)揮，為企業(yè)節(jié)約更多運(yùn)輸成本。

圖10 不同任務(wù)比例下的求解結(jié)果Fig.10 Solution results under different proportions of tasks

4.3 算法性能分析

通過圖9中Gap2值的變化可知，算法多次求解最優(yōu)值與均值的差距隨著任務(wù)規(guī)模的增大而不斷增大，其差距均值為5.21%，最大值為15.81%，證明算法在不同規(guī)模下的求解穩(wěn)定性較優(yōu)。算法在不同規(guī)模任務(wù)下的收斂速度如圖11所示。

圖11 不同規(guī)模下的收斂圖Fig.11 Convergence graph at different scales

在不同任務(wù)規(guī)模下，算法均能夠在較小的時(shí)間內(nèi)獲得較優(yōu)解，證明算法具有穩(wěn)定性和快速收斂性。在較大規(guī)模算例中，由于前置任務(wù)約束和不可行弧過濾策略導(dǎo)致問題求解難度增加，導(dǎo)致計(jì)算時(shí)間的增長。在任務(wù)規(guī)模大于100后，計(jì)算時(shí)間超過10 min，但仍能得到較為良好的結(jié)果。本文所提出的基于不可行弧過濾策略的蟻群算法利用不可行弧過濾策略將不可行弧提前剔除，通過概率選擇操作保證算法在可行解空間中持續(xù)迭代尋優(yōu)，減少了大量不可行解的計(jì)算，提升了算法的性能。因此，在求解多箱型集裝箱運(yùn)輸問題時(shí)，本文所提出的算法能夠較為穩(wěn)定且快速的求解問題最優(yōu)解。

5 結(jié)論

本文通過甩箱模式實(shí)現(xiàn)單周期內(nèi)的多箱型集裝箱空重轉(zhuǎn)化和協(xié)調(diào)運(yùn)輸過程，建立集卡調(diào)度優(yōu)化模型，并設(shè)計(jì)基于不可行弧過濾策略的蟻群算法求解問題。利用Solomon數(shù)據(jù)集進(jìn)行算例試驗(yàn)，驗(yàn)證算法具有較好的穩(wěn)定收斂性能。在任務(wù)規(guī)模數(shù)相同時(shí)，相較于傳統(tǒng)模式，甩箱模式下的集卡總成本平均減少45.10%，且隨著規(guī)模越大，兩種模式下的總成本差距越大。另外，20 ft集裝箱任務(wù)占比增加能夠更好地提升集卡的利用率。將甩箱模式與一車多箱運(yùn)輸模式進(jìn)行結(jié)合，能充分發(fā)揮兩者的優(yōu)勢，在減少集卡空駛和降低集卡運(yùn)輸成本的同時(shí)，提高港口集疏運(yùn)的效率。