[發(fā)明專利]基于滾動時域控制的動態(tài)外賣配送的方法及裝置

在審

• 申請?zhí)枺?/td>: 201811610415.5
• 申請日: 2018-12-27
• 公開（公告）號: CN109858752A
• 公開（公告）日: 2019-06-07
• 發(fā)明（設(shè)計）人: 張玉州;葉亮;鄭軍帥;徐廷政;張子為
• 申請（專利權(quán)）人: 安慶師范大學(xué)
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q10/08
• 代理公司: 溫州市品創(chuàng)專利商標代理事務(wù)所(普通合伙) 33247
• 代理人: 洪中清

1.一種基于滾動時域控制的動態(tài)外賣配送的方法，其特征在于，包括：

基于外賣配送的各個約束條件，建立動態(tài)外賣VRP優(yōu)化總成本最小化的模型和目標函數(shù)；

基于RHC-NN算法對動態(tài)外賣VRP優(yōu)化總成本最小化的模型和目標函數(shù)求解，獲得外賣配送策略。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，外賣配送的各個約束條件，包括：

只考慮單站點單人單車輛的配送，單次行駛距離最大為L，配送速度V；

配送路徑優(yōu)化的目標是行使成本最低，即總延誤時間最小，距離最小；

每位顧客服務(wù)點都要訪問一次，且只訪問一次；

每位顧客預(yù)期的需求時間，當未及時到達，顧客滿意度會受到影響；

每輛車輛的服務(wù)總需求量在該車輛的承載能力Q以內(nèi)，車輛保持勻速行駛；

顧客需求具有動態(tài)性，初始化生成的訂單存在著動態(tài)干擾。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，動態(tài)外賣VRP優(yōu)化總成本最小化的模型和目標函數(shù)為：

ET_i≤t_i≤LT_i i＝1,2,...,N (6)

x_ij,y_ij∈(0,1) i,j＝0,1,...,N (7)

式(1)為目標函數(shù)，是此次配送的車輛的運輸成本最小；式(2)為車輛容量約束，車輛載重貨物總量不得超出承載能力；式(3)保證整個路徑中不存在局部多余的路徑；式(4)、(5)確保每個顧客都會被配送；式(6)為需求時間約束；式(7)為決策變量；

Q：一輛車的車載量；

M_i：每位顧客訂單的需求量；

Tn：車輛配送的最大行駛時間；

En：顧客訂單的最早到達時間；

Fn：顧客訂單最晚到達時間；

N：配送點個數(shù)，其訂單需求記M_i(i＝1，2，…N)；

c_ij：表示從點i到點j的運輸成本；

x_ij：表示車輛從i到j(luò)的配送過程發(fā)生，x_ij＝1；

任務(wù)i最早開始服務(wù)時間為ET_i，任務(wù)最晚服務(wù)時間為LT_i。

4.根據(jù)權(quán)利要求3所述的方法，其特征在于，基于RHC-NN算法對動態(tài)外賣VRP優(yōu)化總成本最小化的模型和目標函數(shù)求解，獲得外賣配送策略，包括：

S21：假設(shè)已知NW外賣訂單到達時間，設(shè)置時間間隔長度T與時域上時間間隔總數(shù)NW，初始化時域序號q＝1；

S22：根據(jù)當前外賣訂單信息，由所有計劃到達時間位于[t(q)，t(q)+NT]的外賣，構(gòu)成當前時域上的待排序外賣訂單集合S(q)；

S23：使用最近鄰域算法NN對S(q)中的外賣進行配送優(yōu)化排序，篩選出存在動態(tài)擾動的訂單，重新排序；

S24：根據(jù)優(yōu)化后的排序，給S(q)中的外賣配送著陸時間，將處于當前時域窗口中的外賣進行配送服務(wù)，其余動態(tài)干擾的外賣訂單，根據(jù)最新的預(yù)期時間，分配到后續(xù)窗口中進行配送；

S25：若所有外賣訂單已送達，則結(jié)束算法；

S26：更新外賣訂單的相關(guān)信息，q＝q+1，轉(zhuǎn)S22繼續(xù)執(zhí)行。

5.一種基于滾動時域控制的動態(tài)外賣配送的裝置，其特征在于，包括：

模型建立模塊，用于基于外賣配送的各個約束條件，建立動態(tài)外賣VRP優(yōu)化總成本最小化的模型和目標函數(shù)；

策略獲得模塊，用于基于RHC-NN算法對動態(tài)外賣VRP優(yōu)化總成本最小化的模型和目標函數(shù)求解，獲得外賣配送策略。