[發(fā)明專利]一種帶硬時間窗的刀具準時配送路徑規(guī)劃算法

有效

• 申請?zhí)枺?/td>: 201810033444.3
• 申請日: 2018-01-15
• 公開（公告）號: CN108267954B
• 公開（公告）日: 2020-04-03
• 發(fā)明（設計）人: 張維;楊洋洋;吳燕;馬志華
• 申請（專利權）人: 西北工業(yè)大學
• 主分類號: G05B13/04
• 分類號: G05B13/04
• 代理公司: 西北工業(yè)大學專利中心 61204
• 代理人: 常威威

1.一種帶硬時間窗的刀具準時配送路徑規(guī)劃算法，其特征在于包括以下步驟：

步驟1：已知刀具倉庫中心中工位每個工序的開工時間和需求、每個工序的硬時間窗、閉合式車輛路徑，且每個工序只有一輛車配送，按以下公式確定決策變量：

其中，x_ijk為表示工序之間的行駛順序以及配送小車的變量，y_ik為表示工序由哪輛車配送的變量，i、j表示工序編號，i＝1,2,…,N，j＝1,2,…,N，N為工序總數(shù)，k表示車輛的編號，k＝1,2,…,K，K為車輛總數(shù)；

步驟2：分別按以下公式建立不等式約束：

t_id＜t_i＜t_iu (3)

其中，t_id表示工序i的時間窗下限，t_iu表示工序i的時間窗上限，t_i表示配送車輛到達工序i所對應工位的時間；

步驟3：按照建立優(yōu)化目標函數(shù)，其中，μ_i為工序i的滿意度，按照計算，t_ie表示工序i的期望小車服務時間；

步驟4：隨機產生popsize個個體作為初始種群，每個個體為所有工序編號的自然數(shù)全排列，即工序編號編碼，popsize為遺傳算法初始化參數(shù)，取值范圍為10～200；

步驟5：根據(jù)各工序的時間窗要求，分別對每個個體進行解碼，即將工序編號編碼轉化為工位編碼，具體為：

步驟a：將小車的發(fā)車時間初始化為最早開工的工序的開工時間的前11min，針對一個個體，首先在工位編碼的第一個編碼位置插入0，然后從左到右遍歷個體的工序編號編碼，根據(jù)配送中心與工序編號所對應工位之間的行駛時間，找出能夠在時間窗內到達工序的所在工位，如果可以找到，將工位編號放入工位編碼里，并將其工序編號從工序編號編碼中去掉，此時，小車的行駛時間為小車的發(fā)車時間加上配送中心到達工序編號所對應工位的行駛時間，轉入步驟b；否則，改變小車的發(fā)車時間為工序編號編碼第一個編碼位置所對應工序的開工時間減去11min，然后從左到右遍歷工序編號編碼,根據(jù)配送中心與工序編號所對應工位之間的行駛時間，找到可以在時間窗內到達工序的所在工位，將工位編號放入工位編碼里，并將其工序編號從工序編號編碼中去掉，此時，小車的行駛時間為小車的發(fā)車時間加上配送中心到達工序編號所對應工位的行駛時間，轉入步驟b；

步驟b：以小車的行駛時間為基礎，從左到右遍歷工序編號編碼，根據(jù)工序編號所對應工位之間的行駛時間，尋找可以在時間窗內到達的工序所在的工位，將工位編號放入工位編碼里，并將其工序編號從工序編號編碼中去掉，小車的行駛時間更新為上一小車行駛時間加上工序編號所對應工位之間的行駛時間，重復此步驟，直到找不到滿足條件的工序，轉入步驟c；

步驟c：在工位編碼的最后位置加入0，并判斷此時工序編號編碼的長度是否為0，如果為0，則解碼結束；否則，返回到步驟a；

步驟6：按照fitness(i)＝value(i),i＝1,2...,popsize計算得到每個個體的適應度值,其中value(i)為第i個體的工序平均滿意度值與車輛數(shù)量值的倒數(shù)之和，工序平均滿意度是指工位編碼中所有非0的編碼對應的工序的滿意度的平均值；車輛數(shù)量值是指工位編碼中0的數(shù)量減1；

步驟7：根據(jù)步驟6計算出來的適應度值，采用比例選擇方法對初始種群進行選擇，得到適應度高的個體組成父代種群；

步驟8：以一定的交叉概率P_c，采用部分匹配法對步驟7選擇出的個體進行交叉，得到子代種群，P_c的取值范圍為0.4～0.99；

步驟9：以一定的變異概率P_m，采用逆轉變異算法對步驟8得到的子代種群進行變異，得到下一代臨時種群，P_m的取值范圍為0.0001～0.1；

步驟10：記錄臨時種群中適應度值最高的個體，并判斷是否達到最大迭代次數(shù)N_d，若是，則結束，從記錄的每一代適應度值最高的個體所組成的集合中，找出適應度值最大的個體，則這個適應度值最大的個體解碼所得的路徑即為最優(yōu)刀具配送路徑；否則，以步驟9得到的臨時種群為初始種群，返回步驟5，迭代次數(shù)加1，所述的迭代次數(shù)初始值為1，最大迭代次數(shù)N_d的取值范圍為100～500。