[發明專利]一種配送車輛的配送計劃生成方法、裝置及系統

在審

• 申請號: 202010627772.3
• 申請日: 2017-07-28
• 公開（公告）號: CN111768043A
• 公開（公告）日: 2020-10-13
• 發明（設計）人: 池田博和
• 申請（專利權）人: 株式會社日立制作所
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q10/08
• 代理公司: 北京銀龍知識產權代理有限公司 11243
• 代理人: 曾賢偉;范勝杰

本發明提供了一種配送車輛的配送計劃生成方法、裝置及系統。本發明在候補配送計劃的總成本中引入了空容器返還任務的任務成本，可以使得算法自動輸出期望的空容器返回的配送順序，滿足實際物流場景的空容器返還的需求，避免了采用人工方式制作配送計劃，降低了配送計劃的制作成本，提高了配送計劃的生成效率。

本申請是申請號201710630010.7，申請日為2017年07月28日，發明名稱為“一種配送車輛的配送計劃生成方法、裝置及系統”的分案申請。

技術領域

本發明涉及車輛路線問題(VRP，Vehicle Routing Problem)技術領域，具體涉及一種配送車輛的配送計劃生成方法、裝置及系統。

背景技術

車輛路線問題(VRP)是指一定數量的客戶，各自有不同數量的貨物需求，配送中心向客戶提供貨物，由一個車隊負責配送貨物，組織適當的行車路線，目標是使得客戶的需求得到滿足，并能在一定的約束下，達到諸如路程最短、成本最小、耗費時間最少等目的。

目前有關車輛路線問題的求解方法，包括精確算法(exact algorithm)與啟發式解法(heuristics)，其中精密算法有分支界限法、分支切割法、集合涵蓋法等；啟發式解法有節約法、模擬退火法、確定性退火法、禁忌搜尋法、基因算法、神經網絡、螞蟻殖民算法、遺傳算法(GA，Genetic Algorithm)等。在車輛配送計劃的自動生成中，通常作為鄰域搜索方法之一的大鄰域搜索(LNS，Large Neighborhood Search)比較有效，使用LNS搜索針對車輛的最佳配送任務分配模式。關于搜索，通常是以接近最佳解的方式，將與最佳解的差(成本總和)數值化，逐步向削減成本的方向重復進行。

VRP的一些應用場景中，需要采用配送容器裝載配送貨物進行配送，這種場景通常需要在貨物配送完成后將空容器返還。例如，在包含汽車配件配送的制造業物流調度中，配送容器因每個供貨商而不同，并且配送容器數量有限，因此，在配送后大多需要立即將空容器返還供貨商。因為有這樣的特殊要求，因此，針對上述應用場景，在技術上，由于僅通過鄰域搜索算法難以較佳地實現配送任務間的順序，因此現有的算法對于包含返還空容器的配送計劃的制作還未達到實用的程度，目前物流業大多還在實施人工制作上述應用場景的配送計劃。

發明內容

本發明實施例要解決的技術問題是提供一種配送車輛的配送計劃生成方法、裝置及系統，用以自動生成包含在配送后將空容器返還供貨商的配送要件的配送計劃，提高配送計劃的生成效率，降低人力成本。

為解決上述技術問題，本發明實施例提供的配送計劃生成方法，配送計劃生成方法，用于輸出利用多個配送車輛在多個站點間進行貨物的取貨和交貨的配送順序，

根據候補配送計劃中的空容器返還任務與關聯的貨物配送任務是否分配給同一配送車輛，以及，該空容器返還任務與關聯的貨物配送任務是否在預定時間內執行，評價候補配送計劃，得到評價結果；

根據所述候補配送計劃的評價結果，將一個或多個候補配送計劃作為最終配送計劃進行輸出；

其中，所述在預定時間內執行包括該空容器返還任務與關聯的貨物配送任務同時執行，或者該空容器返還任務在關聯的貨物配送任務之后，且兩者之間不存在其他配送任務。

本發明實施例還提供了一種配送計劃生成裝置，用于輸出利用多個配送車輛在多個站點間進行貨物的取貨和交貨的配送順序，包括：

配送計劃評價單元，用于根據候補配送計劃中的空容器返還任務與關聯的貨物配送任務是否分配給同一配送車輛，以及，在分配給同一配送車輛時，該空容器返還任務與關聯的貨物配送任務是否在預定時間內執行，評價候補配送計劃，得到評價結果；

配送計劃輸出單元，用于根據所述候補配送計劃的評價結果，將一個或多個候補配送計劃作為最終配送計劃進行輸出；