基于最短距離優(yōu)先的集裝箱空箱調(diào)度優(yōu)化算法

田昌彪， 王曉峰

(上海海事大學(xué) 信息工程學(xué)院，上海 201306)

0 引 言

由于集裝箱具有運(yùn)輸量大、便于機(jī)械化操作、能減少物品破損等優(yōu)點(diǎn)，世界海運(yùn)貨物的集裝箱化已成為不可阻擋的發(fā)展趨勢(shì).然而由于國(guó)際貿(mào)易不平衡及集裝箱管理等方面的原因，每天都有大量的集裝箱空箱由箱源充裕地區(qū)運(yùn)往箱源匱乏地區(qū)，隨即產(chǎn)生集裝箱空箱調(diào)運(yùn)問題.

對(duì)經(jīng)濟(jì)危機(jī)下的船公司來講，一個(gè)好的空箱調(diào)度算法不僅能降低成本、提高經(jīng)濟(jì)效益，而且能提高運(yùn)輸設(shè)備的利用率、改善服務(wù)質(zhì)量.同時(shí)，空箱最優(yōu)化問題的本身就是對(duì)資源的最優(yōu)化配置，解決一類問題，就可以解決很大一部分相似資源的最優(yōu)化配置問題.

國(guó)內(nèi)外學(xué)者對(duì)空箱調(diào)度問題進(jìn)行大量研究，取得一系列成果，為實(shí)際運(yùn)營(yíng)過程提供有益的參考.施欣[1-2]對(duì)海上集裝箱空箱調(diào)運(yùn)過程進(jìn)行分析，建立系統(tǒng)優(yōu)化模型；劉恒江[3-4]把航線經(jīng)營(yíng)人作為主體，建立空箱調(diào)運(yùn)的Petri網(wǎng)模型；周紅梅等[5]借鑒鐵路空車調(diào)度優(yōu)化模型，建立海運(yùn)空箱調(diào)運(yùn)優(yōu)化模型；劉建軍等[6]基于廣義費(fèi)用目標(biāo)函數(shù)提出從港口到貨主企業(yè)間不同運(yùn)輸方式的集裝箱組織優(yōu)化模型.武振業(yè)等[7]建立需求不確定的海運(yùn)集裝箱路徑隨機(jī)規(guī)劃模型.國(guó)外研究方面，F(xiàn)LOREZ[8]建立利潤(rùn)優(yōu)化模型研究遠(yuǎn)洋航運(yùn)企業(yè)空箱租賃和重新配置問題；SHEN等[9]構(gòu)建海運(yùn)空箱調(diào)運(yùn)決策支持系統(tǒng)；WHITE等[10]通過構(gòu)造一個(gè)空間-時(shí)間模型描述現(xiàn)實(shí)中的集裝箱空箱調(diào)運(yùn)問題；CHOONG等[11]建立以美國(guó)五大湖區(qū)為實(shí)際調(diào)運(yùn)背景的空箱多式聯(lián)運(yùn)調(diào)運(yùn)整數(shù)規(guī)劃模型，分析規(guī)劃周期長(zhǎng)短對(duì)多式聯(lián)運(yùn)中空箱管理的影響；JULA等[12]建立線性規(guī)劃模型解決洛杉磯/長(zhǎng)灘復(fù)合港的交通擁擠問題，并提出線性規(guī)劃問題的求解方法和優(yōu)化解.然而這些研究在建立模型時(shí)進(jìn)行大量假設(shè)，與實(shí)際系統(tǒng)相差較遠(yuǎn).本文擬在考慮多箱種的情況下，結(jié)合大型船公司的實(shí)際情況，提出新的空箱調(diào)度優(yōu)化算法，并運(yùn)用實(shí)驗(yàn)進(jìn)行驗(yàn)證.

1 建立模型

1.1 模型假定

假定港口運(yùn)輸網(wǎng)絡(luò)中一共有U個(gè)港口，其中m個(gè)港口多余空箱，n個(gè)港口缺少空箱.模型用到的變量：設(shè)X(k,i,j,t)表示時(shí)刻t空箱經(jīng)船k由多箱港口i調(diào)往缺箱港口j的空箱量，其中，k=1,2,…,K，i=1,2,…,U，j=1,2,…,U，t=1,2,…,T；T(k,i,j,t)表示時(shí)刻t空箱經(jīng)船k由多箱港口i調(diào)往缺箱港口j的時(shí)間；D(k,i,j,t)表示時(shí)刻t經(jīng)船k由多箱港口i調(diào)往缺箱港口j的距離；Z(k,i,j,t)表示時(shí)刻t經(jīng)船k從港口i運(yùn)往港口j的重箱量；O(i,t)表示租箱量；Q(i,t)表示空箱存量；Ti(i,t)表示堆場(chǎng)存放時(shí)間；Tr(i,t)表示租箱時(shí)間.

模型用到的參數(shù)：C(k,i,j,t)表示時(shí)刻t經(jīng)船k由多箱港口i調(diào)往缺箱港口j的單位空箱單位距離運(yùn)輸成本；Y(k,i)表示船k運(yùn)輸能力限制；Ch(i,t)表示單位空箱裝卸成本；Cr(i,t)表示單位空箱單位時(shí)間的租箱費(fèi)率；Ci(i,t)表示單位空箱單位時(shí)間的存箱成本；T表示整個(gè)空箱調(diào)度的周期，為常數(shù)；K表示船舶數(shù)量；N表示箱型數(shù)量.

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

空箱調(diào)度成本一般包括牽引成本、維修成本、管理成本、托運(yùn)成本、空箱裝卸成本、運(yùn)輸成本、堆場(chǎng)成本、租箱成本等.為簡(jiǎn)化模型，只考慮空箱裝卸成本、運(yùn)輸成本、堆場(chǎng)成本、租箱成本.

空箱裝卸成本=調(diào)箱量×單位空箱裝卸成本=

(1)

運(yùn)輸成本=調(diào)箱量×經(jīng)過的距離×單位空箱單位距離運(yùn)輸成本=

(2)

堆場(chǎng)成本=空箱存量×單位空箱單位時(shí)間的堆場(chǎng)成本×堆場(chǎng)存放時(shí)間=

(3)

(4)

因此，航線成本最小化的目標(biāo)函數(shù)為

(5)

判定某一確定缺箱港口與某一確定多箱港口之間選擇空箱調(diào)度的方法：?jiǎn)挝豢障溲b卸成本+單位空箱調(diào)運(yùn)成本+單位空箱堆場(chǎng)成本<單位租箱成本，則調(diào)箱，即

Ch(i,t)+D(k,i,j,t)·C(k,i,j,t)+

Ci(i,t)·Ti(i,t)

約束函數(shù)為

X(k,i,j,t)+Z(k,i,j,t)≤Y(k,i)[13]

(6)

T(k,i,j,t)+Ti(i,t)≤T

(7)

(8)

式(6)表示空箱量和重箱量應(yīng)小于船舶的最大裝載量；式(7)表示空箱調(diào)運(yùn)時(shí)間和占用堆場(chǎng)時(shí)間之和在調(diào)度期限之內(nèi)；式(8)表示空箱調(diào)運(yùn)量小于空箱的總存量.

2 調(diào)度算法

國(guó)內(nèi)大型船公司的箱管部門一般按照人工經(jīng)驗(yàn)[14]調(diào)度空箱，目前以最短距離優(yōu)先調(diào)度為主，即把多余的空箱運(yùn)輸?shù)骄嚯x最近的缺箱港口，從而實(shí)現(xiàn)時(shí)間最少、距離最短，達(dá)到節(jié)約成本的目的.

2.1 最短距離優(yōu)先調(diào)度

距離是指兩物體在空間或時(shí)間上相隔的長(zhǎng)度.最短距離優(yōu)先是指在空箱調(diào)度過程中總是優(yōu)先調(diào)度距離缺箱港口最近的多箱港口的空箱.距離最近的兩個(gè)港口之間實(shí)現(xiàn)空箱最優(yōu)調(diào)度，不僅能減少運(yùn)輸成本和運(yùn)輸時(shí)間，還能有效提高運(yùn)營(yíng)效率.

將任意兩港口之間的實(shí)際距離表示成矩陣，調(diào)度時(shí)只需在距離最近的兩個(gè)港口之間進(jìn)行按需分配即可實(shí)現(xiàn)最短距離優(yōu)先調(diào)度.為敘述方便，給出32個(gè)港口的分布，見圖1.

圖1港口分布網(wǎng)絡(luò)

為實(shí)現(xiàn)空箱調(diào)度成本的最低化，需要已知各港口之間的距離和各個(gè)港口對(duì)應(yīng)空箱箱型的數(shù)量.

式中:dij表示港口i與港口j之間的距離，1≤i,j≤v.

式中:aij表示港口i，箱型為j的集裝箱空箱數(shù)量(1≤i≤v,1≤j≤N),正負(fù)分別表示可供應(yīng)或需求的空箱數(shù)目，0表示不缺少也不多余，但并不代表該港口一個(gè)空箱都沒有，只表示該港口空箱只能滿足自身的需要而且不能提供多余的空箱.假設(shè)f表示空箱最短距離優(yōu)先調(diào)運(yùn)函數(shù)，其中有2個(gè)參數(shù)D和A.{aij|i=1,2,…,v}表示各港口某一箱型j的空箱數(shù)量，數(shù)組S存儲(chǔ)多箱港口的編號(hào)，數(shù)組E存儲(chǔ)缺箱港口的編號(hào),s表示多箱港口編號(hào)，e表示缺箱港口編號(hào)，算法步驟如下：

步驟1將箱型為1的各港口的空箱數(shù)量存入{ai1}數(shù)組.

步驟2將{ai1}中大于0的港口編號(hào)存入數(shù)組S，小于0的港口編號(hào)存入數(shù)組E.

步驟3找出{dij|i∈S,j∈E}的最小值，并把多箱港口編號(hào)賦值給s，缺箱港口編號(hào)賦值給e.

步驟4判斷as1和ae1絕對(duì)值的大小，修改{ai1}，打印出s，e，該箱型空箱的數(shù)目.

步驟5判斷數(shù)組S或E是否為空.若否，則執(zhí)行步驟2；若是，跳出循環(huán)，執(zhí)行步驟6.

步驟6將箱型加1，執(zhí)行循環(huán)，直至N.

2.2 窮舉路徑

空間距離最短的兩個(gè)港口之間往往有很多條路徑，要求得成本最低的路徑，需要窮舉路徑，從中擇優(yōu).實(shí)際最短距離路徑有時(shí)未必是最優(yōu)路徑，成本最低的路徑才是最優(yōu)路徑，因此需要窮舉路徑以決定空箱調(diào)度方案.若圖1中的2號(hào)港口多余很多空箱，4號(hào)缺少很多空箱，而且也滿足最短距離的條件，但如果2號(hào)港口常年出口貨物到4號(hào)港口，這時(shí)2號(hào)港口的空箱通過L001航線運(yùn)輸?shù)?號(hào)港口就會(huì)大大增加成本，而一般的解決辦法就是窮舉路徑.2號(hào)港口到4號(hào)港口的直達(dá)線路L001成本高，就可以取2號(hào)港口運(yùn)輸?shù)?2號(hào)港口、12號(hào)港口運(yùn)輸?shù)?號(hào)港口的路徑，或是其他的窮舉出來的成本更低的路徑.

盡管空箱調(diào)度一般需要幾次中轉(zhuǎn)才能到達(dá)目的港口，但也是有限制的.隨著中轉(zhuǎn)港口增多，中轉(zhuǎn)過程的裝卸費(fèi)用、運(yùn)輸成本會(huì)大大增加.一般中轉(zhuǎn)次數(shù)不超過一個(gè)固定的常數(shù).此處只給出中轉(zhuǎn)3次以內(nèi)的窮舉路徑算法.設(shè)F表示窮舉路徑函數(shù)，其中有3個(gè)參數(shù)：多箱港口編號(hào)s，缺箱港口編號(hào)e，航線L；m1表示中轉(zhuǎn)港口編號(hào)，m2表示另一中轉(zhuǎn)港口編號(hào).具體算法如下.

步驟1判斷港口s和e是否在同一航線上.是則執(zhí)行步驟2，否則執(zhí)行步驟3.

步驟2查航線表L，將港口s與e之間的時(shí)間和距離累加.根據(jù)距離計(jì)算運(yùn)輸費(fèi)用，裝卸費(fèi)用按1次計(jì)算，堆場(chǎng)費(fèi)用為0，租箱費(fèi)用已知，生成結(jié)果集.

步驟3在港口s所在的航線上找中轉(zhuǎn)港口m1及m1所在的航線，判斷m1與e是否在同一航線上.是則執(zhí)行步驟4，否則執(zhí)行步驟5.

步驟4分別查航線表，將港口s與m1，m1與e之間的時(shí)間和距離累加.根據(jù)距離計(jì)算運(yùn)輸費(fèi)用，裝卸費(fèi)用按2次計(jì)算，按航期表計(jì)算堆場(chǎng)時(shí)間，得出堆場(chǎng)費(fèi)用，租箱費(fèi)用已知，生成結(jié)果集.

步驟5在m1所在的航線上再找一中轉(zhuǎn)港口m2及m2所在的航線，判斷m2與e是否在同一航線上,是則執(zhí)行步驟6，否則放棄.

步驟6分別查航線表，將s與m1，m1與m2，m2與e之間的時(shí)間和距離累加.根據(jù)距離計(jì)算運(yùn)輸費(fèi)用，裝卸費(fèi)用按3次計(jì)算，按航期表計(jì)算堆場(chǎng)時(shí)間，得出堆場(chǎng)費(fèi)用，租箱費(fèi)用已知，生成結(jié)果集.

步驟7將結(jié)果集按成本進(jìn)行排序并輸出.

2.3 堆場(chǎng)時(shí)間計(jì)算和配船方案

對(duì)于某一固定的班輪，基本上有固定的掛靠時(shí)刻和掛靠港口，用一個(gè)固定的航期表表示.船期表中所列項(xiàng)目包括港口編號(hào)、上一港口到下一港口的時(shí)間和距離.

假定A和B是同一時(shí)刻某航線上兩端的港口，i和j表示需要進(jìn)行空箱調(diào)度的兩個(gè)港口，i表示起始港口，j表示終點(diǎn)港口，若A→B,B→A方向上各有一班輪，設(shè)初始時(shí)刻為0，班輪周期為T1.用tij表示i到j(luò)所用的時(shí)間.

(1)如果i和j都在AB航線上，則：A→B方向，船舶到i的所有時(shí)刻ti=tAi+K1T1，K1=0,1,2，…；B→A方向，船舶到i的所有時(shí)刻ti=tBi+K1T1，K1=0,1,2，….查船期表，將時(shí)間字段和距離字段相加可得i到j(luò)所需要的總時(shí)間tij和總距離，由于不經(jīng)過中轉(zhuǎn)，堆場(chǎng)時(shí)間為0，把完整的裝一次、卸一次看作裝卸一次，用成本分析就可算得裝卸成本、運(yùn)輸成本、堆場(chǎng)成本.配船方案為AB航線的(K1+1)航次.

(2)如果i和j不在同一航線上，并且兩航線有共同港口M，i在AB航線上，j在CD航線上，且初始時(shí)刻都為0，AB航線的周期為T1，CD航線的周期為T2，則：A→B方向，船舶到i的所有時(shí)刻ti=tAi+K1T1，K1=0,1,2，…；C→D方向，船舶到j(luò)的所有時(shí)刻tj=tCj+K2T2，K2=0,1,2，…；由i到j(luò)所需要的時(shí)間t=tj-ti=tCj-tAi+K2T2-K1T1.船舶運(yùn)輸時(shí)間tiM+tMj.堆場(chǎng)堆放時(shí)間tAM+K2T2-tCM-K1T1(≥0).配船方案為AB航線的(K1+1)航次，和CD航線的(K2+1)航次.

3 實(shí) 驗(yàn)

表1 各航線的船期表

3.1 實(shí)驗(yàn)步驟

假定一個(gè)有32個(gè)港口、7條航線的港口運(yùn)輸網(wǎng)絡(luò)，見圖1.對(duì)某一特定類型的空箱，1號(hào)港口缺少100個(gè)，2號(hào)港口多余400個(gè)，3號(hào)港口缺少100個(gè)，4號(hào)港口多余50個(gè)，7號(hào)港口缺少100個(gè)，12號(hào)港口缺少80個(gè)，25號(hào)港口缺少70個(gè)，其他港口空箱數(shù)目為0.其中部分航線的船期見表1.

為簡(jiǎn)述方便，中轉(zhuǎn)費(fèi)用常數(shù)假定為4，單位距離運(yùn)輸費(fèi)用為5，單位空箱單位時(shí)間堆場(chǎng)費(fèi)用為1，租箱費(fèi)用為65.

3.2 實(shí)驗(yàn)結(jié)果

表2 最短距離優(yōu)先調(diào)度結(jié)果

第一步給出以最短距離優(yōu)先的某一箱型的調(diào)度結(jié)果，包括起始港口和目的港口及需運(yùn)輸?shù)目障鋽?shù)量，見表2.

確定起始港口為2號(hào)港口、目的港口為7號(hào)港口后，計(jì)算出排序后2號(hào)港口到7號(hào)港口的窮舉3次中轉(zhuǎn)限制內(nèi)的路徑結(jié)果集合，見表3.

3.3 結(jié)果分析

當(dāng)單位租箱成本小于單位空箱調(diào)度成本時(shí)，選擇租箱，否則選擇空箱調(diào)度.如，表5中第1條路徑空箱調(diào)度比較劃算，而其他7條選擇租箱比較劃算.

與以人工經(jīng)驗(yàn)調(diào)度為主的空箱調(diào)度比較，該算法按距離遠(yuǎn)近給出調(diào)度先后順序，能有效給出空箱調(diào)度優(yōu)化路徑，并按成本大小排序，同時(shí)對(duì)是否租箱給出輔助決策.

結(jié)果不僅可以按照成本排序，還可以按照時(shí)間進(jìn)行排序，得出空箱調(diào)運(yùn)最短時(shí)間調(diào)運(yùn)方案.

由于空箱調(diào)運(yùn)系統(tǒng)復(fù)雜，根據(jù)單一的排序后的成本或時(shí)間空箱調(diào)運(yùn)方案，并不能得出最優(yōu)方案，二者不可兼得，最終還需要箱管部門結(jié)合其他因素制訂空箱調(diào)度計(jì)劃.

4 總結(jié)和展望

該空箱調(diào)度算法不僅能有效給出空箱調(diào)度最優(yōu)路徑，而且對(duì)是否租箱給出輔助決策，使空箱調(diào)度變得有章可循.與實(shí)際人工經(jīng)驗(yàn)調(diào)度比較，該算法能簡(jiǎn)化調(diào)度過程、提高調(diào)度效率.

該算法適用于航線較多的情況，但對(duì)實(shí)際中特定的情況并不適用.比如，對(duì)于同樣是出口為主的港口上海港和寧波港，基本上沒有空箱調(diào)運(yùn)，該方法失效.為更好地應(yīng)用，還需要進(jìn)一步改進(jìn)算法.

表3 窮舉3次中轉(zhuǎn)限制內(nèi)的路徑結(jié)果

參考文獻(xiàn)：

[1] 施欣. 集裝箱海運(yùn)空箱調(diào)運(yùn)優(yōu)化分析[J]. 系統(tǒng)工程理論與實(shí)踐, 2003, 4(4): 70-76.

[2] 施欣. 基于Petri網(wǎng)的航運(yùn)業(yè)務(wù)流程的仿真優(yōu)化[J]. 系統(tǒng)仿真學(xué)報(bào), 2001, 11(6): 767-780.

[3] 劉恒江. 集裝箱空箱調(diào)運(yùn)分析[J]. 集裝箱化, 2001, 12(10): 11-13

[4] 劉恒江. 集裝箱空箱調(diào)運(yùn)Petri網(wǎng)模型仿真分析[D]. 上海: 上海海運(yùn)學(xué)院, 2002.

[5] 周紅梅, 方芳. 航運(yùn)集裝箱空箱調(diào)運(yùn)優(yōu)化模型的研究[J]. 武漢理工大學(xué)學(xué)報(bào): 交通科學(xué)與工程版, 2003(3): 384-387.

[6] 劉建軍, 楊浩. 港口樞紐集裝箱運(yùn)輸?shù)慕M織優(yōu)化研究[J]. 土木工程學(xué)報(bào), 2004, 37(10): 99-103.

[7] 武振業(yè), 宋天生, 趙柯. 海運(yùn)集裝箱運(yùn)輸路徑選擇[J]. 西南交通大學(xué)學(xué)報(bào), 2006, 41(3): 269-272.

[8] FLOREZ H. Empty container repositioning and leasing:an optimization model[D]. New York: Polytechnic Institute of New York, 1986.

[9] SHEN W S, KHONG C M. A DSS for empty container distribution planning[J]. Decision Support System, 1955, 15(1): 75-82.

[10] WHITE W W，BOMBERAWLT A M. A network algorithm for empty freight car allocation[J]. IBM System J, 1969, 15(2): 147-169.

[11] CHOONG S T, COLE M H, KUTANOGLU E. Empty container management for intermodal transportation networks[J]. Transportation Res Part E: Logistics & Transportation Rev, 2002, 38(6): 423-438.

[12] JULA H, CHASSIAKOS A, IOANNOU P. Port dynamic empty container reuse[J]. Transportation Res Part E: Logistics & Transportation Rev, 2006, 42(1): 43-60.

[13] 劉大镕, 賀斌, 蔣良奎, 等. 隨機(jī)(單箱種)陸上空箱調(diào)運(yùn)模型[J]. 上海海運(yùn)學(xué)院學(xué)報(bào), 2000, 21(3): 8-18.

[14] 楊洋. 班輪公司空箱合作調(diào)運(yùn)優(yōu)化模型[J]. 上海海事大學(xué)學(xué)報(bào), 2010, 31(3): 68-73.