考慮沖突和擁堵的自動(dòng)導(dǎo)引車(chē)調(diào)度與路徑規(guī)劃協(xié)同優(yōu)化

范厚明，牟爽，岳麗君

考慮沖突和擁堵的自動(dòng)導(dǎo)引車(chē)調(diào)度與路徑規(guī)劃協(xié)同優(yōu)化

范厚明，牟爽，岳麗君*

（大連海事大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連 116026）（ ? 通信作者電子郵箱yuelj11@163.com）

針對(duì)自動(dòng)化集裝箱碼頭自動(dòng)導(dǎo)引車(chē)（AGV）調(diào)度與無(wú)沖突路徑規(guī)劃問(wèn)題，提出了AGV沖突擁堵解決策略以生成無(wú)沖突路徑。首先，考慮堆場(chǎng)緩沖支架的容量，運(yùn)行路徑無(wú)擁堵、節(jié)點(diǎn)無(wú)沖突約束，以最大完工時(shí)間最小、AGV總行駛時(shí)間最短為目標(biāo)建立兩階段混合整數(shù)規(guī)劃模型；其次，設(shè)計(jì)改進(jìn)的自適應(yīng)遺傳算法、基于沖突擁堵解決策略的迪杰斯特拉算法求得AGV調(diào)度方案與無(wú)沖突路徑。算例分析結(jié)果表明：改進(jìn)的自適應(yīng)遺傳算法相較遺傳算法平均求解時(shí)間降低了13.56%，且目標(biāo)函數(shù)平均差距率為9.01%；基于沖突擁堵解決策略相較停車(chē)等待策略使得水平運(yùn)輸區(qū)擁堵度降低67.6%，AGV等待時(shí)間減少66.7%?？梢?jiàn)，所提算法求解質(zhì)量高且速度快，同時(shí)驗(yàn)證了所提策略的有效性。

自適應(yīng)遺傳算法；自動(dòng)化集裝箱碼頭；自動(dòng)導(dǎo)引車(chē)調(diào)度；無(wú)沖突路徑規(guī)劃；沖突和擁堵

0 引言

集裝箱吞吐量的不斷增長(zhǎng)和集裝箱船舶大型化的快速發(fā)展對(duì)集裝箱碼頭裝卸作業(yè)效率提出了更高的要求。近年來(lái)，隨著自動(dòng)化技術(shù)的不斷應(yīng)用，我國(guó)集裝箱碼頭的智能化程度顯著提高，特別是自動(dòng)化集裝箱碼頭的裝卸效率得到大幅度提高。自動(dòng)導(dǎo)引車(chē)（Automated Guided Vehicle， AGV），是自動(dòng)化集裝箱碼頭中關(guān)鍵的水平運(yùn)輸工具，承擔(dān)著從岸橋到堆場(chǎng)的集裝箱卸船運(yùn)輸和從堆場(chǎng)到岸橋的集裝箱裝船運(yùn)輸?shù)闹匾蝿?wù)，其合理的調(diào)度以及高效穩(wěn)定的運(yùn)行對(duì)于提高碼頭的作業(yè)效率有非常重要的意義。在實(shí)際作業(yè)環(huán)境中，常配置充裕的AGV以避免岸橋和場(chǎng)橋等待，在多臺(tái)岸橋同時(shí)作業(yè)時(shí)，易發(fā)生AGV沖突和擁堵問(wèn)題。因此，合理為各AGV分配作業(yè)任務(wù)的同時(shí)并優(yōu)化各AGV行駛路徑，不僅能夠減少作業(yè)過(guò)程中設(shè)備間相互等待時(shí)間，而且能夠解決沖突、擁堵等問(wèn)題，提高碼頭作業(yè)效率和AGV運(yùn)輸效率，對(duì)碼頭的實(shí)際運(yùn)營(yíng)有著重要的指導(dǎo)作用。

目前，已有學(xué)者對(duì)AGV調(diào)度問(wèn)題進(jìn)行了大量研究，AGV通常與碼頭其他設(shè)備協(xié)同調(diào)度，如Bae等［1］首先提出作業(yè)面調(diào)度模式，以AGV總行駛距離最短為優(yōu)化目標(biāo)研究作業(yè)面調(diào)度模式，并設(shè)計(jì)啟發(fā)式算法求解；基于作業(yè)面調(diào)度模式，梁承姬等［2］提出了一種岸橋動(dòng)態(tài)調(diào)度與AGV分組作業(yè)面的調(diào)度模式，建立了岸橋與AGV聯(lián)合調(diào)度優(yōu)化的模型，并通過(guò)遺傳算法求解該模型；田宇等［3］針對(duì)自動(dòng)化碼頭雙循環(huán)AGV和場(chǎng)橋集成調(diào)度問(wèn)題，以船舶完工時(shí)間最小為優(yōu)化目標(biāo)建立數(shù)學(xué)模型，并設(shè)計(jì)了基于啟發(fā)式遺傳算法進(jìn)行求解；范厚明等［4］考慮能耗因素，分別以岸橋能耗最小和AGV運(yùn)輸過(guò)程中能耗最小為目標(biāo)建立兩階段優(yōu)化模型，分別設(shè)計(jì)了枚舉法和改進(jìn)遺傳算法進(jìn)行求解。以上將AGV與岸橋或者AGV與場(chǎng)橋協(xié)同調(diào)度研究，缺少對(duì)岸橋、AGV和場(chǎng)橋三者集成調(diào)度的研究。也有學(xué)者對(duì)不同策略下AGV調(diào)度進(jìn)行研究，如Li等［5］研究了多標(biāo)準(zhǔn)調(diào)度策略下自動(dòng)化集裝箱碼頭AGV調(diào)度，基于不同的場(chǎng)景對(duì)問(wèn)題仿真模擬得到AGV的調(diào)度方案；韓曉龍等［6］通過(guò)eM-Plant建立了集裝箱碼頭的仿真模型，設(shè)計(jì)了不同AGV調(diào)度策略下和不同AGV數(shù)量配置下的模型并進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證不同AGV調(diào)度策略對(duì)碼頭作業(yè)效率的影響。通過(guò)模擬碼頭真實(shí)作業(yè)環(huán)境，對(duì)比分析不同AGV調(diào)度策略對(duì)作業(yè)效率的影響，然而仿真模擬只能最大限度模擬真實(shí)作業(yè)環(huán)境，未能考慮實(shí)際作業(yè)其他相關(guān)因素對(duì)調(diào)度的影響。隨著研究的不斷深入，也有少量研究考慮實(shí)際作業(yè)過(guò)程中的相關(guān)因素對(duì)AGV調(diào)度的影響，如電池電量約束［7-8］、緩沖支架容量限制［9-10］等。

目前關(guān)于AGV路徑規(guī)劃的研究大部分針對(duì)柔性制造系統(tǒng)［11-13］，自動(dòng)化集裝箱碼頭與柔性制造系統(tǒng)相比，AGV數(shù)量多且運(yùn)輸行駛區(qū)無(wú)障礙，碼頭連續(xù)作業(yè)要求AGV在運(yùn)輸過(guò)程中盡可能減少岸橋和場(chǎng)橋的相互等待時(shí)間，因此對(duì)AGV路徑規(guī)劃具有一定難度。高一鷺等［14］以任務(wù)完工時(shí)間最短為目標(biāo)，提出了一種基于時(shí)空網(wǎng)路的路徑優(yōu)化方法。由于自動(dòng)化集裝箱碼頭AGV數(shù)量多，AGV行駛過(guò)程中不可避免產(chǎn)生碰撞，在AGV路徑規(guī)劃中沖突問(wèn)題一直是研究的熱點(diǎn)，卻較少研究AGV在行駛中產(chǎn)生的擁堵問(wèn)題，曾慶成等［15］提出了AGV動(dòng)態(tài)路徑規(guī)劃策略，建立考慮擁堵的多AGV路徑優(yōu)化模型，設(shè)計(jì)了基于動(dòng)態(tài)路徑規(guī)劃策略的多種群蟻群算法求解。當(dāng)產(chǎn)生沖突擁堵時(shí)，如何解決AGV沖突問(wèn)題已經(jīng)成為當(dāng)前研究AGV路徑規(guī)劃的重點(diǎn)，仲美穌等［16］提出了交通虛擬環(huán)島策略，建立了集裝箱碼頭的仿真模型；Xin等［17］提出了一種分層控制方法用于生成AGV行駛路徑，以碼頭設(shè)備作業(yè)時(shí)間最短為目標(biāo)構(gòu)建了混合整數(shù)規(guī)劃模型。

也有少量的文獻(xiàn)研究AGV調(diào)度與路徑規(guī)劃問(wèn)題，絕大部分是針對(duì)柔性制造系統(tǒng)進(jìn)行的研究［18-21］，僅有少數(shù)針對(duì)自動(dòng)化碼頭進(jìn)行研究，Yang等［22］以總?cè)蝿?wù)最大完工時(shí)間最小為目標(biāo)構(gòu)建了雙層規(guī)劃模型，設(shè)計(jì)了基于避碰規(guī)則的雙層遺傳算法進(jìn)行求解；Zhong等［23］考慮了自動(dòng)化碼頭集成調(diào)度、路徑優(yōu)化、沖突和死鎖等問(wèn)題，以AGV延遲時(shí)間最小為目標(biāo)建立了混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了啟發(fā)式遺傳粒子群（Heuristic Genetic Algorithm-Particle Swam Optimization， HGA-PSO）混合算法進(jìn)行求解。

通過(guò)對(duì)現(xiàn)有研究分析發(fā)現(xiàn)：1）現(xiàn)有研究較少考慮岸橋、AGV和場(chǎng)橋三個(gè)不同設(shè)備之間的相互關(guān)聯(lián)和制約協(xié)同關(guān)系，大多數(shù)是對(duì)碼頭一種或者兩種設(shè)備進(jìn)行研究和優(yōu)化調(diào)度，對(duì)AGV調(diào)度與路徑規(guī)劃的研究較少；2）現(xiàn)有對(duì)AGV調(diào)度的研究較少考慮實(shí)際作業(yè)過(guò)程中緩沖支架對(duì)各個(gè)設(shè)備之間的影響，現(xiàn)有對(duì)AGV路徑規(guī)劃的研究較少考慮路徑擁堵問(wèn)題；3）目前所采用的算法大多數(shù)在解決AGV沖突時(shí)又重新回到任務(wù)調(diào)度和路徑規(guī)劃，解決沖突的策略主要有停車(chē)等待和重新規(guī)劃路徑，重新規(guī)劃路徑不僅會(huì)增加了計(jì)算時(shí)間而且會(huì)產(chǎn)生新的沖突，增加了研究的復(fù)雜性。

因此，本文針對(duì)AGV調(diào)度與路徑規(guī)劃問(wèn)題，考慮堆場(chǎng)緩沖支架容量，AGV運(yùn)行路徑無(wú)擁堵、節(jié)點(diǎn)無(wú)沖突約束，建立了兩階段混合整數(shù)規(guī)劃模型，并設(shè)計(jì)兩階段混合優(yōu)化算法分階段對(duì)其求解。

1 問(wèn)題描述

在靠港船舶裝卸作業(yè)過(guò)程中，AGV調(diào)度的核心目標(biāo)是每輛AGV按時(shí)到達(dá)岸橋和堆場(chǎng)作業(yè)區(qū)，若AGV到達(dá)岸橋或場(chǎng)橋作業(yè)區(qū)的時(shí)刻早于計(jì)劃作業(yè)時(shí)刻，那么AGV等待；否則，岸橋或場(chǎng)橋等待。作業(yè)面調(diào)度模式下AGV的調(diào)度過(guò)程如圖1所示，岸橋1將卸船箱放至空載AGV，AGV沿著線(xiàn)路1將卸船箱運(yùn)送到箱區(qū)2，作業(yè)完的空載AGV可以沿著線(xiàn)路3到達(dá)岸橋3作業(yè)下一卸船箱，也可以沿著線(xiàn)路2到達(dá)箱區(qū)3作業(yè)下一裝船箱，將裝船箱從箱區(qū)3運(yùn)送到岸橋2。通過(guò)優(yōu)化AGV的空載時(shí)間降低AGV的配置數(shù)量，有利于減小AGV路徑?jīng)_突和擁堵的概率。

圖1　碼頭布局和AGV運(yùn)輸流程示意圖

與傳統(tǒng)碼頭不同，自動(dòng)化碼頭堆場(chǎng)前設(shè)置緩存區(qū)，緩沖支架安裝在箱區(qū)前，用于裝卸集裝箱，當(dāng)作業(yè)進(jìn)口箱時(shí)，若AGV到達(dá)場(chǎng)橋下的時(shí)刻早于場(chǎng)橋計(jì)劃作業(yè)時(shí)刻，AGV無(wú)需等待場(chǎng)橋作業(yè)完上一個(gè)集裝箱，AGV直接將進(jìn)口集裝箱卸到緩沖支架，待場(chǎng)橋作業(yè)完上一集裝箱后直接從緩沖支架提取進(jìn)口箱；作業(yè)出口箱時(shí)，若AGV到達(dá)場(chǎng)橋下的時(shí)刻晚于場(chǎng)橋計(jì)劃作業(yè)時(shí)刻，場(chǎng)橋無(wú)需等待AGV到達(dá)作業(yè)，場(chǎng)橋直接將出口集裝箱卸到緩沖支架上，待AGV到達(dá)箱區(qū)后直接從緩沖支架提取出口箱?？紤]緩沖支架容量?jī)?yōu)化AGV調(diào)度，有利于降低各AGV在箱區(qū)的等待時(shí)間，也可進(jìn)一步降低岸橋延遲時(shí)間。

不同集裝箱所屬船舶貝位和堆場(chǎng)存放位置不同，不同AGV運(yùn)輸集裝箱的行駛路徑也可能不同。在實(shí)際作業(yè)過(guò)程中，多AGV間沖突和擁堵會(huì)增加其運(yùn)輸時(shí)間，若因沖突和擁堵導(dǎo)致AGV晚到達(dá)岸橋或場(chǎng)橋，可能會(huì)導(dǎo)致集裝箱實(shí)際裝卸完工時(shí)間晚于裝卸時(shí)間要求，船舶無(wú)法按時(shí)離港。因此，AGV路徑規(guī)劃的核心目標(biāo)是為每一輛AGV規(guī)劃出一條無(wú)沖突擁堵的最短行駛路徑。

由于碼頭水平運(yùn)輸區(qū)各車(chē)道的長(zhǎng)度和容量固定，需同時(shí)作業(yè)任務(wù)量較多時(shí)，多輛AGV可能會(huì)在同一時(shí)間在同一路段向同一方向行駛而產(chǎn)生相向沖突，如圖2（a）所示；可能會(huì)在同一時(shí)間經(jīng)過(guò)同一節(jié)點(diǎn)而產(chǎn)生節(jié)點(diǎn)沖突，如圖2（b）所示；也可能會(huì)在同一路徑上出現(xiàn)擁堵的情況，如圖3所示。本文研究單向?qū)б窂剑床豢紤]圖2（a）所示的相向沖突，僅針對(duì)圖2（b）所示的節(jié)點(diǎn)沖突和圖3所示的路徑擁堵情況進(jìn)行研究。

圖2　沖突示意圖

圖3　路徑擁堵示意圖

2 模型建立

2.1　模型假設(shè)

本文研究基于以下假設(shè)：

1）岸橋和場(chǎng)橋作業(yè)單個(gè)集裝箱的時(shí)間服從均勻分布；

2）待作業(yè)集裝箱位置及裝卸順序已知，岸橋、箱區(qū)的位置已知，AGV運(yùn)輸起點(diǎn)為出口箱所屬堆場(chǎng)和作業(yè)進(jìn)口箱的卸船岸橋，終點(diǎn)為存儲(chǔ)進(jìn)口箱的堆場(chǎng)和作業(yè)出口箱的裝船岸橋；

3）所有待作業(yè)集裝箱箱型一致，所有的進(jìn)口箱運(yùn)送至指定堆場(chǎng)，所有出口箱運(yùn)送至船上指定箱位。

2.2　第一階段AGV調(diào)度優(yōu)化模型

1） 集合、參數(shù)及狀態(tài)變量如下。

2） 決策變量如下。

3） 數(shù)學(xué)模型如下。

第一階段模型目標(biāo)函數(shù)為：

約束條件為：

式（1）為目標(biāo)函數(shù)，表示最大完工時(shí)間最小化，即岸橋提起最后一個(gè)裝船集裝箱或放下最后一個(gè)卸船集裝箱的時(shí)刻；式（2）表示在每輛AGV只能完成一個(gè)集裝箱任務(wù)；式（3）和式（4）表示一個(gè)集裝箱由且僅由一輛AGV運(yùn)輸；式（5）和式（6）表示一個(gè)集裝箱由一臺(tái)岸橋或場(chǎng)橋作業(yè)；式（7）表示更新后的岸橋計(jì)劃作業(yè)時(shí)間；式（8）表示作業(yè)卸船箱的岸橋的實(shí)際作業(yè)時(shí)間；式（9）表示作業(yè)裝船箱的岸橋的實(shí)際作業(yè)時(shí)間；式（10）表示岸橋?qū)嶋H作業(yè)時(shí)間與計(jì)劃作業(yè)時(shí)間之間的關(guān)系；式（11）表示同一岸橋處理的相鄰兩個(gè)任務(wù)的實(shí)際作業(yè)時(shí)間的間隔要滿(mǎn)足計(jì)劃作業(yè)時(shí)間的間隔；式（12）表示AGV運(yùn)輸裝船箱時(shí)在緩沖支架的實(shí)際作業(yè)時(shí)刻滿(mǎn)足時(shí)間窗約束；式（13）表示AGV運(yùn)輸卸船箱時(shí)在緩沖支架的實(shí)際作業(yè)時(shí)刻滿(mǎn)足時(shí)間窗約束；式（14）表示AGV在場(chǎng)橋下取裝船箱時(shí)滿(mǎn)足時(shí)間窗約束；式（15）表示AGV在場(chǎng)橋下取卸船箱時(shí)滿(mǎn)足時(shí)間窗約束；式（16）表示AGV提取卸船集裝箱時(shí)在岸橋下的等待時(shí)間；式（17）表示AGV交付裝船集裝箱時(shí)在岸橋下的等待時(shí)間；式（18）表示AGV交付卸船集裝箱時(shí)在場(chǎng)橋下的等待時(shí)間；式（19）表示AGV提取裝船集裝箱時(shí)在場(chǎng)橋下的等待時(shí)間；式（20）和式（21）表示AGV送完裝船集裝箱后，開(kāi)始作業(yè)下一個(gè)裝船集裝箱或卸船集裝箱的時(shí)間約束；式（22）和式（23）表示AGV送完卸船集裝箱后，作業(yè)下一個(gè)裝船集裝箱或卸船集裝箱的時(shí)間約束；式（24）和式（25）分別表示變量類(lèi)型和取值范圍。

2.3　第二階段AGV調(diào)度優(yōu)化模型

1） 集合、參數(shù)及狀態(tài)變量。

2）決策變量。

x為第輛AGV從節(jié)點(diǎn)到節(jié)點(diǎn)時(shí)為1，否則為0。

第二階段模型目標(biāo)函數(shù)為：

約束條件為：

式（26）為目標(biāo)函數(shù)，表示最小化AGV的總行駛時(shí)間；式（27）和式（28）表示完成每個(gè)任務(wù)的AGV在每個(gè)節(jié)點(diǎn)至多行駛一次，避免AGV路徑重疊，造成道路死鎖；式（29）表示一個(gè)集裝箱由且僅由一輛AGV運(yùn)輸；式（30）表示路徑網(wǎng)絡(luò)為單向?qū)б窂健?/p>

兩輛AGV通過(guò)同一節(jié)點(diǎn)，如圖5所示。

圖4　AGV路段示意圖

圖5　AGV節(jié)點(diǎn)沖突示意圖

式（33）表示AGV在路徑1和2中存在的相同節(jié)點(diǎn)；式（34）和式（35）表示AGV在相同節(jié)點(diǎn)的時(shí)間檢測(cè)，若兩臺(tái)AGV通過(guò)相同節(jié)點(diǎn)的時(shí)間差小于AGV1順利通過(guò)并與AGV2保持安全距離的時(shí)間，則說(shuō)明發(fā)生沖突。

式（36）表示AGV路徑中重疊路段的檢測(cè)；式（37）表示路段e可容納AGV的數(shù)量，Round（）為向下取整函數(shù)；式（38）表示AGV在路段e上任意時(shí)刻的車(chē)輛數(shù)不能超過(guò)路段容量。

3 模型求解

本文針對(duì)建立的兩階段優(yōu)化模型，設(shè)計(jì)改進(jìn)的自適應(yīng)遺傳算法（Improved Adaptive Genetic Algorithm，IAGA）求解AGV調(diào)度問(wèn)題，設(shè)計(jì)基于沖突擁堵解決策略的迪杰斯特拉（Dijkstra）算法求解AGV的無(wú)沖突路徑規(guī)劃問(wèn)題。將Dijkstra算法與IAGA相結(jié)合，設(shè)計(jì)滿(mǎn)足約束條件的編碼規(guī)則和符合優(yōu)化目標(biāo)的適應(yīng)度函數(shù)，求得各AGV的調(diào)度方案和無(wú)沖突最短路徑，如圖6所示。

圖6　改進(jìn)的自適應(yīng)遺傳算法與迪杰斯特拉算法流程

3.1　第一階段模型求解

第一階段模型是研究AGV調(diào)度問(wèn)題為NP-hard問(wèn)題，在現(xiàn)有研究中，遺傳算法廣泛應(yīng)用于AGV的調(diào)度研究中。傳統(tǒng)的遺傳算法收斂速度慢且容易陷入局部最優(yōu)，因此本文根據(jù)問(wèn)題特點(diǎn)設(shè)計(jì)IAGA對(duì)模型求解，具體步驟如下：

1） 染色體編碼。

本文算法采用實(shí)數(shù)編碼方式，以便于解碼操作和基因操作。染色體長(zhǎng)度為待卸集裝箱數(shù)量，即作業(yè)任務(wù)數(shù)，因此編碼長(zhǎng)度由集裝箱數(shù)量決定，染色體生產(chǎn)中每條染色體長(zhǎng)度均為。初始化時(shí)在染色體每個(gè)基因位上設(shè)置為［1，］（為AGV數(shù)量）的隨機(jī)數(shù)，代表AGV編號(hào)。如圖7所示的染色體，假設(shè)待卸集裝箱數(shù)量為10，由3輛AGV運(yùn)輸集裝箱，AGV1按3-6-7的作業(yè)順序，AGV2按5-8的作業(yè)順序，AGV3按1-2-4-9-10的作業(yè)順序。

圖7　染色體編碼示意圖

2） 修復(fù)。

為滿(mǎn)足種群多樣性，通過(guò)隨機(jī)方式產(chǎn)生初始種群。由于每個(gè)AGV至少分配到一個(gè)任務(wù)的約束，隨機(jī)方式產(chǎn)生初始解會(huì)存在不滿(mǎn)足約束的情況，需要對(duì)不合理基因位上的解進(jìn)行修復(fù)，如圖8所示，使其滿(mǎn)足約束。在式（2）～（6）的約束條件下生成一定數(shù)量的個(gè)體，其中染色體每個(gè)基因位上隨機(jī)生成［1，］的AGV編號(hào)，所有個(gè)體構(gòu)成初始種群。

圖8　染色體修復(fù)示意圖

3） 適應(yīng)度函數(shù)。

目標(biāo)函數(shù)的計(jì)算流程如圖9所示。

圖9　目標(biāo)函數(shù)求解流程

鑒于本文模型以總?cè)蝿?wù)最大完工時(shí)間最小化為目標(biāo)，算法中取目標(biāo)函數(shù)的倒數(shù)為適應(yīng)度函數(shù)，適應(yīng)度值高的個(gè)體直接進(jìn)入下一代，具體適應(yīng)度函數(shù)如下：

其中：f為個(gè)體的適應(yīng)度；（）為個(gè)體的目標(biāo)函數(shù)值。

4）選擇操作。

在遺傳算法運(yùn)行中，如果只使用輪盤(pán)賭選擇算子而不用精英保留策略，交叉、變異會(huì)破壞適應(yīng)度好的染色體，有可能會(huì)失去優(yōu)良的染色體。精英保留策略能夠?qū)⑦m應(yīng)度最大的染色體保留下來(lái)，防止被交叉、變異破壞，使得整個(gè)種群向全局最優(yōu)解方向進(jìn)化。

5）交叉與變異。

遺傳算法收斂速度和搜索能力受到交叉概率和變異概率的影響，二者的取值至關(guān)重要。為提高算法的性能，本文借鑒文獻(xiàn)［24］的交叉概率和變異概率公式，引入自適應(yīng)交叉概率和自適應(yīng)變異概率，具體表達(dá)如式（40）～（41）：

本文采用兩點(diǎn)交叉的方式如圖10所示，在染色體中設(shè)置兩個(gè)交叉點(diǎn)，相互兩個(gè)交叉點(diǎn)之間的部分，產(chǎn)生新的染色體，同時(shí)結(jié)合自適應(yīng)交叉概率，既能保證交叉操作的全局搜索能力，又能保證優(yōu)良染色體最大概率地保留到子代中。

變異與交叉類(lèi)似，如圖11所示，在染色體中設(shè)置兩個(gè)不同基因位置，交換這兩個(gè)位置上的基因，即能變異得到新染色體，同時(shí)結(jié)合自適應(yīng)變異概率，既能充分發(fā)揮變異操作的局部搜索能力，又能避免遺傳算法陷入局部最優(yōu)。

圖10　染色體交叉操作示意圖

圖11　染色體變異操作示意圖

3.2　第二階段模型求解

第二階段模型是AGV路徑規(guī)劃模型，模型求解主要分為三個(gè)部分：

1）利用Dijkstra算法計(jì)算各AGV完成任務(wù)所遍歷的節(jié)點(diǎn)，得到各AGV的最短行駛路徑，在最短路徑有數(shù)條的情況下，依據(jù)路徑轉(zhuǎn)折數(shù)確定優(yōu)先級(jí)來(lái)生成最短路徑。

2）檢測(cè)各AGV是否發(fā)生沖突和擁堵，檢測(cè)流程如圖12、13所示。

圖12　節(jié)點(diǎn)沖突檢測(cè)流程

圖13　路徑擁堵檢測(cè)流程

具體步驟如下：

步驟1 輸入每輛AGV的路徑，中包含節(jié)點(diǎn)集合和路段集合，根據(jù)式（31）～（32）計(jì)算AGV經(jīng)過(guò)每個(gè)節(jié)點(diǎn)和路段的時(shí)間。

3）基于沖突擁堵解決策略為各AGV規(guī)劃出一條無(wú)沖突最短行駛路徑，有效解決AGV沖突擁堵，減小沖突和擁堵概率。

4 算例分析

本文選取不同規(guī)模算例，將IAGA與遺傳算法（GA）進(jìn)行比較驗(yàn)證本文算法的有效性。對(duì)比考慮沖突、擁堵解決策略和不考慮沖突、擁堵解決策略的AGV路徑規(guī)劃的效果，驗(yàn)證了本文基于沖突、擁堵解決策略的有效性。本文算法編程采用Matlab R2018b，操作系統(tǒng)為Windows 10，電腦內(nèi)存為8 GB，CPU為Intel i7-7700M，主頻3.60 GHz。

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

1）以圖1的碼頭布局為模型，參考文獻(xiàn)［25］中的AGV路網(wǎng)布局，如圖14所示。圖中一共有69個(gè)節(jié)點(diǎn)以模擬磁釘點(diǎn)，線(xiàn)段為有向線(xiàn)段，車(chē)道長(zhǎng)200 m，岸橋作業(yè)區(qū)寬10 m，緩沖行駛區(qū)寬60 m，堆場(chǎng)行駛區(qū)車(chē)道寬為10 m。

圖14　自動(dòng)化集裝箱碼頭路徑網(wǎng)絡(luò)布局示意圖

Q1～Q3是岸橋所在位置，B1～B6是箱區(qū)所在位置。其中B1～B2為進(jìn)口箱區(qū)，B3～B6為出口箱區(qū)，占據(jù)的節(jié)點(diǎn)編號(hào)如表1所示。

表1　岸橋及箱區(qū)的節(jié)點(diǎn)編號(hào)對(duì)照

2）模型參數(shù)取值為：=21～300；=3～6；=3；=6；=6；=6；=5 m/s；=5 m；H=5 m。

3）岸橋作業(yè)完上一個(gè)出口箱繼續(xù)作業(yè)下一個(gè)出口箱的作業(yè)時(shí)間為α=U（40，60） s；岸橋作業(yè)完進(jìn)口箱作業(yè)下一個(gè)進(jìn)口箱的作業(yè)時(shí)間為α=U（40，60） s；岸橋作業(yè)完出口箱作業(yè)下一個(gè)進(jìn)口箱的作業(yè)時(shí)間為α=U（60，80） s；岸橋作業(yè)完進(jìn)口箱作業(yè)下一個(gè)出口箱的作業(yè)時(shí)間為α=U（20，40） s。

4）場(chǎng)橋作業(yè)時(shí)間為β=U（80，120） s。

5）本文算法參數(shù)設(shè)置如下：種群規(guī)模=100，最大迭代次數(shù)=200；自適應(yīng)參數(shù)設(shè)置P1=0.6，P2=0.01，P1=0.01，P2=0.002。

4.2　算法驗(yàn)證與結(jié)果分析

表2　算例對(duì)比結(jié)果

此外，由算例1、2、4和6，算例3、5、7、9、11和13，算例8、10、12和14可知，在相同設(shè)備配置的情況下，增加集裝箱任務(wù)數(shù)量會(huì)導(dǎo)致目標(biāo)函數(shù)值增加，即最大完工時(shí)間增加；由算例2和3，算例4和5，算例6、7和8，算例8和9，算例9和10，算例11和12，算例，13和14可知，增加AGV的數(shù)量會(huì)導(dǎo)致目標(biāo)函數(shù)值減小。由此可知，合理配置AGV的數(shù)量能夠提高碼頭的裝卸效率。

4.3　策略有效性驗(yàn)證

為驗(yàn)證本文第二階段沖突、擁堵解決策略的有效性，以算例3為例，對(duì)42個(gè)集裝箱任務(wù)、6輛AGV進(jìn)行實(shí)驗(yàn)，任務(wù)分配如表3所示。

表3　任務(wù)分配

1）AGV調(diào)度結(jié)果。

采用Matlab進(jìn)行編程求解，求得最大完工時(shí)間為988 s，AGV調(diào)度方案如表4所示。

表4　AGV調(diào)度結(jié)果

2）路徑規(guī)劃結(jié)果分析與對(duì)比。

本算例根據(jù)圖15自動(dòng)化集裝箱碼頭路網(wǎng)，通過(guò)Dijkstra算法得出AGV總行駛時(shí)間為2 438 s，完成任務(wù)的行駛路徑如表5～10所示。

表5　AGV1完成任務(wù)的路徑

表6　AGV2完成任務(wù)的路徑

表7　AGV3完成任務(wù)的路徑

表8　AGV4完成任務(wù)的路徑

表9　AGV5完成任務(wù)的路徑

表10　AGV6完成任務(wù)的路徑

圖15顯示了不考慮沖突、擁堵解決策略的各AGV行駛路徑和作業(yè)時(shí)間，如AGV2開(kāi)始作業(yè)第1個(gè)時(shí)間段是0 s～28 s，將裝船箱8從箱區(qū)B4送至岸橋Q3，在自動(dòng)化集裝箱碼頭路網(wǎng)從節(jié)點(diǎn)64運(yùn)送至節(jié)點(diǎn)13；第2個(gè)時(shí)間段是147 s～197 s，AGV2完成上一裝船箱8直接在岸橋Q3作業(yè)下一卸船箱10，將卸船箱從岸橋Q3送至箱區(qū)B2，從節(jié)點(diǎn)13運(yùn)送至節(jié)點(diǎn)60；第3個(gè)時(shí)間段是197 s～227 s，AGV2完成卸船箱10后前往下一卸船箱13所在岸橋Q1，從節(jié)點(diǎn)60到節(jié)點(diǎn)3；第4個(gè)時(shí)間段是285 s～307 s，AGV2作業(yè)卸船箱13從岸橋Q1送至箱區(qū)B2，從節(jié)點(diǎn)3到節(jié)點(diǎn)60；第5個(gè)時(shí)間段是307 s～335 s，AGV2作業(yè)完卸船箱13從箱區(qū)B2作業(yè)下一卸船箱18所在岸橋Q2，從節(jié)點(diǎn)60到節(jié)點(diǎn)8；第6個(gè)時(shí)間段是340 s～376 s，AGV2作業(yè)卸船箱18從岸橋Q2到箱區(qū)B2，從節(jié)點(diǎn)8到節(jié)點(diǎn)60；第7個(gè)時(shí)間段是376 s～394 s，AGV2作業(yè)完卸船箱18從箱區(qū)B2作業(yè)下一裝船箱28所在的箱區(qū)B4，從節(jié)點(diǎn)60到節(jié)點(diǎn)64；第8個(gè)時(shí)間段是410 s～440 s，AGV2作業(yè)裝船箱28從箱區(qū)B4到岸橋Q2，從節(jié)點(diǎn)64到節(jié)點(diǎn)8；第9個(gè)時(shí)間段是568 s～596 s，AGV2作業(yè)完裝船箱28從岸橋Q2開(kāi)始作業(yè)下一裝船箱33所在的箱區(qū)B5，從節(jié)點(diǎn)8到節(jié)點(diǎn)67；第10個(gè)時(shí)間段是596 s～646 s，AGV2作業(yè)裝船箱33從箱區(qū)B5到岸橋Q1，從節(jié)點(diǎn)67到節(jié)點(diǎn)3。

圖15　不考慮沖突、擁堵因素的AGV行駛路徑

AGV在行駛過(guò)程中發(fā)生的路徑擁堵已在圖15中用黑圈示出，節(jié)點(diǎn)沖突用黑框示出，時(shí)間表如表11、12所示。

由表11、12可知：AGV2與AGV5分別在節(jié)點(diǎn)67、66、65、64、63發(fā)生沖突，AGV2與AGV6在節(jié)點(diǎn)3發(fā)生沖突，AGV4與AGV6在節(jié)點(diǎn)60發(fā)生沖突，AGV1與AGV4分別在節(jié)點(diǎn)64、63、51、37、22、7、8發(fā)生沖突，AGV1與AGV6分別在節(jié)點(diǎn)64、63發(fā)生沖突；AGV4與AGV6分別在路段67-66、66-65、65-64發(fā)生擁堵，AGV2與AGV5分別在路段67-66、66-65、65-64發(fā)生擁堵。通過(guò)停車(chē)等待策略解決沖突擁堵，AGV等待時(shí)間為27 s，水平運(yùn)輸區(qū)擁堵度為1.11%。

基于本文沖突擁堵解決策略，AGV2與AGV5分別在177 s、176 s通過(guò)節(jié)點(diǎn)67開(kāi)始發(fā)生沖突，AGV2在節(jié)點(diǎn)67停車(chē)等待1 s；AGV2與AGV6在285 s通過(guò)節(jié)點(diǎn)3發(fā)生沖突，AGV2在節(jié)點(diǎn)3停車(chē)等待2 s；AGV4與AGV6在353 s通過(guò)節(jié)點(diǎn)60發(fā)生沖突，AGV4在節(jié)點(diǎn)60等待2 s；AGV4與AGV6在393 s通過(guò)路段67-66開(kāi)始發(fā)生沖突、擁堵，AGV4在節(jié)點(diǎn)67停車(chē)等待2 s；AGV1與AGV4和AGV6分別在400 s、399 s通過(guò)節(jié)點(diǎn)64開(kāi)始發(fā)生沖突，AGV1在節(jié)點(diǎn)64停車(chē)等待2 s，AGV總停車(chē)等待9 s，水平運(yùn)輸區(qū)擁堵度為0.36%。

本文沖突擁堵解決策略比停車(chē)等待策略解決沖突擁堵所用時(shí)間更短，采用本文沖突擁堵解決策略水平運(yùn)輸區(qū)擁堵度降低67.6%，AGV等待時(shí)間減少66.7%。

考慮沖突、擁堵因素，基于沖突擁堵解決策略下AGV行駛路徑如圖16所示。

對(duì)比圖15、16可知，基于沖突擁堵解決策略能為各AGV規(guī)劃出一條無(wú)沖突最短行駛路徑，采用本文基于沖突擁堵解決策略能有效解決節(jié)點(diǎn)沖突，降低了擁堵程度，避免重新進(jìn)行任務(wù)調(diào)度和路徑規(guī)劃而產(chǎn)生的新沖突和擁堵。

圖16　考慮沖突、擁堵因素的AGV行駛路徑

表11　AGV節(jié)點(diǎn)沖突時(shí)間表

表12　AGV路段擁堵時(shí)間表

5 結(jié)語(yǔ)

本文針對(duì)自動(dòng)化碼頭多AGV調(diào)度和路徑規(guī)劃問(wèn)題展開(kāi)研究，分析自動(dòng)化集裝箱碼頭實(shí)際作業(yè)流程并結(jié)合自動(dòng)化碼頭路徑網(wǎng)路空間布局結(jié)構(gòu)，考慮緩沖支架容量約束以及沖突和擁堵等，以最大完工時(shí)間最小為第一階段優(yōu)化目標(biāo)、AGV總行駛時(shí)間最短為第二階段優(yōu)化目標(biāo)建立兩階段混合整數(shù)規(guī)劃模型。針對(duì)該模型，設(shè)計(jì)了IAGA求解第一階段模型的AGV調(diào)度方案，采用精英保留和輪盤(pán)賭相結(jié)合的選擇操作，保證了算法的有效收斂，同時(shí)結(jié)合自適應(yīng)交叉概率和自適應(yīng)變異概率，既能保證遺傳算法的全局搜索能力，又能避免遺傳算法陷入局部最優(yōu)；設(shè)計(jì)了基于沖突擁堵解決策略的Dijkstra算法求解第二階段模型，可得調(diào)度方案下各AGV的無(wú)沖突路徑。算例分析結(jié)果表明，IAGA比GA求解速度快且質(zhì)量高；與停車(chē)等待策略相比，本文策略能降低水平運(yùn)輸區(qū)擁堵度，降低程度為67.6%。

本文的研究較符合實(shí)際自動(dòng)化集裝箱碼頭船舶裝卸過(guò)程，但還存在一些不足，在實(shí)際作業(yè)過(guò)程中未考慮不確定因素，在實(shí)際作業(yè)過(guò)程中岸橋和AGV的故障、AGV電量不足等不確定情況也會(huì)影響裝卸作業(yè)時(shí)間，這些都有待于未來(lái)進(jìn)一步的研究。

[1] BAE J W， KIM K H. A pooled dispatching strategy for automated guided vehicles in port container terminals［J］. Management Science and Financial Engineering， 2000， 6（2）：47-67.

[2] 梁承姬，申哲，張悅. 干擾約束下考慮分組作業(yè)面的岸橋AGV聯(lián)合調(diào)度［J］. 計(jì)算機(jī)工程與應(yīng)用， 2020， 56（18）：254-261.（LIANG C J， SHEN Z， ZHANG Y. Quay crane and AGV joint scheduling with grouping work surface under interference constraints［J］. Computer Engineering and Applications， 2020， 56（18）：254-261.）

[3] 田宇，周強(qiáng)，朱本飛. 自動(dòng)化集裝箱碼頭雙循環(huán)AGV與場(chǎng)橋的集成調(diào)度研究［J］. 交通運(yùn)輸系統(tǒng)工程與信息， 2020， 20（4）：216-223， 243.（TIAN Y， ZHOU Q， ZHU B F. Integrated scheduling of dual-cycle AGV and yard crane at automated container terminal［J］. Journal of Transportation Systems Engineering and Information Technology， 2020， 20（4）：216-223， 243.）

[4] 范厚明，郭振峰，岳麗君，等. 考慮能耗節(jié)約的集裝箱碼頭雙小車(chē)岸橋與AGV聯(lián)合配置及調(diào)度優(yōu)化［J］. 自動(dòng)化學(xué)報(bào)， 2021， 47（10）： 2412-2426.（FAN H M， GUO Z F， YUE L J， et al. Joint configuration and scheduling optimization of dual-trolley quay crane and AGV for container terminal with considering energy saving［J］. Acta Automatica Sinica， 2021， 47（10）： 2412-2426.）

[5] LI Z H， YU T， CHEN Y X， et al. Multi-objective optimization dispatching strategy for wind-thermal-storage generation system incorporating temporal and spatial distribution control of air pollutant dispersion［J］. IEEE Access， 2020， 8： 44263-44275.

[6] 韓曉龍，樊加偉. 自動(dòng)化港口AGV調(diào)度配置仿真分析［J］. 重慶交通大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2016， 35（5）：151-154， 164.（HAN X L， FAN J W. Analysis of AGV dispatching and configuration simulation of automated container terminals［J］. Journal of Chongqing Jiaotong University （Natural Science）， 2016， 35（5）：151-154， 164.）

[7] 吳洪明，鄒夢(mèng)艷. 考慮電池電量約束的自動(dòng)化碼頭AGV調(diào)度［J］. 起重運(yùn)輸機(jī)械， 2021（3）：47-52.（WU H M， ZOU M Y. AGV scheduling of automated terminal considering battery power constraints［J］. Hoisting and Conveying Machinery， 2021（3）：47-52.）

[8] 鄭亞紅，徐玖龍，謝淳. 自動(dòng)化集裝箱碼頭AGV換電管理與調(diào)度優(yōu)化［J］. 武漢理工大學(xué)學(xué)報(bào)（交通科學(xué)與工程版） ，2021， 45（1）：1-6.（ZHENG Y H， XU J L， XIE C. Electricity exchange management and scheduling optimization of AGV in automated container terminal［J］. Journal of Wuhan University of Technology （Transportation Science and Engineering）， 2021， 45（1）：1-6.）

[9] 文家獻(xiàn)，魏晨，尹宇起，等. 考慮堆場(chǎng)緩沖區(qū)容量的ASC與AGV集成調(diào)度［J］. 計(jì)算機(jī)工程與應(yīng)用， 2020， 56（11）：238-245.（WEN J X， WEI C， YIN Y Q， et al. Integrated scheduling of ASC and AGV considering block buffer capacity［J］. Computer Engineering and Applications， 2020， 56（11）：238-245.）

[10] 程聰聰，梁承姬，李曄. 自動(dòng)化集裝箱港口考慮AGV伴侶的AGV調(diào)度優(yōu)化問(wèn)題研究［J］. 計(jì)算機(jī)應(yīng)用研究， 2019， 36（8）：2349-2354.（CHENG C C， LIANG C J， LI Y. Study on AGV scheduling with considering AGV partner in automated container ports［J］. Application Research of Computers， 2019， 36（8）：2349-2354.）

[11] 鄒裕吉，宋豫川，王馨坤，等. 多目標(biāo)自適應(yīng)聚類(lèi)遺傳算法求解無(wú)路徑?jīng)_突的AGV與加工設(shè)備集成調(diào)度問(wèn)題［J/OL］. 中國(guó)機(jī)械工程. （2021-04-28） ［2021-05-10］.http：//kns.cnki.net/kcms/detail/42.1294.TH.20210428.1022.002.html.（ZOU Y J， SONG Y C， WANG X K， et al. Multi-objective adaptive clustering genetic algorithm to solve the AGVs and machine integrated scheduling problem without path conflict［J/OL］. China Mechanical Engineering. （2021-04-28） ［2021-05-10］.http：//kns.cnki.net/kcms/detail/42.1294.TH.20210428.1022.002.html.）

[12] 鄧希，胡曉兵，江代渝，等. 基于混合遺傳算法的柔性作業(yè)車(chē)間機(jī)器和AGV規(guī)劃［J］. 四川大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2021， 58（2）：73-82.（DENG X， HU X B， JIANG D Y， et al. A hybrid GA approach to the scheduling of machines and automated guided vehicles in flexible job shops［J］. Journal of Sichuan University （Natural Science Edition）， 2021， 58（2）：73-82.）

[13] FANTI M P， MANGINI A M， PEDRONCELLI G， et al. A decentralized control strategy for the coordination of AGV systems［J］. Control Engineering Practice， 2018， 70：86-97.

[14] 高一鷺，胡志華. 基于時(shí)空網(wǎng)絡(luò)的自動(dòng)化集裝箱碼頭自動(dòng)化導(dǎo)引車(chē)路徑規(guī)劃［J］. 計(jì)算機(jī)應(yīng)用， 2020， 40（7）：2155-2163.（GAO Y L， HU Z H. Path planning for automated guided vehicles based on tempo-spatial network at automated container terminal［J］. Journal of Computer Applications， 2020， 40（7）：2155-2163.）

[15] 曾慶成，李明澤，薛廣順. 考慮擁堵因素的自動(dòng)化碼頭多AGV無(wú)沖突動(dòng)態(tài)路徑規(guī)劃模型［J］. 大連海事大學(xué)學(xué)報(bào)， 2019， 45（4）：35-44.（ZENG Q C， LI M Z， XUE G S. Multiple AGV conflict-free dynamic routing model in automated terminals considering congestion factors［J］. Journal of Dalian Maritime University， 2019， 45（4）：35-44.）

[16] 仲美穌，楊勇生. 卸船作業(yè)模式下自動(dòng)化碼頭AGV路徑仿真優(yōu)化［J］.水運(yùn)工程， 2018（4）：122-127.（ZHONG M S， YANG Y S. Based on discharging operation mode automation terminal of AGV path simulation optimization［J］. Port and Waterway Engineering， 2018（4）：122-127.）

[17] XIN J B， NEGENBORN R R， LODEWIJKS G. Trajectory planning for AGVs in automated container terminals using avoidance constraints： a case study［J］. IFAC Proceedings Volumes， 2014， 47（3）：9828-9833.

[18] NISHI T， HIRANAKA Y， GROSSMANN I E. A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles［J］. Computers and Operations Research， 2011， 38（5）： 876-888.

[19] FAZLOLLAHTABAR H， SAIDI-MEHRABAD M， MASEHIAN E. Mathematical model for deadlock resolution in multiple AGV scheduling and routing network： a case study［J］. Industrial Robot， 2015， 42（3）： 252-263.

[20] SAIDI-MEHRABAD M， DEHNAVI-ARANI S， EVAZABADIAN F， et al. An Ant Colony Algorithm （ACA） for solving the new integrated model of job shop scheduling and conflict-free routing of AGVs［J］. Computers and Industrial Engineering， 2015， 86：2-13.

[21] MIYAMOTO T， INOUE K. Local and random searches for dispatch and conflict-free routing problem of capacitated AGV systems［J］. Computers and Industrial Engineering， 2016， 91：1-9.

[22] YANG Y S， ZHONG M S， DESSOUKY Y， et al. An integrated scheduling method for AGV routing in automated container terminals［J］. Computers and Industrial Engineering， 2018， 126：482-493.

[23] ZHONG M S， YANG Y S， DESSOUKY Y， et al. Multi-AGV scheduling for conflict-free path planning in automated container terminals［J］. Computers and Industrial Engineering， 2020， 142： No.106371.

[24] 吳聰，陳侃松，姚靜. 基于改進(jìn)自適應(yīng)遺傳算法的物流配送路徑優(yōu)化研究［J］. 計(jì)算機(jī)測(cè)量與控制， 2018， 26（2）：236-240.（WU C， CHEN K S， YAO J. Study on optimization of logistics distribution route based on improved adaptive genetic algorithm［J］. Computer Measurement and Control， 2018， 26（2）：236-240.）

[25] 張素云，楊勇生，梁承姬，等. 自動(dòng)化碼頭多AGV路徑?jīng)_突的優(yōu)化控制研究［J］. 交通運(yùn)輸系統(tǒng)工程與信息， 2017， 17（2）：83-89.（ZHANG S Y， YANG Y S， LIANG C J， et al. Optimal control of multiple AGV path conflict in automated terminals［J］. Journal of Transportation Systems Engineering and Information Technology， 2017， 17（2）：83-89.）

FAN Houming， born in 1962， Ph. D.， professor. His research interests include transportation system planning and design.

MU Shuang， born in 1995， M. S. candidate. Her research interests include transportation engineering.

YUE Lijun， born in 1995， Ph. D. candidate. Her research interests include transportation planning and management.

Collaborative optimization of automated guided vehicle scheduling and path planning considering conflict and congestion

FAN Houming， MU Shuang， YUE Lijun*

（，，116026，）

In order to solve the problems of Automated Guided Vehicle （AGV） scheduling and conflict-free path planning in automated container terminals， an AGV conflict and congestion resolution strategy was proposed to generate conflict-free paths. Firstly， considering the capacity of the buffer bracket in the container yard as well as the constraints of no congestion on the operation paths and no conflict on the nodes， a two-stage mixed integer programming model was established based on the goal of the smallest maximum completion time and the shortest AGV transportation time. Then， an improved adaptive genetic algorithm and Dijkstra algorithm based on conflict and congestion resolution strategy were designed to obtain the AGV scheduling scheme and conflict-free paths. The results of numerical examples show that the improved adaptive genetic algorithm has the average solution time reduced by 13.56%， and the average gap rate of the objective function reduced by 9.01% compared to the genetic algorithm. Compared with the parking to wait strategy， the conflict and congestion resolution strategy has the congestion rate of the horizontal transportation area reduced by 67.6%， and the AGV waiting time reduced by 66.7%. It can be seen that the proposed algorithm has higher solving quality and faster speed， at the same time， the effectiveness of the proposed strategy is verified.

adaptive genetic algorithm; automated container terminal; Automated Guided Vehicle (AGV) scheduling; conflict-free path planning; conflict and congestion

This work is partially supported by Project of Dalian Science and Technology Innovation Fund （2020JJ26GX033）.

1001-9081（2022）07-2281-11

10.11772/j.issn.1001-9081.2021050819

2021?05?19；

2022?02?21；

2022?05?25。

大連市科技創(chuàng)新基金資助項(xiàng)目（2020JJ26GX033）。

TP18

A

范厚明（1962—），男，山東蓬萊人，教授，博士生導(dǎo)師，博士，主要研究方向：交通運(yùn)輸系統(tǒng)規(guī)劃與設(shè)計(jì)； 牟爽（1995—），女，山東煙臺(tái)人，碩士研究生，主要研究方向：交通運(yùn)輸工程； 岳麗君（1995—），女，河南濮陽(yáng)人，博士研究生，主要研究方向：交通運(yùn)輸規(guī)劃與管理。