付博言 張一帆

(廣西科技大學(xué)經(jīng)濟(jì)與管理學(xué)院 廣西柳州 545006)

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

AGV在我國的發(fā)展時(shí)間較為短暫，直到20世紀(jì)六七十年代，北京起重運(yùn)輸機(jī)研究所、中科院郵政研究規(guī)劃院聯(lián)合清華大學(xué)在內(nèi)的國內(nèi)多家理工類高等院校進(jìn)行AGV小車的研發(fā)，1975年，北京起重運(yùn)輸機(jī)研究所成功制造出國內(nèi)首臺(tái)AGV小車[2]，并進(jìn)行了產(chǎn)品的量產(chǎn)。

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

國內(nèi)眾多學(xué)者提出的路徑優(yōu)化研究都是在模糊神經(jīng)算法、免疫網(wǎng)絡(luò)算法、Dijkstra算法等眾多算法的基礎(chǔ)上，通過對AGV小車在運(yùn)輸過程中的運(yùn)行速度、運(yùn)輸環(huán)境中的自主導(dǎo)航能力進(jìn)行優(yōu)化改良[7]。

本文基于遺傳算法對多AGV小車的路線問題進(jìn)行優(yōu)化，相較傳統(tǒng)的AGV單一路線運(yùn)輸，擁有固定的路線以及需要運(yùn)輸?shù)墓潭ㄎ恢玫呢浳?，多AGV路線研究借助于計(jì)算機(jī)的智能算法對多輛AGV小車的路線進(jìn)行模擬分析[8]，在運(yùn)輸速度與可控性盡可能最大化的情況下將位于不同區(qū)間貨架上的不同貨物位置坐標(biāo)化，然后找到每一輛小車通過這些位置坐標(biāo)的用時(shí)最短、效率最高的路徑。

1 研究方法

1.1 遺傳算法

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

1.2 模型構(gòu)建

1.2.1 模型環(huán)境構(gòu)建

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

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

1.2.2 模型約束構(gòu)建

根據(jù)出庫需求時(shí)間區(qū)間進(jìn)行約束條件設(shè)計(jì)。

最優(yōu)值求解

具體公式

約束條件為：

在運(yùn)行中的AGV小車總數(shù)要小于擁有的AGV小車總數(shù)

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

選擇完成車輛

任意車輛下任務(wù)w隨機(jī)

任意車輛下任務(wù)i隨機(jī)

任意車輛下i=0完成任務(wù)

任意車輛下路徑選擇

任意車輛下W=0完成任務(wù)

任意車輛下AGV滿足時(shí)間窗需求

車輛實(shí)際到達(dá)時(shí)間大于貨柜需求最早時(shí)間小于貨柜需求最晚時(shí)間

數(shù)學(xué)模型中的符號(hào)說明如下：

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

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

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

ρ：懲罰系數(shù)，其為一個(gè)常數(shù)；

τ，υ：懲罰系數(shù)，認(rèn)為無窮大的正實(shí)數(shù)；

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

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

Hj：AGV小車j的容量；

n：需求貨位的總數(shù)；

J：擁有的可供配送的AGV小車總數(shù)；

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

：AGV車輛j到達(dá)客戶i的時(shí)間；

ESi：任務(wù)i期望的最早開始時(shí)間；

Ei：AGV小車實(shí)際到達(dá)任務(wù)i的時(shí)間；

LSi：任務(wù)i期望的最遲開始時(shí)間；

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

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

2 計(jì)算過程及結(jié)果

2.1 坐標(biāo)數(shù)據(jù)選取

采用Excel軟件進(jìn)行隨機(jī)選擇坐標(biāo)點(diǎn)數(shù)據(jù)點(diǎn)在(0，0)至(99，100)之間，如圖2所示。設(shè)計(jì)點(diǎn)(100，50)為出庫站臺(tái)左邊點(diǎn)。并且采用Excel軟件，在原來隨機(jī)數(shù)據(jù)的坐標(biāo)點(diǎn)上進(jìn)行隨機(jī)時(shí)間，要求需求起始時(shí)間小于終止需求時(shí)間，如表1所示。

表1 隨機(jī)點(diǎn)坐標(biāo)和需求時(shí)間短表

圖2 隨機(jī)點(diǎn)坐標(biāo)

2.2 Matlab迭代求解

2.2.1 迭代優(yōu)化

將表1隨機(jī)點(diǎn)坐標(biāo)和需求時(shí)間短表中的數(shù)據(jù)代入matlab軟件，進(jìn)行迭代優(yōu)化，每次迭代的過程逐漸趨于最優(yōu)值，五十次迭代能夠選擇出更具代表性和更加優(yōu)秀的結(jié)果，最終得到迭代次數(shù)-優(yōu)化過程圖，如圖3所示。

圖3 迭代次數(shù)-優(yōu)化過程圖

2.2.2 結(jié)果求解

對于現(xiàn)代物流中心貨物運(yùn)量增加、貨物放置分散，AGV小車固定線路的取貨不夠精準(zhǔn)，無法將加急貨物在需求時(shí)間內(nèi)取出，造成AGV小車運(yùn)輸效率低下，我們利用MATLAB軟件進(jìn)行迭代優(yōu)化，10個(gè)不同編號(hào)的AGV小車對應(yīng)著10條不同的運(yùn)行路線，根據(jù)位置坐標(biāo)AGV從0點(diǎn)即出庫月臺(tái)出發(fā)，經(jīng)由多個(gè)不同坐標(biāo)點(diǎn)，即不同區(qū)間的貨架最終回到出發(fā)點(diǎn)的過程，最終得出最優(yōu)解是車輛使用數(shù)目10輛，車輛行駛總距離2554.8071m。

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

表2 AGV運(yùn)行路線表

3 結(jié)果分析

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

圖4 AGV最優(yōu)配送方案路線圖

4 結(jié)語

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