(北京物資學(xué)院 北京 101149)

一、引言

隨著電商行業(yè)的迅速發(fā)展，自動(dòng)導(dǎo)引車系統(tǒng)(Automated Guided Vehicle System,AGVS)應(yīng)運(yùn)而生，相比于傳統(tǒng)的人工揀選方式，AGV揀選作業(yè)方式大大增加了揀選效率。AGV揀選系統(tǒng)的作業(yè)模式通常為：揀選AGV在接收到任務(wù)之后，沿地面上貼有坐標(biāo)信息的二維碼到達(dá)相應(yīng)的貨架下方，把含有需揀選商品的貨架整個(gè)運(yùn)輸?shù)綊x工作站，揀選工作人員根據(jù)提示把需要的商品拿出并放在料箱，當(dāng)貨架需揀選的商品被揀選完之后，AGV拖運(yùn)貨架重新放回或者放回到其他位置，繼續(xù)執(zhí)行下一個(gè)揀選任務(wù)。電商無(wú)人倉(cāng)揀選作業(yè)區(qū)的基本布局如圖1所示。

圖1 電商無(wú)人倉(cāng)揀選作業(yè)區(qū)基本布局圖

電商無(wú)人倉(cāng)系統(tǒng)路網(wǎng)的布局情況通常為貨架間的細(xì)窄通道，為了提高倉(cāng)庫(kù)的利用效率，每條通道的寬度一般設(shè)為只能一輛AGV通過(guò)，在任務(wù)量少時(shí)AGV可以高效的完成任務(wù)，但是在任務(wù)量比較多的情況下，AGV在運(yùn)行過(guò)程中可能會(huì)出現(xiàn)擁堵、碰撞或死鎖等現(xiàn)象，影響這些的因素有很多，無(wú)人倉(cāng)的路徑網(wǎng)絡(luò)設(shè)計(jì)就為其中一個(gè)關(guān)鍵因素，其不僅影響物流 AGV的工作效率，還會(huì)影響倉(cāng)庫(kù)的利用率，所以對(duì)整個(gè)電商無(wú)人倉(cāng)的效率都起著關(guān)鍵的作用。

二、電商無(wú)人倉(cāng)路徑網(wǎng)絡(luò)概述

電商無(wú)人倉(cāng)路徑網(wǎng)絡(luò)布局問(wèn)題，是在已經(jīng)確定好路徑網(wǎng)絡(luò)的情況下，對(duì)路網(wǎng)中每條路徑規(guī)劃出各自的方向，最終目的是使得AGV在執(zhí)行任務(wù)時(shí)可以用最短路徑、最少時(shí)間完成所有任務(wù)。

對(duì)電商無(wú)人倉(cāng)的研究通常會(huì)將揀選區(qū)抽象為柵格地圖，通過(guò)運(yùn)行歷史訂單來(lái)確定路網(wǎng)中每個(gè)路段的方向，無(wú)人倉(cāng)路網(wǎng)布局主要有兩種基本形式：?jiǎn)蜗蚵窂骄W(wǎng)絡(luò)布局與雙向路徑網(wǎng)路布局。

(一)單向路徑網(wǎng)絡(luò)布局

單向路徑網(wǎng)絡(luò)布局在現(xiàn)有的物流領(lǐng)域使用的最為廣泛，它規(guī)定AGV在無(wú)人倉(cāng)路網(wǎng)中的每個(gè)路段只被允許向一個(gè)方向行駛，這種布局可以有效的減少AGV在運(yùn)行過(guò)程中發(fā)生沖突、碰撞，在這種路徑網(wǎng)路布局下，規(guī)劃路網(wǎng)中每個(gè)路段的可行駛方向是路網(wǎng)布局的關(guān)鍵，但是單向路徑網(wǎng)絡(luò)布局也有其弊端，因?yàn)槁肪W(wǎng)中每個(gè)路段的方向只有一個(gè)，不允許AGV掉頭，在有些情況下會(huì)增加了AGV在執(zhí)行任務(wù)時(shí)的行駛距離和時(shí)間。

對(duì)于單向路徑網(wǎng)絡(luò)布局來(lái)說(shuō)，每個(gè)路段的方向有兩種情況，也就是說(shuō)一個(gè)擁有m條路段的無(wú)人倉(cāng)，它的路網(wǎng)布局情況就有2m個(gè)，不同的路網(wǎng)布局情況下AGV執(zhí)行任務(wù)的效率有可能不同，路網(wǎng)布局是否合理，關(guān)系到AGV的揀選路程與揀選時(shí)間，所以電商無(wú)人倉(cāng)的路網(wǎng)布局優(yōu)化顯得尤為重要，如圖2所示，為同一揀選區(qū)的兩種路網(wǎng)布局方案。

圖2(a)

圖2(b)

(二)雙向路徑網(wǎng)絡(luò)布局

雙向路徑網(wǎng)絡(luò)布局在現(xiàn)實(shí)的物流領(lǐng)域運(yùn)用的比較少，雖然它可以有效的減少AGV的繞行時(shí)間，但是在AGV數(shù)量較多時(shí)，也增加了AGV在行駛過(guò)程中發(fā)生碰撞及死鎖的可能性。此外，雙向路徑網(wǎng)絡(luò)布局還存在雙車道單向路徑網(wǎng)絡(luò)布局形式，無(wú)人倉(cāng)路徑網(wǎng)絡(luò)中每個(gè)路段含有兩條路徑，且每條路徑中AGV 可以被允許行駛的方向相反，所以雙車道單向路徑網(wǎng)絡(luò)布局也是一種特殊的單向路徑網(wǎng)絡(luò)布局[1]。

三、研究現(xiàn)狀

對(duì)于電商無(wú)人倉(cāng)路網(wǎng)規(guī)劃的問(wèn)題，相關(guān)學(xué)者已有相關(guān)的研究文獻(xiàn)。Kelly K.Bartlett[2]指出自動(dòng)機(jī)器人系統(tǒng)擁堵與路網(wǎng)布局和路徑的規(guī)劃方法緊密相關(guān)。所以AGV的路網(wǎng)布局研究是一個(gè)被學(xué)者關(guān)注的問(wèn)題。

Tuan Le-Anh等[3]提出路網(wǎng)布局通常包括單向?qū)б窂较到y(tǒng)、雙向?qū)б窂较到y(tǒng)、單回路路徑系統(tǒng)和串聯(lián)路徑系統(tǒng)等。Gaskins等[4]首先提出單向路徑網(wǎng)絡(luò)的設(shè)計(jì)問(wèn)題，并運(yùn)用0-1整數(shù)規(guī)劃方法來(lái)進(jìn)行路網(wǎng)規(guī)劃。Chiung-Hsi Hsieh[5]在不增加機(jī)器人數(shù)量的前提下，提出了雙軌雙向的系統(tǒng)布局方案，避免AGV在運(yùn)行過(guò)程中的擁堵和死鎖。肖海寧等[6]在設(shè)計(jì)AGV路徑網(wǎng)絡(luò)問(wèn)題時(shí)，把禁忌搜索算法與遺傳算法相結(jié)合形成混合算法，提高了算法的收斂速度并且提高了局部搜索能力。管賢平等[7]在對(duì)單向路徑網(wǎng)絡(luò)進(jìn)行設(shè)計(jì)時(shí)采用改進(jìn)的遺傳算法，將其結(jié)合變鄰域搜索與小生境淘汰運(yùn)算，形成VNS/NGA混合方法，并綜合考慮了負(fù)載和空載的路程，提高了結(jié)果的可行性。

在電商無(wú)人倉(cāng)物流AGV的運(yùn)行當(dāng)中不可避免的會(huì)出現(xiàn)沖突的現(xiàn)象，造成AGV沖突的原因有很多，比如物流AGV的節(jié)點(diǎn)沖突、路途遇到障礙、節(jié)點(diǎn)死鎖等，針對(duì)不同的情況，學(xué)者提出不同的解決方案。Srinivasan Rajagopala[8]在雙向路徑的機(jī)器人環(huán)境下，通過(guò)增加懲罰函數(shù)的混合整數(shù)模型，減少AGV在運(yùn)行過(guò)程中的碰撞和死鎖。Yoonho等[9]在設(shè)計(jì)單向路徑網(wǎng)絡(luò)時(shí)利用了具有良好局部搜索能力的禁忌搜索算法。過(guò)金超等[10]指出AGV發(fā)生路徑?jīng)_突主要在主干道，于是對(duì)發(fā)生沖突的AGV進(jìn)行優(yōu)先級(jí)的排序，對(duì)于優(yōu)先級(jí)高的AGV具有優(yōu)先進(jìn)入主干道權(quán)限的方法，來(lái)控制主干道上AGV的數(shù)量，保證了主干道不會(huì)出現(xiàn)堵死與沖突的問(wèn)題。

四、總結(jié)與展望

電商行業(yè)的迅速崛起，不僅加快了物流的效率，更給我們帶來(lái)了更多的研究領(lǐng)域，像是電商無(wú)人倉(cāng)路網(wǎng)規(guī)劃、路徑規(guī)劃、任務(wù)分配，儲(chǔ)位分配等問(wèn)題，雖然路徑網(wǎng)絡(luò)設(shè)計(jì)只是電商無(wú)人倉(cāng)規(guī)劃環(huán)節(jié)中的一環(huán)，但是它卻發(fā)揮著關(guān)鍵的作用。

國(guó)內(nèi)外學(xué)者對(duì)于電商無(wú)人倉(cāng)路徑網(wǎng)絡(luò)布局的研究，用到了不同的算法，例如遺傳算法，分支定界算法，啟發(fā)式算法等，但是對(duì)于電商無(wú)人倉(cāng)路網(wǎng)模型建立方面，目標(biāo)函數(shù)更多考慮的是最短化AGV執(zhí)行任務(wù)所花費(fèi)的總路程，在實(shí)際的電商無(wú)人倉(cāng)物流AGV應(yīng)用中，規(guī)劃路網(wǎng)過(guò)程中還應(yīng)該考慮AGV在運(yùn)行中的擁堵現(xiàn)象，如果把擁堵因素考慮進(jìn)路網(wǎng)模型中，這樣設(shè)計(jì)出來(lái)的路徑網(wǎng)絡(luò)可以使得AGV在執(zhí)行任務(wù)時(shí)，不僅可以實(shí)現(xiàn)路程最短的效果，并且可以減少AGV在行駛過(guò)程中發(fā)生碰撞、死鎖的可能性。