基于閘口資源配置的送箱集卡預(yù)約優(yōu)化模型*

于 蒙 周 密

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

0 引 言

隨著國(guó)際貿(mào)易的快速發(fā)展，集裝箱進(jìn)出口量越來(lái)越大，集卡作為運(yùn)輸集裝箱的主要工具，其需求量也快速增加，這將出現(xiàn)高峰時(shí)期港口運(yùn)輸集裝箱的集卡同時(shí)抵達(dá)碼頭，造成港口各個(gè)節(jié)點(diǎn)擁堵.由于碼頭是一個(gè)集成作業(yè)系統(tǒng)，一個(gè)環(huán)節(jié)的作業(yè)效率將影響整個(gè)碼頭的作業(yè)效率，所以，港口擁堵將降低整個(gè)碼頭的作業(yè)效率.

為緩解集卡在港口的擁堵，國(guó)內(nèi)外很多港口，如洛杉磯港、溫哥華港，以及上海洋山港等先后實(shí)行了集卡預(yù)約系統(tǒng).國(guó)內(nèi)外學(xué)者也做了很多研究，Chen等[1]通過(guò)為每支到港船舶制定時(shí)間窗來(lái)管理集卡的到達(dá)，從而緩解集裝箱碼頭閘口的擁堵.Zhang等[2]利用休假式排隊(duì)模型描述場(chǎng)橋協(xié)同服務(wù)內(nèi)外集卡的過(guò)程，基于非平穩(wěn)的排隊(duì)理論更準(zhǔn)確的估計(jì)了外集卡在閘口和堆場(chǎng)的平均等待時(shí)間.Yi等[3]提出了一種預(yù)約調(diào)度方法，該方法考慮了停留在碼頭內(nèi)的集卡成本、滯期費(fèi)、集裝箱運(yùn)輸成本，每個(gè)時(shí)間窗和每個(gè)區(qū)塊允許的約會(huì)次數(shù)以及每個(gè)時(shí)間窗內(nèi)可用集卡的數(shù)量.與以前的研究不同，該研究在構(gòu)建預(yù)約時(shí)間表時(shí)考慮預(yù)約對(duì)終端等待時(shí)間的影響.利用基于Frank-Wolfe算法的數(shù)學(xué)公式和啟發(fā)式算法，以在合理的計(jì)算時(shí)間內(nèi)解決該問(wèn)題；滕藤等[4]為緩解碼頭的擁堵問(wèn)題，利用基于支持向量機(jī)和卡爾曼濾波的方法預(yù)測(cè)集卡到達(dá)的時(shí)間，提高集卡到達(dá)時(shí)間的準(zhǔn)確性；曾慶成等[5]在預(yù)約模型中考慮了內(nèi)部集卡對(duì)堆場(chǎng)作業(yè)的影響，提出了基于內(nèi)外集卡協(xié)同服務(wù)的優(yōu)化模型，利用休假式排隊(duì)系統(tǒng)，結(jié)合遺傳算法優(yōu)化集卡在碼頭的等待成本；楊惠云等[6]根據(jù)不同預(yù)約時(shí)段集卡到達(dá)類(lèi)型的不同來(lái)改變閘口的數(shù)量，結(jié)果表明，可變閘口調(diào)度的集卡預(yù)約優(yōu)化減少了集卡的排隊(duì)時(shí)間.

綜上所述，目前碼頭集卡預(yù)約排隊(duì)模型大多考慮集卡到達(dá)、服務(wù)分布等規(guī)律，而未考慮碼頭資源的優(yōu)化配置.閘口通道數(shù)和堆場(chǎng)的容量有限也是造成碼頭擁堵的原因，以送箱集卡為研究對(duì)象，當(dāng)閘口通道數(shù)目有限時(shí)，可根據(jù)不同預(yù)約時(shí)段集卡的集港數(shù)量來(lái)安排閘口數(shù)[7-8].因此，在考慮碼頭現(xiàn)有設(shè)施條件下，優(yōu)化其閘口的資源配置，建立集卡到港預(yù)約排隊(duì)模型，并結(jié)合自適應(yīng)遺傳算法優(yōu)化集卡預(yù)約額，從而使集卡在閘口和堆場(chǎng)的平均等待時(shí)間最小.

1 集卡預(yù)約優(yōu)化模型的構(gòu)建

1.1 問(wèn)題描述

集卡進(jìn)入碼頭后，先后經(jīng)過(guò)閘口和堆場(chǎng)完成運(yùn)輸任務(wù)，然后從出場(chǎng)閘口離開(kāi).在碼頭實(shí)際中，港口集裝箱的進(jìn)出口業(yè)務(wù)繁多，集卡到港時(shí)間的隨機(jī)性是碼頭擁堵的重要原因，集卡預(yù)約可控制集卡的集港量，使集卡到港時(shí)間相對(duì)確定.閘口通道數(shù)有限也會(huì)造成集卡大量排隊(duì)，閘口送提箱通道的業(yè)務(wù)不同，所需的服務(wù)時(shí)間也不同，當(dāng)送箱通道服務(wù)有過(guò)大壓力時(shí)，在不影響提箱集卡作業(yè)的前提下，可開(kāi)放一定數(shù)量的提箱通道協(xié)助送箱集卡完成進(jìn)閘業(yè)務(wù).集卡進(jìn)入堆場(chǎng)后，需要在堆場(chǎng)排隊(duì)，若堆場(chǎng)排隊(duì)隊(duì)長(zhǎng)過(guò)長(zhǎng)，堆場(chǎng)容量有限，反過(guò)來(lái)又會(huì)導(dǎo)致集卡在閘口的排隊(duì)[9].

為解決上述問(wèn)題，在集卡預(yù)約模式下，考慮閘口資源和堆場(chǎng)容量對(duì)集卡排隊(duì)的影響建立預(yù)約模型.在閘口處，可視為M/M/C(t)的排隊(duì)模型，每個(gè)堆場(chǎng)分區(qū)滿足M/G/1/R的排隊(duì)模型，以集卡在閘口和堆場(chǎng)平均等待時(shí)間最小為優(yōu)化目標(biāo)，優(yōu)化各時(shí)段的預(yù)約份額，建立如下模型.

1.2 預(yù)約模型的建立

1.2.1參數(shù)定義

1.2.2預(yù)約模型的構(gòu)建

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

(1)

約束條件:

(2)

(3)

m=T/p

(4)

閘口處：

(5)

(6)

(7)

(8)

(9)

(10)

(11)

堆場(chǎng)處：

(12)

(13)

(14)

(15)

(16)

(17)

(18)

式(1)為集卡在閘口和堆場(chǎng)平均等待時(shí)間最??；式(2)為集卡總數(shù)等于決策期內(nèi)預(yù)約份額之和；式(3)為在預(yù)約時(shí)段內(nèi)集卡未到和遲到后實(shí)際到達(dá)的數(shù)量；式(4)為將預(yù)約時(shí)段p劃分為t的數(shù)量；式(5)為t時(shí)刻集卡到達(dá)閘口的量；式(6)為t時(shí)刻在閘口g的集卡到達(dá)量；式(7)為t時(shí)刻第g個(gè)閘口利用率與隊(duì)長(zhǎng)的關(guān)系；式(8)為在閘口g處集卡排隊(duì)和不需要排隊(duì)的隊(duì)長(zhǎng)；式(9)為t時(shí)刻第g個(gè)閘口集卡的離開(kāi)量；式(10)為集卡P時(shí)段在閘口的平均等待時(shí)間；式(11)為閘口處集卡在決策期的平均等待時(shí)間；式(12)為t時(shí)刻集卡到達(dá)堆場(chǎng)的量；式(13)為t時(shí)刻堆場(chǎng)隊(duì)長(zhǎng)與利用率的關(guān)系；式(14)為堆場(chǎng)y處集卡排隊(duì)和不需要排隊(duì)的隊(duì)長(zhǎng)；式(15)為集卡在任意時(shí)刻不超過(guò)其容量限制；式(16)為t時(shí)刻集卡離開(kāi)堆場(chǎng)的量；式(17)為集卡P時(shí)段在堆場(chǎng)的平均等待時(shí)間；式(18)為堆場(chǎng)處集卡在決策期的平均等待時(shí)間.

2 算法設(shè)計(jì)

由于傳統(tǒng)遺傳算法在進(jìn)化過(guò)程中最優(yōu)解易丟失，容易陷入局部最優(yōu)解，所以，本文采用適應(yīng)度值排序的自適應(yīng)遺傳算法，使算法不易陷入局部最優(yōu)，具體算法步驟如下.

步驟1編碼及種群初始化 染色體采用實(shí)數(shù)編碼的方式進(jìn)行編碼，一條染色體的長(zhǎng)度為決策期內(nèi)預(yù)約時(shí)段數(shù)，其基因值表示集卡預(yù)約數(shù)，首先隨機(jī)生成一組正整數(shù)，使其和等于在決策期內(nèi)集卡的預(yù)約總數(shù)，圖1為一條染色體，初始種群數(shù)為200.

圖1 染色體示意圖

步驟2

碧洲計(jì)算適應(yīng)度 根據(jù)模型約束式(2)～式(18)，計(jì)算每個(gè)個(gè)體的排隊(duì)等待時(shí)間

F

，其適應(yīng)度值

f

可見(jiàn)式(19)，計(jì)算每條染色體的適應(yīng)度值，并求出種群適應(yīng)度的平均值與個(gè)體適應(yīng)度值排序.

f=1/F

(19)

步驟3選擇與交叉 本文采用輪盤(pán)賭進(jìn)行選擇，隨機(jī)從父代中選擇兩個(gè)個(gè)體交叉，由于本文采用的實(shí)數(shù)編碼，所以采用融合交叉的方式對(duì)父代染色體進(jìn)行交叉，見(jiàn)式(20)，其中α為參數(shù)，0<α<1.

(20)

將選中的兩個(gè)個(gè)體適應(yīng)度值較大的排序號(hào)代入到計(jì)算交叉概率pc的式(21)中,用適應(yīng)度值的排序號(hào)替代適應(yīng)度值能適當(dāng)增加迭代后期的交叉概率，從而使算法不易陷入局部最優(yōu).

式中：N1為選中的兩個(gè)染色體中適應(yīng)度值較大的序號(hào)；N2為種群平均適應(yīng)度值的序號(hào)；N3為種群最大適應(yīng)度值的序號(hào)；Pc1為最大交叉概率；Pc2為最小交叉概率.

步驟4變異 變異采用實(shí)值變異的方式，為確保變異后解的可行性且便以操作，隨機(jī)選中染色體的兩點(diǎn)，保證兩點(diǎn)的差值為(0,3],互換兩點(diǎn)的數(shù)值即可實(shí)現(xiàn)變異操作，變異過(guò)程見(jiàn)圖2.

圖2 染色體變異示意圖

變異概率pm按式(22)進(jìn)行自適應(yīng)調(diào)整，其中，Pm1為最大變異概率，Pm2為最小變異概率.

(22)

步驟5算法終止 當(dāng)進(jìn)化次數(shù)達(dá)到最大進(jìn)化次數(shù)后，算法終止，得出集卡預(yù)約等待時(shí)間最小的預(yù)約方案作為最優(yōu)解，否則算法返回第二步.

3 實(shí)例分析

3.1 算例設(shè)計(jì)

以某集裝箱碼頭為例進(jìn)行分析，將決策期N定為7 d，并將其分為84個(gè)預(yù)約時(shí)段，所以每個(gè)預(yù)約時(shí)段長(zhǎng)度為2 h.該碼頭有八個(gè)進(jìn)場(chǎng)閘口，每個(gè)閘口的服務(wù)能力為40輛/h，場(chǎng)橋服務(wù)能力為20輛/h，決策期內(nèi)集卡預(yù)約到港量為5 000輛 ，堆場(chǎng)最大容量為10.

該碼頭閘口有四個(gè)送箱通道，四個(gè)提箱通道，在不影響提箱集卡作業(yè)的前提條件下，本文只考慮送箱集卡的預(yù)約優(yōu)化問(wèn)題.當(dāng)預(yù)約兩小時(shí)內(nèi)集卡的到港數(shù)小于40輛時(shí)，滿足閘口和堆場(chǎng)的服務(wù)能力，此時(shí)開(kāi)放1個(gè)送箱通道；當(dāng)預(yù)約兩小時(shí)內(nèi)集卡的到港數(shù)在161～200輛時(shí)，此時(shí)需要開(kāi)放4個(gè)送箱通道和1個(gè)提箱通道.由于每個(gè)預(yù)約時(shí)段的集卡到達(dá)量在變化，所以各預(yù)約時(shí)段集卡所需的閘口通道數(shù)見(jiàn)表1,這樣不僅可提高閘口的利用率，也能節(jié)約碼頭資源.

表1 不同時(shí)段集卡預(yù)約到港量對(duì)應(yīng)的閘口通道數(shù)目

3.2 模型驗(yàn)證

通過(guò)以上數(shù)據(jù)，運(yùn)用matlab對(duì)預(yù)約模型進(jìn)行編程，見(jiàn)圖3，得出集卡在碼頭的平均等待時(shí)間為14.13 min,根據(jù)對(duì)碼頭的調(diào)研，集卡的實(shí)際平均周轉(zhuǎn)時(shí)間大約為22 min，驗(yàn)證了建立模型的可行性.

圖3 算法收斂圖

3.3 預(yù)約優(yōu)化模型驗(yàn)證

圖4為有無(wú)預(yù)約情況下等待時(shí)間和集卡到達(dá)量的對(duì)比，發(fā)現(xiàn)未實(shí)施預(yù)約前，集卡在某些時(shí)段大量集港，存在擁堵現(xiàn)象，而某些時(shí)段集港數(shù)極低，造成碼頭資源的浪費(fèi)；實(shí)施預(yù)約后，集卡在每個(gè)預(yù)約時(shí)段的集港數(shù)量控制在50～80輛，將高峰時(shí)段的集卡數(shù)分散到集港低谷期，有效的減少了碼頭擁堵現(xiàn)象.

圖4 集卡到港規(guī)律對(duì)比

預(yù)約實(shí)施前后集卡在碼頭的平均等待時(shí)間變化見(jiàn)表2，變化趨勢(shì)見(jiàn)圖5.結(jié)果表明，未實(shí)施預(yù)約前，在閘口處集卡的平均等待時(shí)間為4.89 min，最高等待時(shí)間為13.86 min，預(yù)約后平均等待時(shí)間降為3.97 min，減少約1 min，相比未預(yù)約之前，集卡集港較均勻，所以預(yù)約集港能明顯降低集卡的排隊(duì)時(shí)間.

表2 集卡在碼頭的等待時(shí)間 min

圖5 集卡在碼頭的排隊(duì)等待時(shí)間

未實(shí)施預(yù)約前，在堆場(chǎng)處集卡的平均等待時(shí)間為15.73 min，最高等待時(shí)間約為38 min，預(yù)約后集卡的平均等待時(shí)間降為10.16 min，減少了5.57 min，預(yù)約后最高等待時(shí)間降為20 min.

4 結(jié) 束 語(yǔ)

為解決集卡在集裝箱碼頭的堵塞問(wèn)題，在閘口處，通過(guò)設(shè)置可變閘口的方式來(lái)配置閘口通道資源，在堆場(chǎng)處，考慮場(chǎng)橋的服務(wù)能力來(lái)限制堆場(chǎng)容量，從而提高整個(gè)碼頭的通行能力.本文考慮閘口和堆場(chǎng)的條件約束構(gòu)建了集卡預(yù)約優(yōu)化模型，通過(guò)優(yōu)化各時(shí)段的集卡預(yù)約到港數(shù)目來(lái)減少集卡的平均等待時(shí)間.為求解預(yù)約優(yōu)化模型，設(shè)計(jì)了采用適應(yīng)度值排序的自適應(yīng)的遺傳算法來(lái)求解模型.結(jié)果表明，考慮閘口和堆場(chǎng)資源限制的預(yù)約模型能有效的減少集卡在閘口和堆場(chǎng)的排隊(duì)時(shí)間.