自動(dòng)化集裝箱碼頭自動(dòng)導(dǎo)引車路徑?jīng)_突規(guī)避優(yōu)化策略

章文俊 韓曉龍

自動(dòng)導(dǎo)引車（automated guided vehicle，AGV）是自動(dòng)化集裝箱碼頭的主要運(yùn)輸設(shè)備，用于在碼頭前沿與后方堆場(chǎng)之間水平運(yùn)輸集裝箱。AGV的作業(yè)效率不僅受其自身性能的影響，而且受碼頭布局、行駛路徑和道路容量等因素的影響。在碼頭作業(yè)高峰期，隨著AGV行駛路徑的不斷重疊，可能會(huì)產(chǎn)生AGV路徑?jīng)_突問題，導(dǎo)致AGV作業(yè)效率下降。為了解決AGV路徑?jīng)_突問題，本文在傳統(tǒng)的速度控制策略的基礎(chǔ)上，提出基于道路容量的速度控制與路徑再規(guī)劃相結(jié)合的優(yōu)化策略，并通過算例分析驗(yàn)證優(yōu)化策略的有效性和優(yōu)越性。

1 研究背景

AGV路徑?jīng)_突規(guī)避涉及對(duì)AGV的實(shí)時(shí)控制，已有的研究成果包括：YANG等[1]提出一種用于作業(yè)設(shè)備協(xié)調(diào)和AGV路徑規(guī)劃的整體調(diào)度方案，建立以作業(yè)時(shí)間最短為目標(biāo)的雙層規(guī)劃模型;柯冉絢等[2]建立以無效作業(yè)時(shí)間最短為目標(biāo)的數(shù)學(xué)模型，并采用Netlogo仿真軟件驗(yàn)證作業(yè)面調(diào)度模式的優(yōu)越性;GRUNOW等[3]分析自動(dòng)化集裝箱碼頭應(yīng)用環(huán)境的特點(diǎn)及其對(duì)AGV調(diào)度問題的影響，并考慮多種解決方案;GHASEMZADEH等[4]提出網(wǎng)狀拓?fù)湎到y(tǒng)中AGV調(diào)度和路徑規(guī)劃算法;肖海寧等[5]針對(duì)單向?qū)б窂骄W(wǎng)絡(luò)中AGV碰撞和系統(tǒng)死鎖問題，提出一種規(guī)避環(huán)路死鎖搜索方法，定義單環(huán)路和多環(huán)路死鎖臨界狀態(tài)，并設(shè)計(jì)相應(yīng)的死鎖控制策略;UMAR等[6]采用基于優(yōu)先級(jí)的遺傳算法研究AGV路徑規(guī)劃問題，從而使AGV行駛時(shí)間最短;王佳溶等[7]提出基于改進(jìn)后的兩階段控制策略和多目標(biāo)的帶約束遺傳算法的控制策略，并采用速度控制方法解決AGV路徑?jīng)_突問題，從而實(shí)現(xiàn)對(duì)AGV的優(yōu)化調(diào)度;馮海雙[8]采用A*算法檢測(cè)AGV路徑?jīng)_突情況，并設(shè)置安全距離以規(guī)避沖突;張素云等[9]提出一種改進(jìn)的速度控制策略，根據(jù)AGV通過路口節(jié)點(diǎn)的優(yōu)先級(jí)來控制AGV的速度;仲美酥等[10]提出交通虛擬環(huán)島策略來避免AGV在行駛過程中產(chǎn)生沖突和擁堵。

從已有的研究成果來看，AGV路徑?jīng)_突問題最終還是要通過AGV路徑規(guī)劃來解決。部分學(xué)者采用速度控制策略規(guī)避AGV路徑?jīng)_突，雖然有一定成效，但仍然存在不足之處。本文在傳統(tǒng)的速度控制策略的基礎(chǔ)上，提出基于道路容量的速度控制與路徑再規(guī)劃相結(jié)合的優(yōu)化策略。首先，分析常見的AGV路徑?jīng)_突形式;然后，分別構(gòu)建道路容量檢測(cè)模型、速度控制模型以及速度控制與路徑再規(guī)劃相結(jié)合模型;最后，利用eM-Plant生產(chǎn)系統(tǒng)仿真軟件構(gòu)建自動(dòng)化集裝箱碼頭AGV仿真路網(wǎng)，通過算例分析驗(yàn)證速度控制與路徑再規(guī)劃相結(jié)合策略的有效性和優(yōu)越性。

2 問題描述

如圖1所示：自動(dòng)化集裝箱碼頭的主要作業(yè)區(qū)域包括船舶裝卸作業(yè)區(qū)、水平運(yùn)輸作業(yè)區(qū)和堆場(chǎng)作業(yè)區(qū)，分別由岸橋、AGV和場(chǎng)橋完成相應(yīng)的作業(yè)。在碼頭作業(yè)高峰期，整個(gè)水平運(yùn)輸系統(tǒng)處于繁忙狀態(tài)，AGV在路徑節(jié)點(diǎn)處發(fā)生沖突的情形增加，從而造成道路擁堵，進(jìn)而導(dǎo)致碼頭整體作業(yè)效率下降。AGV路徑?jīng)_突形式包括：（1）AGV沿同一路徑同向而行（見圖2a）），且后車速度比前車快;（2）AGV沿同一路徑相向而行（見圖2b））;（3）不同路徑的AGV同時(shí)到達(dá)同一路口節(jié)點(diǎn)（見圖2c））;（4）AGV長(zhǎng)時(shí)間占據(jù)路口節(jié)點(diǎn)（見圖4d）），且相應(yīng)路徑剩余容量不足。目前已建成的自動(dòng)化集裝箱碼頭大多采用單向?qū)б窂?，并且設(shè)有多個(gè)緩沖區(qū);因此，圖2a）和圖2b）所示的AGV路徑?jīng)_突形式少見，圖2c）和圖2d）所示的AGV路徑?jīng)_突形式最為常見。本文主要研究圖2c）和圖2d）所示的AGV路徑?jīng)_突形式。

3 模型構(gòu)建

3.1 假設(shè)條件

（1）泊位數(shù)量與岸橋數(shù)量之比為1∶3，岸橋在其作業(yè)區(qū)域內(nèi)的位移忽略不計(jì)。

（2）岸橋單箱作業(yè)時(shí)間為100～120 s，AGV在岸橋下的作業(yè)時(shí)間服從（100，120）的整數(shù)分布。

（3）岸橋下方和堆場(chǎng)均設(shè)有緩沖區(qū)，AGV在緩沖區(qū)等待作業(yè)時(shí)產(chǎn)生的路徑?jīng)_突忽略不計(jì)。

（4）不考慮設(shè)備故障等因素的影響。

3.2 符號(hào)說明

用賦權(quán)有向圖G=（S，N）表示AGV路網(wǎng)布局。當(dāng)規(guī)劃多條AGV路徑時(shí)，S為邊集，Sk（i，j）=（ni，nj）為路徑k上第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)的邊，N為AGV路網(wǎng)中所有節(jié)點(diǎn)的集合。為了便于建模，引入以下符號(hào)：L為AGV的長(zhǎng)度;Ls為行駛過程中AGV之間的安全距離;Pk為第k條路徑，k=1，2，3，…，K;K為AGV路徑的集合，k∈K;Dk為路徑k的長(zhǎng)度;R（Pk）為路徑k的道路容量;E（Pk）為路徑k的已用容量;v0為AGV的正常行駛速度;a為AGV在行駛過程中的加速度。

3.3 分步控制模型

針對(duì)AGV路徑?jīng)_突問題構(gòu)建模型，即

其中：式（1）和式（2）表示每個(gè)節(jié)點(diǎn)最多被同一AGV訪問1次，以免造成環(huán)路死鎖;式（3）表示路徑k的長(zhǎng)度為其所有節(jié)點(diǎn)所在邊之和。

不同的AGV同時(shí)經(jīng)過同一路口節(jié)點(diǎn)會(huì)產(chǎn)生AGV路徑?jīng)_突，需要其中一臺(tái)AGV減速或停車，以避讓另一臺(tái)AGV。此外，同一路徑上的AGV需要保持安全距離Ls。

針對(duì)圖2d）所示的AGV路徑?jīng)_突形式，需要考慮路徑剩余容量，即

其中：式（4）表示路徑k的道路容量，Round為向下取整函數(shù);式（5）表示路徑k的剩余容量。

當(dāng)AGV申請(qǐng)進(jìn)入的路段剩余容量為0時(shí)，應(yīng)暫時(shí)禁止其進(jìn)入路口節(jié)點(diǎn)，以免其長(zhǎng)時(shí)間占據(jù)路口節(jié)點(diǎn)導(dǎo)致其他AGV無法運(yùn)行，造成道路擁堵或死鎖。計(jì)算路徑k1和k2的沖突節(jié)點(diǎn)集合，即

C（k1，k2）=∩（6）

式中：和分別為路徑k1和k2的沖突節(jié)點(diǎn)。

3.4 速度控制模型

對(duì)于檢測(cè)存在路徑?jīng)_突的AGV，根據(jù)AGV的優(yōu)先級(jí)采取相應(yīng)策略：優(yōu)先級(jí)較高的AGV保持現(xiàn)有速度勻速通過沖突節(jié)點(diǎn)，優(yōu)先級(jí)較低的AGV則以加速度a減速至v1。據(jù)此構(gòu)建速度控制模型，即

其中：式（7）表示優(yōu)先級(jí)較低的AGV從距離沖突節(jié)點(diǎn)處開始減速，并以減速后的速度v1勻速通過沖突節(jié)點(diǎn);式（8）表示優(yōu)先級(jí)較低的AGV從正常速度v0減速至v1的行駛距離;式（9）表示優(yōu)先級(jí)較低的AGV在到達(dá)沖突節(jié)點(diǎn)前的減速行駛時(shí)間以及通過沖突節(jié)點(diǎn)后的加速行駛時(shí)間;式（10）表示優(yōu)先級(jí)較高的AGV 以正常速度v0通過沖突節(jié)點(diǎn)所需要的時(shí)間;式（11）表示使AGV經(jīng)過沖突節(jié)點(diǎn)前后所需要的時(shí)間最短。

3.5 速度控制與路徑再規(guī)劃相結(jié)合模型

對(duì)于檢測(cè)存在路徑?jīng)_突的AGV，在采取速度控制策略的同時(shí)，根據(jù)道路容量決定是否重新規(guī)劃AGV路徑。如果優(yōu)先級(jí)較低的AGV減速行駛至路口節(jié)點(diǎn)后，下一路段的AGV仍未全部駛出該路段，導(dǎo)致AGV需要在路口節(jié)點(diǎn)等待較長(zhǎng)時(shí)間，則考慮重新規(guī)劃AGV路徑。據(jù)此構(gòu)建速度控制與路徑再規(guī)劃相結(jié)合模型，即

其中：式（12）表示下一路段的AGV全部以正常速度v0駛出該路段所需要的時(shí)間;式（13）表示AGV從距離路口節(jié)點(diǎn)處開始減速;式（14）表示AGV在距離路口節(jié)點(diǎn)處開始減速行駛直至停在路口節(jié)點(diǎn)所需要的時(shí)間;式（15）表示AGV從相鄰路段以正常速度v0行駛所需要的時(shí)間;式（16）表示AGV在路口節(jié)點(diǎn)等待下一路段的AGV全部駛出該路段的時(shí)間;式（17）表示使AGV通過路口節(jié)點(diǎn)的時(shí)間最短。

4 算例分析

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

參照?qǐng)D1，利用eM-Plant軟件構(gòu)建自動(dòng)化集裝箱碼頭AGV仿真路網(wǎng)（見圖3）。假設(shè)每艘船安排3臺(tái)岸橋同時(shí)作業(yè)，并且每臺(tái)岸橋?qū)?yīng)多個(gè)箱區(qū)。設(shè)置基本參數(shù)如下：L=6 m，Ls=2 m，v0=4 m/s，v1=2 m/s，作業(yè)箱量為200個(gè)。

4.2 仿真結(jié)果比較

采用Dijkstra算法規(guī)劃AGV初始路徑，在eM-Plant軟件中設(shè)置傳感器檢測(cè)AGV路徑?jīng)_突節(jié)點(diǎn)，通過速度控制策略和速度控制與路徑再規(guī)劃相結(jié)合策略規(guī)避AGV路徑?jīng)_突，并計(jì)算和比較采用不同策略完成相同作業(yè)量所需要的時(shí)間、沖突節(jié)點(diǎn)處相鄰路徑的利用率和平均等待率、AGV在作業(yè)過程中的利用率和平均等待率等。

由圖4可見：隨著作業(yè)量增加，速度控制與路徑再規(guī)劃相結(jié)合策略在作業(yè)時(shí)間方面的優(yōu)勢(shì)逐步顯現(xiàn);當(dāng)作業(yè)量達(dá)到200個(gè)集裝箱時(shí)，采用速度控制與路徑再規(guī)劃相結(jié)合策略完成作業(yè)量所需要的時(shí)間明顯短于速度控制策略。

由圖5可見：在速度控制策略下，沖突節(jié)點(diǎn)處相鄰3條路徑的利用率分別為35.67%、60.47%和61.18%，路徑1的利用率遠(yuǎn)遠(yuǎn)低于路徑2和路徑3;在速度控制與路徑再規(guī)劃相結(jié)合策略下，沖突節(jié)點(diǎn)處相鄰3條路徑的利用率分別為48.68%、53.94%和46.95%，三者相差不大，路徑利用更為合理。

由圖6可見：在速度控制策略下，沖突節(jié)點(diǎn)處相鄰3條路徑的平均等待率分別為13.48%、36.10%和24.42%;在速度控制與路徑再規(guī)劃相結(jié)合策略下，沖突節(jié)點(diǎn)處相鄰3條路徑的平均等待率分別為13.22%、18.02%和22.47%，總體低于速度控制策略下的平均等待率，其中路徑2的平均等待率大幅下降18個(gè)百分點(diǎn)。

由圖7可見：在速度控制策略下，AGV在作業(yè)過程中的利用率為92.7%，平均等待率為7.3%;在速度控制與路徑再規(guī)劃相結(jié)合策略下，AGV在作業(yè)過程中的利用率為95.8%，平均等待率為4.2%，優(yōu)于速度控制策略下的同類指標(biāo)。

5 結(jié)束語

本文在傳統(tǒng)的速度控制策略的基礎(chǔ)上，提出基于道路容量的速度控制與路徑再規(guī)劃相結(jié)合的優(yōu)化策略，以解決自動(dòng)化集裝箱碼頭AGV路徑?jīng)_突問題。仿真結(jié)果表明：速度控制與路徑再規(guī)劃相結(jié)合策略不僅能夠有效解決自動(dòng)化集裝箱碼頭AGV路徑?jīng)_突問題，而且效果優(yōu)于速度控制策略。需要注意的是：本次仿真過程中設(shè)定的作業(yè)量較少，只有200個(gè)集裝箱;未來需要驗(yàn)證速度控制與路徑再規(guī)劃相結(jié)合策略是否適用于大規(guī)模作業(yè)和復(fù)雜路網(wǎng)情況，并針對(duì)其可能存在的問題進(jìn)一步優(yōu)化模型，以滿足自動(dòng)化集裝箱碼頭的實(shí)際需要。

參考文獻(xiàn)：

[1] YANG Y S， ZHONG M S， DESSOUKY Y， et al. An integrated scheduling method for AGV routing in automated container terminals[J]. Computers & Industrial Engineering， 2018， 126（12）：482-493.

[2] 柯冉絢，任亞東. 集裝箱碼頭AGV調(diào)度優(yōu)化[J]. 集美大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，21（1）：35-41.

[3] GRUNOW M， G躈THER H O， LEHMANN M. Dispatching multi-load AGVs in highly automated seaport container terminals[J]. OR Spectrum， 2004， 26（2）：211-235.

[4] GHASEMZADEH H， BEHRANGI E， AZGOMI M A. Conflict- free scheduling and routing of automated guided vehicles in mesh topologies[J]. Robotics and Autonomous Systems， 2009， 57（6/7）：738-748.

[5]肖海寧，樓佩煌.自動(dòng)導(dǎo)引車系統(tǒng)避碰及環(huán)路死鎖控制方法[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2015，21（5）：1244-1252.

[6] UMAR U A， ARIFFIN M K A， ISMAIL N， et al. Priority-based genetic algorithm for conflict-free automated guided vehicle routing[J]. Procedia Engineering， 2012（50）：732- 739.

[7] 王佳溶，樓佩煌，王曉勇. 基于改進(jìn)的兩階段控制策略的AGV路徑優(yōu)化調(diào)度研究[J]. 機(jī)械科學(xué)與技術(shù)，2008，27（9）：1211-1216.

[8] 馮海雙. AGV自動(dòng)運(yùn)輸系統(tǒng)調(diào)度及路徑規(guī)劃的研究[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)，2013.

[9] 張素云，楊勇生，梁承姬，等. 自動(dòng)化碼頭多AGV路徑?jīng)_突的優(yōu)化控制研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息，2017，17（2）：83-89.

[10] 仲美酥，楊勇生. 卸船作業(yè)模式下自動(dòng)化碼頭AGV路徑仿真優(yōu)化[J]. 水運(yùn)工程，2018（4）：122-127.

（編輯：張敏 收稿日期：2019-07-14）