[發明專利]一種車間無人運輸系統任務分配與路徑規劃方法

在審

• 申請號: 201910850108.2
• 申請日: 2019-09-10
• 公開（公告）號: CN110674978A
• 公開（公告）日: 2020-01-10
• 發明（設計）人: 史彥軍;王魯軍;沈衛明
• 申請（專利權）人: 大連理工大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q10/08
• 代理公司: 21200 大連理工大學專利中心
• 代理人: 溫福雪;侯明遠

本發明用于車間無人運輸系統，具體涉及一種基于局部搜索的無人運輸系統的任務分配與路徑規劃方法。局部搜索算法即通過對當前解進行一個擾動，產生一個新解，如果新解優于當前解，則更新新解為當前解。局部搜索算法可以高效的找到一個可行解，但是由于在更新當前解時只接受更優解，這樣便容易陷入局部最優解，并且由于任務是固定的，會使得搜索范圍較小，很可能錯失其他區域的更好的解。因此，本發明旨在解決陷入局部最優解和擴大搜索區域。本發明通過使用兩個參數，使得在適當的時刻跳出局部最優解，從而得到更高效的路徑。

技術領域

本發明用于車間無人運輸系統，具體涉及一種車間無人運輸系統任務分配與路徑規劃方法。

背景技術

隨著5G與人工智能的發展，移動云基機器人(mobile cloud robotics，MCR)會越來越多的被運用到無人運輸系統內，用來減少人力花費，提高生產效率。MRC將人工智能、云與機器人技術結合在一起，在5G技術的支持下，使得無人運輸系統不再受機載計算、內存或軟件資源的限制。相較于自動導引車(AGV)，MCR成本更低，效率更高。

在制造車間內，有多個物料倉庫，每個倉庫停有一個有容量限制的MCR，根據每個加工地點的位置與需求量，將它們分配給合適的MCR，MRC從初始倉庫出發，將物料送到對應的加工地點，并且最終回到初始倉庫，這個問題是一個有容量限制的路徑規劃與調度問題(CVRP)。該問題可以簡化看成在一個制造車間里的多個旅行商問題(Travelling salesmanproblem，TSP)，屬于NP-Hard問題，采用局部搜索方法求解很可能陷入局部最優解。本發明通過改進局部搜索方法，避免陷入局部最優解，實現無人運輸系統成本最小化。

發明內容

本發明要解決的技術問題，是制造車間無人運輸系統的任務分配與路徑規劃問題，最終使得無人運輸系統成本最小化。

為了達到上述目的，本發明技術方案如下：

一種車間無人運輸系統任務分配與路徑規劃方法，步驟如下：

第一步，將實際問題簡化成模型

一個制造車間有M個物料倉庫，有N個加工地點有物料需求，每個物料倉庫有一輛容量相同的MCR。目標是在運輸距離最短的情況下滿足每個加工地點的需求。以下介紹模型中符號的含義：

M：MCR的個數，即物料倉庫的個數；

N：需要運送物料的加工地點的個數，即運輸任務數；

K：所有MCR的集合，K＝{1，2…M}；

B：物料倉庫集合，B＝{1,2…M}；

k：MCR的編號，k∈K；

C：每個MCR的容量；

V：全部點組成的集合，包括所有倉庫和加工地點，V＝{1,2…N,N+1,N+2,…N+M}；

i，j：集合V中的任意點；

A：工作地點集合，也即運輸任務集合，A＝{1，2…N}；

C_A：A中每一個工作地點的物料需求量集合；

C_Ai：A中任意一個工作地點i的物料需求量，C_Ai>0；

V_k：編號為k的MCR分配到的運輸任務點集合，V_k∈V；

V′_k：編號為k的MRC的路徑中應該包括的點,包括物料倉庫點；

N_k：編號為k的MCR分配到的運輸任務數量,