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

胡 志 華

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

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

胡 志 華1，2

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

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

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

0 引言

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

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

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

1 互拖問題

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

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

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

2 兩階段方法

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

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

2.1.1 集合與參數(shù)

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

2）TL:兩個碼頭之間的運輸時間。

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

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

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

2.1.2 虛擬任務(wù)

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

起止兩個虛擬任務(wù)的時間窗通過下面的規(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ù)圖連接矩陣和運輸時間矩陣。

2.1.3 計算任務(wù)之間的時間矩陣

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

通過以上定義得到任務(wù)集合V、任務(wù)時間窗口［Li，Ui］、任務(wù)之間的時間矩陣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é)點。

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

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

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

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

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

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

6）DP1=1，DP2=NJ+2:表示起止兩個虛擬任務(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對任務(wù)i∈V開始服務(wù)的時間。

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

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

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

2.2.5 約束函數(shù)

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

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

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

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

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

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

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

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

3 算例分析

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

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

采用Gurobi 4.6對2.2節(jié)建立的混合整數(shù)規(guī)劃模型進行求解，經(jīng)過0.01 s左右計算，得目標(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個任務(wù)。通過調(diào)整參數(shù)，設(shè)置CAP=7，通過0.01 s左右的計算得到結(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ù)序列，以及各個任務(wù)的時間窗口與分派的開始作業(yè)時間，如表2，最后的任務(wù)方向表明互拖任務(wù)是從哪一個碼頭轉(zhuǎn)運到另一個碼頭。

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

（續(xù)表2）

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

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

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

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

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

4 結(jié)語

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

（References）:

［1］ 張欣，施欣.基于合作對策的江蘇沿江港口合作競爭研究［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è)合作定價策略［J］.上海交通大學(xué)學(xué)報，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］包繼華，張鑫，張建武.一種新的汽車列車動力學(xué)建模方法［J］.上海交通大學(xué)學(xué)報，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é)基金項目（71101088，71171129）;社會科學(xué)基金重大項目（11＆ZD169）;中國博士后科學(xué)基金項目（2011M500077，2012T50442）;教育部人文社科一般項目（10YJC630087）;教育部博士點基金項目（20113121120002）;上海市自然科學(xué)基金項目（10ZR1413200，10190502500，11510501900）;上海市教委項目（11YZ137）

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