[發(fā)明專利]揀貨路徑規(guī)劃方法與裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201711321490.5
• 申請(qǐng)日: 2017-12-12
• 公開（公告）號(hào): CN109919345B
• 公開（公告）日: 2021-06-29
• 發(fā)明（設(shè)計(jì)）人: 王天文;董紅宇;莫澤
• 申請(qǐng)（專利權(quán)）人: 北京京東振世信息技術(shù)有限公司
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06Q10/08;G06N3/00
• 代理公司: 北京律智知識(shí)產(chǎn)權(quán)代理有限公司 11438
• 代理人: 闞梓瑄;王衛(wèi)忠

本公開提供一種基于蟻群算法的揀貨路徑規(guī)劃方法與裝置。揀貨路徑規(guī)劃方法包括：以多個(gè)節(jié)點(diǎn)為起點(diǎn)，啟動(dòng)多只螞蟻的路徑遍歷，所述節(jié)點(diǎn)包括多個(gè)揀貨節(jié)點(diǎn)、揀貨起點(diǎn)、揀貨終點(diǎn)；根據(jù)多個(gè)所述節(jié)點(diǎn)之間的路徑的信息素?cái)?shù)值計(jì)算所述螞蟻轉(zhuǎn)移到其他所述節(jié)點(diǎn)的轉(zhuǎn)移概率，將螞蟻移動(dòng)到所述轉(zhuǎn)移概率最大的所述節(jié)點(diǎn)上；判斷一只螞蟻遍歷所有所述節(jié)點(diǎn)后，更新路徑的信息素?cái)?shù)值，記錄一個(gè)遍歷路徑；根據(jù)多個(gè)遍歷路徑確定最優(yōu)路徑。本公開提供的揀貨路徑規(guī)劃方法可以提高揀貨效率，節(jié)省揀貨路徑規(guī)劃時(shí)間。

技術(shù)領(lǐng)域

本公開涉及機(jī)器學(xué)習(xí)技術(shù)領(lǐng)域，具體而言，涉及一種基于精英蟻群算法的揀貨路徑規(guī)劃方法與裝置。

背景技術(shù)

隨著電子商務(wù)的發(fā)展，在倉庫揀貨過程中的路徑規(guī)劃成為提高物流效率的重要環(huán)節(jié)。在倉庫中，由于邏輯區(qū)面積較大，揀選的區(qū)域范圍較廣，一個(gè)集合單涉及揀選的儲(chǔ)位通常有幾十個(gè)，尋找合理的揀貨路徑可以降低揀貨距離，提升揀貨效率并且節(jié)省人力成本。尤其每當(dāng)大促期間，通過優(yōu)化揀貨環(huán)節(jié)，可以明顯地加快發(fā)貨速度，提高倉儲(chǔ)的利用率并改善用戶體驗(yàn)。

揀貨路徑優(yōu)化是指通過優(yōu)化減少揀貨員在倉庫間的行走距離，以最短的時(shí)間揀出貨品，提高揀貨效率。相關(guān)的揀貨路徑優(yōu)化往往通過基于策略的方法，比如基于U型策略或S型策略的揀貨方法。由于倉庫儲(chǔ)位布局各有區(qū)別，現(xiàn)有的揀貨路徑策略可以給出一個(gè)具有固定起點(diǎn)和終點(diǎn)的揀貨路徑方案，但是由于存在起點(diǎn)和終點(diǎn)固定的約束條件，生成的遍歷路徑難以保證路徑最短，從而導(dǎo)致揀貨人員繞路以及揀貨效率低等問題；此外，揀貨路徑優(yōu)化問題屬于NP-Hard問題，隨著問題規(guī)模增加，原有揀貨路徑算法在求解時(shí)間和優(yōu)化效果上尚有一定提升空間。

因此，需要一種能夠快速規(guī)劃出最優(yōu)揀貨路徑的揀貨路徑規(guī)劃方法。

需要說明的是，在上述背景技術(shù)部分公開的信息僅用于加強(qiáng)對(duì)本公開的背景的理解，因此可以包括不構(gòu)成對(duì)本領(lǐng)域普通技術(shù)人員已知的現(xiàn)有技術(shù)的信息。

發(fā)明內(nèi)容

本公開的目的在于提供一種揀貨路徑規(guī)劃方法與路徑規(guī)劃裝置，用于在提高揀貨路徑規(guī)劃效率的同時(shí)提供更優(yōu)的揀貨路徑規(guī)劃方案。

根據(jù)本公開實(shí)施例的第一方面，提供一種揀貨路徑規(guī)劃方法，包括：以多個(gè)節(jié)點(diǎn)為起點(diǎn)，啟動(dòng)多只螞蟻的路徑遍歷，所述節(jié)點(diǎn)包括多個(gè)揀貨節(jié)點(diǎn)、揀貨起點(diǎn)、揀貨終點(diǎn)；根據(jù)多個(gè)所述節(jié)點(diǎn)之間的路徑的信息素?cái)?shù)值計(jì)算所述螞蟻轉(zhuǎn)移到其他所述節(jié)點(diǎn)的轉(zhuǎn)移概率，將螞蟻移動(dòng)到所述轉(zhuǎn)移概率最大的所述節(jié)點(diǎn)上；判斷一只螞蟻遍歷所有所述節(jié)點(diǎn)后，更新路徑的信息素?cái)?shù)值，記錄一個(gè)遍歷路徑；根據(jù)多個(gè)遍歷路徑確定最優(yōu)路徑。

根據(jù)本公開實(shí)施例的第二方面，提供一種路徑規(guī)劃裝置，包括：初始化模塊，設(shè)置為以多個(gè)節(jié)點(diǎn)為起點(diǎn)，啟動(dòng)多只螞蟻的路徑遍歷，所述節(jié)點(diǎn)包括多個(gè)揀貨節(jié)點(diǎn)、揀貨起點(diǎn)、揀貨終點(diǎn)；路徑生成模塊，設(shè)置為根據(jù)多個(gè)所述節(jié)點(diǎn)之間的路徑的信息素?cái)?shù)值計(jì)算所述螞蟻轉(zhuǎn)移到其他所述節(jié)點(diǎn)的轉(zhuǎn)移概率，將螞蟻移動(dòng)到所述轉(zhuǎn)移概率最大的所述節(jié)點(diǎn)上；信息素更新模塊，設(shè)置為判斷一只螞蟻遍歷所有所述節(jié)點(diǎn)后，更新路徑的信息素?cái)?shù)值，記錄一個(gè)遍歷路徑；最優(yōu)選擇模塊，設(shè)置為根據(jù)多個(gè)遍歷路徑確定最優(yōu)路徑。

根據(jù)本公開的第三方面，提供一種路徑規(guī)劃裝置，包括：存儲(chǔ)器；以及耦合到所屬存儲(chǔ)器的處理器，所述處理器被配置為基于存儲(chǔ)在所述存儲(chǔ)器中的指令，執(zhí)行如上述任意一項(xiàng)所述的方法。

根據(jù)本公開的第四方面，提供一種計(jì)算機(jī)可讀存儲(chǔ)介質(zhì)，其上存儲(chǔ)有程序，該程序被處理器執(zhí)行時(shí)實(shí)現(xiàn)如上述任意一項(xiàng)所述的揀貨路徑規(guī)劃方法。

本公開提供的揀貨路徑規(guī)劃方法通過將基于現(xiàn)有策略產(chǎn)生的最優(yōu)揀貨路徑方案作為異步并行精英蟻群優(yōu)化算法的參考精英方案，異步并行計(jì)算出最優(yōu)揀貨路徑方案，在提高揀貨路徑規(guī)劃效率的同時(shí)提供了更優(yōu)的揀貨路徑規(guī)劃方案。異步并行精英蟻群優(yōu)化算法保證了算法的求解時(shí)間和優(yōu)化效果，解決了現(xiàn)有單純基于策略的揀貨路徑規(guī)劃方案優(yōu)化效果不理想和機(jī)器學(xué)習(xí)等算法時(shí)效差的問題。

應(yīng)當(dāng)理解的是，以上的一般描述和后文的細(xì)節(jié)描述僅是示例性和解釋性的，并不能限制本公開。