[發(fā)明專利]用于路徑規(guī)劃的方法和裝置

有效

• 申請?zhí)枺?/td>: 201810242130.4
• 申請日: 2018-03-22
• 公開（公告）號: CN108492068B
• 公開（公告）日: 2020-07-03
• 發(fā)明（設計）人: 范竣翔
• 申請（專利權）人: 北京百度網訊科技有限公司
• 主分類號: G06Q10/08
• 分類號: G06Q10/08;G06Q10/04
• 代理公司: 北京英賽嘉華知識產權代理有限責任公司 11204
• 代理人: 王達佐;馬曉亞

1.一種用于路徑規(guī)劃方法，包括：

獲取任務信息，所述任務信息包括各待配送物品所處的初始節(jié)點的位置、各所述待配送物品的目的節(jié)點的位置，以及處于初始節(jié)點和目的節(jié)點之間的中間節(jié)點的位置；

根據所述任務信息生成初始路徑信息，所述初始路徑信息包括第一序列集合與第二序列集合，所述第一序列集合包括至少一個第一序列，所述第一序列用于指示配送單元將各所述待配送物品自初始節(jié)點配送至其中一個中間節(jié)點的路徑，所述第二序列集合包括至少一個第二序列，所述第二序列用于指示配送單元將各所述待配送物品自其中一個中間節(jié)點配送至該待配送物品的目的節(jié)點的路徑；

執(zhí)行如下更新步驟：

隨機移除所述第二序列集合中的第二序列包括的預定數目個目的節(jié)點得到第三序列集合，并將各所移除的目的節(jié)點隨機加入所述第三序列集合中的一個第三序列，生成更新后的第二序列集合；根據更新后的第二序列集合更新所述第一序列集合中的第一序列；基于更新后的第一序列集合和更新后的第二序列集合確定配送單元的配送代價；響應于基于更新后的第一序列集合和更新后的第二序列集合確定的配送單元的配送代價不小于目標配送代價，統(tǒng)計連續(xù)確定出基于更新后的第一序列集合和更新后的第二序列集合確定的配送單元的配送代價不小于目標配送代價的次數；響應于所統(tǒng)計的次數大于預設閾值，隨機選取中間節(jié)點，移除所述第二序列集合中第二序列包括的與所選取的中間節(jié)點關聯的目的節(jié)點得到第四序列集合，并將各所移除的目的節(jié)點隨機加入所述第四序列集合中的一個第四序列，生成更新后的第二序列，根據更新后的第二序列集合更新所述第一序列集合中的第一序列，并基于更新后的第一序列集合和更新后的第二序列集合確定配送單元的配送代價；將基于更新后的第一序列集合和更新后的第二序列集合確定的配送單元的配送代價確定為目標配送代價；

所述方法還包括：

響應于所確定的配送代價滿足預設的配送代價條件，基于更新后的第一序列集合和更新后的第二序列集合確定各所述待配送物品自初始節(jié)點經中間節(jié)點配送至目的節(jié)點的路徑。

2.根據權利要求1所述的方法，其中，所述根據所述任務信息生成初始路徑信息，包括：

利用大規(guī)模鄰域搜索算法，根據所述任務信息生成第二序列集合中的第二序列；

根據所生成的第二序列，確定各所述中間節(jié)點待存儲的各所述待配送物品的物品信息；

利用大規(guī)模鄰域搜索算法，根據所確定的物品信息生成所述第一序列集合中的第一序列。

3.根據權利要求1所述的方法，其中，所述根據更新后的第二序列集合更新所述第一序列集合中的第一序列，包括：

根據更新后的第二序列集合，確定中間節(jié)點待存儲的所述待配送物品的物品信息；

利用大規(guī)模鄰域搜索算法，根據所確定的物品信息更新所述第一序列集合中的第一序列。

4.根據權利要求1所述的方法，其中，所述基于更新后的第一序列集合和更新后的第二序列集合確定配送單元的配送代價之后，所述更新步驟還包括：

響應于基于更新后的第一序列集合和更新后的第二序列集合確定的配送單元的配送代價小于目標配送代價，將基于更新后的第一序列集合和更新后的第二序列集合確定的配送單元的配送代價確定為目標配送代價。

5.根據權利要求1所述的方法，其中，所述響應于所確定的配送代價滿足預設的配送代價條件，基于更新后的第一序列集合和更新后的第二序列集合確定各所述待配送物品自初始節(jié)點經中間節(jié)點配送至目的節(jié)點的路徑，包括：

響應于達到預先設置的更新終止條件，獲取所確定的配送代價中最小的配送代價；

基于與所獲取的配送代價關聯的第一序列集合和第二序列集合確定各所述待配送物品自初始節(jié)點經中間節(jié)點配送至目的節(jié)點的路徑。