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

1引言

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

2同時送取貨(VRPB)的數(shù)學(xué)模型

2.1問題描述

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

2.2參變量定義

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

2.3數(shù)學(xué)模型

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

2.4改進遺傳算法求解

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

本文選用整數(shù)編碼。將其中一條可行路線編成長度為n+k+1的染色體(i11，i12，i13，…，i1s，0，i21，i22，i23，…，i2t，0，…，0，ik1，ik2，…，ikw)，其中0表示配送中心，ikj表示第k輛車路徑上的第j個顧客的顧客號。下面對這個染色體結(jié)構(gòu)進行解析:第一輛車從配送中心0出發(fā)，經(jīng)過客戶i11，i12，i13，…，i1s后，回到配送中心0，形成子路徑1;第二輛車從配送中心0出發(fā)，經(jīng)過以前未服務(wù)過的客戶i21，i22，…，i2t回配送中心0，形成子路徑2;如此反復(fù)，直到所有客戶的要求全部被滿足。為簡化編碼，可將染色體中的第一個“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;從這種染色體的結(jié)構(gòu)可以看出，它具有子路徑內(nèi)部有序而子路徑之間無序的特點。

2．4．2選擇

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

3實例計算與試驗分析

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

4結(jié)束語

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