□ 胡 菡

(武漢理工大學 物流工程學院，武漢 430063)

1 引言

面對經濟全球化的發(fā)展趨勢，現代港口在社會經濟發(fā)展中的作用和地位發(fā)生了深刻變化，港口被定位為經濟網絡中的重要節(jié)點。在大宗貨物的水路運輸中，集裝箱運輸起著關鍵作用。為了提高集裝箱港口的作業(yè)效率和服務水平，各國港口和研究機構投入了大量的人力和財力。集裝箱卡車(簡稱集卡)是我國大部分集裝箱港口所采用的水平運輸工具，主要用于銜接集裝箱的裝卸和場內集裝箱堆放業(yè)務。由于集裝箱港口需要裝卸大量集裝箱，并且存在港口道路限制，進出口船舶的停泊時間限制以及集裝箱儲存地點的限制等，集裝箱港口的水平運輸調度系統(tǒng)非常復雜。集卡的調度和配置是否有效合理直接影響到岸橋等裝卸設備的作業(yè)效率，并對整個集裝箱碼頭的作業(yè)系統(tǒng)能否高效順暢的運轉產生重要影響。因此，如何合理調度港區(qū)集卡，有效提高集卡的運行效率已成為重要的研究課題，并逐漸引起港口管理者及相關專家學者的關注。

對集裝箱碼頭集卡調度的研究較為廣泛，Kim等[1]以最小化岸橋等待時間和水平調度車總行駛時間為目標，提出了一種基于混合整數規(guī)劃模型的集卡調度方法。Nishimura等[2]在針對集裝箱港口作業(yè)中集卡通常被分配給固定的岸橋的情況，提出了一種更高效的集卡分配規(guī)則，即動態(tài)調度。Shang[3]討論了如何確定集卡車隊的規(guī)模以及如何分配送貨工作，并提出了一種考慮雙40英尺碼頭起重機工作特性的混合整數規(guī)劃模型。楊靜蕾[4]以集卡總行駛路徑最短為目標，建立了集卡路徑優(yōu)化模型，并對算例進行了求解。曾慶成等[5]以最小化岸橋等待時間為目標，建立了集卡動態(tài)調度模型。Han等[6]在提出了一種整合集卡調度和一種分配集裝箱存儲空間的方法，旨在平衡各個碼頭區(qū)域的工作量，以盡量減少集卡造成的交通擁堵。Lee等[7]綜合考慮了集卡調度和進口集裝箱存儲分配問題，并建立了一個混合整數規(guī)劃模型，通過減少集卡的等待時間來到達最小化卸貨任務完成時間的目標。邢子超[8]基于碼頭集卡的定位系統(tǒng)，設計了一種集卡共享式實時調度算法和作業(yè)線搭配調度算法，使得集卡完成固定數量任務的時間最短。

本文對集卡調度問題進行了研究，構建了基于“作業(yè)面”模式的集卡動態(tài)調度數學模型，包括模型的假設、目標函數、約束條件和模型的適應對象。對所建數學模型用lingo數學軟件進行了編程求解，并應用兩個算例分別在基于“作業(yè)線”模式下和在基于“作業(yè)面”調度模式下進行了求解，并對求解結果進行對比分析，驗證了所建數學模型的正確性和有效性。

2 問題分析和數學建模

集卡在執(zhí)行裝卸船任務時所處的狀態(tài)有：等待岸橋、由岸橋進行裝卸操作、等待場橋、由場橋進行裝卸操作、重載行駛和空載行駛等狀態(tài)。由于岸橋一般是港口裝卸作業(yè)的瓶頸，岸橋的效率直接影響著港口整體的作業(yè)效率。為保證岸橋的工作效率，集卡經常會在岸橋下等待其操作。港區(qū)內場橋的數量一般充足，所以本文不考慮集卡等待場橋情況。本文綜合考慮集卡和岸橋的協同作業(yè)，以集卡的行駛路徑為研究對象，對裝卸船作業(yè)中的集卡的調度進行研究。集卡在執(zhí)行一次任務的行駛過程可分為兩部分：集卡由當前位置行駛至任務起始地，集卡載著集裝箱行駛至任務終止地。其中第一部分為空駛段，這一部分的行駛里程是港口希望縮短的。目前，集裝箱碼頭的集卡調度方法可分為基于“作業(yè)線”的調度法和基于“作業(yè)面”的調度法。在基于“作業(yè)線”的調度方法中，集卡受“作業(yè)線”的約束，集卡在完成一次任務后必須空駛返回岸橋或堆場處，集卡的空駛率高，沒有太大改進的空間。而在“作業(yè)面”模式中，集卡采用動態(tài)調度的方式而“重進重出”，有效縮短空駛里程，降低集卡的空駛率。

本文以“作業(yè)面”模式為基礎，對集卡的動態(tài)調度方案進行研究。綜合考慮了集卡工作過程中的兩種會出現集卡空駛里程的情形，包括集卡在執(zhí)行第一個任務時，從當前位置前往任務起始地的空駛里程；集卡在完成一個任務后從當前任務的終點前往下一任務起點的空駛里程。本文的調度方案是通過降低這兩種空駛里程來降低空駛率，即在保證整體效率的基礎上，讓集卡以空駛里程最短為目標去選擇將要執(zhí)行的集裝箱任務。同時，我們將船舶?？繒r間作為評價港口整體作業(yè)效率的重要指標。以最小化船舶?？繒r間為目標有兩個原因：一是更加貼合實際情況；二是如果只以最小化空駛時間為目標，會產生部分集卡集中承擔大部分任務的情況，導致所有任務完成的時間大幅延長，降低了港口整體效率。

港口在裝卸作業(yè)中主要考慮的對象為：集裝箱、岸吊、場吊和集卡。在一個集裝箱任務中，和岸吊和場吊相關的時間點為它們執(zhí)行任務的開始時間和結束時間；和集卡相關的時間點為到達任務起點的時間點、集裝箱裝載時間點、到達任務終止點的時間點、集裝箱卸載時間點。對某一岸吊或集卡而言，上一個任務的結束時間小于等于下一任務的開始時間。根據任務中各時間點的聯系確定約束條件。根據裝(卸)船任務流程建立約束條件。在卸船任務流程中，集卡從當前位置前往任務起點，集卡到達任務起點，集裝箱任務開始。若不需要排隊等待，岸吊可以操作開始，經過岸吊的操作后，集裝箱裝載上集卡，岸吊操作結束。集卡前往任務終點，到達后場吊可以開始卸載集裝箱，經過場吊操作后，集裝箱完成卸載，任務結束。在裝船任務流程中，集卡從當前位置出發(fā)前往任務起點位置，集卡到達起點后，場吊可以裝載集裝箱，場吊操作完成后集裝箱完成裝載。集卡前往任務終點，若不需排隊等待，岸吊可以開始操作，經過岸吊操作時間后，集裝箱完成卸載，岸吊操作完成，任務結束。

為方便建模，我們對問題做出如下假設：

?所有集卡在港區(qū)內是勻速行駛的，因此，往返于堆場的箱區(qū)間或堆場與岸吊間所花費的時間是固定的；

?港口內的運作都是有序的，忽略擁堵現象影響；

?忽略港口內其他作業(yè)(例如導向、提箱、收箱操作等)對裝卸作業(yè)集卡調度的影響；

?場橋數量充足，不考慮集卡等待場橋的情況。

在模型建立之前，需要確定模型的輸入和輸出。具體輸入如下：

?集裝箱任務數量及任務起始點與終止點的具體信息；

?港口詳細的布局地理信息圖，需要把港口相關的點提取出來，算出每兩點間的距離；

?集卡數量及其初始位置。

輸出信息中，我們可以得到每輛集卡的集裝箱任務序列，并得到所有任務完成時間，根據需要可以統(tǒng)計出集卡的空駛率。

符號定義：

N代表港口某段時間內的所有裝卸的集裝箱集合

M代表港口可供使用的集卡的集合

K代表港口內可供使用的岸橋的集合

wi代表集裝箱任務i的起始時間

ci代表集裝箱任務i的結束時間

oi代表集裝箱任務i的起始地點

ei代表集裝箱任務i的終止地點

ski代表岸橋開始執(zhí)行集裝箱任務i的時間

lm代表集卡m的初始位置

sij代表從集裝箱任務i的終點位置到集裝箱任務j起點距離(以集卡行駛時間計)

dij代表地點i和地點j之間距離(以集卡行駛時間計)

qim代表集卡m初始位置和集裝箱任務i起始點之間距離(以集卡行駛時間計)

th代表岸橋對一個集裝箱進行裝卸操作所需時間

ty代表場橋對一個集裝箱進行裝卸操作所需時間

R代表一個足夠大的數

a，b代表目標函數中主要目標與次要目標所占的權重

決策變量(0-1)：

xijm若集卡m在執(zhí)行完集裝箱任務i后執(zhí)行任務j，則為1；否則為0

yim若集卡m負責執(zhí)行集裝箱任務i，則為1；否則為0

gijk若岸橋k在執(zhí)行完集裝箱任務i后執(zhí)行任務j，則為1；否則為0

zi若集裝箱i是裝船集裝箱則為1；否則為0

fik若岸橋k負責執(zhí)行集裝箱任務i則為1；否則為0

目標函數與約束條件

Min:z=a*max(ci)+b*(∑i,jsijxijm+∑mqim)

(1)

約束條件：

(2)

(3)

(4)

xijm+xjim≤1) ?i,j∈Nandi≠j,?m∈M

(5)

(6)

(7)

(8)

gijk+gjik≤1 ?i,j∈Nandi≠j,?k∈K

(9)

(10)

sij=deioj?i,j∈Nandi≠j

(11)

ti=doiei?i∈N

(12)

(13)

(14)

(15)

r+qim≤wi?i∈N，?m∈M

(16)

對于卸船集裝箱任務，即zi=0時：

wi≤ski?i∈N

(17)

ski+th+ti+ty=ci?i∈N

(18)

對于裝船集裝箱任務，即zi=1時：

wi+ty+ti≤ski?i∈N

(19)

ski+th=ci?i∈N

(20)

xijm,yim,gijk∈{0,1}

(21)

式(1)是目標函數的表達式，即最小化船舶?？繒r間和集卡空駛時間的加權之和。約束條件(2)至(6)對集卡的任務序列進行約束。約束條件(7)至(10)對岸橋的任務序列進行約束：式(7)表明在岸橋的任務序列中，任意一個集裝箱任務最多有一個后續(xù)任務；式(8)表明在岸橋的任務序列中，任意一個集裝箱任務最多有一個前續(xù)任務；式(9)表明在岸橋的任務序列中，如果集裝箱任務i是任務j的后續(xù)任務，則任務j不會是任務i的后續(xù)任務；式(10)描述了任一岸橋負責的集裝箱任務數與任務組合數之間的數量關系。約束條件(11)至(13)對集卡行駛過程中各種行駛距離的計算方式進行描述：式(11)描述了兩個任務間集卡空駛時間的計算方式；式(12)描述任意一個集裝箱任務運輸時間的計算方式；式(13)表明如果任務i是集卡m的第一個任務，則執(zhí)行任務i前的空駛時間等于集卡從當前位置行駛至第一個任務起始點的時間。約束條件(14)至(16)對集卡各任務階段的時間進行約束：式(14)表明同一集卡的后續(xù)任務的開始時間大于等于當前任務的完成時間加上兩任務間的空駛時間；式(15)表明同一岸橋的后續(xù)任務的開始時間大于等于當前任務的完成時間加上岸橋操作的時間；式(16)表明如果任務i是集卡m的第一個任務，則任務i的開始時間大于等于初始時間加上對應的空駛時間(模型中假設初始時間為0)。約束條件(17)至(18)針對進口集裝箱任務中的集卡行駛時間進行約束：式(17)表明集裝箱任務i開始的時間小于等于岸橋操作開始的時間，集卡無需在岸橋下等待時取等號；式(18)表明岸橋的操作完成后，在經過運輸時間，集卡將集裝箱運至堆場，經場橋卸下集裝箱后，任務完成。式(19)表明集卡到達堆場處的時間，加上場橋裝載集裝箱的時間和集卡運輸時間，小于等于岸橋操作開始時間。式(20)表明岸橋操作完成后，任務完成。式(21)表示變量范圍。

3 算例計算分析

上述所建模型是非線性整數規(guī)劃模型，目前關于這類問題的求解還沒有通用的解法，屬于較為復雜的一類數學問題。本文選擇lingo數學求解軟件對問題進行編程求解。我們選用國內某沿海集裝箱港口的實際數據作為算例數據，用來驗證模型的正確性和有效性。具體數據如下：岸橋對一個集裝箱進行裝卸作業(yè)所需時間為120秒，場橋對一個集裝箱進行裝卸作業(yè)所需時間為90秒，集卡以5米/秒的速度在港區(qū)內勻速行駛。為了驗證所建模型在各種情形下的有效性，我們分別設計了兩個算例，第一個算例中港口可以同時進行裝卸作業(yè)，第二個算例中港口只能分別進行裝卸作業(yè)。

算例1

集裝箱碼頭堆場有4個可供存儲的箱區(qū)，編號為箱區(qū)1至箱區(qū)4和2個可以使用的泊位即泊位1和泊位2。每個停泊有1臺岸橋，分別是岸橋1和岸橋2。有6個集裝箱裝卸任務，包括3個裝船任務和3個卸船任務，需要被2輛集卡運送到目標地點。在模型求解我們生成相關的隨機數據，包括裝卸集裝箱起點和終點的詳細數據、集卡初始地以及各地點間的距離，詳見表1和表2。

表1 集裝箱、集卡初始信息

表2 港口各點間距離

其中，泊位1至泊位2的地點編號為1至2，箱區(qū)1至箱區(qū)4的地點編號為3至6。港口內集卡勻速行駛，速度為5米/秒。表2中的距離是以集卡的行駛時間表示，單位是秒。目標函數中的權重系數a=0.7，b=0.3。將上述數據輸入lingo軟件，并啟動全局求解器對模型進行求解，由于變量太多，我們只將結果中的非0決策變量和與空駛時間有關的非0變量統(tǒng)計到表3中。

表3 算例1的決策變量結果

從表3中可以看出，集卡1執(zhí)行集裝箱3、4、5的運輸任務，集卡2執(zhí)行集裝箱1、2、6的運輸任務。集卡1的集裝箱任務序列為：任務4，任務3，任務5。集卡2的集裝箱任務序列為：任務2，任務6，任務1。岸橋1的集裝箱任務序列為：任務2，任務3，任務1。岸橋2的集裝箱任務序列為：任務4，任務6，任務5?？梢钥闯黾ㄔ谕瓿梢粋€裝船(或卸船)集裝箱任務后會去執(zhí)行另一個卸船(或裝船)集裝箱任務，實現了集卡的“重進重出”。各集裝箱任務的開始時間和結束時間如表4所示。

表4 算例1集裝箱任務時間安排

從表中可以看出最后一個任務完成的時間是1454秒。集卡1執(zhí)行第一個任務前不需要空駛，后續(xù)任務執(zhí)行時空駛時間和總空駛時間為80秒；集卡2需要空駛80秒到達第一個任務的起點，后續(xù)任務執(zhí)行時空駛時間為80秒和總空駛時間為160秒。集卡總的空駛時間為240秒，空駛率為15.1%，目標函數值為1090秒。同時可以注意到集卡執(zhí)行卸船集裝箱任務時，集卡到達岸橋處的時間等于岸橋操作的開始時間，這是因為在算例中的集卡數量和集裝箱任務的數量過少，岸橋無法得到有效利用，存在岸橋等待集卡的情況。

在此算例中若采用“作業(yè)線”模式對集卡進行調度，最佳方案是集卡1負責泊位2中的所有裝船集裝箱任務，集卡2負責泊位1中所有的卸船集裝箱任務。集卡1的集裝箱任務序列為：任務4，任務6，任務5。集卡2的集裝箱任務序列為：任務3，任務1，任務2。每輛集卡執(zhí)行單一的裝船集裝箱任務或卸船集裝箱任務，無法實現集卡的“重進重出”。在“作業(yè)線”模式下，各集裝箱任務的開始時間和結束時間如表5所示。

表5 算例1“作業(yè)線”模式下任務時間安排

可以看出在“作業(yè)線”模式下最后一個集裝箱任務完成的時間為1982秒，集卡1的空駛時間為536秒，集卡1初始位置與集裝箱任務4的起始位置相同，空駛時間為0。集卡1在完成集裝箱任務4后，從岸橋1處前往集裝箱6所在箱區(qū)，空駛時間為292秒。集卡1完成集裝箱任務6后，從岸橋1處前往集裝箱5所在箱區(qū)，空駛時間為244秒。集卡2的空駛時間404秒，集卡2從初始位置前往岸橋1的空駛時間為80秒，集卡2完成集卸船裝箱任務3后，從集裝箱任務3的目的地前往岸橋1處，空駛時間為156秒，集卡2完成卸船集裝箱任務1后，從集裝箱任務1的目的地前往岸橋1處，空駛時間為168秒。統(tǒng)計可以知道集卡總的空駛時間為940秒,集卡空駛率為41%，總的目標函數值為1669秒。

對比兩種調度模式下的集卡空駛時間及最后一個任務的完成時間，如表6所示。采用基于“作業(yè)面”模式下的動態(tài)調度集卡1的空駛時間降低了456秒，集卡2的空駛時間降低了244秒，總的空駛時間降低了700秒，空駛率降低了26%。同時所有任務的完成時間提前了528秒。通過對比可知，所建模型相比傳統(tǒng)的“作業(yè)線”模式下的靜態(tài)調度，無論在是集卡空駛率還是船舶?？繒r間上都有巨大的優(yōu)勢，明顯提高了集卡的工作效率和利用率以及港口整體的運作效率。

表6 算例1兩種模式數據對比

算例2

在算例1中港口可以同時進行裝卸作業(yè)，且裝船集裝箱任務與卸船集裝箱任務的數目相同，在這種情況下基于“作業(yè)面”的動態(tài)集卡調度模式優(yōu)勢發(fā)揮明顯，可以大量減少空駛時間。為了驗證在無法進行裝卸協同作業(yè)條件下模型的有效性，算例2考慮港口無法同時進行裝卸協同作業(yè)。算例2只對集裝箱任務的相關數據做出改變，其他數據和算例1相同，不再重復。集裝箱任務的相關數據如表7所示。

表7 算例2集裝箱初始信息

表8 算例2決策變量結果

將上述數據輸入lingo，并啟動全局求解器進行求解，得到的結果如表8所示。從上表中可以看出，集卡1執(zhí)行集裝箱2、3、5的運輸任務，集卡2執(zhí)行集裝箱1、4、6的運輸任務。集卡1的集裝箱任務序列為：任務5，任務3，任務2。集卡2的集裝箱任務序列為：任務4，任務1，任務6。岸橋1的集裝箱任務序列為：任務1，任務3，任務2。岸橋2的集裝箱任務序列為：任務4，任務5，任務6。各集裝箱任務的開始時間和結束時間如表9所示。

表9 算例2集裝箱任務時間安排

從以上兩表中可以看出最后一個任務完成的時間是1826秒。集卡1需要空駛280秒到達第一個任務的起點，后續(xù)任務執(zhí)行時空駛時間為312秒，總空駛時間為592秒。集卡2執(zhí)行第一個任務前不需要空駛，后續(xù)任務執(zhí)行時空駛時間為438秒，總空駛時間為438秒。集卡總的空駛時間為1030秒，空駛率為43.4%，總的目標函數值為1587.2秒。與案例1相同可以注意到集卡執(zhí)行卸船集裝箱任務時，集卡到達岸橋處的時間等于岸橋操作的開始時間，這是因為在算例中的集卡數量和集裝箱任務的數量過少的原因。

在此算例中若采用“作業(yè)線”模式對集卡進行調度，最佳方案是集卡1負責泊位1中的卸船集裝箱任務，集卡2負責泊位2中卸船集裝箱任務。集卡1的任務序列為任務1，任務3，任務2。集卡2的任務序列為任務4，任務5，任務6。各集裝箱任務的開始時間和結束時間如表10所示。從表10中的數據，可以看出在“作業(yè)線”模式下最后一個集裝箱任務完成的時間為1970秒。同時可計算出集卡1的空駛時間為516秒；集卡2的空駛時間為524秒，總的空駛時間為1040秒，集卡空駛率為43.6%，總的目標函數值1691秒。

表10 “作業(yè)線”模式下集裝的相關時間

表11 算例2兩種模式數據對比

將兩組數據進行比較，如表11所示。當港口不能同時進行裝卸作業(yè)的情況下，“作業(yè)面”模式下和“作業(yè)線”模式下集卡總的空駛率幾乎一樣。但在“作業(yè)面”模式下，所有任務的完成時間比在“作業(yè)面”模式下提前了144秒。從以上兩個算例的分析中可以看出，當港口可以同時進行裝卸作業(yè)時，本文所建的模型相比“作業(yè)線”的調度模式在船舶停靠時間和集卡空駛率上優(yōu)勢明顯。當港口中只進行裝船作業(yè)或卸船作業(yè)時，本文所建的模型可以縮短船舶的停靠時間，提高港口整體的作業(yè)效率，為港口創(chuàng)造更多收益。由此兩個算例證明了所建數學模型的正確性和有效性。

4 總結和展望

本文從集裝箱港口吞吐量逐年增長而面臨的挑戰(zhàn)與機遇出發(fā)，分析了港口提高自身服務能力，需要優(yōu)化港口各環(huán)節(jié)的作業(yè)調度。為提高港口作業(yè)效率和集卡利用率，本文建立了基于“作業(yè)面”模式的集卡調度數學模型，綜合考慮了集卡和岸橋的協同作業(yè)情況，在模型中以最小化船舶?？繒r間和集卡空駛時間作為優(yōu)化目標。為了驗證所建模型的正確有效，根據港口是否可以同時進行裝卸業(yè)務情況分別設計了兩個算例，并用Lingo軟件對所建數學模型進行編程求解。通過對兩個算例的結果進行分析得出，基于“作業(yè)面”的集卡調度模式相比“作業(yè)線”的調度模式在船舶?？繒r間和集卡空駛率上優(yōu)勢明顯，從而提高港口整體的作業(yè)效率，為港口創(chuàng)造更多收益。需要指出的是，本文沒有考慮集卡與場橋的協同作業(yè)情況，在實例驗證過程所采取的算例規(guī)模小，后續(xù)研究中應該在這兩個方面有所改進。