[發(fā)明專利]一種基于自適應(yīng)鄰域搜索算法的共享單車搬運優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 202110289562.2
• 申請日: 2021-03-12
• 公開（公告）號: CN112907188B
• 公開（公告）日: 2022-05-24
• 發(fā)明（設(shè)計）人: 李想;張博文;于海濤;張思成;肖冉東
• 申請（專利權(quán)）人: 北京化工大學(xué);北京市智慧交通發(fā)展中心（北京市機(jī)動車調(diào)控管理事務(wù)中心）
• 主分類號: G06Q10/08
• 分類號: G06Q10/08;G06Q10/04;G06Q10/06
• 代理公司: 北京科迪生專利代理有限責(zé)任公司 11251
• 代理人: 安麗

1.一種基于自適應(yīng)鄰域搜索算法的共享單車搬運優(yōu)化方法，其特征在于，步驟為：

第一步，根據(jù)共享單車位置與人們出行需求，基于運輸車搬運共享單車至所需的位置，構(gòu)建以運輸成本最小化為目標(biāo)的共享單車平衡搬運模型；

第二步，基于共享單車平衡搬運模型中運輸車的搬運時間、取放動作和容量限制，設(shè)計自適應(yīng)算子選擇規(guī)則，然后采用大鄰域搜索算法和鄰域搜索算法融合的方法，構(gòu)建自適應(yīng)鄰域搜索算法,求解共享單車平衡搬運模型，得出運輸車的最優(yōu)行駛路徑；

所述大鄰域搜索算法由擾動算子和修復(fù)算子組成，所述擾動算子用于刪除共享單車平衡搬運模型中運輸車行駛路徑上的若干個需求位置，為運輸車行駛路徑的改善提供空間；所述修復(fù)算子用于將擾動算子刪除的需求位置重新插入至運輸車行駛路徑，降低共享單車平衡搬運模型中的運輸成本；

所述鄰域搜索算法由鄰域搜索算子構(gòu)成，鄰域搜索算子用于交換修復(fù)算子修復(fù)好的運輸車行駛路徑上的需求位置，進(jìn)一步降低共享單車平衡搬運模型中的運輸成本；

第一步中，所述共享單車平衡搬運模型由目標(biāo)函數(shù)與約束條件兩部分構(gòu)成；

目標(biāo)函數(shù)：

約束條件：

上述模型中，涉及到的參數(shù)含義如下：

N₀：運輸車起始位置集合；

N₁：需要配送一輛共享單車的位置集合；

N₂：需要拾取一輛未破損共享單車的位置集合；

N₃：需要拾取一輛已破損共享單車的位置集合；

N：上述所有位置的集合，N＝N₀∪N₁∪N₂∪N₃；

Q：運輸車容量；

C：運輸車單位人力成本；

運輸車裝卸一輛共享單車的時間；

α：運輸車在路上行駛的單位費用；

t_ij：運輸車行從位置i行駛到位置j所需的時間，i∈N,j∈N；

T_max：平衡搬運作業(yè)所被允許的最大運行時間；

x_ij：運輸車是否從位置i行駛到了位置j，是取1，否則取0,i∈N,j∈N；

x_ji：運輸車是否從位置j行駛到了位置i，是取1，否則取0,i∈N,j∈N；

x_ii：運輸車是否從位置i行駛到了位置i，是取1，否則取0,i∈N,j∈N；

τ_i：運輸車到達(dá)位置i的時間點，i∈N；

τ_j：運輸車到達(dá)位置j的時間點，j∈N；

a_ij：運輸車從位置i到j(luò)的路徑上裝載的未破損共享單車的數(shù)量,i∈N,j∈N；

a_ji：運輸車從位置j到i的路徑上裝載的未破損共享單車的數(shù)量,i∈N,j∈N；

b_ij：運輸車從位置i到j(luò)的路徑上裝載的已破損共享單車的數(shù)量,i∈N，j∈N；

b_ji：運輸車從位置j到i的路徑上裝載的已破損共享單車的數(shù)量,i∈N,j∈N；

M:表示數(shù)學(xué)模型中取1000000的數(shù)值 ；

Z：表示所取得的數(shù)值為整數(shù)。

2.根據(jù)權(quán)利要求1所述的基于自適應(yīng)鄰域搜索算法的共享單車搬運優(yōu)化方法，其特征在于：第二步中，對擾動算子、修復(fù)算子和鄰域搜索算子的搜索能力分別賦予不同的權(quán)重，再利用輪盤賭隨機(jī)抽樣的方法，構(gòu)建自適應(yīng)算子選擇規(guī)則。