[發明專利]一種用于自動化倉庫的車輛路徑優化方法

有效

• 申請號: 201811270333.0
• 申請日: 2018-10-29
• 公開（公告）號: CN109492800B
• 公開（公告）日: 2023-05-02
• 發明（設計）人: 吳勝昔;劉威;李勇亮;李一塵;張勇;盧文建;吳瀟穎;李銳;顧幸生
• 申請（專利權）人: 華東理工大學;上港集團物流有限公司興寶倉儲分公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明提供一種用于自動化倉庫的車輛路徑優化方法。該方法基于模擬退火和禁忌搜索的混合算法，針對車輛路徑中的入庫出庫始末位置確定的規劃問題，設置約束條件，采用模擬退火算法求得初始解，使得禁忌搜索算法可以避免選取隨機產生的初始解，直接引用模擬退火算法的初始解進行二次優化，從而得到效果更佳的全局解。該方法運用于一種始末位置確定的車輛路徑優化，屬于倉庫作業調度領域。優化之后，車輛從指定入庫位置出發，遍歷倉庫中的所有庫位，經過每個庫位有且僅有一次，最后達到指定出庫位置。結合倉庫實際的車輛路徑調度情況，該優化方法實用性強，可用性好。

技術領域

本發明屬于倉儲物流自動化調度領域，涉及一種用于自動化倉庫的車輛路徑優化的方法。

背景技術

伴隨物流倉儲行業的迅猛發展，過去的倉儲方式與如今的物資生產和流通的需求相比，出現了滯后情況，因此立體倉庫得以被越來越多的人們重視并加以運用。立體倉庫的作業效率取決于多方面因素，包括倉庫貨位的分配策略，車輛路徑的優化選擇以及考慮倉庫軟硬件的結合設計等等。因此，關于立體倉儲庫位優化、車輛路徑規劃(Vehicle?RoutingProblem，VRP)的問題模型和算法的研究成為倉儲行業自動化調度的研究重點。

自動化倉庫調度問題是對旅行商(Traveling?Salesman?Problem，TSP)問題的一種擴展，屬于最困難的組合優化問題之一。Golden，Magnanti?and?Nguyan于1972年以“vehicle?routing”為標題研究車輛路徑問題。其后，Golden?and?Stewart在1978年將不確定概率論引入VRP問題。到20世紀90年代，得益于個人計算機的飛速發展，VRP問題得到進一步研究。同樣地，這個時期也出現了各類求解混合優化問題的啟發式算法，這些算法也被用來解決VRP問題。Laporte?and?Gendreau?et?al.于1998年研究了VRP的算法運用，諸如遺傳算法、蟻群算法、神經網絡算法、模擬退火、禁忌搜索等等。并且還提出了旅行商概率問題PTSP、車輛路徑概率問題PVRP和隨機車輛路徑問題SVRP，另外還有時間依賴旅行商問題TD-TSP、時間依賴車輛路徑問題TD-VRP以及動態車輛路徑問題。

對比國外，國內研究車輛路徑問題的起步較晚，在90年代末才開始研究VRP，之后逐步受到重視，越來越多的人開始深入研究。就近十多年的時間經歷了國外幾個階段的發展。無論從算法本身的研究，還是關于車輛路徑的擴展都有長足和廣泛的研究，每年關于車輛路徑問題的研究文獻數量成倍增長。

發明內容

針對現有技術的倉儲物流自動化調度所存在的上述缺陷，本發明提供了一種用于自動化倉庫的車輛路徑優化的方法。本發明所要解決的問題與典型的TSP問題不同，研究對象為自動化倉庫的車輛路徑優化問題，通常指入庫出庫的始末位置確定的情況下的車輛路徑調度。采用本發明的車輛路徑優化方法，在倉庫的分塊區域，從指定入庫位置出發，遍歷倉庫中的所有庫位，經過每個庫位有且僅有一次，最后達到指定出庫位置。

依據本發明的一個方面，提供了一種自動化倉庫的車輛路徑優化方法，用于實現所述自動化倉庫的入庫出庫始末位置確定時的車輛路徑調度，該方法包括以下步驟：

步驟1：針對各個區域，均不考慮倉庫庫位始末位置，剩余庫位點采用模擬退火算法搜尋最優初始解，并由模擬退火算法生成較優庫位序列串號以及車輛路徑長度，其中利用Matlab軟件中的randperm函數生成隨機序列，作為初始庫位序列S0，計算按該庫位序列行駛的車輛路徑長度D0，初始化參數，定義初值T₀，下降比率α，結束值T_f，禁忌表Tlist，設置禁忌表長度tl，候選解個數cl；

步驟2：依據下降公式T(n+1)＝α*T(n)，如果T(n+1)≤T_f，返回庫位序列Sequence和對應的車輛路徑長度d_best，跳轉至步驟6，否則執行下一步驟；