[發明專利]用于車輛路徑優化的方法、裝置和計算設備

有效

• 申請號: 201810810590.2
• 申請日: 2018-07-23
• 公開（公告）號: CN110503229B
• 公開（公告）日: 2022-04-22
• 發明（設計）人: 同鯨渭;向達;王子卓;王曦
• 申請（專利權）人: 杉數科技（北京）有限公司;上海杉數網絡科技有限公司;杉數科技（蘇州）有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 北京永新同創知識產權代理有限公司 11376
• 代理人: 鐘勝光

本發明涉及用于車輛路徑優化的方法和裝置，該方法包括：將需要完成的貨物運送任務集拼成至少一個運送組；基于第一優化目標將任一運送組包括的貨物運送任務聚類成該任一運送組的至少一個任務集；如果該至少一個運送組中存在具有多個任務集的一個或多個運送組，則根據約束信息和基于第二優化目標在該一個或多個運送組中的任意運送組的多個任務集之間調整貨物運送任務；基于該至少一個運送組各自具有的任務集，至少確定完成該至少一個運送組各自包括的貨物運送任務所需的具體車輛和每個具體車輛的行駛路線。利用該方法和裝置能夠提高車輛路徑問題的求解精度和求解速度和使得車輛路徑問題求解算法涵蓋多種業務場景和約束條件。

技術領域

本發明涉及用于車輛路徑優化的方法、裝置和計算設備。

背景技術

車輛路徑問題(Vehicle Routing Problem,VRP)是一種物流運輸等中的路徑組合優化問題，其指在多個客戶各自需要從提貨地點向其運送貨物的情況下，利用車隊經由適當組織的行車路線將貨物從提貨地點運送給該多個客戶，以在一定的約束(例如，貨物需求量、發送量、交發貨時間窗、車輛容量限制、行駛里程限制、行駛時間限制等)下，達到諸如路程最短、成本最小、耗費時間最少等目的。

VRP是一個大規模組合優化及整數規劃問題，計算量大且求解精度要求高。然而，目前很多面對VRP問題的企業所采用的VRP求解算法沒有足夠能力應對如此大的計算量和如此高的精度需求，導致求解精度和求解速度無法滿足業務需求。而且，這些求解算法通常僅適用于單一業務場景和約束條件。

發明內容

鑒于現有技術的以上問題，本發明的實施例提供用于車輛路徑優化的方法、裝置和計算設備，其能夠提高車輛路徑問題求解算法的求解速度和求解精度和使得車輛路徑問題求解算法涵蓋多種業務場景和約束條件。

按照本發明的實施例的一種用于車輛路徑優化的方法，包括：將需要完成的貨物運送任務集拼成至少一個運送組，每一個運送組包括可一起裝車運送的至少一個貨物運送任務，并且在所述至少一個貨物運送任務中某一特定貨物運送任務的卸貨地點與其它各個貨物運送任務的卸貨地點的距離小于距離閾值；基于第一優化目標將所述至少一個運送組中的任一運送組包括的貨物運送任務聚類成所述任一運送組的至少一個任務集，其中，所述任一運送組的所述至少一個任務集中的每一個任務集的總貨物量不大于可用的最大車輛的最大載貨量，以及，當按照所述任一運送組的所述至少一個任務集中的每一個任務集由一個車輛完成的方式完成所述任一運送組的所述至少一個貨物運送任務時所述第一優化目標的值最小；如果所述至少一個運送組中存在各自具有多個任務集的一個或多個運送組，則根據約束信息和基于第二優化目標在所述一個或多個運送組中的任意運送組的多個任務集之間調整貨物運送任務；以及，在進行調整之后，基于所述至少一個運送組各自具有的任務集，至少確定完成所述至少一個運送組各自包括的貨物運送任務所需的具體車輛和每個具體車輛的行駛路線。

按照本發明的實施例的一種用于車輛路徑優化的裝置，包括：集拼模塊，用于將需要完成的貨物運送任務集拼成至少一個運送組，每一個運送組包括可一起裝車運送的至少一個貨物運送任務，并且在所述至少一個貨物運送任務中某一特定貨物運送任務的卸貨地點與其它各個貨物運送任務的卸貨地點的距離小于距離閾值；聚類模塊，用于基于第一優化目標將所述至少一個運送組中的任一運送組包括的貨物運送任務聚類成所述任一運送組的至少一個任務集，其中，所述任一運送組的所述至少一個任務集中的每一個任務集的總貨物量不大于可用的最大車輛的最大載貨量，以及，當按照所述任一運送組的所述至少一個任務集中的每一個任務集由一個車輛完成的方式完成所述任一運送組的所述至少一個貨物運送任務時所述第一優化目標的值最小；調整模塊，用于如果所述至少一個運送組中存在各自具有多個任務集的一個或多個運送組，則根據所述約束信息和基于第二優化目標在所述一個或多個運送組中的任意運送組的多個任務集之間調整貨物運送任務；以及，確定模塊，用于在進行調整之后，基于所述至少一個運送組各自具有的任務集，至少確定完成所述至少一個運送組各自包括的貨物運送任務所需的具體車輛和每個具體車輛的行駛路線。