[發明專利]調度優化方法和裝置

在審

• 申請號: 201810487232.2
• 申請日: 2018-05-21
• 公開（公告）號: CN108665115A
• 公開（公告）日: 2018-10-16
• 發明（設計）人: 陳科第;范竣翔;周淼;楊愛民;沈忠剛;周保玉;王可情;孟泉;王蔚
• 申請（專利權）人: 北京百度網訊科技有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q10/08
• 代理公司: 北京市鑄成律師事務所 11313
• 代理人: 王珺;徐瑞紅

本發明實施例提出一種調度優化方法和裝置。其中該方法包括：采用聚類消除策略，從初始調度方案中消除設定數量的客戶點，其中，所述初始調度方案包括各車輛的初始路線；采用優化插入策略，將被消除的客戶點重新插入被消除的調度方案中，得到更新調度方案，其中，所述被消除的調度方案包括消除設定數量的客戶點后各車輛的路線，所述更新調度方案包括重新插入客戶點后各車輛的路線；根據初始調度方案與更新調度方案的代價函數，確定最優調度方案。利用聚類消除策略和相應的優化插入策略，對初始調度方案進行優化，能夠更加合理的安排車輛運行的路線，較好地均衡各個車輛的負載，降低配送的運營成本和配送時間。

技術領域

本發明涉及智能調度技術領域，尤其涉及一種調度優化方法和裝置。

背景技術

新零售具有路徑短、貨物普遍偏小、要求即時配送，且送貨點大量聚集的同城配送等特點。如何在較短的時間內將貨物送達，并維持較低的配送成本，是一個具有顯著商業價值的問題。

目前新零售同城配送主要使用兩類方案。一類是基于傳統的啟發算法來求解配送方案，一種是通過人工對當天的訂單進行調配。基于單個啟發算法的調度方案一般采用遺傳算法、模擬退火、蟻群算法或禁忌搜索等。這些算法的設計是針對于通用的優化場景，也適用于同城配送方案的優化。通過人工對訂單進行調配，主要是各個承載新零售配送運力的供應商，依托其線下運營人員比較豐富的線下調配經驗，對當天的配送訂單和運力進行合理的調度與協調。

但是，使用傳統啟發式算法來優化同城調配方案，由于單個啟發算法的啟發規則是比較有限且相對通用的，在特定場景領域的優化效果不佳。如遺傳算法只有交叉和變異兩種啟發策略，這些相對固定而且單一的啟發規則，無法更好地優化新零售配送場景。若使用人工的方式對訂單進行調配，則調配結果的優劣很大程度取決于運營人員本身的經驗積累與素質高低，嚴重依賴資深員工。對于訂單量較大的場景，采用人工經驗產生的調度方案非常不可控，無法有效降低配送成本。

發明內容

本發明實施例提供一種調度優化方法和裝置，以解決現有技術中的一個或多個技術問題。

第一方面，本發明實施例提供了一種調度優化方法，包括：

采用聚類消除策略，從初始調度方案中消除設定數量的客戶點，其中，所述初始調度方案包括各車輛的初始路線；

采用優化插入策略，將被消除的客戶點重新插入被消除的調度方案中，得到更新調度方案，其中，所述被消除的調度方案包括消除設定數量的客戶點后各車輛的路線，所述更新調度方案包括重新插入客戶點后各車輛的路線；

根據初始調度方案與更新調度方案的代價函數，確定最優調度方案。

結合第一方面，本發明實施例在第一方面的第一種實現方式中，還包括：

多次執行聚類消除、優化插入和確定最優調度方案的步驟；

其中，如果迭代次數未達到閾值或執行結果不滿足截止條件，則將當前的最優調度方案作為新的初始調度方案，則執行聚類消除、優化插入和確定最優調度方案的步驟；如果迭代次數達到閾值或執行結果滿足截止條件，則輸出最優調度方案。

結合第一方面，本發明實施例在第一方面的第二種實現方式中，采用聚類消除策略，從初始調度方案中消除客戶點，包括：

采用近鄰消除策略，從初始調度方案中消除客戶點；或

采用強連通分量消除策略，從初始調度方案中消除客戶點。

結合第一方面的第二種實現方式，本發明實施例在第一方面的第三種實現方式中，采用近鄰消除策略，從初始調度方案中消除客戶點，包括：

如果消除集N中沒有客戶點，則從初始調度方案中選擇一個客戶點加入消除集N；