考慮早晚高峰期影響的集卡預(yù)約系統(tǒng)多約束調(diào)度模型與算法

許波桅，劉小艷+，楊勇生，李軍軍

(1.上海海事大學(xué) 物流科學(xué)與工程研究院，上海 201306； 2.上海海事大學(xué) 商船學(xué)院，上海 201306)

0 引言

集裝箱港口在全球運(yùn)輸系統(tǒng)中發(fā)揮的作用日益凸顯，持續(xù)增長(zhǎng)的港口吞吐量導(dǎo)致了陸側(cè)集疏運(yùn)交通量的大幅增加，而早晚高峰期擁堵會(huì)進(jìn)一步增加集卡運(yùn)輸時(shí)間的不確定性，這是港口管理者面臨的重大難題。海德俊等[1]從城市交通、土地資源、環(huán)境污染等方面論述了上海特大型港口城市的港城矛盾，指出城市交通的擁堵影響集卡的運(yùn)輸效率，且同時(shí)段的集卡高峰也會(huì)使得城市交通擁堵更加嚴(yán)重;彭建[2]研究發(fā)現(xiàn)，以公路為主導(dǎo)的港口貨運(yùn)交通疏港體系在難以大幅擴(kuò)容的背景下，出現(xiàn)了嚴(yán)重的港城客貨沖突、環(huán)境污染等問題。因此，考慮城市交通對(duì)集疏運(yùn)的影響非常有必要。為提高集裝箱港口的作業(yè)效率、緩解集卡擁堵問題，國(guó)內(nèi)外一些港口，如美國(guó)洛杉磯港與長(zhǎng)灘港、加拿大溫哥華港以及我國(guó)天津港等相繼實(shí)施了集卡預(yù)約系統(tǒng)(Truck Appointment System，TAS)。

集卡預(yù)約系統(tǒng)是一種較為先進(jìn)的解決港口擁堵的方法，主要用于與港口作業(yè)相關(guān)的外集卡作業(yè)[3]。集卡公司根據(jù)預(yù)先安排的集卡的工作時(shí)間，為每輛集卡預(yù)約時(shí)間窗[4]，港務(wù)公司依據(jù)每個(gè)時(shí)間窗的配額預(yù)先確定堆場(chǎng)設(shè)備的分配[5]。目前已有許多學(xué)者對(duì)集卡預(yù)約系統(tǒng)進(jìn)行了研究。最早的是Giuliano等[6]研究了長(zhǎng)灘和洛杉磯港口實(shí)施TAS的潛在影響，研究發(fā)現(xiàn)并不是所有預(yù)期收益都來自集卡公司。為進(jìn)一步研究影響集卡預(yù)約系統(tǒng)實(shí)施效果的潛在因素，Huynh等[7]研究了規(guī)定集卡到達(dá)時(shí)間對(duì)堆場(chǎng)起重機(jī)使用和集卡周轉(zhuǎn)時(shí)間的影響，通過對(duì)數(shù)學(xué)公式和仿真的結(jié)合，提出一種可以確定港口每個(gè)時(shí)間窗能接受的最大集卡數(shù)量的方法;而且，Huynh等[8]通過為每輛集卡分配不同的預(yù)約時(shí)間窗改進(jìn)了集卡預(yù)約系統(tǒng)。

諸多學(xué)者為了將集卡預(yù)約系統(tǒng)與港口內(nèi)部作業(yè)有效結(jié)合，通過數(shù)學(xué)模型對(duì)每個(gè)時(shí)間窗集卡預(yù)約數(shù)量進(jìn)行有效決策，從而緩解了集卡在閘口的擁堵。Zehendner等[9]提出一個(gè)混合整數(shù)線性規(guī)劃模型，根據(jù)總體工作量和可處理能力，為不同運(yùn)輸模式分配相應(yīng)的集卡預(yù)約數(shù)量。Phan等[4]研究了集卡改變到達(dá)時(shí)間帶來的影響，建立了數(shù)學(xué)公式和分散決策結(jié)合的模型，支持集卡公司和港務(wù)公司之間的協(xié)商，使得集卡能夠更均勻地到達(dá)港口;Chen等[10]提出一種“船舶相關(guān)時(shí)間窗”的方法來控制集卡到達(dá)，該方法使集卡更均勻地到達(dá)閘口，顯著地減少了閘口處的擁堵。

上述文獻(xiàn)大部分用來解決港口擁堵問題，沒有考慮到對(duì)環(huán)境的影響?；诖?，Schulte等[11]建立了一個(gè)基于有時(shí)間窗的多旅行商問題的優(yōu)化模型，可以有效利用集卡之間的協(xié)作來降低成本和排放;Mohammad等[12]考慮到排放和集卡預(yù)約變更成本，建立了一個(gè)混合整數(shù)非線性模型，可以同時(shí)為集卡公司和港務(wù)公司服務(wù)，能夠在有效減少運(yùn)輸成本的基礎(chǔ)上緩解集卡在閘口處的擁堵及相關(guān)排放量。但目前很多TAS的實(shí)際性能與預(yù)計(jì)性能并不一致。Giuliano等[6]研究發(fā)現(xiàn)長(zhǎng)灘和洛杉磯港口實(shí)施TAS時(shí)，由于破壞性事件阻礙了TAS的順利運(yùn)行，集卡在閘口的擁堵現(xiàn)象并沒有顯著緩解，重型柴油集卡的排放也沒有因此得到顯著減少;Islam等[13]研究得出，在新西蘭港口，TAS的實(shí)施加大了集卡公司對(duì)于集卡工作時(shí)間安排的局限性。

上述解決方案旨在減少集卡在閘口或堆場(chǎng)的等待時(shí)間，進(jìn)而減少怠速排放。雖然對(duì)TAS的研究越來越成熟，但現(xiàn)有研究沒有考慮到城市交通對(duì)集卡到達(dá)時(shí)間的影響，大大限制了TAS的實(shí)際應(yīng)用價(jià)值。為此，本文考慮了城市交通早晚高峰期擁堵對(duì)于集卡到達(dá)時(shí)間的影響，以及集卡在減速和怠速狀態(tài)下造成的環(huán)境污染成本，建立了一種基于混合整數(shù)非線性規(guī)劃(Mixed Integer Nonlinear Programming, MINLP)的集卡預(yù)約多約束調(diào)度模型。針對(duì)不同規(guī)模問題，采用Lingo軟件和自適應(yīng)量子遺傳算法(Self-Adaptive Quantum Genetic Algorithm，SQGA)進(jìn)行優(yōu)化求解。仿真結(jié)果表明，本文提出的模型和算法在獲得最佳調(diào)度方案的同時(shí)，有效地為集卡公司及港口降低了運(yùn)營(yíng)成本。

1 集卡預(yù)約系統(tǒng)描述

集卡預(yù)約系統(tǒng)是指依靠現(xiàn)代信息技術(shù)和網(wǎng)絡(luò)通信技術(shù)有效地建立港口和外集卡之間聯(lián)系，從而合理確定外集卡到港時(shí)間的系統(tǒng)。港口將一天工作時(shí)間平均分成若干時(shí)間窗，均衡考慮集卡排隊(duì)等待時(shí)間等眾多因素，給出各時(shí)間窗的預(yù)約份額，確定每個(gè)時(shí)間窗可接受的最大預(yù)約集卡數(shù)量，并利用線上預(yù)約系統(tǒng)對(duì)集卡到港進(jìn)行約束。

通過建立這種預(yù)約模式，港口在集卡到港前能全面掌控到港貨量信息，可以更有計(jì)劃地調(diào)配碼頭作業(yè)機(jī)械配置。集卡預(yù)約系統(tǒng)的可控性明顯優(yōu)于傳統(tǒng)的外集卡到港模式，在這種情況下，港口可以有計(jì)劃地進(jìn)行集港與疏港作業(yè)，能夠有效地避免集卡集中到達(dá)所導(dǎo)致的髙峰擁堵和運(yùn)力浪費(fèi)等問題。通過這種方式，不僅可以讓客戶避開集港高峰、縮短集港等候時(shí)間，還從根本上解決了外集卡到港擁堵和壓車問題，實(shí)現(xiàn)港務(wù)公司、集卡公司與客戶的共贏。

集卡公司采用網(wǎng)上預(yù)約的模式，集卡預(yù)約調(diào)度決策過程如圖1所示。首先，港口根據(jù)自身的集疏港作業(yè)能力、第二天的預(yù)貨物處理量以及以往的集卡到港規(guī)律等數(shù)據(jù)，將第二天的每個(gè)時(shí)間窗的預(yù)約配額提交給集卡預(yù)約系統(tǒng)，并通過集卡預(yù)約系統(tǒng)網(wǎng)站對(duì)預(yù)約配額及預(yù)約客戶進(jìn)行公布；然后集卡公司根據(jù)計(jì)劃和預(yù)約情況酌情選擇預(yù)約時(shí)間窗(預(yù)約分先后)，當(dāng)時(shí)間窗集卡預(yù)約數(shù)量達(dá)到預(yù)約配額上限，則該時(shí)間窗自動(dòng)關(guān)閉，如此，集卡公司不得不選擇自己可接受的次等時(shí)間窗;最后，第二天的預(yù)約情況將在前一天固定時(shí)段(本文設(shè)定每天下午5點(diǎn))停止預(yù)約，即港務(wù)公司可以在預(yù)約系統(tǒng)關(guān)閉后了解第二天的整體預(yù)約情況，即預(yù)約總量及各個(gè)時(shí)間窗的集卡預(yù)約數(shù)量，以方便港口更好地對(duì)即將到港的車流進(jìn)行管理。

影響集卡預(yù)約的主要因素有預(yù)約份額、預(yù)約時(shí)長(zhǎng)、集卡到達(dá)規(guī)律。在本文中，考慮到高峰期以及第二天到貨量的影響，對(duì)預(yù)約份額進(jìn)行不均勻分配；預(yù)約時(shí)段的長(zhǎng)度會(huì)影響集卡的到達(dá)分布，預(yù)約時(shí)長(zhǎng)短對(duì)集卡到達(dá)的管理有利，但會(huì)降低集卡在預(yù)約時(shí)段內(nèi)準(zhǔn)時(shí)到達(dá)的概率。因此，本文將每天上午8:00到下午6:00分為10個(gè)時(shí)間窗，每個(gè)時(shí)間窗的持續(xù)時(shí)間為1 h。集卡到達(dá)規(guī)律具有隨時(shí)間變化的規(guī)律，本文采用逐點(diǎn)平穩(wěn)流體流動(dòng)近似(Pointwise Stationary Fluid Flow Approximation, PSFFA)的方法[4,14]來描述集卡到達(dá)規(guī)律。

2 集卡預(yù)約系統(tǒng)的多約束調(diào)度模型

本文的集卡預(yù)約系統(tǒng)額外考慮了城市交通早晚高峰期擁堵對(duì)于集卡到達(dá)時(shí)間的影響，以及集卡在減速和怠速狀態(tài)下造成的環(huán)境污染成本。為了能準(zhǔn)時(shí)在預(yù)約時(shí)間窗下到達(dá)港口，集卡公司在申請(qǐng)預(yù)約時(shí)會(huì)考慮城市交通早晚高峰期對(duì)運(yùn)輸時(shí)間的影響，因此本文將早晚高峰期擁堵造成的集卡額外運(yùn)輸時(shí)間進(jìn)行了量化，使得集卡預(yù)約系統(tǒng)在確定集卡最佳預(yù)約方案時(shí)考慮更為全面。同時(shí)，為了減少集卡在城市早晚高峰期的擁堵，減少涉及早晚高峰期時(shí)間窗的配額數(shù)量，可以相對(duì)減少高峰期時(shí)段的集卡數(shù)量。本文集卡預(yù)約系統(tǒng)的多約束調(diào)度模型用來確定集卡預(yù)約時(shí)間，以便集卡可以更加均勻地到達(dá)港口，同時(shí)使得集卡公司和港務(wù)公司的綜合運(yùn)營(yíng)成本達(dá)到最小。

2.1 符號(hào)、集合、參數(shù)決策變量

2.1.1 符號(hào)

tw為港口時(shí)間窗；

ti為每個(gè)時(shí)間窗的時(shí)間間隔；

k為集卡ID；

i為一輛集卡的預(yù)約次數(shù)；

b為一輛集卡的預(yù)約的號(hào)碼；

d為集卡公司ID。

2.1.2 集合

A為時(shí)間窗集合，A={1,…,10}，如A=1表示8:00AM～9:00AM的時(shí)間窗；

Atw為一個(gè)時(shí)間窗內(nèi)的時(shí)間間隔集合，如A1={1,…,10}，A2={1,…,10}等，A1=1表示第一個(gè)時(shí)間窗內(nèi)8:00AM-8:06AM的時(shí)間間隔；

I為每輛集卡的預(yù)約次數(shù)集合(本文設(shè)置為1～4次)，I={1,…,4}，如I=3表示集卡有3次預(yù)約；

Ri為具有i次預(yù)約的集卡的預(yù)約集合，Ri=1,…,i；如Ri={1}，Ri={1,2}等；

D為集卡公司集合，D={1,2,…}，如D=1表示1號(hào)集卡公司；

Kd為d號(hào)集卡公司的所有集卡集合，如K1={1,2,…}，K1=1表示1號(hào)集卡公司的第一輛集卡；

j為城市道路等級(jí)集合，j={1,2,3}，如j=1表示快速路，j=2表示主干路，j=3表示次干路；

g為尾氣污染物集合，g={1,2,3}，如g=1表示一氧化碳(CO)，g=2表示碳?xì)浠衔?，g=3表示PM。

2.1.3 參數(shù)

ctw為時(shí)間窗tw的最大可預(yù)約次數(shù)；

Pkib為具有i次預(yù)約的集卡k的第b次預(yù)約的期望時(shí)間窗；

μti為時(shí)間間隔ti內(nèi)閘口處的服務(wù)效率；

σ為一個(gè)時(shí)間窗內(nèi)時(shí)間間隔的個(gè)數(shù)；

e為閘口服務(wù)時(shí)間的方差系數(shù)；

Cl為實(shí)際時(shí)間差大于期望時(shí)間差的懲罰值；

Cs為實(shí)際時(shí)間差小于期望時(shí)間差的懲罰值；

Cp為實(shí)際達(dá)到時(shí)間早于期望到達(dá)時(shí)間的懲罰值；

Cn為實(shí)際達(dá)到時(shí)間晚于期望到達(dá)時(shí)間的懲罰值；

Cq為集卡在閘口排隊(duì)等候的懲罰值；

nd為集卡公司d提交的預(yù)約總數(shù)；

THd為各個(gè)集卡公司運(yùn)輸成本之間差異的閾值；

dtpkib為具有i次預(yù)約的集卡k的第b次預(yù)約和第b+1次預(yù)約的時(shí)間差；

η為集卡擁堵下的經(jīng)濟(jì)損失換算系數(shù)；

Lj為j類道路的長(zhǎng)度；

Kj為j類道路上集卡的數(shù)量；

Vj為j類道路上集卡擁堵時(shí)的臨界速度；

Wg為集卡在道路擁堵條件下的g類污染物的排放系數(shù)；

CEg為每增加一種g類污染物造成的環(huán)境成本。

2.1.4 決策變量

λti為在時(shí)間間隔ti內(nèi)，集卡到達(dá)閘口的平均到達(dá)率；

Wti為在時(shí)間間隔ti內(nèi)，集卡在閘口處的平均隊(duì)列長(zhǎng)度；

Vti為在時(shí)間間隔ti內(nèi)，集卡從閘口到堆場(chǎng)的平均發(fā)車率；

dtkib為具有i次預(yù)約的集卡k的第b次到達(dá)和第b+1次到達(dá)的時(shí)間差；

Nkib為dtkib-dtpkib的差值；

Qkib為dtpkib-dtkib的差值；

Skib為集卡實(shí)際到達(dá)時(shí)間窗與期望到達(dá)時(shí)間窗的差值；

Zkib為集卡期望到達(dá)時(shí)間窗與實(shí)際到達(dá)時(shí)間窗的差值；

Td為集卡公司d預(yù)約變更總成本；

TC為集卡額外擁堵時(shí)間；

Qj為集卡在j類道路上的高峰期流量。

2.2 模型建立

由于港口的時(shí)間窗是離散的，在模型中建立一個(gè)二元決策變量Xkibtw進(jìn)行決策，該決策變量表示具有i次預(yù)約的集卡k在時(shí)間窗tw內(nèi)的第b次預(yù)約的狀態(tài)[4]。

(1)

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

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

(2)

2.2.2 約束條件

(3)

式(3)計(jì)算了每個(gè)集卡公司更改預(yù)約的成本，第1項(xiàng)表示對(duì)于一天內(nèi)具有多個(gè)預(yù)約的集卡，更改后的連續(xù)預(yù)約之間的時(shí)間差大于期望的時(shí)間差的更改成本(單位成本用Y1表示)；第2項(xiàng)表示更改后的連續(xù)預(yù)約之間的時(shí)間差小于期望時(shí)間差的更改成本(單位成本用Y2表示)；第3項(xiàng)表示更改為較晚時(shí)間窗的更改成本(單位成本用Y3)；第4項(xiàng)表示更改為較早時(shí)間窗的更改成本(單位成本用Y4表示)。

式(4)和式(5)是dtkib-dtpkib最大值的線性化表示：

Nkib≥0，?d∈D,?K∈Kd,?i∈I{1},

?b∈Ri{i}；

(4)

Nkib≥dtkib-dtpkib，?d∈D,?K∈Kd,

?i∈I{1},?b∈Ri{i}。

(5)

式(6)和式(7)是dtpkib-dtkib最大值的線性化表示：

Qkib≥0，?d∈D,?K∈Kd,?i∈I{1},

?b∈Ri{i}；

(6)

Qkib≥dtpkib-dtkib，?d∈D,?K∈Kd,

?i∈I{1},?b∈Ri{i}。

(7)

式(8)和式(9)是對(duì)實(shí)際到達(dá)時(shí)間窗與期望到達(dá)時(shí)間窗的差值最大值的線性化表示：

Skib≥0，?d∈D,?K∈Kd,?i∈I{1},

?b∈Ri{i}；

(8)

?K∈Kd,?i∈I{1},?b∈Ri{i}。

(9)

式(10)和式(11)是對(duì)期望到達(dá)時(shí)間窗與實(shí)際到達(dá)時(shí)間窗的差值最大值的線性化表示：

Zkib≥0，?d∈D,?K∈Kd,?i∈I{1},

?b∈Ri{i}；

(10)

(11)

式(12)是確保每一家集卡公司的更改時(shí)間窗的成本增加額不超過預(yù)定的閾值，閾值由式(13)確定，其優(yōu)點(diǎn)在于考慮了每一家集卡公司的預(yù)約次數(shù)，預(yù)約次數(shù)集卡較多的集卡公司的閾值較低。

(12)

THd=a+c·h-nd，?d∈D。

(13)

其中：a為港口給所有集卡公司的最低閾值;c為預(yù)約次數(shù)相對(duì)較少的集卡公司的起始閾值;h為斜率或閾值的下降速率。

式(14)和式(15)分別計(jì)算對(duì)于一天內(nèi)有多個(gè)預(yù)約集卡的兩個(gè)實(shí)際連續(xù)預(yù)約之間的時(shí)間差、兩個(gè)期望連續(xù)預(yù)約之間的時(shí)間差：

?d∈D,?K∈Kd,?i∈I{1},?b∈Ri{i}；

(14)

dtpkib=Pki(b+1)-Pkib，?d∈D,?K∈Kd,

?i∈I{1},?b∈Ri{i}。

(15)

式(16)表示應(yīng)滿足預(yù)約請(qǐng)求的條件：

?i∈I{1},?b∈Ri{i}。

(16)

式(17)為要求每個(gè)時(shí)間窗中的預(yù)約次數(shù)少于指定配額的容量約束：

(17)

預(yù)先規(guī)定的配額計(jì)算如式(18)所示：

(18)

其中AQ為每個(gè)時(shí)間窗的平均配額。本文中除了與港口時(shí)間窗持續(xù)時(shí)間的靈敏度分析有關(guān)的實(shí)驗(yàn)外，所有實(shí)驗(yàn)都是在10個(gè)時(shí)間窗內(nèi)進(jìn)行的。

式(19)為每個(gè)時(shí)間窗的配額設(shè)置：

tw=[0.9AQ,0.9AQ,1.1AQ,1.1AQ,1.1AQ,

1.1AQ,1.1AQ,1.1AQ,0.9AQ,0.9AQ]。

(19)

式(20)確保了具有多次預(yù)約的集卡在調(diào)整后的預(yù)約順序與請(qǐng)求時(shí)的順序相同。

?i∈I{1},?b∈Ri{i}。

(20)

式(21)將一個(gè)時(shí)間窗內(nèi)到達(dá)的所有集卡數(shù)量除以該時(shí)間窗內(nèi)的時(shí)間間隔個(gè)數(shù)，得到每個(gè)時(shí)間間隔內(nèi)集卡到達(dá)的平均數(shù)量，時(shí)間間隔這一術(shù)語僅用于隊(duì)列長(zhǎng)度估計(jì)。

(21)

(22)

式(23)用來計(jì)算每個(gè)時(shí)間間隔的集卡隊(duì)列長(zhǎng)度：

Wti+1=Wti+λti-Vti，?ti∈Atw,?tw∈A。

(23)

式(24)表示決策變量的取值：

Xkibtw={0 or 1}，?d∈D,?K∈Kd,

?i∈I{1},?b∈Ri{i},?tw∈A。

(24)

式(25)表示不同等級(jí)道路上集卡在高峰期的流量：

(25)

本文模型中城市道路分為快速路、主干路、次干路3個(gè)等級(jí)，分別計(jì)算不同擁堵強(qiáng)度條件下不同道路等級(jí)集卡的集卡擁堵的時(shí)間成本，集卡在不同時(shí)間狀態(tài)下的臨界速度參考城市不同類型道路交通狀態(tài)分類標(biāo)準(zhǔn)。

式(26)為早晚高峰期擁堵造成的集卡額外運(yùn)輸時(shí)間：

(26)

3 求解方法

集卡預(yù)約調(diào)度問題是一個(gè)NP-hard問題，它屬于基于時(shí)間窗的多重旅行商問題(multiple Traveling Salesman Problem with Time-Windows, m-TSPTW)[16]的擴(kuò)展，本文額外考慮了集卡在高峰期路段行駛增加的等待時(shí)間以及減速和怠速狀態(tài)下增加的污染物排放量，增加了求解難度，使得集卡預(yù)約系統(tǒng)的多約束調(diào)度問題變得更為復(fù)雜。

本文利用Lingo軟件求解混合整數(shù)非線性規(guī)劃問題的精確度及快速性的特點(diǎn)，對(duì)小、中規(guī)模的問題進(jìn)行了精確解的求解。Lingo軟件在求解大規(guī)模問題是會(huì)出現(xiàn)“內(nèi)存不足”的提示，進(jìn)而本文提出一種自適應(yīng)量子遺傳算法來求解大規(guī)模問題。

3.1 算法流程

遺傳算法[17]在較短的幾代時(shí)間內(nèi)都能很好地接近全局最優(yōu)點(diǎn)，但當(dāng)問題規(guī)模較大時(shí)容易陷入“早熟”。為解決該問題并進(jìn)一步提高求解問題的精度，Narayanan提出了量子遺傳算法(Quantum Genetic Algorithm，QGA)，該算法是一種基于量子計(jì)算原理的概率優(yōu)化方法，是量子計(jì)算與遺傳算法相結(jié)合的產(chǎn)物[18]。本文提出的SQGA通過實(shí)數(shù)與量子比特編碼相結(jié)合的編碼方式，可大大減小編碼長(zhǎng)度；設(shè)計(jì)動(dòng)態(tài)量子旋轉(zhuǎn)門，可提高求解問題的精度；提出新的迭代方式，減少算法的求解時(shí)間。具體算法流程圖如圖3a所示。SQGA算法步驟如下：

步驟1初始化種群Qiter及參數(shù)，a=8，c=4a，h=1.35，最大迭代次數(shù)為3 000，染色體長(zhǎng)度m=4，生成實(shí)數(shù)編碼染色體。

步驟2計(jì)算適應(yīng)度值并記錄最優(yōu)解。根據(jù)目標(biāo)函數(shù)計(jì)算每一個(gè)體的成本，將其倒數(shù)的1 000倍作為該個(gè)體的適應(yīng)度值f，即f=1000/fobj。

步驟3判斷是否滿足終止條件。如果滿足終止條件，輸出當(dāng)前最優(yōu)解；否則，繼續(xù)以下操作。

步驟4使用量子旋轉(zhuǎn)門Uiter更新種群Qiter。

步驟5進(jìn)行量子交叉和變異操作更新種群Qiter。

步驟6降低參數(shù)a的值，即a=a-0.1，同時(shí)iter=iter-1，返回步驟2。

3.2 算法關(guān)鍵技術(shù)

3.2.1 編碼規(guī)則

針對(duì)本文提出的集卡預(yù)約多約束調(diào)度問題，染色體采用實(shí)數(shù)編碼，確定集卡預(yù)約的狀態(tài)，由于每輛集卡的每天最大預(yù)約次數(shù)為4，染色體長(zhǎng)度m=4。將實(shí)數(shù)編碼轉(zhuǎn)換為二進(jìn)制編碼后再進(jìn)行量子比特編碼，一個(gè)量子比特表示如下：|φ〉=α·|xmin〉+β·|xmax〉，其中α、β為兩個(gè)復(fù)常數(shù)，分別表示量子取偏下限態(tài)和取偏上限態(tài)的幾率幅，且滿足歸一化條件|α|2+|β|2=1。

3.2.2 交叉變異操作

本文采用多點(diǎn)交叉，相互配對(duì)的兩個(gè)染色體，在編碼串中隨機(jī)選取兩個(gè)交叉點(diǎn)，然后兩者互換交叉點(diǎn)之間的部分，從而產(chǎn)生兩個(gè)新個(gè)體。同時(shí)，本文采用自適應(yīng)變異，變異的改變量為[-0.9,1.2]間的一個(gè)隨機(jī)整數(shù)且互為相反數(shù)，變異概率pm根據(jù)進(jìn)化代數(shù)自動(dòng)調(diào)整，計(jì)算公式為：

其中：pmax為最大變異概率;pmin為最小變異概率。

3.2.3 自適應(yīng)量子旋轉(zhuǎn)門更新

3.2.4 終止條件

本文終止條件包括以下兩個(gè)：

(1)判斷模型是否有可行解，若有可行解，降低參數(shù)a的值，直到模型無法求解，停止運(yùn)行輸出最優(yōu)解，這代表集卡預(yù)約系統(tǒng)已得到每個(gè)集卡公司的最佳閾值。

(2)設(shè)置最大迭代次數(shù)為算法的終止條件，當(dāng)算法的迭代次數(shù)達(dá)到最大值時(shí)，停止迭代并輸出最優(yōu)解。

當(dāng)滿足兩個(gè)終止條件中的任意一個(gè)即可停止運(yùn)行輸出最優(yōu)解。

4 算例分析

為驗(yàn)證本文所建立的模型和算法的可行性，進(jìn)行仿真實(shí)驗(yàn)和比較研究。實(shí)驗(yàn)在以年吞吐量500萬TEU的集裝箱港口為例的正方形網(wǎng)絡(luò)上生成，有一個(gè)集裝箱港口、多個(gè)空箱堆場(chǎng)和多個(gè)集卡池，如圖4所示。選擇的正方形網(wǎng)絡(luò)足夠大，集卡沿著網(wǎng)絡(luò)邊緣的行程時(shí)間為160 min。每個(gè)實(shí)驗(yàn)都提供了網(wǎng)絡(luò)的大小和集裝箱港口的位置。集卡倉(cāng)庫(kù)和空集裝箱倉(cāng)庫(kù)的位置是為不同的貨運(yùn)公司隨機(jī)選擇的?？蛻粑恢秒S機(jī)放置在網(wǎng)絡(luò)中，客戶的取貨和送貨時(shí)間窗為4:00AM～10:00PM，集裝箱港口從8:00AM～6:00PM運(yùn)營(yíng)，使用10個(gè)港口時(shí)間窗，每個(gè)時(shí)間窗口都是1 h。所有實(shí)驗(yàn)都是在Intel Core i7、1.8 GHz CPU和8 GB RAM的計(jì)算機(jī)上進(jìn)行。

本文用的基本數(shù)據(jù)如下：集卡在港口內(nèi)的周轉(zhuǎn)時(shí)間為43.2 min；港口每天的工作時(shí)間為10 h，時(shí)間窗的數(shù)量為10個(gè)[16]；港口堆場(chǎng)的平均排隊(duì)時(shí)間為10 min[10][16]；安裝/卸載集裝箱的時(shí)間為5 min[19]。

針對(duì)本文2.1節(jié)涉及到的5個(gè)懲罰值，每一個(gè)的取值范圍均為1～10的整數(shù)，對(duì)其進(jìn)行排列組合，計(jì)算在每組懲罰值下，無約束集卡調(diào)度模型的目標(biāo)函數(shù)值和受約束集卡調(diào)度模型的目標(biāo)函數(shù)值之間的差值，最小差值對(duì)應(yīng)的懲罰值即為最優(yōu)懲罰值。最終確定最優(yōu)懲罰值分別為Cl=1，Cs=3，Cp=1，Cn=3，Cq=1。

4.1 不同規(guī)模下集卡預(yù)約調(diào)度仿真實(shí)驗(yàn)

如表1所示為針對(duì)一家集卡公司的預(yù)約及TAS提供的最優(yōu)解決方案的實(shí)驗(yàn)，本文通過該實(shí)驗(yàn)來解釋TAS內(nèi)部工作原理。表1中Y1～Y7分別表示更改后時(shí)間差變大、更改后時(shí)間差變小、更改后時(shí)間窗推遲、更改后時(shí)間窗提前、閘口平均等待、早晚高峰期擁堵和排放的單位成本。實(shí)驗(yàn)1中集卡公司為一輛集卡進(jìn)行預(yù)約，期望的時(shí)間窗為1，3，6和8，TAS提供的最優(yōu)時(shí)間窗為1，4，6和8，由于時(shí)間窗3的貨物分配額為0，將時(shí)間窗3的預(yù)約延至?xí)r間窗4;實(shí)驗(yàn)2和實(shí)驗(yàn)3都是對(duì)兩輛集卡的調(diào)度，實(shí)驗(yàn)3的TAS提供的最優(yōu)時(shí)間窗即為期望時(shí)間窗，總目標(biāo)值是集卡在閘口排隊(duì)的單位成本、早晚高峰期造成的單位時(shí)間成本以及減速和怠速狀態(tài)下的單位環(huán)境污染成本的總和。

表1 一家集卡公司的時(shí)間窗及TAS提供的最優(yōu)方案

表2所示為28個(gè)額外實(shí)驗(yàn)的參數(shù)?；诒?的實(shí)驗(yàn)參數(shù)，對(duì)只考慮到閘口擁堵問題的TAS[10]、考慮到預(yù)約更改成本及閘口擁堵問題的TAS[12]和本文的目標(biāo)TAS進(jìn)行仿真實(shí)驗(yàn)。其中實(shí)驗(yàn)4～實(shí)驗(yàn)18為小規(guī)模問題，實(shí)驗(yàn)19～實(shí)驗(yàn)25為中規(guī)模問題，實(shí)驗(yàn)26～實(shí)驗(yàn)31為大規(guī)模問題(規(guī)模大小分配參考文獻(xiàn)[12])。小、中規(guī)模問題均用Lingo求得準(zhǔn)確解，大規(guī)模問題用自適應(yīng)量子遺傳算法進(jìn)行優(yōu)化求解，具體實(shí)驗(yàn)結(jié)果如表3所示。

集卡公司方面希望盡可能減少集卡數(shù)量來降低成本，通過對(duì)3種TAS的實(shí)驗(yàn)比較，本文的TAS對(duì)集卡數(shù)量的要求最少，能滿足集卡公司的需求。對(duì)于整個(gè)集卡預(yù)約機(jī)制下的運(yùn)輸問題，本文設(shè)計(jì)的TAS的目標(biāo)值最小，即整個(gè)成本是最小的，這表明該TAS充分利用好每一輛集卡的時(shí)間，提高了整個(gè)系統(tǒng)的效率。在整個(gè)作業(yè)系統(tǒng)中，盡可能降低綜合運(yùn)營(yíng)成本可以更好地服務(wù)于集卡公司和港口，考慮到城市早晚高峰期對(duì)集卡行程時(shí)間的影響，合理地分配預(yù)約時(shí)間窗可以使整個(gè)運(yùn)營(yíng)成本減少。

選取文獻(xiàn)[12]中4個(gè)大規(guī)模集卡預(yù)約系統(tǒng)調(diào)度的算例，將本文提出的SQGA與遺傳算法[16]、反應(yīng)式禁忌搜索算法[12]進(jìn)行Benchmark性能比較。4個(gè)算例的編號(hào)分別為N1、N2、N3、N4，具體比較結(jié)果如表4所示。由表4可知，自適應(yīng)量子遺傳算法在求解大規(guī)模問題時(shí)，速度明顯優(yōu)于另外兩種算法。同時(shí)，在N1、N3、N4實(shí)驗(yàn)中，本文提出的算法得到的最優(yōu)解決方案的目標(biāo)值明顯優(yōu)于另外兩種算法得到的目標(biāo)值；在N2實(shí)驗(yàn)中，本文算法得到的最優(yōu)解決方案優(yōu)于遺傳算法差于反應(yīng)式禁忌搜索算法，但求解速度明顯比兩者都優(yōu)；更符合本文減小集卡公司與港務(wù)公司綜合運(yùn)營(yíng)成本的目標(biāo)。

為驗(yàn)證本文提出的自適應(yīng)量子遺傳算法能更加快速精準(zhǔn)地求解該模型，基于實(shí)驗(yàn)27的參數(shù)，采用以上3種算法進(jìn)行優(yōu)化求解，將3種算法連續(xù)運(yùn)行10次。適應(yīng)度、收斂代數(shù)、收斂時(shí)間的盒圖比較如圖5所示。算法1～算法3分別為本文算法、遺傳算法[16]和反應(yīng)式禁忌搜索算法[12]。

表2 實(shí)驗(yàn)參數(shù)

續(xù)表2

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

表4 算法benchmark性能比較

由圖5可知，本文算法的收斂時(shí)間明顯優(yōu)于算法2，同時(shí)運(yùn)行連續(xù)10次的平均收斂時(shí)間明顯優(yōu)于算法3。本文算法的收斂代數(shù)也明顯優(yōu)于其他兩種算法，本文適應(yīng)度值雖然變化波動(dòng)較大，但結(jié)果明顯優(yōu)于其他兩種算法。

綜上所述，本文方法的最優(yōu)解決方案和Benchmark性能均優(yōu)于另外兩種算法，這是因?yàn)楸疚尼槍?duì)集卡預(yù)約系統(tǒng)多約束模型，提出的實(shí)數(shù)編碼方式，能減小編碼的長(zhǎng)度、有效節(jié)省編碼時(shí)間。充分利用式(13)閾值概念設(shè)置新穎的迭代方式，不僅能夠減少不必要的計(jì)算開銷，還能提高求解的精確度。本文提出動(dòng)態(tài)調(diào)整旋轉(zhuǎn)角機(jī)制，進(jìn)行自適應(yīng)量子旋轉(zhuǎn)門更新，可使求解方向一直趨于最優(yōu)解方向，加快求解速度。

4.2 運(yùn)營(yíng)成本的影響分析

4.2.1 不同顧客時(shí)間窗對(duì)運(yùn)營(yíng)成本的影響

為檢驗(yàn)客戶工作時(shí)間窗對(duì)運(yùn)營(yíng)成本的影響，基于以上模型分別對(duì)不同客戶工作時(shí)間窗進(jìn)行了5次實(shí)驗(yàn)，并將本文的TAS與文獻(xiàn)[10]、文獻(xiàn)[12]中的TAS作比較，圖6所示為不同顧客時(shí)間窗下3種TAS運(yùn)營(yíng)成本變化及比較實(shí)驗(yàn)結(jié)果。由圖6可見，3種TAS的運(yùn)營(yíng)成本隨著時(shí)間窗的減少而增加，運(yùn)營(yíng)成本的增長(zhǎng)率也會(huì)越來越高。而本文的TAS由于考慮到早晚交通高峰期，更加合理地分配預(yù)約集卡，總的運(yùn)營(yíng)成本要低于另外兩種TAS的運(yùn)營(yíng)成本。

4.2.2 時(shí)間窗的不同持續(xù)時(shí)間對(duì)運(yùn)營(yíng)成本的影響

本文港口時(shí)間窗的數(shù)量為10個(gè)，每個(gè)時(shí)間窗的時(shí)間為1 h。為了分析港口每個(gè)時(shí)間窗持續(xù)時(shí)間對(duì)整個(gè)港口及集卡公司運(yùn)營(yíng)成本的影響，分別對(duì)以上3種不同TAS進(jìn)行實(shí)驗(yàn)，結(jié)果如圖7表示。對(duì)這3種TAS來說，增加港口時(shí)間窗口持續(xù)時(shí)間都會(huì)導(dǎo)致運(yùn)營(yíng)成本的降低。對(duì)于港口方面，時(shí)間窗持續(xù)時(shí)間短使得集卡到達(dá)港口的時(shí)間誤差相對(duì)較小，使得港口方面的控制力提高。對(duì)于集卡公司方面，時(shí)間窗持續(xù)時(shí)間長(zhǎng)會(huì)減少整個(gè)運(yùn)營(yíng)成本。但是考慮到運(yùn)輸路徑的變化等不確定因素，持續(xù)時(shí)間更長(zhǎng)的時(shí)間窗

對(duì)整個(gè)系統(tǒng)更有利。相對(duì)于文獻(xiàn)[10]TAS與文獻(xiàn)[12]TAS的運(yùn)營(yíng)成本減少值來說，本文TAS與文獻(xiàn)[12]TAS運(yùn)營(yíng)成本的減少值要小。這是因?yàn)闀r(shí)間窗的持續(xù)時(shí)間足夠大，文獻(xiàn)[12]TAS考慮的成本是針對(duì)全部時(shí)間窗，而本文TAS考慮的是早晚高峰期擁堵情況下對(duì)集卡行程時(shí)間以及排放的影響，針對(duì)的是與早晚高峰期時(shí)間臨近的時(shí)間窗。同時(shí)，當(dāng)時(shí)間窗的持續(xù)時(shí)間大于120 min時(shí)，文獻(xiàn)[12]與本文的TAS的運(yùn)營(yíng)成本幾乎不再改變。原因是時(shí)間窗的持續(xù)時(shí)間足夠大時(shí)，早晚高峰對(duì)一個(gè)時(shí)間窗內(nèi)集卡到達(dá)時(shí)間的影響減小，同時(shí)可以增加集卡準(zhǔn)時(shí)預(yù)約的可能性，更改預(yù)約的可能性也會(huì)減小。但是，不同持續(xù)時(shí)間的時(shí)間窗下，本文TAS的整個(gè)運(yùn)營(yíng)成本均低于另外兩種TAS。

4.2.3 不同集卡周轉(zhuǎn)時(shí)間對(duì)運(yùn)營(yíng)成本的影響

為了分析在不同調(diào)度策略下，集卡在港口內(nèi)的周轉(zhuǎn)時(shí)間對(duì)整體運(yùn)營(yíng)成本的影響，通過將集卡周轉(zhuǎn)

時(shí)間分為五組(20 min，30 min，40 min，50 min，60 min)，分別進(jìn)行實(shí)驗(yàn)分析比較，結(jié)果如圖8所示。由圖8可知，在20 min～60 min的集卡周轉(zhuǎn)時(shí)間下，隨著周轉(zhuǎn)時(shí)間的增加，運(yùn)營(yíng)成本不斷增加。但是當(dāng)周轉(zhuǎn)時(shí)間接近60 min時(shí)，可以看到各個(gè)TAS的運(yùn)營(yíng)成本不斷接近。因此，當(dāng)周轉(zhuǎn)時(shí)間越來越大時(shí)，集卡的周轉(zhuǎn)時(shí)間對(duì)整體的運(yùn)營(yíng)成本影響程度會(huì)降低。對(duì)于同一個(gè)TAS，集卡的周轉(zhuǎn)時(shí)間越長(zhǎng)，綜合運(yùn)營(yíng)成本越高，這是因?yàn)橹苻D(zhuǎn)時(shí)間越長(zhǎng)，集卡一天內(nèi)的作業(yè)數(shù)量減少，導(dǎo)致集卡的運(yùn)輸成本增加，港口整體的作業(yè)效率降低；對(duì)于不同的TAS，由于本文TAS考慮了早晚高峰期擁堵以及擁堵條件下的排放，在相同集卡周轉(zhuǎn)時(shí)間下，本文TAS的綜合運(yùn)營(yíng)成本最低，且隨著集卡周轉(zhuǎn)時(shí)間的減少，綜合運(yùn)營(yíng)成本降低得越大。因此，集卡早晚高峰期擁堵時(shí)間成本以及集卡減速及怠速環(huán)境污染成本在整個(gè)TAS設(shè)計(jì)中不容忽視。

5 結(jié)束語

針對(duì)集卡擁堵問題，本文綜合考慮集卡公司預(yù)約變更成本、閘口排隊(duì)等候成本、早晚高峰期擁堵時(shí)間成本及怠速排放成本，構(gòu)造了一種基于混合整數(shù)非線性規(guī)劃(MINLP)的集卡預(yù)約多約束調(diào)度模型，利用Lingo求解小、中規(guī)模問題的精確解，設(shè)計(jì)動(dòng)態(tài)調(diào)整旋轉(zhuǎn)角機(jī)制，提出了一種自適應(yīng)量子遺傳算法求解大規(guī)模問題，改進(jìn)了現(xiàn)有的集卡預(yù)約系統(tǒng)(TAS)。實(shí)驗(yàn)結(jié)果表明，本文提出的模型和算法能有效降低港口及集卡公司的綜合運(yùn)營(yíng)成本，減少了集卡行程中早晚高峰期的擁堵時(shí)間，為港口和集卡公司提供更加理想的預(yù)約方案。

本文研究的問題局限于確定環(huán)境下對(duì)集卡預(yù)約系統(tǒng)的改進(jìn)，未來的研究將考慮在不確定環(huán)境下構(gòu)造集卡預(yù)約模型，使其面對(duì)不確定環(huán)境時(shí)更加靈活可靠。