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

有效

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

1.一種用于車輛路徑優化的方法，包括：

將需要完成的貨物運送任務集拼成至少一個運送組，每一個運送組包括可一起裝車運送的至少一個貨物運送任務，并且在所述至少一個貨物運送任務中某一特定貨物運送任務的卸貨地點與其它各個貨物運送任務的卸貨地點的距離小于距離閾值；

基于第一優化目標將所述至少一個運送組中的任一運送組包括的貨物運送任務聚類成所述任一運送組的至少一個任務集，其中，所述任一運送組的所述至少一個任務集中的每一個任務集的總貨物量不大于可用的最大車輛的最大載貨量，以及，當按照所述任一運送組的所述至少一個任務集中的每一個任務集由一個車輛完成的方式完成所述任一運送組的所述至少一個貨物運送任務時所述第一優化目標的值最小；

如果所述至少一個運送組中存在各自具有多個任務集的一個或多個運送組，則根據約束信息和基于第二優化目標在所述一個或多個運送組中的任意運送組的多個任務集之間調整貨物運送任務；以及

在進行調整之后，基于所述至少一個運送組各自具有的任務集，至少確定完成所述至少一個運送組各自包括的貨物運送任務所需的具體車輛和每個具體車輛的行駛路線。

2.如權利要求1所述的方法，其中，根據約束信息和基于第二優化目標在所述一個或多個運送組中的任意運送組的多個任務集之間調整貨物運送任務包括：

在多次迭代的每一次迭代中，從上一次迭代調整后的所述任意運送組的所述多個任務集的每一個中選取至少一個貨物運送任務，以得到多個選取的貨物運送任務；

計算每一個選取的貨物運送任務的多個評測值-觀測值對，其中，任一選取的貨物運送任務的任一評測值-觀測值對中的評測值等于假設將所述任一選取的貨物運送任務放入上一次迭代調整后的所述任意運送組的所述多個任務集的其中一個任務集，用于完成假設已放入了所述任一選取的貨物運送任務的所述其中一個任務集所包括的貨物運送任務的各個可行的行駛路線中的特定行駛路線的第二優化目標的值，以及，所述任一評測值-觀測值對中的觀測值等于按照一個任務集由一個車輛完成的方式完成上一次迭代調整后的所述任意運送組的所述多個任務集所需的第二優化目標的值與在假設將所述任一選取的貨物運送任務放入上一次迭代調整后的所述任意運送組的所述多個任務集中的所述其中一個任務集之后按照一個任務集由一個車輛完成的方式完成所述任意運送組的所述多個任務集所需的第二優化目標的值的差值，其中，所述特定行駛路線是所述各個可行的行駛路線中的第二優化目標的值最小的行駛路線，以及，在計算所述各個可行的行駛路線的第二優化目標的值時考慮所述約束信息；

計算所述任意運送組的所述多個選取的貨物運送任務各自的后悔值，其中，每一個選取的貨物運送任務的后悔值等于該選取的貨物運送任務的所述多個評測值-觀測值對中的次最小評測值與最小評測值之差；

計算所述多個選取的貨物運送任務各自的綜合值，其中，每一個選取的貨物運送任務的綜合值等于該選取的貨物運送任務的后悔值和該選取的貨物運送任務的多個評測值-觀測值對中的各個觀測值的加權和；以及

將所述多個選取的貨物運送任務中的具有最大綜合值的貨物運送任務，放入上一次迭代調整后的所述任意運送組的所述多個任務集中的與所述具有最大綜合值的貨物運送任務的最小評測值對應的第一任務集，以得到此次迭代調整后的所述任意運送組的多個任務集，其中，所述具有最大綜合值的貨物運送任務的最小評測值是假設將所述具有最大綜合值的貨物運送任務放入所述第一任務集中計算得到的。

3.如權利要求2所述的方法，其中，

所述多個選取的貨物運送任務包括上一次迭代調整后的所述任意運送組的所述多個任務集的每一個任務集中的超過時間限制的貨物運送任務、超出容量限制的貨物運送任務、發生繞路現象的貨物運送任務、和/或具有較小任務相關度的貨物運送任務。

4.如權利要求1所述的方法，其中，

所述第一優化目標是總成本、總耗費時間或者總路程，以及

所述第二優化目標是總成本、總耗費時間或者總路程。

5.如權利要求1所述的方法，其中，

所述約束信息包括貨物需求量、發送量、交發貨時間窗、車輛容量限制、行駛里程限制和行駛時間限制。