基于工廠物流中遺傳算法的多AGV路徑規劃研究

付博言 張一帆

(廣西科技大學經濟與管理學院 廣西柳州 545006)

進入21世紀以來，中國加入世貿組織，對外貿易出口日益增加，伴隨而來的經濟體量大幅度增加，一些小眾企業不得不轉型升級，為了讓企業的效益得到最大化，很多企業先后引入自動化物流來提高企業自身的生產效率[1]，而AGV作為自動化中的一環在提高生產效率、企業效益方面尤為關鍵，有著更加廣闊的市場應用前景，在未來的發展中它將可能完全替代人力成為主要的勞動輸出。

AGV在我國的發展時間較為短暫，直到20世紀六七十年代，北京起重運輸機研究所、中科院郵政研究規劃院聯合清華大學在內的國內多家理工類高等院校進行AGV小車的研發，1975年，北京起重運輸機研究所成功制造出國內首臺AGV小車[2]，并進行了產品的量產。

AGV的量產成功地邁開了第一步，如何提高AGV在實際生產中的運用顯得尤為重要，在生產中AGV通過牽引、拉拽裝載貨物的貨架將其送到指定地點就算完成一次運輸任務，為了提高AGV的運輸效率，Dijkstra首先提出了AGV最短路徑問題的研究[3]，此后，AGV的路徑算法被越來越多地研究出來，國內學者對于路徑算法的理論研究提出了自己的見解，其中陳華志[4]通過神經網絡并行性和融合性，研發了一種基于神經網絡的AGV小車路徑規劃的算法，提高了路徑規劃的速度；肖本賢(2004)[5]運用模糊邏輯實現對超聲波和視覺傳感器的數據進行融合，使AGV小車能在不確定的環境中進行自主導航；李建華等(2005)[6]提出了一種AGV軌跡更理想自適應的軌跡跟蹤控制方法。

國內眾多學者提出的路徑優化研究都是在模糊神經算法、免疫網絡算法、Dijkstra算法等眾多算法的基礎上，通過對AGV小車在運輸過程中的運行速度、運輸環境中的自主導航能力進行優化改良[7]。

本文基于遺傳算法對多AGV小車的路線問題進行優化，相較傳統的AGV單一路線運輸，擁有固定的路線以及需要運輸的固定位置的貨物，多AGV路線研究借助于計算機的智能算法對多輛AGV小車的路線進行模擬分析[8]，在運輸速度與可控性盡可能最大化的情況下將位于不同區間貨架上的不同貨物位置坐標化，然后找到每一輛小車通過這些位置坐標的用時最短、效率最高的路徑。

1 研究方法

1.1 遺傳算法

基本遺傳算法是一種模擬自然演變尋找最優解的方法。通過模擬自然選擇的方式來復制初始群體中的個體，不斷發生交叉、變異等操作產生優于上一代且更適應于新環境的群體，不斷通過迭代進化直到產生最優個體。遺傳算法具有不斷優化的特性，采用遺傳算法來對多AGV小車路徑進行優化可得出最優的路線選擇。

1.2 模型構建

1.2.1 模型環境構建

柳州某物流中心位于柳州市柳南區，是現代物流基地的重點物流中心，該物流中心是集工程機械、汽車配件、高新技術等產業為一體的大型綜合工業園區，為了提高企業效益，公司采用AGV小車進行物料和貨物的運輸，由于物流中心的貨物放置過于分散且該物流中心的AGV小車運行只能進行單一的固定線路運輸，為了增加運輸效率進而提升效益，決定對單一的固定運輸線路進行優化并增設多條AGV運輸線路。首先對AGV出庫運輸貨物建立出庫模型，AGV起始點為出庫月臺，其次采用數據為隨機數據設計一百個出庫貨位點，并用0—100序號進行標號。最后用Excel軟件進行隨機選擇坐標點，坐標點在(0，0)至(99，100)，建立(0，100)范圍內的二維坐標系，出庫月臺點設計坐標為(100，50)，對應序號為0，如圖1所示。

圖1 柳南物流中心出庫模型二維平面圖

1.2.2 模型約束構建

根據出庫需求時間區間進行約束條件設計。

最優值求解

具體公式

約束條件為：

在運行中的AGV小車總數要小于擁有的AGV小車總數

路線中所有貨架、貨物容量小于AGV小車容量

選擇完成車輛

任意車輛下任務w隨機

任意車輛下任務i隨機

任意車輛下i=0完成任務

任意車輛下路徑選擇

任意車輛下W=0完成任務

任意車輛下AGV滿足時間窗需求

車輛實際到達時間大于貨柜需求最早時間小于貨柜需求最晚時間

數學模型中的符號說明如下：

φ：目標函數值；

φ1：車輛配送過程中因超載帶來的懲罰成本；

φ6：由于配送車輛早到或者延遲帶來的時間懲罰成本；

ρ：懲罰系數，其為一個常數；

τ，υ：懲罰系數，認為無窮大的正實數；

Oi：表示第i個貨位的需求出庫量；

Gji：貨位i的任務由配送AGV小車j完成的選擇變量；

Hj：AGV小車j的容量；

n：需求貨位的總數；

J：擁有的可供配送的AGV小車總數；

：車輛j在路段(Ow O i)上行駛的選擇變量；

：AGV車輛j到達客戶i的時間；

ESi：任務i期望的最早開始時間；

Ei：AGV小車實際到達任務i的時間；

LSi：任務i期望的最遲開始時間；

EUi：貨位能夠接受的配送車輛最早卸貨時間；

LUi：貨位能夠接受的配送車輛最晚的卸貨時間

2 計算過程及結果

2.1 坐標數據選取

采用Excel軟件進行隨機選擇坐標點數據點在(0，0)至(99，100)之間，如圖2所示。設計點(100，50)為出庫站臺左邊點。并且采用Excel軟件，在原來隨機數據的坐標點上進行隨機時間，要求需求起始時間小于終止需求時間，如表1所示。

表1 隨機點坐標和需求時間短表

圖2 隨機點坐標

2.2 Matlab迭代求解

2.2.1 迭代優化

將表1隨機點坐標和需求時間短表中的數據代入matlab軟件，進行迭代優化，每次迭代的過程逐漸趨于最優值，五十次迭代能夠選擇出更具代表性和更加優秀的結果，最終得到迭代次數-優化過程圖，如圖3所示。

圖3 迭代次數-優化過程圖

2.2.2 結果求解

對于現代物流中心貨物運量增加、貨物放置分散，AGV小車固定線路的取貨不夠精準，無法將加急貨物在需求時間內取出，造成AGV小車運輸效率低下，我們利用MATLAB軟件進行迭代優化，10個不同編號的AGV小車對應著10條不同的運行路線，根據位置坐標AGV從0點即出庫月臺出發，經由多個不同坐標點，即不同區間的貨架最終回到出發點的過程，最終得出最優解是車輛使用數目10輛，車輛行駛總距離2554.8071m。

以下是10輛AGV運行路線表及運行過程圖，如表2和圖4所示。

表2 AGV運行路線表

3 結果分析

根據圖4 AGV最優方案配送路線圖可知，多AGV小車生成了各自的一條運輸路線，且每一條運輸路線都在約束條件下經由電腦模擬產生，AGV小車由藍色出庫站臺點出發，經過不同區間上的貨架裝載著不同貨物，最終回到藍色出庫站臺點，該路線符合當時該生產時刻的運載需求，并能夠更好地滿足運輸線路上裝載多種商品運輸，對比傳統的固定線路往返式運輸大大降低時間成本，傳統的AGV小車在往返式運輸線路上空載時以1m/s的速度運行，以表2 AGV運行路線表中的2號車輛運輸線路為例，當AGV小車從初始點出發，首先到達43序號點，其位置坐標為(93，76)，裝載貨物后返回時負載運行速度是0.5m/s，逐一到達該線路其他5個坐標點，完成一組商品的運輸總計耗費538.11秒，優化后的運輸路線只需將本次運輸需要的所有要取得的貨物位置坐標輸入系統，就會生成多區間、多貨架、多品種貨物的運輸路線圖，將2號運輸線路的位置坐標輸入，生成的運輸線路且完成該線路總計用時399.99秒，優化后的路線比傳統路線快138.12秒。此外，將剩余的9條運輸線路計算并進行對比，最終得出10條運輸路線在優化后比原先快了近2.86小時，證實了在時間窗條件下大運量AGV通過算法的優化能夠保證最短路徑和最優時間進行高效地運行。同時也表明企業要想實現對于一組商品完成快速的出庫任務，僅靠傳統模式已遠遠不夠，在兼顧效率與成本的前提下多AGV的自主決策路徑運輸將是推動企業提高效益的關鍵步驟。

圖4 AGV最優配送方案路線圖

4 結語

通過對Matlab運行結果的分析，傳統的AGV運輸路徑在運輸效率、運輸時間方面表現為運輸效率低下、用時過長，對傳統運輸線路進行優化改變了效率低下、用時過長的缺點，并根據其優化結果能更好地調整AGV小車在這些方面的問題，以使效率、時間達到最優化為目標，進而降低了企業的時間成本，時間成本在物流成本中占有很大比重，企業要想獲得高額效益，就應盡可能提升貨物收發環節的拿取效率。因此，對于路徑的規劃尤為重要，根據遺傳算法模型可知，規劃后的AGV小車能在一次路線上運輸多個貨架的不同貨物，對比以往的先進先出式運輸方法大大提高了作業效率，這使得企業能夠應對不同場景、不同情況下的貨物，本文優化結果僅能采用與模擬環境中的倉庫模型。具有相同智能貨柜和AGV智能小車修改不同貨柜位置和倉庫環境參數，能夠應用于現代智能倉庫路徑優化方案。AGV小車根據需求時間區間規劃路線能夠滿足急需出庫貨物的需求，延后不需要急出庫貨物時間，充分提高了貨物流轉效率，同時提高了AGV小車的使用效率和企業效益。