一種產品車輛路徑實現方法和裝置與流程
2023-10-05 14:33:44
本發明涉及物流配送領域，尤其涉及一種產品車輛路徑實現方法和裝置。
背景技術：
：隨著經濟全球化和網絡信息技術的快速發展，物流配送作為一個新的經濟增長點越來越引起人們的關注，隨著市場競爭的日益激烈以及客戶要求的不斷提高，配送在未來的市場競爭中將起到舉足輕重的作用。在物流配送系統中採取有效的配送策略可以減少浪費，降低成本並顯著提高經濟效益。車輛路徑問題(VehicleRoutingProblem，VRP)源於現代物流系統，其作為物流配送優化過程中的關鍵環節，是一類典型的組合優化問題，也是運籌學和管理學科的前沿研究熱點問題之一。帶時間窗的車輛路徑問題(VehicleRoutingProblemWithTimeWindows，VPRTW)是在VRP問題的基礎上對客戶服務時間進行約束，這一約束更貼近物流配送的現實情況，該問題實現的好壞將直接影響到一個企業的成本、效益、對客戶的服務質量以及實現物流配送管理的科學化，所以對VRPTW的研究越來越受到人們的重視。本文重點研究了帶有軟時間窗約束的多種生鮮農產品車輛路徑問題。隨著科技的發展和生活水平的提高，消費者對生鮮農產品的需求不斷增加，與此同時，消費者對於生鮮農產品的質量和新鮮度要求也越來越高。因此，在滿足客戶對新鮮度需求的前提下，尋找最優配送路徑，實現配送費用最小化是物流配送領域需要解決的重要問題。由於VRPTW是一個NP難題，採用一般的精確算法解決VRPTW時，時間複雜度較高，而粒子群算法是通過粒子之間的相互作用來尋找最優解，缺乏變異機制，容易陷入局部最優，因此本文採用混合遺傳算法進行求解，並且取得了很好的求解結果。在以往車輛路徑問題的求解中存在以下三個方面的問題。(1)現有的生鮮農產品VRP中很少考慮道路的實際情況，各個配送客戶之間的距離是以直線距離作為計算依據的，脫離了客戶之間的實際道路情況。(2)現有的生鮮農產品VRP中研究的多是硬時間窗約束，要求車輛必須在規定的時間窗內到達，早到必須等待，遲到則拒收，很少考慮配送車輛在時間窗以外到達，若早到或晚到接受處罰的軟時間窗情況。(3)現有的生鮮農產品VRP中配送過程中大多考慮一種生鮮農產品，很少考慮具有不同新鮮度約束的不同種類生鮮農產品同時配送的情況。技術實現要素：基於此，本發明的目的在於提供一種產品車輛路徑實現方法。本發明的第二目的在於，提供所述產品車輛路徑的實現裝置。為實現上述目的，本發明採用了以下技術。本發明一種產品車輛路徑實現方法，其特徵在於，所述方法包括：讀取城市道路的點邊集信息；根據預設算法對所述點邊集信息進行計算以得到最短路徑信息，所述最短路徑信息包括配送中心到各個客戶的最短路徑以及各個客戶之間的最短路徑；採用一預設編碼方式初始化種群；根據所述最短路徑信息以及所述初始化種群計算每個解對應的目標函數值；從各個解對應的目標函數值中選出最小的目標函數值，以及與該最小的目標函數值對應的解；對所述目標函數值依次進行選擇操作、交叉操作、變異操作、重插入以及更新記錄。在本發明所述的方法中，所述採用一預設編碼方式初始化種群的步驟包括：將客戶序列隨機打亂得到一個新的序列1；在序列1的N-1個空隙中隨機選取K-1個插入0，得到序列2，其中N表示客戶總數量，K表示配送車輛總數目；在序列2的兩端分別補上0，得到序列3，序列3即為一個初始解；根據所述初始解獲取初始化的種群。在本發明所述的方法中，所述對所述目標函數值進行選擇操作、交叉操作、變異操作、重插入、更新記錄的步驟包括：選擇操作，根據當前種群中每個解的目標函數值，從中選出偶數組解；交叉操作，在選擇操作後的新種群中，對所有的解進行兩兩配對，將配對在一起的兩個解進行交叉操作；變異操作，對每一個解隨機生成一個預設數值，如果該預設數值小於變異概率，對當前解進行變異操作，否則，不對當前解進行變異操作；重插入，將變異操作後的一組解及原種群中的部分解重新組合得到新的種群；更新記錄，如果新種群的最優值小於記錄的上一種群的最優值，則用新種群的最優值及其對應的解替換記錄的上一種群中的最優值及其對應的解，同時令解不變次數為0；否則，不更新記錄中的最優值及其對應的解，同時令解不變次數加1。在本發明所述的方法中，所述在選擇操作後的新種群中，對所有的解進行兩兩配對，將配對在一起的兩個解進行交叉操作的步驟包括：從配對在一起的解向量A和解向量B中分別隨機選取兩個相鄰0之間的非零向量，且此非零向量的長度不超過N-K+1，記為向量A1和向量B1，反之，如果隨機選取的非零向量的長度超過N-K+1，則將無法完成後續的操作，即會出現某個輛車不被安排任何客戶進行配送；將解向量B中沒有在向量A1出現的所有非零分量按順序組成向量A2；同理，將解向量A中沒有在向量B1中出現的所有非零分量按順序組成向量B2；在向量A2和向量B2的分量之間的空隙中分別隨機選取K-2個位置插入0，得到新的向量A3和B3平；按照(0A10A30)的形式重新組合得到新的解向量C；按照(0B10B30)的形式重新組合得到新的解向量D。在本發明所述的方法中，所述根據預設算法對所述點邊集信息進行計算以得到最短路徑信息，所述最短路徑信息包括配送中心到各個客戶的最短路徑以及各個客戶之間的最短路徑的步驟包括：計算頂點集V中一點a到其餘各點的最短路經，其中a表示配送中心，頂點集V表示配送中心和客戶組成的點集；把頂點集V分成兩組，一組為已經求出最短路徑的頂點集，用R表示；初始時只有一個源點a中每求出一條最短路，便加入到R中，直到全部頂點都加入到R中，算法結束；另一組為其餘未確定最短路徑的頂點集，用V\R表示；按最短路徑長度的遞增次序依次加入到R中，在加入過程中，保持從源點a到中各頂點的最短路徑長度小於等於從源點a到V\R中任何頂點的最短路徑長度。在本發明所述的方法中，還包括：獲取道路交通信息和帶時間窗的生鮮農產品VRP問題的基本參數；其中，所述基本參數主要包括客戶地理位置、訂單需求量、客戶時間窗約束、新鮮度約束。為實現上述第二目的，本發明採用了以下技術。一種產品車輛路徑實現裝置，其特徵在於，包括：讀取模塊，用於讀取城市道路的點邊集信息；第一計算模塊，用於根據預設算法對所述點邊集信息進行計算以得到最短路徑信息，所述最短路徑信息包括配送中心到各個客戶的最短路徑以及各個客戶之間的最短路徑；初始化模塊，用於採用一預設編碼方式初始化種群；第二計算模塊，用於根據所述最短路徑信息以及所述初始化種群計算每個解對應的目標函數值；選擇模塊，用於從各個解對應的目標函數值中選出最小的目標函數值，以及與該最小的目標函數值對應的解；操作模塊，用於對所述目標函數值依次進行選擇操作、交叉操作、變異操作、重插入以及更新記錄。在本發明所述的裝置中，所述初始化模塊用於將客戶序列隨機打亂得到一個新的序列1；在序列1的N-1個空隙中隨機選取K-1個插入0，得到序列2，其中N表示客戶總數量，K表示配送車輛總數目；在序列2的兩端分別補上0，得到序列3，序列3即為一個初始解；根據所述初始解獲取初始化的種群。在本發明所述的裝置法中，所述操作模塊包括：選擇單元，用於根據當前種群中每個解的目標函數值，從中選出偶數組解；交叉單元，用於在選擇操作後的新種群中，對所有的解進行兩兩配對，將配對在一起的兩個解進行交叉操作；變異單元，用於對每一個解隨機生成一個預設數值，如果該預設數值小於變異概率，對當前解進行變異操作，否則，不對當前解進行變異操作；重插入單元，用於將變異操作後的一組解及原種群中的部分解重新組合得到新的種群；更新單元，用於如果新種群的最優值小於記錄的上一種群的最優值，則用新種群的最優值及其對應的解替換記錄的上一種群中的最優值及其對應的解，同時令解不變次數為0；否則，不更新記錄中的最優值及其對應的解，同時令解不變次數加1。在本發明所述的裝置法中，所述交叉單元用於從配對在一起的解向量A和解向量B中分別隨機選取兩個相鄰0之間的非零向量，且此非零向量的長度不超過N-K+1，記為向量A1和向量B1，反之，如果隨機選取的非零向量的長度超過N-K+1，則將無法完成後續的操作，即會出現某個輛車不被安排任何客戶進行配送；將解向量B中沒有在向量A1出現的所有非零分量按順序組成向量A2；同理，將解向量A中沒有在向量B1中出現的所有非零分量按順序組成向量B2；在向量A2和向量B2的分量之間的空隙中分別隨機選取K-2個位置插入0，得到新的向量A3和B3平；按照(0A10A30)的形式重新組合得到新的解向量C；按照(0B10B30)的形式重新組合得到新的解向量D。本發明的積極效果是：通過讀取城市道路的點邊集信息；根據預設算法對所述點邊集信息進行計算以得到最短路徑信息，所述最短路徑信息包括配送中心到各個客戶的最短路徑以及各個客戶之間的最短路徑；採用一預設編碼方式初始化種群；根據所述最短路徑信息以及所述初始化種群計算每個解對應的目標函數值；從各個解對應的目標函數值中選出最小的目標函數值，以及與該最小的目標函數值對應的解；對所述目標函數值依次進行選擇操作、交叉操作、變異操作、重插入以及更新記錄。本發明極大地減少了實際運輸與理論運輸之間的誤差，無論是在生鮮農產品配送，還是在交通路徑中都具有很強的現實意義。附圖說明為了更清楚地說明本發明的運行原理和使用的技術方案，下面將對運行原理和使用的技術中所需要使用的附圖作簡單地介紹。顯而易見，下面描述中的附圖僅僅是本發明的一些運行例子，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其它的附圖。圖1是本發明一種產品車輛路徑實現方法的流程圖。圖2是本發明一種產品車輛路徑實現方法的目標函數優化曲線圖。圖3是本發明車輛1的行車路線圖。圖4是本發明車輛2的行車路線圖。圖5是本發明車輛3的行車路線圖。圖6是本發明車輛4的行車路線圖。圖7是本發明車輛5的行車路線圖。圖8是本發明車輛6的行車路線圖。具體實施方式下面結合附圖對本發明的技術方案進行清楚、完整地描述，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員在沒有作出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。參見圖1，一種產品車輛路徑實現方法，包括：S1：讀取城市道路的點邊集信息需要說明的是，讀取信息：自動讀取城市道路的點邊集信息，即G＝(V，E)。S2：根據預設算法對所述點邊集信息進行計算以得到最短路徑信息，所述最短路徑信息包括配送中心到各個客戶的最短路徑以及各個客戶之間的最短路徑。S3：採用一預設編碼方式初始化種群需要說明的是，為了滿足VRPSTWFAP解的結構的特殊性以及更方便地進行交叉操作和變異操作，本發明採用如下編碼方式對種群進行初始化(其中一個種群對應一組解，種群中的每條染色體對應每個解，染色體的每個分量稱為基因，基因對應解的分量)，具體步驟如下。S4：根據所述最短路徑信息以及所述初始化種群計算每個解對應的目標函數值需要說明的是，根據S2得到的配送中心到各客戶以及各客戶之間的最短路徑和S3生成的初始種群，計算每個解對應的目標函數值。對於種群中的每個解，分別計算解中每個車輛的總載重量、總行駛距離、車輛到達客戶的時間、車輛到達客戶時各種生鮮農產品的新鮮度以及車輛離開客戶的時間。S5：從各個解對應的目標函數值中選出最小的目標函數值以及與該最小的目標函數值對應的解。S6：對所述目標函數值依次進行選擇操作、交叉操作、變異操作、重插入以及更新記錄。S7：終止規則在其中一個實施例中，所述步驟S3包括：S301：將客戶序列隨機打亂得到一個新的序列1。S302：在序列1的N-1個空隙中隨機選取K-1個插入0，得到序列2，其中N表示客戶總數量，K表示配送車輛總數目。S303：在序列2的兩端分別補上0，得到序列3，序列3即為一個初始解；然後根據該初始解即可得到初始化的種。在其中一個實施例中，所述步驟S4中計算所述種群中的每個解的目標函數值包括：S401：根據配送中心到各客戶以及各客戶之間的最短路徑和步驟S2生成的初始種群。S402：計算每個解對應的目標函數值。S403：對於種群中的每個解，分別計算解中每個車輛的總載重量、總行駛距離、車輛到達客戶的時間、車輛到達客戶時各種生鮮農產品的新鮮度以及車輛離開客戶的時間。在其中一個實施例中，所述步驟S5包括：S501：選擇操作，根據當前種群中每個解的目標函數值，採用輪盤賭的方式從中選出偶數組解，以便進行下述交叉操作和變異操作。S502：交叉操作，由於初始解的生成採用了特殊的編碼方式，為保證交叉後的解是可行解，對採用特殊編碼方式後的種群進行特殊的交叉操作，在選擇操作後的新種群中，對所有的解進行兩兩配對，將配對在一起的兩個解進行交叉操作。S503：變異操作，為了避免全部解陷入局部極小值，對於交叉操作後的一組解，採用如下方式進行變異操作：對每一個解隨機生成一個很小的數，如果該數小於變異概率，對當前解進行變異操作；否則，對當前解不進行變異操作。S504：重插入，將變異操作後的一組解及原種群中的部分解重新組合得到新的種群，以保證種群中解的數量一致。S505：更新記錄，為了保證算法的收斂性，計算新種群的最優值及其對應的解，如果新種群的最優值小於步驟S4中記錄的上一種群的最優值，則用新種群的最優值及其對應的解替換記錄的上一種群中的最優值及其對應的解，同時令解不變次數為0；否則，不更新記錄中的最優值及其對應的解，同時令解不變次數加1。在其中一個實施例中，步驟S2包括：S201：求一點(設為a)到其餘各點的最短路經，其中a表示配送中心，V表示配送中心和客戶組成的點集，E表示邊集。S202：把頂點集V分成兩組，一組為已經求出最短路徑的頂點集，用R表示，初始時只有一個源點a中每求出一條最短路，便加入到R中，直到全部頂點都加入到R中，算法結束。S203：另組為其餘未確定最短路徑的頂點集，用V\R表示，按最短路徑長度的遞增次序依次加入到R中，在加入過程中，保持從源點a到中各頂點的最短路徑長度小於等於從源點a到V\R中任何頂點的最短路徑長度。在其中一個實施例中，所述步驟S6中的交叉操作，包括：S601：從配對在一起的解向量A和解向量B中分別隨機選取兩個相鄰0之間的非零向量，且此非零向量的長度不超過N-K+1，記為向量A1和向量B1，反之，如果隨機選取的非零向量的長度超過N-K+1，則將無法完成後續的操作，即會出現某個輛車不被安排任何客戶進行配送。S602：將解向量B中沒有在向量A1出現的所有非零分量按順序組成向量A2；同理，將解向量A中沒有在向量B1中出現的所有非零分量按順序組成向量B2。S603：在向量A2和向量B2的分量之間的空隙中分別隨機選取K-2個位置插入0，得到新的向量A3和B3平。S604：按照(0A10A30)的形式重新組合得到新的解向量C。S605：按照(0B10B30)的形式重新組合得到新的解向量D。在步驟S7中，終止規則，計算當前最優值的不變次數以及算法循環次數，如果當前最優解的不變次數或算法循環次數有一個達到上限，則算法終止。在另一具體實施例中，本發明一種產品車輛路徑實現方法包括以下步驟：S1：讀取城市道路的點邊集信息。S2：根據Dijkstra算法對所述點邊集信息進行計算以得到配送中心到各客戶以及各客戶之間的最短路徑。S3：採用一預設編碼方式初始化種群。S4：計算所述種群中的每個解的目標函數值以及記錄當前種群的最優值及其對應的解，比較每個解對應的目標函數值，從中選出最小的目標函數值及其對應的解。S5：對所述目標函數值進行選擇操作、交叉操作、變異操作、重插入、更新記錄。S6：終止規則。本發明的目的是採用遺傳算法和Dijkstra算法相結合的方法求解帶軟時間窗約束的生鮮農產品車輛路徑問題。本發明極大減少了實際運輸與理論運輸之間的誤差，無論是在生鮮農產品配送，還是在交通路徑中都可以具有很強的現實意義。首先，我們建立具有軟時間窗約束的多種生鮮農產品車輛路徑優化問題模型為：假設某一物流公司有一個配送中心、N位客戶、K輛同型車，用(0，1，...，N)表示，其中0代表配送中心；W種生鮮農產品；客戶對生鮮農產品需求新鮮度為δi，w，其中0.3≤δi，w≤1；時間窗為[Ei，Si]；需求量qi，w；配送車輛k到達i的時間ti，θk，i，w；對每個客戶的平均服務時間為T0；從客戶i到客戶i的時間為Tk，ij；其中可能經過的交點數目為lk，ij；配送距離dk，ij；車輛k服務的顧客數mk；每輛車的固定費用為c；單位行駛距離配送費用為c1(單位配送成費用和冷顫費用)；早到單位時間懲罰費用為p1；晚到單位時間懲罰費用為p2；生鮮農產品w在保質期內但低於客戶需求新鮮度時單位懲罰費用為γw，超過保質期將產生較大的懲罰費用為γ(γ＞γw)；車輛從配送中心出發完成配送任務後返回配送中心，每位客戶的需求量小於車輛的最大載重量，客戶距離配送中心的距離小於最大行駛距離。配送的各種生鮮農產品在性質上具有極大的相關性。建立數學模型：配送車輛固定費用：配送車輛行駛費用：時間窗懲罰費用：生鮮農產品w的新鮮度：其中，θw0為產品w的初始新鮮度，其與生鮮農產品性質有關。新鮮度懲罰費用：總費用數學模型：約束條件：1≤mk≤N(4)。tk，i+Tk，ij+To＝tkj(6)。0＜θk，i，w≤1(8)。其中，式(2)表示每輛車的載重量約束。式(3)表示每輛車的行駛距離約束。式(4)表示每輛車服務客戶約束。式(5)表示所有車輛服務的客戶數等於總的訂單數。式(6)和(7)表示時間約束。式(8)表示新鮮度約束。式(9)表示車輛k服務的客戶數。式(10)表示每個客戶僅有一輛車服務。式(11)表示每輛車從配送中心出發並返回配送中心。式(12)和式(13)表示0、1決策變量。數學模型求解步驟如下：對於上述數學模型採用混合遺傳算法進行求解，其中，N表示訂單數，K表示0的個數，等於車輛數加1。Step1讀取信息：自動讀取城市道路的點邊集信息，即G＝(V，E)，採用Dijkstra算法計算配送中心到各客戶以及各客戶之間的最短路徑。具體Dijkstra算法如下：Step1.1令R＝{a}，l(a)＝0，對於任意的點x∈V\R，令l(x)＝d(a，x)，其中，若(a，x)∈E，則d(a，x)為邊(a，x)的長度，否則，d(a，x)＝∞。Step1.2當R≠V時，求一點x∈V\R，使得l(x)＝min{l(x)|x∈V\R}，令R＝R∪{x}。Step1.3對任意的點y∈V\R，且(x，y)∈E，則l(y)＝min{l(u)，l(x+c(x，y))}。Step1.4重複上述步驟，知道所有的點都加入到R中。Step2種群初始化：為了滿足VRPSTWFAP解的結構的特殊性，以及更方便地進行交叉操作和變異操作，本發明採用如下編碼方式對種群進行初始化(其中一個種群對應一組解，種群中的每條染色體對應每個解，染色體的每個分量稱為基因，基因對應解的分量)，具體步驟如下。Step2.1將客戶序列隨機打亂得到一個新的序列1。Step2.2在序列1的N-1個空隙中隨機選取K-1個插入0，得到序列2，其中N表示客戶總數量，K表示配送車輛總數目。Step2.3在序列2的兩端分別補上0，得到序列3，序列3即為一個初始解。將12位客戶序列隨機打亂的到新的序列1：163427850192在序列1的10個空隙中隨機選取2個位置插入0，即第三個和第五個空隙位置中插入0，得到序列2：16304207850192在上述序列2的兩端分別補上0得到一個初始解：0163042078501920Step3計算種群中每個解的目標函數值：根據Step1得到的配送中心到各客戶以及各客戶之間的最短路徑和Step2生成的初始種群，計算每個解對應的目標函數值。對於種群中的每個解，分別計算解中每個車輛的總載重量、總行駛距離、車輛到達客戶的時間、車輛到達客戶時各種生鮮農產品的新鮮度以及車輛離開客戶的時間。Step4記錄當前種群的最優值及其對應的解：比較每個解對應的目標函數值，從中選出最小的目標函數值及其對應的解。Step5選擇操作：根據當前種群中每個解的目標函數值，採用輪盤賭的方式從中選出偶數組解，以便進行下述交叉操作和變異操作。Step6交叉操作：由於Step2中初始解的生成採用了特殊的編碼方式，為保證交叉後的解是可行解，對採用特殊編碼方式後的種群進行特殊的交叉操作。在選擇操作後的新種群中，對所有的解進行兩兩配對，將配對在一起的兩個解進行交叉操作：Step6.1從配對在一起的解向量A和解向量B中分別隨機選取兩個相鄰0之間的非零向量，且此非零向量的長度不超過N-K+1，記為向量A1和向量B1。反之，如果隨機選取的非零向量的長度超過N-K+1，則將無法完成後續的操作，即會出現某個輛車不被安排任何客戶進行配送。Step6.2將解向量B中沒有在向量A1出現的所有非零分量按順序組成向量A2；同理，將解向量A中沒有在向量B1中出現的所有非零分量按順序組成向量B2。Step6.3在向量A2和向量B2的分量之間的空隙中分別隨機選取K-2個位置插入0，得到新的向量A3和B3。因為在Step6.1中已經限制了向量A1和向量B1的長度都小於等於N-K+1，所以A2和B2分量之間的空隙都大於等於K-2，保證每個0都有位置插入。Step6.4按照(0A10A30)的形式重新組合得到新的解向量C；同樣，按照(0B10B30)的形式重新組合得到新的解向量D。此時，解向量C和解向量D即為由解向量A和解向量B進行交叉操作後得到的新的成對解。解向量C和解向量D的結構與初始解的結構相同，從而保證了交叉操作將一對可行解變成新的成對可行解。例:在VRPSTWFAP中，由3輛車配送12個訂單的交叉操作：解1：0139108427060520解2：0026107843520190如果選擇兩個交叉點分別為解1：11和13，解2：1和6，經過Step6.1後，可得向量A1和向量B1：A1:6B10261經過Step6.2後可得向量A2和B2A202178435219B213984275經過Step6.3後可得向量A3和向量B3：A3021078435219B3139084275經過Step6.4後可得交叉操作後的新解向量C和新解向量DC0600210784352190D0026101390842750Step6.5對初始種群重複上述過程，可以得到交叉操作後的新種群。Step7變異操作：為了避免全部解陷入局部極小值，對於交叉操作後的一組解，採用如下方式進行變異操作：對每一個解隨機生成一個很小的數，如果該數小於變異概率，對當前解進行變異操作；否則，對當前解不進行變異操作。Step8重插入：將變異操作後的一組解及原種群中的部分解重新組合得到新的種群，以保證種群中解的數量一致。Step9更新記錄：為了保證算法的收斂性，計算新種群的最優值及其對應的解，如果新種群的最優值小於Step4中記錄的上一種群的最優值，則用新種群的最優值及其對應的解替換記錄的上一種群中的最優值及其對應的解，同時令解不變次數為0；否則，不更新記錄中的最優值及其對應的解，同時令解不變次數加1。Step10終止規則：計算當前最優值的不變次數以及算法循環次數，如果當前最優解的不變次數或算法循環次數有一個達到上限，則算法終止，否則返回Step5。車輛路徑問題是一個NP-hard，只有在節點較少時才能求得精確解。雖然很多文獻或專利中都表明能夠解決帶時間窗的車輛路徑問題，然而並沒有透露可行解的編碼方法，也不能保證每次都能夠求得可行解。如由Clarke和Wright提出的節約算法、Pureza和Franca研究的Tabu搜索算法等。這些算法用以求解車輛路徑問題時雖然很有效，但也出現了一些缺陷:如節約算法按節約量從大到小構造路徑，具有運算速度快的優點，但存在未組合點零亂、邊緣點難於組合的問題；Tabu搜素太貪婪地對都一個局部區域以及鄰域搜索，導致一葉障目。為了避免這些缺陷，本發明採用改進遺傳算法，不僅採用群體搜索策略和個體之間信息交換策略，還引用了Dijkstra算法和實際主要道路數據，在此基礎上對算法編碼中的交叉操作做出改進，保證了交叉操作後的解的可行性，最後通過循環策略對配送車輛數進行優化，儘量減少配送人力、物力等費用，經過本發明的改進，生鮮農產品車輛路徑配送費用降到最低。最重要的是很多文獻或專利中都表明能夠解決帶時間窗的車輛路徑問題，然而並沒有透露可行解的編碼方法，也不能保證每次都能夠求得可行解。本發明的改進混合遺傳算法不僅公開了編碼方法，還結合道路數據，保證了每次都能實現可行解。本發明的改進混合遺傳算法解決多種生鮮農產品車輛路徑優化問題，在滿足客戶需求的情況下使配送費用降到最低。區別於以往的以時間最短為目的的路徑優化問題。本發明還提供了一種產品車輛路徑實現系統，所述系統包括：基本參數設置模塊、實際路況計算模塊、遺傳算法優化模塊、結果顯示模塊。在其中一個實施例中，所述基本參數設置模塊用於輸入生鮮農產品路徑優化問題所需的基本參數數據，用於實現種群數量、最大迭代次數、車輛負載、懲罰費用等數據的錄入功能。實際路況計算模塊用於計算配送中心到客戶以及各客戶之間的最短實際距離，使計算結果更加接近於實際運營結果，並加速了遺傳算法優化模塊的計算。遺傳算法優化模塊用於優化生鮮農產品的配送路徑和配送車輛數，使配送成本降到最低。結果顯示模塊用於顯示生鮮農產品的目標函數優化曲線和最終配送路徑。本優化系統包括基本參數設置模塊、實際路況計算模塊、遺傳算法優化模塊、結果顯示模塊。基本參數設置模塊用於輸入生鮮農產品路徑優化問題所需的基本參數數據，能夠實現種群數量、最大迭代次數、車輛負載、懲罰費用等數據的錄入功能。實際路況計算模塊用於計算配送中心到客戶以及各客戶之間的最短實際距離，使計算結果更加接近於實際運營結果，並加速了遺傳算法優化模塊的計算。遺傳算法優化模塊用於優化生鮮農產品的配送路徑和配送車輛數，使配送成本降到最低。結果顯示模塊用於顯示生鮮農產品的目標函數優化曲線和最終配送路徑。為了驗證本發明的實用性和優越性，下面通過實例進行詳細說明。本發明所建模型僅考慮1個配送中心，配送車輛型號單一，載重量、最大行駛距離、行駛速度(勻速)已知，全部以配送中心作為起點。配送的生鮮農產品可以混裝，每個客戶的需求量不超過配送車輛的最大載重量，客戶的位置和需求量已知，每個客戶有且僅有一輛車一次配送完成。每輛車的配送過程中只有卸貨沒有裝貨，且完成配送任務後返回配送中心。本例中設3種生鮮農產品，10輛配送車，222個位置點，其中有20個是客戶點，以位置編號為102的點作為配送中心。例如，參照圖3-圖8，其為車輛1至6的行車路線圖。建立生鮮農產品配送成本數學模型：(1)獲取道路交通信息(參考上海市部分主要道路數據)和帶時間窗的生鮮農產品VRP問題的基本參數，主要包括：客戶地理位置、訂單需求量、客戶時間窗約束、新鮮度約束等。(2)配送中心點的坐標為(121.4149，31.22065)，配送車輛的最大載重量為30t、車速為10km/h、每輛車出行最大行駛距離為300km、早到懲罰費用為5元(￥)、晚到懲罰費用為10元、單位行駛距離成本為1元、生鮮農產品在保質期內，但新鮮度超過客戶需求新鮮度時單位懲罰費用分別為20元、15元、10元、超過保質期單位懲罰費用為均為100元。用10輛同型車，對訂單點進行配送，通過本發明設計的混合遺傳算法，可以得到6輛車對這些客戶進行配送的目標優化函數曲線圖和優化路線圖。本發明還提供了一種產品車輛路徑實現裝置，包括：讀取模塊、第一計算模塊、初始化模塊、第二計算模塊、選擇模塊以及操作模塊。其中，該讀取模塊用於讀取城市道路的點邊集信息。該第一計算模塊用於根據預設算法對所述點邊集信息進行計算以得到最短路徑信息，所述最短路徑信息包括配送中心到各個客戶的最短路徑以及各個客戶之間的最短路徑。該初始化模塊用於採用一預設編碼方式初始化種群。該初始化模塊具體用於將客戶序列隨機打亂得到一個新的序列1；在序列1的N-1個空隙中隨機選取K-1個插入0，得到序列2，其中N表示客戶總數量，K表示配送車輛總數目；在序列2的兩端分別補上0，得到序列3，序列3即為一個初始解；根據所述初始解獲取初始化的種群。該第二計算模塊用於根據所述最短路徑信息以及所述初始化種群計算每個解對應的目標函數值。該選擇模塊用於從各個解對應的目標函數值中選出最小的目標函數值，以及與該最小的目標函數值對應的解。該操作模塊用於對所述目標函數值依次進行選擇操作、交叉操作、變異操作、重插入以及更新記錄。該操作模塊包括：選擇單元，用於根據當前種群中每個解的目標函數值，從中選出偶數組解。交叉單元，用於在選擇操作後的新種群中，對所有的解進行兩兩配對，將配對在一起的兩個解進行交叉操作。變異單元，用於對每一個解隨機生成一個預設數值，如果該預設數值小於變異概率，對當前解進行變異操作，否則，不對當前解進行變異操作。重插入單元，用於將變異操作後的一組解及原種群中的部分解重新組合得到新的種群。更新單元，用於如果新種群的最優值小於記錄的上一種群的最優值，則用新種群的最優值及其對應的解替換記錄的上一種群中的最優值及其對應的解，同時令解不變次數為0；否則，不更新記錄中的最優值及其對應的解，同時令解不變次數加1。交叉單元具體用於從配對在一起的解向量A和解向量B中分別隨機選取兩個相鄰0之間的非零向量，且此非零向量的長度不超過N-K+1，記為向量A1和向量B1，反之，如果隨機選取的非零向量的長度超過N-K+1，則將無法完成後續的操作，即會出現某個輛車不被安排任何客戶進行配送。將解向量B中沒有在向量A1出現的所有非零分量按順序組成向量A2；同理，將解向量A中沒有在向量B1中出現的所有非零分量按順序組成向量B2。在向量A2和向量B2的分量之間的空隙中分別隨機選取K-2個位置插入0，得到新的向量A3和B3平。按照(0A10A30)的形式重新組合得到新的解向量C。按照(0B10B30)的形式重新組合得到新的解向量D。以上對本發明的運行原理進行了詳細介紹，上述運行原理的說明只是用於幫助理解本發明的方法及其核心技術思路；對於本領域的一般技術人員，依據本發明的核心技術思路，在具體實施方式及應用範圍上均會有改變之處。綜上所述，本說明書內容不應理解為對本發明的限制。當前第1頁1 2 3