[發明專利]一種帶有時間窗的自動化集裝箱碼頭AGV重進重出路徑規劃方法

有效

• 申請號: 202010858779.6
• 申請日: 2020-08-24
• 公開（公告）號: CN112053046B
• 公開（公告）日: 2022-03-11
• 發明（設計）人: 亓亮;徐藝翔;馬慧娟;張福新;欒文靜
• 申請（專利權）人: 山東科技大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q10/08;G06N3/12;B65G67/60
• 代理公司: 青島錦佳專利代理事務所(普通合伙) 37283
• 代理人: 朱玉建

1.一種帶有時間窗的自動化集裝箱碼頭AGV重進重出路徑規劃方法，其特征在于，

包括如下步驟：

I.構建帶有時間窗約束的單一貨船多AGV重進重出調度模型；

首先給出與單一貨船多AGV重進重出調度模型相關的參數的定義，分別如下：

N＝{1,2,···}表示自然數的集合；m表示所有AGV數量，m∈N；

N_m＝{1,2,···,m}；

B表示堆場集合；V表示一個任務點的集合，V＝{v₁,v₂,…,v_n}，n表示任務點數量；

v_i表示集合V中的任務點，v_i＝(b,T₁,T₂)；

b表示集裝箱i存放的堆場，b∈B；

T₁表示AGV運輸集裝箱i到達堆場的最早時刻t₁₁和最晚時刻t₁₂的集合，T₁＝[t₁₁,t₁₂]；

T₂表示AGV運輸集裝箱i到達岸橋的最早時刻t₂₁和最晚時刻t₂₂的集合，T₂＝[t₂₁,t₂₂]；

X表示堆場卸箱任務集合，從船上卸載的集裝箱存放到堆場，X∈V；

Y表示堆場裝箱任務集合，將堆場中的集裝箱裝載到船上，Y∈V；

x表示堆場卸箱任務集合X中任務點的編號，0≤x≤|X|，|X|表示集合X的元素個數；

y表示堆場裝箱任務集合Y中任務點的編號，|X|+1≤y≤|V|，|V|表示集合V的元素個數；

Vs表示一個虛擬的開始任務點，Ve表示一個虛擬的結束任務點；

k表示第k輛AGV的編號，簡記為A_k，k∈N_m；

L_i^k表示岸橋從A_k裝載或卸載集裝箱i的時刻；

P_i^k表示場橋從A_k裝載或卸載集裝箱i的時刻；

T_i^k表示A_k運輸任務點v_i的時間，對于卸箱任務點而言，T_i^k是指從岸橋到集裝箱i存放的堆場的運輸時間，對于裝箱任務點而言，T_i^k是指從集裝箱i存放的堆場到岸橋的運輸時間；

P_ij^k表示A_k在堆場區從任務點v_i卸箱后到任務點v_j裝箱前的空車行駛時間；

L_ij^k表示岸橋從A_k提取任務點v_i到裝載新任務點v_j到A_k的操作時間；

M表示無窮大；

定義如下決策變量：

構建帶有時間窗約束的單一貨船多AGV重進重出調度模型，該單一貨船多AGV重進重出調度的目標函數為最短調度時間，目標函數滿足公式(1)：

其中，表示所有AGV結束時間中最晚的時間；

Z表示所有AGV運輸的結束時間，minZ表示所有求解結果的最短時間；

該單一貨船多AGV重進重出調度模型的目標函數的約束條件如公式(2)-(11)所示；

公式(2)表示所有任務點以及虛擬結束節點有且僅有一個前驅任務點；

其中，公式(2)中χ_i^j表示若任務點v_i前有一個任務點是v_j，則χ_i^j＝1，否則χ_i^j＝0；

公式(3)表示所有任務點以及虛擬開始節點有且僅有一個后繼任務點；

其中，公式(3)中χ_i^j表示若任務點v_j后有一個任務點是v_i，則χ_i^j＝1，否則χ_i^j＝0；

公式(4)表示對于所有的卸箱任務點，其前驅和后繼不能為卸箱任務點；

其中，公式(4)中v_x,v_x'分別表示卸箱任務集合X中的任務點，表示若一輛AGV運輸任務點v_x后運輸任務點v_x'，則否則

公式(5)表示對于所有的裝箱任務點，其前驅和后繼不能為裝箱任務點；

其中，公式(5)中v_y,v_y'分別表示卸箱任務集合Y中的任務點，表示若一輛AGV運輸任務點v_y后運輸任務點v_y'，則否則

公式(6)表示所有任務點僅由一輛AGV運輸；

公式(7)表示AGV完成卸箱任務點后駛往裝箱任務點的到達時間要早于裝箱任務點開始時間；其中，表示場橋從A_k卸載任務點v_x的時刻，表示A_k在堆場區從任務點v_x卸箱后到任務點v_y裝箱前的空車行駛時間，表示場橋從A_k裝載任務點v_y的時刻；

表示若一輛AGV運輸完任務點v_x后運輸任務點v_y，則否則

公式(8)表示岸橋在從AGV提箱后裝載卸箱任務的完成時間要早于卸箱任務點開始時間；其中，表示岸橋從A_k卸載任務點v_y的時刻，表示岸橋從A_k提取任務點v_y到裝載新任務點v_x到A_k的操作時間，表示岸橋從A_k裝載任務點v_y的時刻；

表示若一輛AGV運輸完任務點v_y后運輸任務點v_x，則否則

公式(9)表示對于每一個任務點，其裝箱時刻和卸箱時刻滿足任務的時間窗要求；

公式(10)表示對卸箱任務的時間要求；其中，表示岸橋從A_k裝載任務點v_y的時刻，表示A_k從岸橋到任務點v_x的運輸時間，表示場橋從A_k卸載任務點v_x的時刻；

公式(11)表示對裝箱任務的時間要求；其中，表示場橋從A_k裝載任務點v_y的時刻，表示A_k從任務點v_y到岸橋的運輸時間，表示岸橋從A_k卸載任務點v_y的時刻；

II.基于遺傳算法對以上帶有時間窗約束的單一貨船多AGV重進重出調度模型求解；

首先給出與遺傳算法求解相關的參數的定義，分別如下：

q表示遺傳算法初始種群數量；q′表示遺傳算法子代種群數量；

t表示當前迭代次數；t_max表示最大迭代次數；

P表示個體適應度值；P_l表示重進重出懲罰系數；P_t表示場橋時間窗懲罰系數；P_q表示岸橋時間窗懲罰系數；T表示個體調度序列中AGV的行駛時間總和；

P_c表示交叉概率；P_v表示變異概率；P_r表示逆轉概率；

利用遺傳算法對帶有時間窗約束的單一貨船多AGV重進重出調度模型的求解過程為：

II.1.給定卸箱任務集合X和裝箱任務集合Y；

將卸箱任務集合X和裝箱任務集合Y中所有任務點進行統一編號；將所有編號按照調度要求的AGV最早到達時間進行排序，得到一組AGV調度序列；

將該AGV調度序列分配給一輛AGV調度，剩余的m-1輛AGV處于空載狀態，然后將該AGV調度序列復制q份，稱之為q個個體；設置當前迭代次數t＝1；

II.2.對于每一個個體，計算該個體在AGV調度過程中出現的不合法情況的次數；

其中，AGV調度過程中不合法的情況分為三種，即AGV運輸過程中不符合岸橋時間窗、不符合場橋時間窗以及AGV運輸過程不符合重進重出要求；

當出現不合法情況時，該個體的時間會在當前運輸時間上累加一部分懲罰值；

定義不符合岸橋時間窗的任務點數量為a，不符合場橋時間窗的任務點數量為b，不符合重進重出的任務點數量為c，則該個體的個體適應度值P＝a*P_q+b*P_t+c*P_l+T；

其中，a*P_q表示調度序列不符合岸橋時間窗的懲罰值，b*P_t表示調度序列不符合場橋時間窗的懲罰值，c*P_l表示調度序列不符合重進重出的懲罰值；

對于每個個體，分別計算該個體的個體適應度值P；個體適應度值P越小，則被選擇概率越大，按照輪盤賭的方式從q個個體中選擇q′個個體生成子代種群，進入進化過程；

II.3.對于步驟II.2中選擇的q′個個體所代表的AGV調度序列進行隨機變換，隨機生成q′個AGV調度序列，然后將AGV調度序列分配給AGV去調度；

其中，隨機變換包括將子代種群兩兩組合，以交叉概率P_c進行交叉操作，對每個個體以變異概率P_v進行變異操作，以及以逆轉概率P_r進行逆轉操作；

II.4.首先將步驟II.3中隨機變換生成的q′個個體插入初始種群中生成新種群，并根據步驟II.2中的個體適應度值P作出保留和淘汰，從新種群中選擇q個個體；

其次，判斷是否達到最大迭代次數t_max：

如果未達到最大迭代次數t_max，則進入步驟II.2進行迭代；否則輸出個體適應度最好的個體，即具有最小個體適應度值P的合法調度序列，該序列滿足時間窗和重進重出的要求。