[發明專利]一種排班調度方法、系統以及電子設備

在審

• 申請號: 201810682122.1
• 申請日: 2018-06-27
• 公開（公告）號: CN109002908A
• 公開（公告）日: 2018-12-14
• 發明（設計）人: 周軼凡;徐鵬飛
• 申請（專利權）人: 杭州數夢工場科技有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q50/30
• 代理公司: 北京博思佳知識產權代理有限公司 11415
• 代理人: 林祥

1.一種排班調度方法，其特征在于，排班對象集合中的排班對象分別被預先規劃了出發地點；以及，到達所述出發地點的起始時間和最晚返回所述出發地點的終止時間；所述方法包括：

獲取為所述排班對象集合中的各排班對象確定出的，從所述出發地點出發在執行多次中轉調度事項后返回所述出發地點的初始最優路徑，并迭代執行以下步驟直到滿足預設條件時停止：

從所述排班對象集合中選擇出部分排班對象，列舉出所述部分排班對象中的各排班對象從所述出發地點出發，在執行多次中轉調度事項后返回所述出發地點的可行路徑，并基于列舉出的所述可行路徑為所述各排班對象生成樹狀關系圖；其中，所述可行路徑包括由若干個中轉地點和到達各中轉地點的中轉時間構成的中轉節點；

確定所述樹狀關系圖中位于不同的可行路徑，并且包含相同的中轉地點的多個中轉節點，并基于選定的對齊時間點對所述多個中轉節點的中轉時間進行偏移對齊處理后，合并所述中轉時間相同的中轉節點；

基于預設的算法模型從所述樹狀關系圖中的各可行路徑中為各排班對象確定出最優路徑，并基于所述最優路徑對所述初始最優路徑進行優化處理。

2.根據權利要求1所述的方法，其特征在于，所述方法還包括：

列舉出所述排班對象集合中的各排班對象從所述出發地點出發，在執行多次中轉調度事項后返回所述出發地點的可行路徑，并基于列舉出的所述可行路徑生成所述樹狀關系圖；

基于預設的算法模型從所述樹狀關系圖中的各可行路徑中為各排班對象確定出所述初始最優路徑。

3.根據權利要求2所述的方法，其特征在于，通過以上迭代步驟對所述初始最優路徑進行優化時采用的時間粒度，小于為各排班對象確定所述初始最優路徑時采用的時間粒度。

4.根據權利要求1所述的方法，其特征在于，所述可行路徑還包括由所述出發地點和所述起始時間構成的起始節點、由所述出發地點和所述終止時間構成的終止節點；其中，所述樹狀關系圖中的任意兩節點之間的連線，用于指示對應的中轉調度事項。

5.根據權利要求1所述的方法，其特征在于，所述基于選定的對齊時間點對所述多個中轉節點的中轉時間進行偏移對齊處理，包括：基于選定的對齊時間點對所述多個中轉節點中，早于所述對齊時間點的中轉時間的進行偏移對齊處理。

6.根據權利要求5所述的方法，其特征在于，所述對齊時間點為從預設的時間點集合中隨機選定的對齊時間點；其中，每輪迭代均預設了固定的對齊時間點；所述時間點集合中的對齊時間點，為在所述固定的對齊時間點的基礎上進行隨機長度的時間偏移后得到的對齊時間點。

7.根據權利要求6所述的方法，其特征在于，所述時間點集合中加入了上一輪迭代選定的對齊時間點。

8.根據權利要求4所述的方法，其特征在于，所述預設條件包括以下示出的任一：

如果所述初始最優路徑上的終止節點的所述終止時間，匹配規劃出的最晚返回所述出發地點的終止時間，則終止迭代；

如果所述初始最優路徑上的終止節點的所述終止時間，始終不匹配為規劃出的最晚返回所述出發地點的終止時間，則在迭代次數達到預設閾值時終止迭代；

如果所述初始最優路徑上的終止節點的所述終止時間，始終不匹配規劃出的最晚返回所述出發地點的終止時間，則在迭代時長達到預設閾值時終止迭代。

9.根據權利要求4所述的方法，其特征在于，所述基于所述最優路徑對所述初始最優路徑進行優化處理，包括：

確定所述最優路徑是否優于所述初始最優路徑上對應的局部路徑；如果是，基于所述最優路徑替換所述局部路徑；反之，保持所述局部路徑。