胡 志 華

（1.同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院，上海 200092;2.上海海事大學(xué) 物流研究中心，上海 201306）

集裝箱碼頭間互拖的集卡甩掛運(yùn)輸調(diào)度問題

胡 志 華1，2

（1.同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院，上海 200092;2.上海海事大學(xué) 物流研究中心，上海 201306）

集裝箱碼頭間的互拖是一種促進(jìn)相鄰碼頭資源重新組織與優(yōu)化的協(xié)作方式，集裝箱甩掛運(yùn)輸能夠解耦互拖與港內(nèi)作業(yè)之間的復(fù)雜耦合關(guān)系。為了提高互拖的集裝箱甩掛運(yùn)輸?shù)挠行?，滿足碼頭間協(xié)調(diào)的時(shí)間要求和對(duì)集卡資源的有效利用，提出了互拖集卡甩掛運(yùn)輸調(diào)度的兩階段方法。首先建立互拖任務(wù)之間的時(shí)間關(guān)系網(wǎng)絡(luò)，然后在此基礎(chǔ)上建立集卡調(diào)度的混合整數(shù)規(guī)劃模型。算例分析說明了該方法的有效性;演示集卡作業(yè)任務(wù)序列，分析其碼頭作業(yè)量分布對(duì)于港內(nèi)作業(yè)調(diào)度的影響。研究結(jié)果提供了碼頭間互拖集卡甩運(yùn)輸?shù)囊环N參考方法。

互拖;甩掛運(yùn)輸;集裝箱運(yùn)輸;車輛路徑規(guī)劃問題;混合整數(shù)規(guī)劃

0 引言

集裝箱互拖是已經(jīng)被上海洋山港2期和3期碼頭、外高橋1期和2期碼頭以及其他多個(gè)集裝箱港口采用的協(xié)作策略。通過互拖通道連接兩個(gè)碼頭，使得集裝箱裝卸可以在相鄰碼頭完成，從而拓展了集裝箱港口運(yùn)作優(yōu)化與協(xié)調(diào)的范圍與空間。港口之間的合作關(guān)系歷來受到港口企業(yè)與學(xué)術(shù)界的重視［1-3］，而互拖則是相鄰碼頭之間合作的一種具體形式，目前在國內(nèi)外學(xué)術(shù)文獻(xiàn)中未見研究。然而，現(xiàn)有的模式要求互拖與兩碼頭內(nèi)部運(yùn)作之間進(jìn)行緊密協(xié)調(diào)，以盡量減少集卡等待時(shí)間。由于運(yùn)輸過程和港口裝卸作業(yè)的復(fù)雜性，對(duì)運(yùn)作優(yōu)化提出挑戰(zhàn)。筆者提出基于集裝箱甩掛的互拖模式，解耦互拖與碼頭內(nèi)部作業(yè)的復(fù)雜關(guān)系。

甩掛運(yùn)輸（truck-and-trailer transport）是指用牽引車拖帶掛車至目的地，將掛車甩下后，直接轉(zhuǎn)接新運(yùn)輸任務(wù)的運(yùn)輸方式。Gerdessen［4］較早對(duì)帶掛車的車輛路徑問題（Truck and Trailer Routing Problem，簡稱 TTRP）進(jìn)行研究。Scheuerer［5］和 Chao［6］使 用 Tabu Search 求 解 TTRP。Lin，等［7-9］采用模擬退火算法研究 TTRP。國內(nèi)學(xué)者包繼華，等［10］則從甩掛車輛技術(shù)和國內(nèi)開展甩掛運(yùn)輸?shù)挠行赃M(jìn)行論證與分析。對(duì)甩掛運(yùn)輸車輛調(diào)度的研究，目前文獻(xiàn)中非常少見。隨著甩掛運(yùn)輸方式的普及，相關(guān)的調(diào)度、優(yōu)化和決策問題的研究必將得到重視。

甩掛運(yùn)輸將貨物裝卸過程與運(yùn)輸過程分離，從而提高牽引車的利用率。這一特點(diǎn)與互拖的結(jié)合，使得互拖集裝箱運(yùn)輸與集裝箱的裝卸作業(yè)分離，顯著降低碼頭多種作業(yè)設(shè)備之間的耦合。

1 互拖問題

互拖是集裝箱碼頭，尤其是相鄰碼頭之間充分共享堆場空間、前沿作業(yè)空間，以及集裝箱作業(yè)設(shè)施的一種有效方式，逐漸被沿海港口采用。并且在信息技術(shù)的支持下，以互拖公共服務(wù)平臺(tái)為紐帶，實(shí)現(xiàn)協(xié)作碼頭之間作業(yè)信息的貢獻(xiàn)，從而極大的促進(jìn)了集裝箱港口資源的重調(diào)配與再優(yōu)化。兩個(gè)相鄰碼頭之間的雙港互拖是目前港口企業(yè)主要適用的互拖模式，雖然多港互拖理論上具有可行性，但尚未見報(bào)道。A和B兩個(gè)碼頭之間通過集卡轉(zhuǎn)運(yùn)集裝箱，如圖1。通常轉(zhuǎn)運(yùn)的集裝箱是重箱，而空箱轉(zhuǎn)運(yùn)也可行，只是一般不如重箱緊急。從A碼頭將集裝箱帶往B碼頭后，可能帶箱回A碼頭，抑或空車回。

圖1 A、B碼頭之間集裝箱互拖示意Fig.1 Illustration of container mutual transportbetween port A and port B

在不使用甩掛運(yùn)輸?shù)幕ネ舷到y(tǒng)中，從A碼頭將集裝箱轉(zhuǎn)運(yùn)到B碼頭后，直接卸到B碼頭堆場，或是等待橋吊或龍門吊等直接對(duì)集裝箱作業(yè)。這種方式又可稱為跨港“轉(zhuǎn)堆”。因此，要求精確控制集裝箱運(yùn)輸出發(fā)和抵達(dá)的時(shí)間，以減少集卡的等待。為了充分利用橋吊和龍門吊等優(yōu)先級(jí)別更高的港內(nèi)作業(yè)設(shè)施，通常犧牲集卡利益，等待難以避免。而甩掛運(yùn)輸則可以充分避免這一點(diǎn)。集卡帶箱到B碼頭，通過控制甩掛裝置，直接將集裝箱甩到掛車裝置上，即可開始新的任務(wù)。當(dāng)B碼頭能夠安排該箱的裝卸作業(yè)時(shí)，再直接調(diào)度橋吊和龍門吊等裝卸作業(yè)設(shè)備，或是通過其他甩掛牽引車將該箱帶到作業(yè)位置。從而將互拖任務(wù)完全轉(zhuǎn)化為可控的碼頭內(nèi)部作業(yè)調(diào)度。然而，通過甩掛運(yùn)輸實(shí)現(xiàn)互拖的一個(gè)問題是，集裝箱甩下后采用平堆方式將占用碼頭空間，在空間非常緊張的碼頭難以推行。因此，即使采用甩掛，同樣要求盡量精確地控制任務(wù)的時(shí)間窗，以及控制互拖的兩個(gè)碼頭的作業(yè)量。

2 兩階段方法

2.1 階段1——生成任務(wù)網(wǎng)絡(luò)

在兩個(gè)碼頭之間的互拖運(yùn)輸問題中，所涉及的物流網(wǎng)絡(luò)簡單，僅包括如圖1的A和B兩個(gè)碼頭，以及在A和B之間的雙向互拖通道。互拖的關(guān)鍵是盡量降低集裝箱在目的港的堆放時(shí)間，最佳策略是直接通過橋吊裝船。如果是進(jìn)口箱則直接由外集卡到集裝箱所在碼頭取箱，避免再次中轉(zhuǎn)。根據(jù)互拖集裝箱在兩個(gè)碼頭的時(shí)間約束，建立互拖任務(wù)之間的優(yōu)先關(guān)系圖，即任務(wù)網(wǎng)絡(luò)。

2.1.1 集合與參數(shù)

1）N={2，3，…，NJ+1}:任務(wù)集合。

2）TL:兩個(gè)碼頭之間的運(yùn)輸時(shí)間。

3）TP:集裝箱運(yùn)輸?shù)侥康母酆?，僅完成甩掛所需作業(yè)時(shí)間。

4）Fn∈{0，1}:如果任務(wù)n∈N是從A碼頭運(yùn)輸?shù)紹碼頭，則為0;否則為1。

5）［Ij，IIj］:任務(wù)j∈N的時(shí)間窗口，顯然應(yīng)當(dāng)滿足IIj-Ij≥TL+2TP。

2.1.2 虛擬任務(wù)

定義兩個(gè)虛擬任務(wù):開始任務(wù)1和結(jié)束任務(wù)（NJ+2），加入集合J得到V=N∪{1，NJ+2}。

起止兩個(gè)虛擬任務(wù)的時(shí)間窗通過下面的規(guī)則定義:

1）定義為［L，U］∶［L1，U1］=［LNJ+2，UNJ+2］=［minj∈NIj，maxj∈JIIj］;

2）?n∈N，［Ln，Un］=［In，IIn］

在集合N之上，定義參數(shù)A和T分別表示任務(wù)圖連接矩陣和運(yùn)輸時(shí)間矩陣。

2.1.3 計(jì)算任務(wù)之間的時(shí)間矩陣

如果任務(wù)i∈V和j∈V由同一集卡相繼服務(wù)，任務(wù)之間由于場地變換的時(shí)間定義為Ti，j。對(duì)于虛擬開始任務(wù)，能夠緊接著對(duì)任意任務(wù)進(jìn)行服務(wù);對(duì)于虛擬結(jié)束任務(wù)則可以在任意任務(wù)結(jié)束后執(zhí)行;另外，如果第1個(gè)任務(wù)是從A到B，而第2個(gè)任務(wù)是從B到A，則依次對(duì)兩個(gè)任務(wù)服務(wù)的時(shí)間間隔都定義為0。如果從第1個(gè)任務(wù)最早時(shí)間開始，經(jīng)過源港裝卸、運(yùn)輸、目的港裝卸之后，能夠趕上第2個(gè)任務(wù)的最晚開始時(shí)間，則兩個(gè)任務(wù)之間的連接時(shí)間是TL。在以上情況之外，T=∞。即，矩陣T通過式（1）定義:

通過以上定義得到任務(wù)集合V、任務(wù)時(shí)間窗口［Li，Ui］、任務(wù)之間的時(shí)間矩陣T和連接矩陣A。

2.2 階段2——集卡甩掛調(diào)度

第2階段集卡甩掛調(diào)度的關(guān)鍵是確定集卡的作業(yè)序列。

2.2.1 集 合

1）V={1，2，…，NJ，NJ+1，NJ+2}:其中，1 和（NJ+2）為虛擬起止節(jié)點(diǎn)。

2）K={1，2，…，NK}:即集卡牽引車集合。2.2.2 參 數(shù)

1）Di:任務(wù)?i∈V需要的容量，由于采用集卡單元化運(yùn)輸，則?i∈N，Di=1，且D1=DNJ+2=0，從完整角度看該參數(shù)能夠處理帶有多掛車的運(yùn)輸任務(wù)。

2）Pi:任務(wù)?i∈V的處理時(shí)間，?i∈N，Pi=TL+2TP，且P1=PNJ+2=0。

3）Ti，j，?i∈V，j∈V:在第1 階段定義的任務(wù)時(shí)間矩陣。

4）Ai，j，?i∈V，j∈V:在第1 階段定義的任務(wù)連接矩陣。

5）M:一個(gè)足夠大的數(shù)，主要用于轉(zhuǎn)換非線性表達(dá)式。

6）DP1=1，DP2=NJ+2:表示起止兩個(gè)虛擬任務(wù)。

7）CAP:集卡線路上任務(wù)數(shù)量限制。

2.2.3 決策變量

1）xk，i，j∈{0，1}:x是流變量，如果車輛k∈K在服務(wù)完任務(wù)i∈V后緊接著服務(wù)任務(wù)j∈V，則為xk，i，j=1;否則為 0。

2）τk，i:車輛k∈K對(duì)任務(wù)i∈V開始服務(wù)的時(shí)間。

2.2.4 目標(biāo)函數(shù)目標(biāo)是總服務(wù)時(shí)間的最小化，如式（3）:

2.1.4 計(jì)算任務(wù)連接矩陣

任務(wù)連接矩陣是0/1矩陣，1表示兩個(gè)任務(wù)之間可以直接相繼為同一集卡作業(yè);0則表示不可行，如式（2）:

2.2.5 約束函數(shù)

虛擬任務(wù)之外的其他任何任務(wù)都僅需要被服務(wù)1次，如式（4）:

對(duì)于任意集卡，從虛擬開始節(jié)點(diǎn)出發(fā)，到虛擬結(jié)束節(jié)點(diǎn)后完成運(yùn)輸，僅負(fù)責(zé)一個(gè)任務(wù)序列，約束如式（5）和式（6）:

對(duì)任意集卡，對(duì)任意非虛擬任務(wù)，滿足該任務(wù)在任務(wù)網(wǎng)絡(luò)中的流約束，如式（7）:

對(duì)任意集卡負(fù)責(zé)的線路，即該線路上的任務(wù)序列，通過相繼關(guān)系x及相應(yīng)時(shí)間序關(guān)系t規(guī)避線路上的子回路，式（8）是一個(gè)非線性表達(dá)式:

式（8）通過式（9）轉(zhuǎn)化為一個(gè)線性表達(dá)式，從而使得最終建立的模型是0/1整數(shù)規(guī)劃模型:

根據(jù)式（10）和式（11）建立時(shí)間窗約束:

根據(jù)式（12）建立集卡線路的工作量約束，在滿足其他約束和最小化服務(wù)時(shí)間的前提下可以通過該參數(shù)均衡各個(gè)集卡的工作量:

通過目標(biāo)函數(shù)式（3），約束函數(shù)式（4）～式（7），式（9）～式（12）定義了集卡甩掛任務(wù)調(diào)度的0/1整數(shù)規(guī)劃模型。

3 算例分析

以上海洋山港2期和3期碼頭之間，以及外高橋1期和2期碼頭之間的互拖通道為例，驗(yàn)證文中提出的兩階段方法。取TL=15，TP=2，CAP=20。20個(gè)互拖任務(wù)及其時(shí)間窗和轉(zhuǎn)運(yùn)方向見表1。其中，虛擬任務(wù)1和22分別表示起止任務(wù)節(jié)點(diǎn)，時(shí)間窗?。?，240］，即20是個(gè)互拖任務(wù)要在一個(gè)4 h的小工班內(nèi)完成，它們的時(shí)間窗配置也正是說明這一點(diǎn)。然后，根據(jù)式（1）計(jì)算任務(wù)之間的時(shí)間矩陣T。根據(jù)式（2），計(jì)算任務(wù)之間的連接矩陣A。

表1 互拖任務(wù)及其時(shí)間窗與轉(zhuǎn)運(yùn)方向Table 1 Mutual transport tasks，time windows and transport directions

采用Gurobi 4.6對(duì)2.2節(jié)建立的混合整數(shù)規(guī)劃模型進(jìn)行求解，經(jīng)過0.01 s左右計(jì)算，得目標(biāo)函數(shù)為338。因而3條線路及其依次服務(wù)的任務(wù)如下:①11，13，3，2，5;②7，6，10，9，14，19，16，12;③17，8，4，20，21，18，15。

3條線路分別完成5，8和7個(gè)任務(wù)。通過調(diào)整參數(shù)，設(shè)置CAP=7，通過0.01 s左右的計(jì)算得到結(jié)果，目標(biāo)函數(shù)值依然是338。3條線路如下:①11，20，4，13，3，16，21;②19，2，15，9，10，8，5;③7，6，14，17，18。

綜合3條線路，線服務(wù)的任務(wù)序列，以及各個(gè)任務(wù)的時(shí)間窗口與分派的開始作業(yè)時(shí)間，如表2，最后的任務(wù)方向表明互拖任務(wù)是從哪一個(gè)碼頭轉(zhuǎn)運(yùn)到另一個(gè)碼頭。

表2 線路任務(wù)排序及其開始時(shí)間與時(shí)間窗口Table 2 Task sequences，the starting time and time windows

（續(xù)表2）

圖2為根據(jù)表2的信息，直觀地說明了3個(gè)任務(wù)序列在兩個(gè)碼頭之間的集裝箱轉(zhuǎn)運(yùn)過程。3種不同線型分別表示3個(gè)任務(wù)序列。從圖中可以看出，有些折線相互并沒有連接在一起，則表明相繼的任務(wù)之間集卡有等待時(shí)間。

圖2 兩個(gè)碼頭之間的互拖線路安排Fig.2 Routing between two ports for container mutual transport

根據(jù)表2和圖2的信息，通過將作業(yè)工班劃分為5個(gè)區(qū)間，每個(gè)區(qū)間50 min，通過每個(gè)區(qū)間內(nèi)A和B兩個(gè)碼頭的作業(yè)量，得到作業(yè)量分布如圖3。

圖3 碼頭裝卸作業(yè)量分布Fig.3 Workload distribution of container loading and unloading in ports

從圖3可以看出，由于是獨(dú)立的一個(gè)工班，沒有前后的滾動(dòng)任務(wù)，因此在首部時(shí)段作業(yè)量較少;而后的4個(gè)時(shí)段作業(yè)量基本均衡;從兩個(gè)碼頭各個(gè)時(shí)段的作業(yè)量來看，也非常均衡，其中主要的一個(gè)原因是兩港之間的轉(zhuǎn)運(yùn)時(shí)間與甩掛時(shí)間之和在15～19之間，完全在一個(gè)時(shí)間區(qū)間之內(nèi)。圖3的另一個(gè)更重要的目的是為兩個(gè)碼頭的裝卸搬運(yùn)調(diào)度服務(wù)。通過該直方圖能夠獲得不同時(shí)段對(duì)橋吊、龍門吊或正面吊等其他集裝箱作業(yè)資源的需求。另一方面，該直方圖也能夠反過來約束集卡甩掛的調(diào)度，通過建立資源約束的甩掛調(diào)度模型使得不同時(shí)段滿足不同的資源限制。

4 結(jié)語

通過對(duì)雙港互拖問題的研究，提出基于集裝箱甩掛運(yùn)輸?shù)幕ネ戏椒ㄒ越怦罨ネ吓c集裝箱港口內(nèi)部作業(yè)調(diào)度之間的復(fù)雜關(guān)系。建立了兩個(gè)碼頭之間集裝箱互拖甩掛運(yùn)輸調(diào)度的混合整數(shù)規(guī)劃模型，通過算例驗(yàn)證模型的有效性。下一步的研究方向包括:大規(guī)模甩掛調(diào)度的有效調(diào)度策略與算法;考慮軟時(shí)間窗口和運(yùn)輸時(shí)間不確定性的集卡甩掛調(diào)度;多港協(xié)調(diào)的集卡甩掛資源配置與調(diào)度;集卡甩掛與碼頭內(nèi)作業(yè)的協(xié)調(diào)優(yōu)化。

（References）:

［1］ 張欣，施欣.基于合作對(duì)策的江蘇沿江港口合作競爭研究［J］.中國航海，2007（3）:69-72.

Zhang Xin，Shi Xin.Research on co-competition among ports along the Yangtze river in Jiangsu province based on cooperative game model［J］.Navigation of China，2007（3）:69-72.

［2］ 周鑫，沙梅，鄭士源，等.基于空間區(qū)位模型的港口企業(yè)合作定價(jià)策略［J］.上海交通大學(xué)學(xué)報(bào)，2011，45（1）:125-129.

Zhou Xin，Sha Mei，Zheng Shiyuan，et al.Pricing strategy of port enterprises under cooperation condition based on located spatial model［J］.Journal of Shanghai Jiaotong University，2011，45（1）:125-129.

［3］ 莊佩君.集裝箱港口競合戰(zhàn)略研究［J］.中國航海，2005（1）:77-81.

Zhuang Peijun.Co-opetition:A new strategy for container ports［J］.Navigation of China，2005（1）:77-81.

［4］ Gerdessen J C.Vehicle routing problem with trailers［J］.European Journal of Operational Research，1996，93（1）:135-147.

［5］ Scheuerer S.A tabu search heuristic for the truck and trailer routing problem［J］.Computers and Operations Research，2006，33（4）:894-909.

［6］ Chao I M.A tabu search method for the truck and trailer routing problem［J］.Computers and Operations Research，2002，29（1）:33-51.

［7］ Lin S W，Yu V F，Chou S Y.Solving the truck and trailer routing problem based on a simulated annealing heuristic［J］.Computers and Operations Research，2009，36（5）:1683-1692.

［8］ Lin S W，Yu V F，Chou S Y.A note on the truck and trailer routing problem ［J］.Expert Systems with Applications，2010，37（1）:899-903.

［9］ Lin S W，Yu V F，Lu C C.A simulated annealing heuristic for the truck and trailer routing problem with time windows［J］.Expert Systems with Applications，2011，38（12）:15244-15252.

［10］包繼華，張鑫，張建武.一種新的汽車列車動(dòng)力學(xué)建模方法［J］.上海交通大學(xué)學(xué)報(bào)，2007，41（2）:244-249.

Bao Jihua，Zhang Xin，Zhang Jianwu.A new method of dynamic model building of combination vehicles［J］.Journal of Shanghai Jiaotong University，2007，41（2）:244-249.

Scheduling of Container Truck-and-Trailer Transport between Two Ports

Hu Zhihua1，2
（1.School of Economics＆ Management，Tongji University，Shanghai 200092，China;
2.Logistics Research Center，Shanghai Maritime University，Shanghai 201306，China）

Mutual transport among container ports cooperatively enhances the reorganization and re-optimization of operational resources among neighboring ports.In order to enhance the validity of mutual transport by container truck-and-trailer transport，and to satisfy the time constraints，a two-stage approach is proposed for scheduling container trucks for mutual transport.First，a time relationship matrix is built among mutual transport tasks;second，a mixed integer linear programming model is built for container trucks.Numeric samples are employed to show the validity of the approach，and demonstrate the sequences of the tasks for trucks.Moreover，the influences of distribution of mutual transport tasks to operations scheduling within ports are analyzed.The result provides a reference approach for scheduling truck-and-trailer container trucks for biport mutual transport.

container mutual transport;truck-and-trailer transport;container transport;vehicle routing problem;mixed integer linear programming

F253.4

A

1674-0696（2013）02-0313-05

10.3969/j.issn.1674-0696.2013.02.30

2012-05-11;

2012-09-05

國家自然科學(xué)基金項(xiàng)目（71101088，71171129）;社會(huì)科學(xué)基金重大項(xiàng)目（11＆ZD169）;中國博士后科學(xué)基金項(xiàng)目（2011M500077，2012T50442）;教育部人文社科一般項(xiàng)目（10YJC630087）;教育部博士點(diǎn)基金項(xiàng)目（20113121120002）;上海市自然科學(xué)基金項(xiàng)目（10ZR1413200，10190502500，11510501900）;上海市教委項(xiàng)目（11YZ137）

胡志華（1977—），男，湖南長沙人，博士，主要從事港航與物流運(yùn)作優(yōu)化、社會(huì)科學(xué)計(jì)算實(shí)驗(yàn)與計(jì)算智能方面的工作。E-mail:zhhu@shmtu.edu.cn。