[發明專利]線路設計方法和裝置

有效

• 申請號: 201711457148.8
• 申請日: 2017-12-28
• 公開（公告）號: CN109978209B
• 公開（公告）日: 2022-04-12
• 發明（設計）人: 林世洪;夏繼光
• 申請（專利權）人: 北京京東尚科信息技術有限公司;北京京東世紀貿易有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/14
• 代理公司: 中原信達知識產權代理有限責任公司 11219
• 代理人: 張一軍;楊曉偉

1.一種線路設計方法，其特征在于，所述方法包括：

根據用戶需求信息構建多個需求線路向量；所述需求線路向量中的每個元素代表一個站點；

循環迭代如下步驟，直至不存在相似度大于預設閾值的需求線路向量對：計算各需求線路向量之間的相似度，并將相似度大于預設閾值的需求線路向量對作為待優化線路向量對，按照相似度由大到小的順序，依次判斷每一待優化線路向量對是否滿足合并條件；在滿足合并條件時，將該待優化線路向量對中的站點進行合并；

從優化后的線路向量、以及相似度小于或等于預設閾值的需求線路向量中挑選出不重復的線路，確定每個挑選出的線路所包括的站點的游覽次序，再基于確定游覽次序的線路生成線路規劃結果；

其中，根據如下公式計算各需求線路向量之間的相似度；

其中，S_j,k表示第j個需求線路向量與第k個需求線路向量的相似度，M_j表示第j個需求線路向量所包括的站點集合，M_k表示第k個需求線路向量所包括的站點的集合，∩(M_j,M_k)表示對M_j與M_k取交集后的站點數，∪(M_j,M_k)表示對M_j與M_k取并集后的站點數。

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

在對待優化線路向量對進行合并情況下的利潤預估值大于在對待優化線路向量對不進行合并情況下的利潤預估值。

3.根據權利要求2所述的方法，其特征在于，根據如下公式計算在對待優化線路向量對不進行合并情況下的利潤預估值：

其中，F表示利潤預估值，Price為每條線路的價格，n為用戶數，表示最終參與的用戶比例，∑M表示所有用戶需求的站點之和，∑W表示在對待優化線路不進行合并情況下所有用戶實際被提供的站點之和，K為在對待優化線路向量對不進行合并情況下所需的車輛數，num(L_i)表示在對待優化線路向量對不進行合并情況下線路L_i的用戶數，Q表示每輛車可以承載的用戶數，表示對進行向上取整。

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

在生成線路規劃結果之后，對所述線路規劃結果進行評估，并將評估結果進行展示。

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

接收用戶需求信息，并對所述用戶需求信息進行保存。

6.一種線路設計裝置，其特征在于，所述裝置包括：

構建模塊，用于根據用戶需求信息構建多個需求線路向量；所述需求線路向量中的每個元素代表一個站點；

計算模塊，用于循環迭代如下步驟，直至不存在相似度大于預設閾值的需求線路向量對：計算各需求線路向量之間的相似度，并將相似度大于預設閾值的需求線路向量對作為待優化線路向量對；調用優化模塊按照相似度由大到小的順序依次判斷每一待優化線路向量對是否滿足合并條件；在滿足合并條件時，將該待優化線路向量對中的站點進行合并；

優化模塊，用于對所述待優化線路向量對進行迭代優化處理，并從優化后的線路向量、以及相似度小于或等于預設閾值的需求線路向量中挑選出不重復的線路，確定每個挑選出的線路所包括的站點的游覽次序，再基于確定游覽次序的線路生成線路規劃結果；

其中，所述計算模塊根據如下公式計算各需求線路向量之間的相似度；

其中，S_j,k表示第j個需求線路向量與第k個需求線路向量的相似度，M_j表示第j個需求線路向量所包括的站點集合，M_k表示第k個需求線路向量所包括的站點的集合，∩(M_j,M_k)表示對M_j與M_k取交集后的站點數，∪(M_j,M_k)表示對M_j與M_k取并集后的站點數。