[發明專利]信息輸出方法和裝置

有效

• 申請號: 201710264864.8
• 申請日: 2017-04-21
• 公開（公告）號: CN107085754B
• 公開（公告）日: 2021-02-26
• 發明（設計）人: 趙媛媛;譚學壘
• 申請（專利權）人: 北京京東尚科信息技術有限公司;北京京東世紀貿易有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 北京英賽嘉華知識產權代理有限責任公司 11204
• 代理人: 王達佐;馬曉亞

1.一種信息輸出方法，其特征在于，所述方法包括：

獲取用于構建線路圖的至少一個節點的位置信息和歷史配送信息，其中，所述至少一個節點包括：根節點、至少一個中轉節點和至少一個第一葉子節點，所述根節點是所述線路圖中每條線路的起始節點，第一葉子節點是所述線路圖中在預設的第一配送時間范圍內到達的線路的終止節點，中轉節點是用于連接所述根節點和各葉子節點的節點，所述至少一個節點還包括至少一個第二葉子節點，第二葉子節點是所述線路圖中在預設的第二配送時間范圍內到達的線路的終止節點；

將各個中轉節點連接到所述根節點；

對于每個第一葉子節點，根據所述至少一個節點的位置信息確定與該第一葉子節點距離最近的中轉節點，并根據所述至少一個節點的歷史配送信息確定從所述根節點經由所述距離最近的中轉節點配送至該第一葉子節點的第一到達時間；若所述第一到達時間在所述第一配送時間范圍內，則將該第一葉子節點連接到所述距離最近的中轉節點；否則，將該第一葉子節點連接到所述根節點；

獲取每個第二葉子節點與所述至少一個節點的連接關系；

對于每個第二葉子節點，執行如下步驟，包括：根據所述至少一個節點的位置信息和所述連接關系確定與所述根節點直接或間接連接的、與該第二葉子節點距離最近的第二葉子節點，并根據所述至少一個節點的歷史配送信息確定從所述根節點經由所述距離最近的第二葉子節點配送至該第二葉子節點的第二到達時間；若所述第二到達時間在所述第二配送時間范圍內，則將該第二葉子節點連接到所述距離最近的第二葉子節點；否則，根據所述至少一個節點的位置信息確定與該第二葉子節點距離最近的中轉節點，并根據所述至少一個節點的歷史配送信息確定從所述根節點經由所述距離最近的中轉節點配送至該第二葉子節點的第三到達時間；若所述第三到達時間在所述第二配送時間范圍內，則將該第二葉子節點連接到所述距離最近的中轉節點，否則，將該第二葉子節點連接到所述根節點；

將所述至少一個第一葉子節點和/或所述至少一個第二葉子節點組成子節點集合；

對于所述子節點集合中的每個子節點，執行如下步驟：根據所述至少一個節點的位置信息，確定該子節點與各中轉節點之間的距離以及該子節點與根節點之間的距離；按照距離由小到大的順序將各中轉節點排序得到排序后的至少一個中轉節點；從所述排序后的至少一個中轉節點中選取距離該子節點最近的中轉節點；若所述最近的中轉節點與該子節點之間的距離與所述根節點與該子節點之間的距離相等，則將該子節點連接至所述根節點；否則，對于每個非最近的中轉節點，確定該中轉節點、所述根節點和該子節點構成的三角形的邊長和角度是否滿足預定的第一條件或第二條件，若滿足所述第一條件或第二條件，則將該子節點連接至該中轉節點；

根據所述至少一個節點之間的連接關系輸出從所述根節點配送至各節點的線路圖。

2.根據權利要求1所述的方法，其特征在于，在所述根據所述至少一個節點之間的連接關系輸出從所述根節點配送至各節點的線路圖之前，所述方法還包括：

對于未與第二葉子節點連接的每個第一葉子節點，執行如下步驟：

根據所述至少一個節點的位置信息確定與該第一葉子節點距離最近的第一葉子節點，并根據所述至少一個節點的歷史配送信息確定從所述根節點經由所述距離最近的第一葉子節點配送至該第一葉子節點的第四到達時間；

若所述第四到達時間在所述第一配送時間范圍內，則將該第一葉子節點連接到所述距離最近的第一葉子節點；

否則，根據所述至少一個節點的位置信息確定與該第一葉子節點距離最近的中轉節點，并根據所述至少一個節點的歷史配送信息確定從所述根節點經由與該第一葉子節點距離最近的中轉節點配送至該第一葉子節點的第五到達時間；若所述第五到達時間在第一配送時間范圍內，則將該第一葉子節點連接到所述距離最近的中轉節點，否則，將該第一葉子節點連接到所述根節點。

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

所述根節點與所述子節點構成的邊的邊長大于或等于所述根節點與所述中轉節點構成的邊的邊長；并且

所述子節點和所述中轉節點構成的邊與所述根節點和所述中轉節點構成的邊之間的夾角大于預定的角度；并且

所述子節點和所述中轉節點構成的邊的邊長與所述根節點和所述中轉節點構成的邊的邊長之和，小于所述根節點和所述子節點構成的邊的邊長與第一系數之積，其中，所述第一系數大于1。