[發明專利]基于滾動時域控制的動態外賣配送的方法及裝置

在審

• 申請號: 201811610415.5
• 申請日: 2018-12-27
• 公開（公告）號: CN109858752A
• 公開（公告）日: 2019-06-07
• 發明（設計）人: 張玉州;葉亮;鄭軍帥;徐廷政;張子為
• 申請（專利權）人: 安慶師范大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q10/08
• 代理公司: 溫州市品創專利商標代理事務所(普通合伙) 33247
• 代理人: 洪中清

本發明實施例提供一種基于滾動時域控制的動態外賣配送的方法及裝置，所述方法設計了一種基于RHC的NN算法(RHC?NN)對問題模型進行求解，其通過在規定時域窗口T內送到，出車一次的總時間最短，且行駛距離縮小。

技術領域

本發明實施例涉及智能物流技術領域，尤其涉及一種基于滾動時域控制的動態外賣配送的方法及裝置。

背景技術

餐飲行業的外賣O2O(Online to Offline)迅速發展，已成為現代客戶依賴的主流消費方式。在提供外賣配送服務開始前，系統會根據客戶訂單分配預期配送時間，選擇配送路線，開始配送。所以，外賣配送實質是車輛路徑規劃問題(vehicle routing problem，VRP)的實際應用案例問題。VRP最早由Dantzig和Ramser于1959年提出，指存在一定數量需求的顧客，由配送中心點向客戶提供配送服務，選擇合適的配送路徑，并在規定的約束條件下，實現如需求滿足、總路徑最短、總耗費時間最少等目的。由于VRP本身的復雜性及廣泛的應用背景，國內外學者對VRP問題進行了大量的研究，許多與時間相關的運輸車輛調度問題都可以歸納為VRP問題的一類重要拓展，稱為帶時間窗限制車輛路線問題(vehiclerouting problems with timewindows，VRPTW)，例如郵件的投遞、應急模式下的物資配送等。同時，VRPTW屬于NP難問題，難以用精確算法求解，啟發式算法是求解此類拓展問題的主要方法，例如節約法、捕食搜索算法、最近鄰域算法(nearest neighboralgorithm，NN)、遺傳算法等、禁忌搜索算法等。啟發式算法的優點為具有全局搜索的能力，求解效率高，目前求解規模通常在100個算例以內，如Kwon等人運用禁忌搜索算法求解VRP問題，求解數在50-100。

近年來，人工智能方法在解決組合優化問題上顯示出強大的算法功能，在各個領域得到充分應用，張建強、潘立軍等利用遺傳算法求解物流配送路徑優化問題。戴韜等則利用VRP理論考慮了船舶航線規劃問題，郭月等通過使用節約里程法對校園外賣配送路徑的優化，從而達到配送的高效率，楊博文等人對餐飲外賣目標市場發展趨勢進行了分析。而在配送過程中，難點是客戶主觀選擇服務時間的干擾性強、隨機性大，配送路徑隨訂單變動而變化，易造成訂單配送延誤，超出客戶預期等待時間，影響客戶滿意度和未來消費。滾動時域控制(receding horizon control，RHC)作為一種動態狀態下在線優化有效策略，國內外相關學者也設計了基于RHC的算法對動態優化問題進行求解，驗證了基于RHC策略的合理性和有效性。

綜上所述，隨時間窗推移而發生的動態干擾的外賣配送問題研究仍然較少，學界對餐飲外賣配送的探究在不斷深入，現實配送中，客戶訂單服務信息常動態變化，如訂單的取消、預期到達時間的更改等。

但上述現有技術在配送服務質量和客戶滿意度方面仍有待提高。

發明內容

本發明實施例提供一種基于滾動時域控制的動態外賣配送的方法，用以解決現有技術中配送服務質量和客戶滿意度有待提高的問題。

根據本發明實施例的第一個方面，提供一種基于滾動時域控制的動態外賣配送的方法，包括：

基于外賣配送的各個約束條件，建立動態外賣VRP優化總成本最小化的模型和目標函數；

基于RHC-NN算法對動態外賣VRP優化總成本最小化的模型和目標函數求解，獲得外賣配送策略。

進一步，外賣配送的各個約束條件，包括：

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

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

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

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