摘要：隨著自動(dòng)化機(jī)器人技術(shù)和網(wǎng)絡(luò)通信技術(shù)的發(fā)展，在工業(yè)場(chǎng)域?qū)嵺`中，可自主移動(dòng)的無(wú)人載具逐漸嘗試取代人工駕駛的叉車等傳統(tǒng)載具導(dǎo)入物料搬運(yùn)流轉(zhuǎn)流程中。其中，高效的無(wú)人載具調(diào)度系統(tǒng)為實(shí)施的核心技術(shù)，負(fù)責(zé)調(diào)度無(wú)人載具將工件由存放中心有效地運(yùn)輸?shù)焦ぷ髦行摹１疚膶?duì)無(wú)人載具調(diào)度系統(tǒng)中的路徑規(guī)劃策略進(jìn)行說(shuō)明及比較。

關(guān)鍵詞：無(wú)人載具調(diào)度系統(tǒng);路徑規(guī)劃策略;集成決策

中圖分類號(hào)：TP242 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-9129（2020）06-0054-02

Abstract：Withthedevelopmentofautomaticrobottechnologyandnetworkcommunicationtechnology，inindustrialfieldpractice，unmannedvehiclesthatcanmoveautonomouslyaregraduallytryingtoreplacetraditionalvehiclessuchasforkliftsdrivenbyhumanbeingstobeintroducedintothematerialhandlingflow.Amongthem，efficientunmannedvehicledispatchingsystemisthecoretechnologyofimplementation，whichisresponsiblefordispatchingtheworkpiecefromthestoragecentertotheworkcentereffectively.Inthispaper，pathplanningstrategiesinunmannedvehicleschedulingsystemaredescribedandcompared.

Keywords：unmannedvehicleschedulingsystem;Pathplanningstrategy;Integrateddecisionmaking

引言：無(wú)人載具調(diào)度系統(tǒng)的設(shè)計(jì)問(wèn)題由許多決策變量組成，先進(jìn)的自動(dòng)化調(diào)度系統(tǒng)的研發(fā)和使用可極大地提升工業(yè)物流效率。標(biāo)準(zhǔn)的調(diào)度系統(tǒng)應(yīng)具有以下調(diào)度及控制功能：敏捷的流程配置，可靠的死鎖避免和沖突解決策略，可定位的?？课恢?，成熟的混合方向配置，可根據(jù)載具搬運(yùn)參數(shù)、負(fù)載及任務(wù)狀態(tài)動(dòng)態(tài)選擇路線。調(diào)度系統(tǒng)可有效減少搬運(yùn)工作的用時(shí)，減少空載及調(diào)度時(shí)間，平衡載具的工作量。

調(diào)度系統(tǒng)的性能直接關(guān)系到整個(gè)搬運(yùn)系統(tǒng)的性能。通過(guò)研究改進(jìn)調(diào)度策略和算法，如路徑規(guī)劃策略、避免死鎖算法、調(diào)度規(guī)則、吞吐量分析模型、負(fù)載均衡策略、無(wú)沖突移動(dòng)策略、沖突解決策略等所有方面的相互集成，可有效提升搬運(yùn)系統(tǒng)性能。本文將對(duì)各種路徑規(guī)劃策略及其特性、優(yōu)缺點(diǎn)和對(duì)系統(tǒng)性能參數(shù)的影響進(jìn)行分析。

1路徑規(guī)劃策略

調(diào)度系統(tǒng)中的路徑規(guī)劃和布局設(shè)計(jì)問(wèn)題被認(rèn)為是研究無(wú)人載具在搬運(yùn)系統(tǒng)中高效運(yùn)行的最基本問(wèn)題之一。路徑規(guī)劃策略的設(shè)計(jì)很大程度上取決于工作場(chǎng)域的布局。在布局中，路徑通常以通道、轉(zhuǎn)彎點(diǎn)和交叉點(diǎn)組成，并可在通道上的任何位置設(shè)置停站點(diǎn)。無(wú)人載具在通道上移動(dòng)，同時(shí)將工件從一個(gè)停站點(diǎn)運(yùn)送至另一個(gè)停站點(diǎn)。具有起始停站點(diǎn)和結(jié)束停站點(diǎn)的有向通道表示無(wú)人載具的行進(jìn)方向。這表明與路徑規(guī)劃策略有關(guān)的問(wèn)題也可以使用基于網(wǎng)絡(luò)的系統(tǒng)方法進(jìn)行分析。

文中根據(jù)路徑拓?fù)鋱D、通道類型和移動(dòng)方式來(lái)研究的路徑規(guī)劃策略的特性。

（I）路徑拓?fù)鋱D：無(wú)人載具在場(chǎng)域中的各類移動(dòng)路徑的布局圖。

（II）通道類型：通道有單通道和平行通道兩種，平行通道指路徑策略中提供兩個(gè)彼此平行并且通行方向相反的通道。

（III）移動(dòng)方式：無(wú)人載具通常有單向和雙向兩種移動(dòng)方式。單向移動(dòng)可以簡(jiǎn)化調(diào)度邏輯，但會(huì)犧牲時(shí)間代價(jià);而雙向移動(dòng)可加大搬運(yùn)吞吐量，但容易導(dǎo)致死鎖或與發(fā)生路徑?jīng)_突。

1.1路徑規(guī)劃策略的比較指標(biāo)。在路徑規(guī)劃策略設(shè)計(jì)的背景下，無(wú)人載具的工作性能參數(shù)，即稼動(dòng)率、運(yùn)輸耗時(shí)、任務(wù)隊(duì)列長(zhǎng)度和物料轉(zhuǎn)移成本等，取決于路徑規(guī)劃策略的是否有效設(shè)計(jì)和實(shí)施。其中，無(wú)人載具行駛總距離的最小化是最典型的性能指標(biāo)。經(jīng)研究，載具部署的規(guī)模、路徑長(zhǎng)度和路徑策略，可作為具有目標(biāo)函數(shù)的多準(zhǔn)則決策問(wèn)題計(jì)算得出最優(yōu)解。而系統(tǒng)運(yùn)行后的空載行駛時(shí)間、死鎖或干擾發(fā)生的概率和時(shí)長(zhǎng)、運(yùn)輸失敗率等數(shù)據(jù)，可作為分析搬運(yùn)系統(tǒng)整體性能的參考指標(biāo)。

1.2常規(guī)單向路徑規(guī)劃策略。在常規(guī)單向路徑規(guī)劃策略中，所有停站點(diǎn)都通過(guò)一條通道連接。通道可能具有交叉點(diǎn)和捷徑。通道可以是單向的，也可以是雙向的。單向通道僅允許車輛朝一個(gè)方向行駛，而在雙向通道系統(tǒng)中，載具可以朝前后兩個(gè)方向行駛。

常規(guī)單向路徑規(guī)劃策略是最基本最直接的路徑規(guī)劃策略。此策略中通道的布局可以直接由實(shí)際工作區(qū)域的連線構(gòu)成，并根據(jù)實(shí)際需求確定載具數(shù)量配置、速度設(shè)定和調(diào)度規(guī)則。其優(yōu)勢(shì)在于規(guī)劃直觀便捷，缺點(diǎn)在于通常缺乏靈活性且未考慮最優(yōu)路徑。

1.3常規(guī)雙向路徑規(guī)劃策略。常規(guī)單向路徑規(guī)劃策略的改進(jìn)是采用雙向通道系統(tǒng)，即載具可以按照搬運(yùn)要求在前后兩個(gè)方向行進(jìn)。與單向通道設(shè)計(jì)相比，雙向通道的設(shè)計(jì)，但系統(tǒng)的控制復(fù)雜度會(huì)大幅提高。雙向平行通道的優(yōu)勢(shì)在于提供更大的靈活性和效率，載具間碰撞和相互干擾的概率大幅極低。缺點(diǎn)在于系統(tǒng)調(diào)度復(fù)雜度提升，在任何設(shè)施中規(guī)劃平行車道的成本較高，并且需要更多空間。

1.4單環(huán)路徑規(guī)劃策略。環(huán)狀路徑指設(shè)施中的路徑只由通道和轉(zhuǎn)彎點(diǎn)組成，無(wú)捷徑且形成閉環(huán)。其中最基本的策略稱為單環(huán)路徑規(guī)劃策略，即無(wú)人載具僅沿單方向環(huán)路行進(jìn)。

單環(huán)路徑系統(tǒng)的優(yōu)勢(shì)在于在部署的載具運(yùn)行參數(shù)一樣的前提下，發(fā)生路徑死鎖或碰撞的機(jī)會(huì)幾乎為零。但少數(shù)場(chǎng)景下若需要使用混合載具，即多個(gè)載具以不同的速度運(yùn)動(dòng)時(shí)，碰撞的可能性會(huì)提升。在部署相同數(shù)量載具的前提下，單環(huán)路徑策略的局限性在于吞吐量較小，需要通過(guò)增加載具部署以提升搬運(yùn)吞吐量。在實(shí)際應(yīng)用中，單一使用單環(huán)路徑策略的場(chǎng)景較少，通常以單環(huán)路徑為基礎(chǔ)，多個(gè)環(huán)路混合規(guī)劃。

1.5串聯(lián)路徑規(guī)劃策略。串聯(lián)路徑規(guī)劃就是以單環(huán)路徑為基本單元通過(guò)串聯(lián)方式組合的路徑策略，其中最基本的配置方式是串聯(lián)環(huán)路規(guī)劃。即將工作區(qū)域劃分為一個(gè)以上的環(huán)路分區(qū)，一個(gè)載具分配給一個(gè)環(huán)路分區(qū)，各個(gè)運(yùn)行區(qū)域間設(shè)置傳輸轉(zhuǎn)移點(diǎn)。由于將工作中心放置在制造設(shè)施中的不同位置，因此在運(yùn)輸中的工件需要多個(gè)載具，以便在串聯(lián)環(huán)路中將工件從一個(gè)分區(qū)運(yùn)輸?shù)侥康墓ぷ鞣謪^(qū)。以此策略基礎(chǔ)上，通過(guò)增加分區(qū)可以提升運(yùn)輸效率，并減少對(duì)分區(qū)間轉(zhuǎn)移點(diǎn)的需求。然而缺點(diǎn)在于增加運(yùn)輸分區(qū)會(huì)增加空間和成本投入。

通過(guò)改進(jìn)，將傳統(tǒng)的串聯(lián)環(huán)路策略分為非重疊的串聯(lián)組合來(lái)規(guī)劃串聯(lián)路徑系統(tǒng)，稱為串聯(lián)專區(qū)環(huán)路路徑規(guī)劃策略。通過(guò)配置專用載具為每個(gè)分區(qū)服務(wù)，即在一個(gè)分區(qū)中只允許一輛載具工作，并在相鄰單環(huán)之間建立接口的附加傳輸點(diǎn)，可以達(dá)到更大的靈活性（圖1）。在此改進(jìn)策略下載具可以雙向行駛，阻塞問(wèn)題可完全消除。

經(jīng)過(guò)一系列模擬驗(yàn)證，以分析和比較系統(tǒng)中無(wú)人載具的性能參數(shù)（平均遲滯百分比，平均遲滯度，利用率和平均流動(dòng)時(shí)間）的常規(guī)和串聯(lián)策略。觀察到串聯(lián)路徑策略的綜合效率比常規(guī)路徑策略更優(yōu)。串聯(lián)路徑策略其優(yōu)勢(shì)在于更易于調(diào)度控制，且有效避免擁塞和死鎖。劣勢(shì)在于串聯(lián)路徑策略對(duì)系統(tǒng)故障的容忍度較低，并且系統(tǒng)的吞吐量隨著傳輸緩沖區(qū)的額外要求而降低，處理時(shí)間增加。在串聯(lián)環(huán)路策略的設(shè)計(jì)上，可以通過(guò)：1.解決旅行推銷員問(wèn)題（TravellingSalesmanProblem）以劃分工作中心的子集。2.應(yīng)用馬爾可夫鏈模型找出工，作中心的最終子集。在進(jìn)一步的改進(jìn)中，提出了基于混合算法優(yōu)化的串聯(lián)回路策略，通過(guò)設(shè)計(jì)一個(gè)串聯(lián)環(huán)帶區(qū)域防止載具在交叉路徑發(fā)生死鎖（圖2）。

通過(guò)對(duì)三種串聯(lián)路徑規(guī)劃策略的性能參數(shù)的比較，研究在不同規(guī)模設(shè)施下的總行駛時(shí)間和載具空載的比例。通過(guò)離散仿真運(yùn)行，計(jì)算三種串聯(lián)路徑策略對(duì)空載行駛時(shí)間值之比的影響，串聯(lián)回路路徑策略表現(xiàn)最佳。

2路徑規(guī)劃策略性能分析

3結(jié)論

在以上文章中分析，無(wú)人載具的路徑規(guī)劃策略是在任何設(shè)施中進(jìn)行有效物料搬運(yùn)操作的最重要因素之一。即通過(guò)不同類型的路徑規(guī)劃策略的設(shè)計(jì)和實(shí)施，對(duì)設(shè)施中無(wú)人載具的最佳規(guī)模進(jìn)行估算，對(duì)調(diào)度有效運(yùn)行規(guī)則進(jìn)行分析，以最佳利用路徑策略滿足設(shè)施中的搬運(yùn)要求。

路徑規(guī)劃策略可分為常規(guī)單向/雙向、單環(huán)、串聯(lián)環(huán)路、串聯(lián)專區(qū)環(huán)路和串聯(lián)回路等。通過(guò)幾項(xiàng)參數(shù)的對(duì)比發(fā)現(xiàn)，每種策略的處理方式都是唯一的，其對(duì)于特定的制造環(huán)境具有其特定的應(yīng)用。實(shí)踐中可根據(jù)需求采用單個(gè)或多個(gè)策略的組合提供的最佳解決方案。

參考文獻(xiàn)：

[1]V.K.Chawla1，A.K.Chanda，andSurjitAngra.Automaticguidedvehiclesystemsintheflexiblemanufacturingsystem-Areview[J].InternationalJournalofIndustrialEngineering，26（5），737-765，2019

[2]Mantel，R.J.andLandeweerd，H.R.A.（1995）.DesignandoperationalcontrolofanAGVsystem[J].InternationalJournalofProductionEconomics，41（1-3）：257-266.

[3]Ko，K.C.，&Egbelu，P.J.（2003）.UnidirectionalAGVguidepathnetworkdesign：aheuristicalgorithm[J].InternationalJournalofProductionResearch，41（10）：2325-2343.

[4]Hamzeei，M.，F(xiàn)arahani，R.Z.，&Rashidi-Bejgan，H.（2013）.AnexactandasimulatedannealingalgorithmforsimultaneouslydeterminingflowpathandthelocationofP/Dstationsinbidirectionalpath[J].JournalofManufacturingSystems，32（4）：648-654.

[5]Asef-Vaziri，A.，&Goetschalckx，M.（2008）.DualtrackandsegmentedsingletrackbidirectionalloopguidepathlayoutforAGVsystems[J].EuropeanJournalofOperationalResearch，186（3）：972-989

[6]Kim，K.S.，&DoChung，B.（2007）.DesignforatandemAGVsystemwithtwo-loadAGVs[J].Computers&IndustrialEngineering，53（2）：247-251.

[7]Al-Hawari，T.，Ena'amS，A.Z.，&Alshraideh，H.（2016）.StudyingtheEffectofFacilitySizeontheSelectionofAutomatedGuidedVehicleFlowConfigurations[J].JournalofAutomationandControlEngineering，4（2）：132-139

作者簡(jiǎn)介：林蔚（1986-），男，碩士，工程師，主要從事工業(yè)互聯(lián)網(wǎng)生態(tài)系統(tǒng)建設(shè)及工業(yè)無(wú)人載具系統(tǒng)研究。