基于時間窗的自動化集裝箱碼頭多載AGV調(diào)度研究

田呂 高燕 黃昕 祝潤澤 申淑麗 廖偉東

1.廣州機械科學(xué)研究院有限公司，中國·廣東 廣州 510700

2.國機智能科技有限公司，中國·廣東 廣州 510700

1 引言

隨著全球經(jīng)濟和科學(xué)技術(shù)的快速發(fā)展，作為維系社會經(jīng)濟運行的基礎(chǔ)產(chǎn)業(yè)——港口發(fā)展也愈加快速，港口不但提供中轉(zhuǎn)、裝卸和倉儲等功能，而且提供客戶貿(mào)易和金融等服務(wù)，同時拉動了多式聯(lián)運的發(fā)展?？梢娔壳案劭谝咽菄H市場交接點，將貨流、商流、資金流、信息流進行全面的融通，特別是對國民經(jīng)濟和區(qū)域發(fā)展方面等起的作用越發(fā)重要。其中集裝箱碼頭作為整個港口系統(tǒng)的樞紐站也正發(fā)生著從傳統(tǒng)的運輸模式向綜合物流的轉(zhuǎn)變，提高了碼頭的周轉(zhuǎn)能力和港口運輸?shù)男?，使港口相關(guān)功能得以不斷提升和優(yōu)化。

伴隨綜合物流時代的到來，中國經(jīng)濟發(fā)展已進入沿海經(jīng)濟與內(nèi)陸經(jīng)濟協(xié)同發(fā)展的新時期,江河海運一體化開始成為長江航運發(fā)展的新常態(tài)，為打造成重點突出、合理分工、層次分明的世界先進港口，通過產(chǎn)業(yè)集群的方式提升整個區(qū)域的競爭能力已成為必然趨勢[1]，這不僅需要在硬件方面達到世界先進水平，更要求中國在集裝箱軟件管理方面擁有自主創(chuàng)新的技術(shù)[2]，因此實現(xiàn)AGV 聯(lián)合優(yōu)化調(diào)度是進一步提升碼頭效率的迫切需要[3]。論文重點研究動態(tài)作業(yè)面調(diào)度模式下，裝卸作業(yè)并行工作，同時基于調(diào)度原則、速度設(shè)置、交通規(guī)劃即路徑設(shè)置對多AGV 展開全面分析，并利用遺傳算法對模型進行求解，利用Matlab 軟件對其進行計算與驗證得出最優(yōu)調(diào)度方案。

2 自動化集裝箱碼頭多AGV 調(diào)度系統(tǒng)

2.1 自動化集裝箱碼頭AGV 調(diào)度原理

在集裝箱自動化碼頭中，中央控制室生產(chǎn)過程控制系統(tǒng)（Process Control System,簡稱PCS）利用無線區(qū)域網(wǎng)絡(luò)監(jiān)控著AGV 的運行狀態(tài)，并進行數(shù)據(jù)判斷與傳輸，下達正確的任務(wù)指令。由于每個碼頭的機械設(shè)備配置、容忍參數(shù)、利用率等性能參數(shù)的不同，導(dǎo)致AGV 調(diào)度方法也需相應(yīng)調(diào)整，調(diào)度決策的科學(xué)性也直接影響AGV 的承載率、耗能率以及及時性，同時AGV 運輸集裝箱的目的不僅僅是將其運載到指定的堆存處，更需要將其時間約束、運輸路徑、裝載成本考慮在內(nèi)，因此多AGV 水平運輸?shù)恼{(diào)度系統(tǒng)主要考慮以下三個方面。

（1）合理假設(shè)避免資源浪費，論文研究的是岸橋和AGV 的聯(lián)合調(diào)度，岸橋和AGV 的任務(wù)分配是改善AGV 作業(yè)效率的關(guān)鍵環(huán)節(jié)，因此設(shè)置過多AGV 數(shù)量造成空載會導(dǎo)致無效成本的增加。

（2）最大化物流協(xié)同效益和運輸設(shè)備協(xié)調(diào)，因此可合理規(guī)劃AGV 運輸路線避免岸橋等待和AGV 阻塞現(xiàn)象發(fā)生，同時減少空載時間。

（3）由于AGV 重載和空載情況下其耗電不同導(dǎo)致行駛速度不同，因此需合理設(shè)置對象參數(shù)以優(yōu)化AGV 配車數(shù)量，提高碼頭的作業(yè)效率。

論文研究的多AGV 調(diào)度問題為：在一個水平運輸為任務(wù)送達主要輔助環(huán)節(jié)的系統(tǒng)中，在現(xiàn)有約束條件下合理調(diào)度AGV 數(shù)量完成配送，并且在最大程度上減少固定成本和運輸成本。在實際的多AGV 調(diào)度系統(tǒng)中，并行工作行駛路徑最長的那輛AGV 直接決定作業(yè)完成路徑的長短、作業(yè)時間的消耗。

因此，為了實現(xiàn)作業(yè)時間最小，使該AGV 的行駛路徑最小便可以達到優(yōu)化的目的。AGV 從中控室接收到下達的指令后，需要對任務(wù)作出及時地回應(yīng)，即AGV 可從當(dāng)前的位置出發(fā)運行至任務(wù)起始位置，并按照系統(tǒng)規(guī)劃的路徑完成任務(wù)的裝卸最終到達目的地處。同時，系統(tǒng)需要計算起止點之前及各個節(jié)點之間的距離，實時監(jiān)控AGV 的運行狀態(tài)，根據(jù)反饋信息處理AGV 將會面臨的突發(fā)情況，實時更新行駛路線和任務(wù)分配任務(wù)[4]。

2.2 多AGV 調(diào)度操作方法

在對AGV 進行調(diào)度時，應(yīng)考慮AGV 當(dāng)前的運輸狀態(tài)、地理位置、待執(zhí)行任務(wù)、任務(wù)緊急程度等，綜合以上因素再對AGV 下達執(zhí)行指令。當(dāng)AGV 處于空閑狀態(tài)或故障排除狀態(tài)時，則首先應(yīng)當(dāng)根據(jù)緊急分配原則進行任務(wù)下達指令；在處理不同尺寸的集裝箱時，AGV 可根據(jù)當(dāng)時的運載能力進行調(diào)度優(yōu)化。

2.3 多AGV 調(diào)度策略

（1）任務(wù)分配方案

由于AGV 的調(diào)度問題即為合理安排AGV 和任務(wù)的分配關(guān)系及其順序關(guān)系，因此對其進行合理安排可以有效對緊急任務(wù)作出及時反應(yīng)和調(diào)整，可根據(jù)按時分配、就近分配、緊急分配等原則系統(tǒng)規(guī)劃任務(wù)執(zhí)行順序[5]。

（2）交通規(guī)劃策略

由于AGV 任務(wù)下達主要依據(jù)其位置、狀態(tài)等信息，因此AGV 在運輸?shù)缆飞系慕煌ㄒ?guī)則便起到至關(guān)重要的作用。合理的交通規(guī)則不僅可以提高物流運輸?shù)男剩瑫r可對AGV進行優(yōu)化指派數(shù)量、縮短周轉(zhuǎn)時間、有效處理緊急故障、避免碰撞及死鎖等保障作用。因此，論文對AGV 實行以下交通規(guī)則。

①AGV 在場地運輸通道上行駛并進行集裝箱裝卸，道路上所有點稱為節(jié)點，其中AGV 的起止點和中轉(zhuǎn)點為作業(yè)節(jié)點，所經(jīng)過的道路交叉口為路口節(jié)點。

②AGV 的可通行道路分為主干道和次干道。其中主干道上的交通流在經(jīng)過交叉口時不受限制,兩輛AGV 之間必須時刻保持安全距離，避免在轉(zhuǎn)彎時出現(xiàn)死鎖現(xiàn)象。然而次干道上的交通流必須根據(jù)AGV 是否具有安全時間間隔才被允許進入，若不具備則將發(fā)生小車的等待。

③賦予場地內(nèi)所有AGV 所裝卸集裝箱的優(yōu)先級，并用數(shù)字編號以示區(qū)分。當(dāng)兩輛AGV 同時出現(xiàn)在同一路口節(jié)點時，優(yōu)先級高的先通過路口，且規(guī)定在系統(tǒng)中道路節(jié)點處至多有兩輛AGV 會面臨碰撞現(xiàn)象[6]。

在AGV 所負責(zé)的任務(wù)集里，小車進行連續(xù)作業(yè)且保持勻速狀態(tài)，因此當(dāng)兩輛小車在同一干道上行駛時，必須保證兩者距離不得少于安全距離，避免出現(xiàn)急停造成交通事故，同時系統(tǒng)也自動避免設(shè)備故障的發(fā)生。

（3）速度設(shè)置策略

論文重點研究的是基于時間窗的多載AGV 調(diào)度，因此不重點研究在交叉口通過速度的調(diào)節(jié)來保持物流系統(tǒng)的高效與穩(wěn)定，通過假定路口發(fā)生沖突時，AGV 進行等待或者先行來設(shè)置AGV 的速度參數(shù)。安排方法同交通規(guī)劃策略相似，在同一道路上，AGV 在保證安全距離的基礎(chǔ)上保持勻速行駛，當(dāng)前小車轉(zhuǎn)彎或急停時，后小車則在合理的時間范圍內(nèi)停止通行進行等待。當(dāng)在交叉口處需綜合考慮小車道路的優(yōu)先級、運載貨物的緊急情況與未通行路徑長度，作為繼續(xù)通行還是停車等待的標(biāo)準(zhǔn)，且不考慮其速度改變過程的時間。

2.4 路徑規(guī)劃策略

在綜合考慮最短路徑、最大運載量、最短排隊列長、最小等待時間的情況下，論文AGV 路徑規(guī)劃策略大致可描述為：通過賦予岸橋時間窗，從而安排AGV 按照設(shè)定的先后排列次序開展任務(wù)活動，避免碰撞與死鎖現(xiàn)象，并且利用時間定義道路優(yōu)先級增強AGV 的動態(tài)適應(yīng)性。以下因素是影響路徑優(yōu)化的重要條件。

（1）作業(yè)節(jié)點性質(zhì)：它是AGV 工作的起止點或中轉(zhuǎn)點，由于AGV 自身不具備提升功能，因此該節(jié)點是岸橋或場橋與AGV 進行任務(wù)交接的場地。論文以成本最小作為目標(biāo)函數(shù)，利用時間窗模型和懲罰函數(shù)對作業(yè)節(jié)點進行任務(wù)約束。

（2）集裝箱承載量：作為港口吞吐量的重要換算單位，目前AGV 的裝載容量為40 英尺標(biāo)準(zhǔn)箱，但是在大多研究論文中當(dāng)AGV 運載一個20 英尺的集裝箱時，其工作能力僅僅為50%，隨著集裝箱量的不斷擴大必然會造成經(jīng)濟損失、資源浪費，因此論文將集裝箱的尺寸加以區(qū)分最大程度上減少AGV 運載的次數(shù)。

（3）任務(wù)約束條件：論文主要從AGV 的容量和時間兩個方面進行考慮，并且每次進行多任務(wù)運輸時只有一個入口和一個出口，前后任務(wù)時間上也存在客觀正確的邏輯關(guān)系。

（4）目標(biāo)函數(shù)：通過對AGV 加以交通規(guī)則、速度控制及路徑規(guī)劃等約束，使系統(tǒng)安排的集裝箱任務(wù)能在規(guī)定的時間范圍內(nèi)完成，并且在有限的AGV 數(shù)量下實現(xiàn)最小化運輸次數(shù)和運輸路徑以實現(xiàn)最小化成本的目標(biāo)。

由于以上因素相互作用、相互促進，因此集裝箱的運輸作業(yè)不僅僅是單一的水平運輸過程，還需要各個方面的整體優(yōu)化最終實現(xiàn)目標(biāo)的完成與優(yōu)化，防止岸橋等待時間過長造成船舶非正常?？康那闆r發(fā)生、路徑選擇不經(jīng)濟、AGV 配置數(shù)量過多等情況的發(fā)生[7]。

3 基于時間窗的多載AGV 模型

3.1 多載AGV 調(diào)度模型

3.1.1 水平運輸系統(tǒng)

對于自動化集裝箱碼頭水平運輸系統(tǒng)，其效率的高低直接代表了整個碼頭運作的工作水平。AGV 通常為可承載40英尺集裝箱，若被指派裝卸20 英尺集裝箱時，則導(dǎo)致一半裝載容量被浪費，因此為達到最小化等待時間和行駛路徑的目標(biāo)，多載AGV 不僅需要考慮其分配任務(wù)，還需要從自身容量出發(fā)對任務(wù)順序進行優(yōu)化處理，使多載AGV 的調(diào)度任務(wù)格外復(fù)雜與困難[8]。

3.1.2 調(diào)度方案

論文以成本最小為原則，當(dāng)岸橋處有需要進行卸載的集裝箱時，根據(jù)緊急原則或就近原則對空載AGV 進行搜索并下達任務(wù)安排，隨后AGV 將執(zhí)行任務(wù)滿足請求。由于論文研究的AGV 容量為40 英尺集裝箱，因此當(dāng)AGV 此時承載一個20 英尺集裝箱，在滿足的時間窗條件下還可以允許該集裝箱承載另一個20 英尺的集裝箱，隨后將其各自運送回目的地處完成任務(wù)交付，結(jié)束此次調(diào)度活動后中控室便為AGV 更新任務(wù)分配。若不滿足時間窗范圍，則需利用懲罰函數(shù)找出問題的最優(yōu)解。

3.2 多載AGV 調(diào)度優(yōu)化模型的建立

3.2.1 模型假設(shè)

論文是在帶時間窗的車輛調(diào)度問題上展開的自動化集裝箱碼頭多載AGV 調(diào)度研究，根據(jù)實際情況考慮到AGV 和集裝箱的實際尺寸和碼頭的停泊時間，因此以下是確定的基于時間窗約束的多載AGV 調(diào)度研究。

假設(shè)條件：

（1）已知岸橋被分配的集裝箱任務(wù)集合。

（2）場橋為兩個，各自各組出口箱和進口箱。

（3）理論不能出現(xiàn)岸橋停滯等待AGV 的情況，超過時間窗便帶來成本的損失。

（4）AGV 數(shù)量充足，不能出現(xiàn)AGV 等待場橋的情況，且AGV 可行駛路徑為已知。

3.2.2 參數(shù)設(shè)置

i：運輸任務(wù)(1、2、3...n)

K：場地AGV 的集合

i：任務(wù)i 的起始點；

n+i：任務(wù)i 的交付點；

P：起始點的集合，其中P={1,2,3…,n}

D：交付點的集合，其中D={n+1,n+2,n+3…,n}

N：所有起始點和交付點的集合，其中N=P∪D

di：任務(wù)i 所執(zhí)行的運輸個數(shù),若任務(wù)i 從i 點運輸di個至n+i 點，則Li= di，Ln+i=?di

o(k)：AGVk所有任務(wù)集合的起始點

d(k)：AGVk所有任務(wù)集合的?？奎c

Nk：AGVk的所有任務(wù)集合，其中Nk=Pk∪Dk

Vk：AGVk所有任務(wù)點與AGVk的起始點和?？奎c的集合，其中

Ak：AGVk所有通行路徑的連接的弧，其中Ak∈Vk×Vk

Gk：AGVk的路徑形成的通行網(wǎng)路，其中Gk=（Vk,Ak）

Ck：AGVk的最大負載能力，為固定值

ti,j,k：AGVk從i到j(luò)的通行所需時間，其中i,j∈Vk

ci,j,k：AGVk從i到j(luò)的通行所需費用，其中i,j∈Vk

Ce：AGVk早到的懲罰成本

Cl：AGVk遲到的懲罰成本

si：任務(wù)i的執(zhí)行時間

[ao,bo]：船舶?？康臅r間窗，為最大一個時間范圍

[ai,bi]：硬時間窗，指代是點i 的計劃時間窗，其中i∈C

針對場地中任意AGVk，其運行路徑為：收到起始點o(k)的任務(wù)后便開始運行，行駛路線為Gk中的最優(yōu)路徑，到達任務(wù)停靠點d(k)便進行任務(wù)裝卸，并其中要求AGV 到達被分配岸橋的時間必須在時間窗 [ai',bi']內(nèi)，如果AGV早到或者延時都將被懲罰。其中，多載AGV 在運輸中并不是每次都為多載，是在能減少運輸數(shù)量并滿足容量條件的情況下才為多載，否則仍為單載AGV。

3.2.3 變量定義

（1）若AGVk行駛路徑（i,j）∈Ak，則xi,j,k=1，否則xi,j,k=0。

（2）Ti,k為AGVk在起始點i 開始運行的時間，其中i∈kV。

（3）Li,k為AGVk在起始點i 完成裝卸后的荷載。

3.2.4 模型建立

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

約束條件：

其中（3）～（5）表示AGVk有一個起始點o(k)并且最后停靠在終止點d(k)，經(jīng)過的入口點數(shù)目等于出口點的數(shù)目。（6）（7）表示每個裝卸任務(wù)只能被運輸一次，任意一個集裝箱的裝卸必須為一輛AGVk完成。（8）～（10）表示當(dāng)xi,j,k=1，AGVk執(zhí)行任務(wù)j 的時間Tj,k大于等于AGVk執(zhí)行i 的起始時間Ti,k、任務(wù)i 執(zhí)行過程的時間si與AGVk從i 點運行到j(luò) 點的時間之和。（11）～（16）為AGV 裝載和在起始點o(k)和終止點d(k)的負載約束。

4 求解算法

4.1 求解思路

中國對于集裝箱碼頭的分析主要集中于AGV局部調(diào)度，任亞東[9]探討了 AGV 調(diào)度系統(tǒng)的原理、原則以及影響因素，隨后分析了“作業(yè)線”和“作業(yè)面”調(diào)度模型各自的優(yōu)缺點，以無效作業(yè)時間最小為原則建立了數(shù)學(xué)模型，基于 Netlogo平臺進行仿真模擬，對比分析不同環(huán)境下AGV 的等待率，得出了最佳的車道和岸橋以及AGV 的最佳參數(shù)配比。汪先超[10]研究了根據(jù)實時調(diào)度的方法，解決了多AGV 基于靜態(tài)調(diào)度、實時調(diào)度、出現(xiàn)故障三種條件下的調(diào)度問題。

Confessore G 等將AGV 調(diào)度問題視為最小流問題，構(gòu)建了最小流模型，通過貪婪算法和單純形算法進行計算并展開分析。Kumaran 和 Richard 等人針對AGV 死鎖問題展開了分析，將場地劃分為不同的矩形區(qū)域，根據(jù)判斷該區(qū)域是否存在其余AGV 從而避免死鎖的發(fā)生。Kusiak 和 Cyrus 從時間最短為原則，最小化AGV 閑置的時間 ，在算法設(shè)計上采用了遺傳算法。Golden 等驗證了多載AGV 調(diào)度問題為NPhard 問題，論文用遺傳算法來進行問題的求解。

4.2 算法設(shè)計

4.2.1 編碼

遺傳算法的編碼一般有浮點編碼和二進制編碼兩種，論文采用二進制編碼方式。若第i 個任務(wù)由AGVk完成，則第i 個位置的編碼為k，染色體長度為岸橋被分配的任務(wù)數(shù)量，對應(yīng)的編碼分別為1～7 的整數(shù)，表示場地上有7 輛AGV。

4.2.2 解碼

由于解碼的目的是為了將二進制數(shù)據(jù)還原為十進制，根據(jù)公式可得出：

4.2.3 交配

交配運算為單點或多點進行交叉的算子，首先選定隨機數(shù)產(chǎn)生一個或多個交配點的位置，然后在兩個父代個體交配的位置上交換部分基因形成兩個新的個體，隨后根據(jù)適應(yīng)度函數(shù)來篩選子代染色體，并重復(fù)更換基因組和篩選對的過程最終得到一個最優(yōu)的子代染色體。

4.2.4 突變

突變即在基因位上進行基因突變，為了避免過早出現(xiàn)算法的收斂，對于二進制基因碼組成的個體種群，實行基因碼的小幾率翻轉(zhuǎn)。

4.2.5 倒位

除了交配和突變，對于個別復(fù)雜問題可能需要應(yīng)用倒位，是指一個染色體某區(qū)域的正常排序進180°翻轉(zhuǎn)，已致DNA序列進行重新排列，其中包括臂內(nèi)倒位和臂間倒位兩種方式。倒位純合體不影響個體的生活率，但改變了染色體上相鄰的基因位置，使某些表現(xiàn)型發(fā)生順序更改，同時也改變了與相鄰基因的交換值。

4.2.6 個體適應(yīng)度評估

遺傳算法中根據(jù)與個體適應(yīng)度成正比的幾率決定當(dāng)前種群中個體是否能遺傳到下一代，適應(yīng)度大的將更容易被遺傳到下一代，因此通常把求目標(biāo)函數(shù)最優(yōu)解問題當(dāng)做檢測個體適應(yīng)度大小的函數(shù)。

4.2.7 復(fù)制

若設(shè)種群中個體總數(shù)為N，個體i 的適應(yīng)度為fi，則個體i 被選取的幾率為：

個體被復(fù)制后再產(chǎn)生[0,1]區(qū)間的均勻隨機數(shù)來決定哪些個體參與復(fù)制，被選取的幾率和個體適應(yīng)度成正比例關(guān)系，個體的遺傳基因會因此擴散或者被逐漸淘汰。

根據(jù)算法設(shè)計得出以下結(jié)論：

（1）多載AGV 相對于單載AGV 的空載率、空載次數(shù)和運輸費用都低。

（2）隨著集裝箱量的增加，碼頭機械設(shè)備的參數(shù)不斷進行更改，多載AGV 的運輸費用始終比單載AGV 低。

5 結(jié)語

論文通過對集裝箱自動化碼頭主要業(yè)務(wù)的分析，提出一種基于軟時間窗的策略，該策略主要考慮了船舶靠泊時間會影響整個碼頭作業(yè)產(chǎn)生的系列費用，以及集裝箱尺寸會影響AGV 調(diào)度的作業(yè)次序以及次數(shù)，因此通過配置最優(yōu)交通規(guī)則、速度控制及路徑規(guī)劃等要素力求得出最優(yōu)的AGV 調(diào)度方案。此外，為了實現(xiàn)AGV 能及時響應(yīng)岸橋，因此論文在算法設(shè)計中討論了硬時間窗和軟時間窗兩種情況，適用于不同特點的碼頭。

論文通過對AGV 調(diào)度的原則、方法及目標(biāo)等的分析，針對AGV 容量限制建立了費用最小為目標(biāo)函數(shù)的優(yōu)化模型，采用遺傳算法進行模型的求解，并在求解過程中設(shè)置相關(guān)對比組進行方案分析，基于碼頭實際情況不斷對AGV 分配比例進行優(yōu)化改進，同時考慮到碼頭集裝箱量在不斷增加，因此在設(shè)置任務(wù)數(shù)量時需要進行多組對照，以便得出多載AGV在理論中優(yōu)于單載AGV 的結(jié)果。此外，論文利用了時間窗和懲罰函數(shù)，通過采集大量碼頭真實數(shù)據(jù)及實驗結(jié)果進行驗證分析，不斷調(diào)整得到合理的時間窗區(qū)間范圍。