[發明專利]一種O2O外賣平臺智能調度與路線優化方法有效
申請號: | 201710368060.2 | 申請日: | 2017-05-23 |
公開(公告)號: | CN107180276B | 公開(公告)日: | 2020-06-30 |
發明(設計)人: | 李桃迎;陳燕;張春剛 | 申請(專利權)人: | 大連海事大學 |
主分類號: | G06Q10/04 | 分類號: | G06Q10/04;G06Q10/08;G06Q50/12 |
代理公司: | 大連東方專利代理有限責任公司 21212 | 代理人: | 李洪福 |
地址: | 116026 遼*** | 國省代碼: | 遼寧;21 |
權利要求書: | 查看更多 | 說明書: | 查看更多 |
摘要: | |||
搜索關鍵詞: | 一種 o2o 外賣 平臺 智能 調度 路線 優化 方法 | ||
1.一種O2O外賣平臺智能調度與路線優化方法,其特征在于:包括以下步驟:
A、對外賣訂單數據進行預處理
A1、依據當前未配送外賣訂單記錄,令K為已指派尚未完成配送的外賣訂單數,K’為未指派配送員的外賣訂單數,則Lsk或Lsk’分別為第k或k’個訂單的商家位置,Lck或Lck’分別為第k或k’個訂單的客戶位置,由于位置主要用于計算距離,而外賣配送的區域范圍非常小,用直線距離取代地理空間距離對結果不產生影響;k=1,2,…,K,k’=1,2,…,K’;
A2、令該配送區域內配送員數為N,xki=1或xk’i=1分別表示訂單k或k’指派給配送員i,xki=0或xk’i=0分別表示訂單k或k’未指派給配送員i;xi(s,t)表示配送員i是否需要走邊e(s,t),即是否需要從s位置直接沿著邊e(s,t)去t位置,其中是為1,否為0,邊長記為l(s,t);訂單k生效時刻為Tk0,訂單k的客戶希望最遲送達時刻為LTk,配送員到訂單k的商家取餐的時刻為Tks,配送員把訂單k送達客戶的時刻為Tkt;s,t∈{(K+K’)個訂單的商家或客戶位置},i=1,2,…,N;
A3、給定配送員平均配送速度為v,單位時間配送成本為uc,超出指定配送時間的延遲單位時間成本為dc,通過當前配送員的手機GPS獲取位置數據;計算當前所有K’+K個外賣訂單的所有商家Lsk、客戶位置Lck的邊長,邊長矩陣L=(l(s,t))2K×2K,邊長實際為兩點s(s1,s2)、t(t1,t2)的歐氏距離,如式(1)所示:
B、快速生成外賣訂單智能指派模型
B1、給定配送員已指派未配送的訂單容量約束為Q;
B2、判斷:如果K’+K≤N×Q,則全部指派,否則只取K’中先下訂單的(N×Q-K)作為本次要指派的訂單,其他(K’+K-N×Q)個訂單下次調度時指派,同時將本次需要指派的訂單作為K’;
B3、將當前所有未指派訂單按照訂單生成的先后順序排序,訂單序號越小,表示訂單生成越早,應該更優先被指派;設定當前未指派訂單序號k’=1;
B4、判斷:當前是否有空閑配送員i,i=1、2、…、N,有則將訂單k’指派給配送員i,即xk’i=1,轉到步驟B7,否則轉到步驟B5;
B5、計算當前訂單k’到所有已指派未完成訂單的距離,如式(2)所示:
d(k’,k)=l(Lsk’,Lsk)+l(Lck’,Lck),k=1、2、…、K (2)
B6、將d(k’,k)按照距離由小到大的順序排列,對應排序后的訂單序號kmin=1、2、…、K,之后為訂單k’指派配送員:
B61、設定當前排序后的訂單序號kmin=1;
B62、訂單kmin已指派的配送員為imin,判斷:如果配送員imin已指派未完成數:
其中k為訂單序號,1≤k≤K;
是則轉到步驟B63;否則轉到步驟B64;
B63、令kmin=kmin+1,判斷:如果kmin≤K,轉到步驟B62;否則轉到步驟B8;
B64、將k’指定給配送員imin,即xk’imin=1;
B7、令當前商品節點序號k’=k’+1,K=K+1;判斷:如果k’≤K’,則轉到步驟B4;否則轉到步驟B8;
B8、所有訂單指派完畢,停止指派;
C、確定配送路線,估算配送成本
C1、設定當前配送員序號i=1,已指派未完成訂單的配送成本Z=0;
C2、判斷:如果配送員序號i≤N,則轉到步驟C3,否則轉到步驟C5;
C3、判斷:如果配送員i沒有已指派尚未完成的訂單,則令Zi=0,轉到步驟C4,否則估算配送員i的配送成本Zi:
C31、假定指派給配送員i的訂單為ki=1,2,…,Ki,令Di={配送員i要配送訂單的所有商家位置}={Lski|ki=1,2,…,Ki},Di’=Φ,Φ為空集,位置變量li為配送員i的當前位置,Zi=0,當前時刻為T;
C32、計算Di中距離li最近的位置dmin,令INT()表示上取整,T=T+ti,li=dmin;
C33、判斷:如果dmin為某訂單ki的商家位置Lski,則令Di’=Di’∪{dmin},同時用訂單ki對應的客戶位置Lcki取代Di中的dmin,Tkis=T,Zi=Zi+ti×uc;否則dmin為某訂單的客戶位置,則Di’=Di’∪{dmin},同時將dmin從Di中移除,即Di=Di-{dmin},Tkit=T,Zi=Zi+ti×uc+max{Tkit-LTk,0}×dc;
C34、判斷:如果Di≠Φ,則轉到步驟C32;否則Di’中元素的順序即為配送順序,轉到步驟C4;
C4、令Z=Z+Zi,i=i+1,轉到步驟C2;
C5、停止計算,輸出每個配送員i的最優配送路線Di’和總的配送成本Z。
該專利技術資料僅供研究查看技術是否侵權等信息,商用須獲得專利權人授權。該專利全部權利屬于大連海事大學,未經大連海事大學許可,擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作,請聯系【客服】
本文鏈接:http://www.szxzyx.cn/pat/books/201710368060.2/1.html,轉載請聲明來源鉆瓜專利網。
- 同類專利
- 專利分類
G06Q 專門適用于行政、商業、金融、管理、監督或預測目的的數據處理系統或方法;其他類目不包含的專門適用于行政、商業、金融、管理、監督或預測目的的處理系統或方法
G06Q10-00 行政;管理
G06Q10-02 .預定,例如用于門票、服務或事件的
G06Q10-04 .預測或優化,例如線性規劃、“旅行商問題”或“下料問題”
G06Q10-06 .資源、工作流、人員或項目管理,例如組織、規劃、調度或分配時間、人員或機器資源;企業規劃;組織模型
G06Q10-08 .物流,例如倉儲、裝貨、配送或運輸;存貨或庫存管理,例如訂貨、采購或平衡訂單
G06Q10-10 .辦公自動化,例如電子郵件或群件的計算機輔助管理