[發(fā)明專利]一種考慮實(shí)際多約束的多條等效最優(yōu)路徑規(guī)劃方法

在審

• 申請?zhí)枺?/td>: 202210874939.5
• 申請日: 2022-07-25
• 公開（公告）號: CN115146866A
• 公開（公告）日: 2022-10-04
• 發(fā)明（設(shè)計）人: 葛洪偉;張海飛;江明;李婷
• 申請（專利權(quán)）人: 江南大學(xué)
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q10/08;G06N3/00
• 代理公司: 哈爾濱市陽光惠遠(yuǎn)知識產(chǎn)權(quán)代理有限公司 23211
• 代理人: 呂永芳

1.一種考慮實(shí)際多約束的多條等效最優(yōu)路徑規(guī)劃方法，其特征在于，所述方法包括：

考慮符合實(shí)際的多約束條件并構(gòu)造對應(yīng)的目標(biāo)函數(shù)；所述多約束條件包括復(fù)雜路網(wǎng)約束、負(fù)載約束、時間窗約束、需求可拆分約束；

采用改進(jìn)差分進(jìn)化算法EIDSDE求解得到物流配送的多條等效最優(yōu)路徑規(guī)劃，所述改進(jìn)差分進(jìn)化算法EIDSDE在種群初始化階段引入廣義反向?qū)W習(xí)策略約束種群的搜索空間；在個體選擇階段，以三種概率方式在種群中選擇生成差分向量的個體，并對被選擇的所有個體進(jìn)行擁擠距離和特殊擁擠距離的計算，同時將擁擠距離的計算方式轉(zhuǎn)換為相鄰歐氏距離的加權(quán)和；在變異階段，若變異產(chǎn)生的個體不滿足邊界條件，則進(jìn)行二次變異，若二次變異的個體仍不滿足邊界條件，則按照預(yù)設(shè)修補(bǔ)策略進(jìn)行修補(bǔ)使其滿足邊界條件；在環(huán)境選擇階段，選擇預(yù)定百分比的前級個體；所述種群中的每個個體代表物流配送的一條可能的路徑。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述復(fù)雜路網(wǎng)約束指交通要素以及城市路網(wǎng)拓?fù)浣Y(jié)構(gòu)產(chǎn)生的約束；所述負(fù)載約束指車輛在進(jìn)行裝貨時不得超過車輛的最大負(fù)載；所述時間窗約束指物流配送的時間上下線；所述需求可拆分約束指配送貨物是否可被拆分的約束。

3.根據(jù)權(quán)利要求2所述的方法，其特征在于，所述方法考慮4種約束下所構(gòu)造對應(yīng)的目標(biāo)函數(shù)分別為：

f₁車輛數(shù):

f₂總距離:

f₃總配送時間:

f₄總配送成本:

其中，R為完成配送任務(wù)所需的車輛數(shù)，q_i為顧客i的需求量，w為車輛最大運(yùn)載能力，n表示顧客的數(shù)量，表示向上取整；

d_ij為顧客點(diǎn)i到顧客點(diǎn)j的配送距離，表示第r條路線中車輛是否通過弧(i,j)，r∈R，i,j∈C'為決策變量，當(dāng)且僅當(dāng)?shù)趓條路線中車輛通過弧(i,j)時，否則表示每個顧客至少被訪問1次，C＝{0,1,2,...,n}表配送中心和顧客的集合，C'＝C/{C₀}表n個顧客的集合；

Td_j為車輛在顧客j處的等待時間，v表示配送車輛的速度，β為違反顧客所規(guī)定的配送時間而產(chǎn)生的時間成本系數(shù)，表示配送任務(wù)是否有時間要求，b_ir表示車輛r到達(dá)顧客i處的實(shí)際時間，b_or＝0表示車輛出發(fā)時刻為0，LT_i表示允許配送車輛到達(dá)顧客i處的最晚時間；

FY為費(fèi)用矩陣，每條路徑a_ij∈A對應(yīng)的費(fèi)用fy_ij∈FY，G為車輛的固定成本，l為時間延遲成本，α為單位距離對應(yīng)的時間延遲成本，S^r表示第r條路線中服務(wù)的顧客集合，即第r輛車負(fù)責(zé)配送的顧客集合，|S^r|表示集合中包含的元素個數(shù)，即顧客個數(shù)，(x_i,y_i)表示顧客i的坐標(biāo)。

4.根據(jù)權(quán)利要求3所述的方法，其特征在于，所述方法中，每個個體代表物流配送的一條可能的路徑，對應(yīng)至種群中，每個個體對應(yīng)一個點(diǎn)，每個點(diǎn)的維度表示該路徑所經(jīng)過的客戶數(shù)；所述在種群初始化階段引入廣義反向?qū)W習(xí)策略約束種群的搜索空間包括：

假設(shè)P為候選解，表示一條可能的路徑，假設(shè)P＝(z₁,z₂,...,z_D)為一個D維空間的點(diǎn)，其中z₁,z₂,...,z_D∈R且z_m∈[L_m,U_m]，f(·)為候選解的目標(biāo)函數(shù)適應(yīng)值，則P的反向點(diǎn)為其中k＝random(0,1)，若則若則表示比P具有更好的適應(yīng)值，此時選擇代替P，否則保持不變。