導語：物流取送件路線優化模式及算法一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

1引言

如今物流配送在經濟增長中的地位日益顯著，而車輛調度又是物流配送中的主心骨之一，選取恰當的車輛路徑方案，可以提高服務質量，增加客戶滿意度，也能節約成本，帶來更大的效益。所以對車輛取送貨問題(即VRPB)這種復雜普遍的車輛問題的研究優化是當下前沿熱點之一。正是對車輛問題研究的廣泛性，從中可以得出遺傳算法對解決NP難題更有優越性，所以本文研究VRPB優化問題也同樣選擇遺傳算法，不過為了更加方便有效地進行運算，本文對遺傳算法進行了一定的改進。

2同時送取貨(VRPB)的數學模型

2.1問題描述

VRPB問題可以描述為，車隊車輛從初始點出發，完成節點的取貨送貨任務，并回到初始點的過程。為了將現實的取送貨問題抽象為數學模型，建立如下假設:①只有一個初始點，每輛車都從初始點出發，完成任務后又回到初始點;②車輛載重能力為已知，車輛的取送貨量不能超過車輛的能力;③節點位置已知，即各節點之間以及節點與初始點之間的距離;④每個節點的取送貨量已知;⑤每個客戶只能由一輛車服務一次;⑥在客戶處同時完成送貨和取貨任務。

2.2參變量定義

V，所有節點的集合，V={i}，i=0為初始點，i=1，…，n為客戶需求點;I，所有客戶需求點集合，其中V=I∪{0};M，所有車輛的集合，M={k}，k=1，…，m;Qk，車輛k的能力;M，車輛的最長行駛距離;C，各節點間的距離矩陣，C=(cij)，i∈V，j∈V;其中cii=∞，i∈I，c00=0;pi，客戶i的取貨量，i∈I;di，客戶i的送貨量，i∈I;sij，車輛從節點i到達j的距離;xij，車輛是否從節點i直接到達節點j，當xij=1時表示車輛服務于節點i與j之間;否則xij=0。yijk:從節點i直接到達節點j時車輛k上的送貨量;zijk:從節點i直接到達節點j時車輛k上的取貨量;uik:節點i是否由車輛k服務，當uik=1時表示車輛k服務于節點i，否則uik=0;

2.3數學模型

Minf=∑ni=0∑nj=0∑mk=0cijxijk(1)∑ni=0x0ik=2，k∈M;(2)公式(1)為目標函數，是求最優解，使總運輸成本最小，即距離最短;公式(2)表示每輛車都是從配送中心出發最后回到配送中心;公式(3)是保證進入每個節點的車輛又從該節點駛出，并且保證每個節點只被一輛車服務一次;公式(4)～(7)表明車輛任何時間所載貨物不能超過其最大能力;公式(8)表示每輛車不能超過它的最大行駛距離;公式(9)為各個決策變量取值約束。

2.4改進遺傳算法求解

2．4．1編碼及初始值生成

本文選用整數編碼。將其中一條可行路線編成長度為n+k+1的染色體(i11，i12，i13，…，i1s，0，i21，i22，i23，…，i2t，0，…，0，ik1，ik2，…，ikw)，其中0表示配送中心，ikj表示第k輛車路徑上的第j個顧客的顧客號。下面對這個染色體結構進行解析:第一輛車從配送中心0出發，經過客戶i11，i12，i13，…，i1s后，回到配送中心0，形成子路徑1;第二輛車從配送中心0出發，經過以前未服務過的客戶i21，i22，…，i2t回配送中心0，形成子路徑2;如此反復，直到所有客戶的要求全部被滿足。為簡化編碼，可將染色體中的第一個“0”省略。例如，染色體3－2－5－0－9－7－6－0－4－1－8表示如下行車路線:子路徑1:配送中心0→客戶3→客戶2→客戶5→配送中心0;子路徑2:配送中心0→客戶9→客戶7→客戶6→配送中心0;子路徑3:配送中心0→客戶4→客戶1→客戶8→配送中心0;從這種染色體的結構可以看出，它具有子路徑內部有序而子路徑之間無序的特點。

2．4．2選擇

我們運用適應度來對染色體進行選擇。對于染色體S的適值函數h(S)則可基于目標函數式(1)進行構建。由式(10)表示:h(S)=1/f(10)為方便說明下面會取一些簡單的數值進行闡述，具體如下:每個節點用其i值表示，車與車之間用起始點i=0隔開，即如果需要5輛車，為n=12個客戶服務，那么編碼形式如下:(012401130560780129100)。2．4．3交叉運用改進的OX交叉法，將被交叉的子串復制以后移到對方的首位。這不僅能夠在相同雙親的情況下，產生新染色體，避免早熟，做到和放在原位置一樣的作用，同時又能夠將對原染色體的破壞降到最低，盡可能保留原路徑的最優性，具體如下:圖1交叉示意圖運用于實例，如下:染色體V1:(012401130560780129100)染色體V2:(031001248012011670950)由上述圖示的變換我們可得到交叉后的子染色體P1:(124812113567910)，進行完交叉，又要再次對其進行解碼，得P1:(0124801211035607910)。2．4．4變異運用可行性變異操作，使每次變異的結果都能得出有效解，從而提高算法的效率。例如給定各節點取送貨需求量如下表，其中Q1=Q2=Q3=10染色體P1經過第一步變異操作后得到P11:(125601211034807910)。可行性變異操作需要分成兩階段進行:首先檢驗每輛車所取送的貨物是否超出車輛運輸能力，如果超出則進行車輛間節點調換;然后檢驗編碼是否滿足公式(4)～(7)的約束。如果不滿足，則調節車輛內部節點順序。具體操作如下:第一階段:車輛間可行性調整。依次檢驗每一個節點，如不滿足約束，則將該節點調整到下一個0節點之后，由下一輛車服務。經過第一階段，該染色體最后的編碼ρ12:(0124081201135067910)。第二階段:車輛內部可行性調整操作。滿足總送貨輛和總取貨輛的限制，并不代表染色體可行。還需要調整節點順序，實現真正可行。以第一輛車為例，按上述方法將不滿足約束的節點調整到最后服務。產生新染色體:(0124081201135067910)。

3實例計算與試驗分析

運用MATLAB7.0進行實例驗證，設有快遞公司配送中心0，及它所負責區域的100個客戶，客戶點坐標如下表，運輸的車輛載重量一致，均為100。在計算中，設定相關參數:M=300，交叉概率，變異概率分別為:Pc=0．85，Pm=0．02。為證明實驗的有效性，我們進行4次運行，最后運行得結果如下表。通過上表，可得四次試驗的平均成最優目標值為1968.4，車輛數為17，平均跌代數為280。其中第3次得到的最優解最佳，目標函數值為1960.1。

4結束語

根據實際情況，綜合各方面因素對取送貨車輛運輸路線進行優化。在選用最為適用的遺傳算法時，根據具體情況，對算法進行創新改進，使它對整個求解過程更具有效性和方便性，最終用實例求出的最優解證明模型和算法的可行性。但模型和算法都有一定的復雜繁瑣性，還有待進一步簡化改進。