[發明專利]一種O2O外賣平臺智能調度與路線優化方法

有效

• 申請號: 201710368060.2
• 申請日: 2017-05-23
• 公開（公告）號: CN107180276B
• 公開（公告）日: 2020-06-30
• 發明（設計）人: 李桃迎;陳燕;張春剛
• 申請（專利權）人: 大連海事大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06Q50/12
• 代理公司: 大連東方專利代理有限責任公司 21212
• 代理人: 李洪福

本發明公開了一種O2O外賣平臺智能調度與路線優化方法，包括以下步驟：對外賣訂單數據進行預處理；快速生成外賣訂單智能指派模型；確定配送路線，估算配送成本。本發明對外賣訂單數據進行預處理時考慮了配送時間、延遲成本等因素，減少了指派、路線選取環節的計算量。本發明對外賣訂單進行智能快速指派提高外賣訂單的指派效率。本發明利用外賣配送需先去商家取貨后去客戶送貨的思想快速選取配送路線。本發明利用外賣訂單預處理完成對動態時間、配送員位置與容量約束及配送與延遲單位成本等參數的初始化，對待指派訂單按照其與已指派訂單的距離智能選擇配送員，利用外賣配送必先到商家取貨、后向客戶配送的思想為每個配送員快速選擇配送路線。

技術領域

本發明屬于物流調度與優化技術，特別是一種O2O外賣平臺訂單智能調度與路線優化方法。

背景技術

當前有很多O2O外賣平臺，如百度外賣、餓了么、美團等，而外賣調度與配送作為餐飲O2O的重要支撐環節，其優劣直接影響互聯網餐飲外賣的進一步擴張與發展。然而，由于區域性限制、時效性要求高、利潤點相對較低等諸多原因，外賣配送物流成本居高不下，外賣調度與配送優化是外賣平臺最大的難題。

目前專門針對O2O外賣平臺外賣調度與配送路線的公開文獻較少，多數仍然采用傳統物流配送優化模型及其變形，如設施選址-分配問題(LAP)、路徑優化問題(VRP)和同時送取貨VRP問題(VRPSPD)。LAP重點是確定配送中心最佳位置，不允許路線巡回訪問；VRP雖允許路線巡回訪問，但要求開始與結束位置都必須為同一配送中心，且二者都為先從配送中心取貨，后向客戶配送的過程；VRPSPD為同時送取貨的車輛路徑問題，所有配送貨物都要從配送中心裝車送至客戶，所有從客戶裝車的貨物都要送至配送中心。但這些方法應用于O2O外賣平臺訂單調度與配送路線選取時效果都不理想：1)由于外賣配送一般會劃分合理的區域范圍且距離不會太遠，同時為了避免影響餐品質量與口味，一般要求出餐后30分鐘送達客戶，有嚴格的配送時間約束；2)傳統物流配送優化問題都有固定的配送中心(一般中心較少)且車輛都從中心出發最終回到中心的閉環結構，而外賣配送路線優化問題，必須保證先去訂單的商家取餐、后配送到客戶，商家、客戶不能同等對待，訂單的商家、客戶位置為動態需求且調度時配送員位置也不固定；3)傳統物流配送優化問題調度之后轉化為旅行商問題(TSP)，尋找最優路線屬于NP問題，多采用啟發式算法求解，算法效率普遍較低，而O2O外賣平臺訂單非常多且比較集中，需要快速指派配送員并給出推薦路線。這些因素共同影響，使得O2O外賣平臺外賣調度與配送優化問題的處理更為復雜。

發明內容

為解決現有技術存在的上述問題，本發明要提出一種同時考慮配送時間約束、商家與客戶位置依據訂單需求動態變化且快速高效的O2O外賣平臺智能調度與路線優化方法。

為了實現上述目的，本發明的技術方案如下：1、一種O2O外賣平臺智能調度與路線優化方法，其特征在于：包括以下步驟：

A、對外賣訂單數據進行預處理

A1、依據當前未配送外賣訂單記錄，令K為已指派尚未完成配送的外賣訂單數，K’為未指派配送員的外賣訂單數，則Ls_k或Ls_k’分別為第k或k’個訂單的商家位置，Lc_k或Lc_k’分別為第k或k’個訂單的客戶位置，由于位置主要用于計算距離，而外賣配送的區域范圍非常小，用直線距離取代地理空間距離對結果不產生影響；k＝1,2,…,K，k’＝1,2,…,K’；