[發明專利]一種基于場景推演的物流配送調度算法

在審

• 申請號: 202010020350.X
• 申請日: 2020-01-09
• 公開（公告）號: CN111242368A
• 公開（公告）日: 2020-06-05
• 發明（設計）人: 代宏硯;陶家威;姜海
• 申請（專利權）人: 中央財經大學;清華大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q10/08
• 代理公司: 杭州浙科專利事務所(普通合伙) 33213
• 代理人: 沈淵琪

本發明公開了一種基于場景推演的物流配送調度算法。該方法提取決策時刻點及過去的若干場景的多維特征；針對每一維特征計算決策時刻點和過去的場景庫的距離，將多個距離組合后，選取距離最小的歷史場景對應的訂單集作為對未來訂單集的預測；基于現有未完成的訂單集和未來時段的預測訂單集，構建配送調度模型，利用啟發式算法給出物流配送調度方案。本發明將針對大規模稀疏網絡的訂單集的預測問題，轉變為構建高維特征空間，并在該高維空間計算不同場景距離的問題。并構建配送優化模型將該預測結果整合到調度決策過程中，避免調度方案的短視性，有效降低配送成本和配送時間。

技術領域

本發明屬于機器學習和物流管理的交叉領域,尤其是涉及對未來訂單分布進行分析的物流配送調度算法。

背景技術

互聯網、移動營銷、新零售的發展，使得O2O即時物流成為一種重要的運營方式。即時物流調度與傳統物流的不同在于高波動性、即時性兩大特征，要求平臺能夠在較短的時間內做出物流調度方案，同時還需要根據訂單的變化不斷更新調度方案。由于訂單的高波動性，如果不考慮未來的訂單集，會造成調度方案的短視性。但是對于O2O即時物流，其配送規模很大，擁有數量龐大的商家和消費者，通常在一個5km×5km的配送區域內，擁有超過100個商家，近萬的消費者，組成一個大規模的配送網絡，但對于某個決策時刻點，配送區域內的訂單數目一般不到300個，配送網絡的連接非常稀疏。對于一個大規模的稀疏網絡，要進行高頻的訂單集實時預測非常困難，因此需要一個新的方法來支持對大規模網絡的訂單集進行高頻的實時預測，并將該預測結果整合到調度模型中，優化調度方案，提升企業運營效率，降低運營成本。

現有的物流調度算法，主要分為兩類：靜態的調度方案、動態的調度方案。靜態的調度方案中，訂單不會動態更新，平臺只需要做一次決策。動態的調度方案考慮了隨時間不斷更新的訂單，平臺會進行多次的決策，給出調度方案。

上述算法大都未考慮未來訂單的信息，而目前考慮未來訂單的主流方法有兩種，第一種方式假定需求服從一定的隨機分布，并利用歷史數據估計隨機分布的參數，第二種方法通過機器學習的方法去預測網絡中每一個連接發生的概率。但是這些方法均不適用于大規模的稀疏網絡。

發明內容

針對現有技術存在的問題，本發明的目的在于設計提供一種基于場景推演的物流配送調度算法的技術方案。

本發明采用如下技術方案：

確定調度決策周期時長τ^a，場景片段時長τ^s，當前決策時刻t，向前追溯的歷史場景數目p；一個訂單c包含起點、終點、產生時間等信息，提取時刻t所有未完成的訂單組成的訂單集定義待預測的時刻t之后時長τ_s的訂單集為提取時刻t的場景特征集場景特征集由n類不同的特征組成；對于時刻之前的每一個決策時刻提取場景屬性S_j；根據特征集計算當前場景與歷史場景庫中的每一個場景的距離D_t,j，選取距離最小的場景，對應下標為j^*；提取時刻j^*往后時長τ^s內的訂單集作為對訂單集的預測；基于訂單集C_t和構建配送調度模型；利用啟發式算法求解物流配送調度方案。

具體步驟如下：

1.數據準備:

1.1確定調度決策周期時長τ^a，場景片段時長τ^s，當前決策時刻t，向前追溯的歷史場景數目p。

1.2提取時刻t未完成的訂單集

1.3提取時刻t的場景特征集

1.4對于時刻之前的每一個決策時刻提取時刻j的場景特征集

2.場景計算:

2.1對于時刻j，計算時刻t的場景與時刻j的場景的特征子集之間的距離