1. 引言

VRP問題指車輛路線優(yōu)化問題，一般而言，有一個(gè)或多個(gè)供應(yīng)點(diǎn)，多個(gè)需求點(diǎn)有不同的貨物需求，分析如何組織貨車在這些需求點(diǎn)中進(jìn)行配送從而達(dá)到總里程最小、配送時(shí)間最短、總成本最低等目標(biāo)。VRP問題普遍被認(rèn)為是NP問題(多難問題)，目前有許多關(guān)于該問題的研究，并衍生出了更多的相關(guān)問題，比如VRPTW問題(帶時(shí)間窗的車輛路線問題)、CVRP (簡(jiǎn)單的車輛路線問題)、VRPDP問題(追求最佳服務(wù)時(shí)間的車輛路線問題)等等。

關(guān)于VRPTW問題最早提出的是Solomon [1] 的啟發(fā)式算法研究，隨后有更多學(xué)者對(duì)該問題進(jìn)行了深入的研究，Paessens [2] 為了降低該問題的復(fù)雜度，使用了更加簡(jiǎn)單的結(jié)構(gòu)體系，Wee-Kit [3] 通過對(duì)啟發(fā)式算法進(jìn)行深入研究，利用多種啟發(fā)式算法的進(jìn)行組合尋求近似最優(yōu)解。Ombuki [4] 分別將最短時(shí)間和最少車輛定為優(yōu)化目標(biāo)，使用遺傳算法和禁忌搜索算法對(duì)該目標(biāo)進(jìn)行了求解，并發(fā)現(xiàn)該組合算法的求解結(jié)果優(yōu)于各種單一算法的運(yùn)算結(jié)果。謝秉磊 [5] 通過設(shè)立不同的約束條件設(shè)計(jì)出了能夠同時(shí)解決軟時(shí)間窗約束和硬時(shí)間窗約束的遺傳算法。張麗萍 [6] 等人通過交叉算子，提出了改進(jìn)遺傳算法，在某種程度上能夠有效避免局部最優(yōu)的現(xiàn)象出現(xiàn)。張海剛 [7] 使用改進(jìn)免疫遺傳算法，實(shí)現(xiàn)了帶硬時(shí)間窗的車輛調(diào)度問題的優(yōu)化改進(jìn)。楊宇棟 [8] 引入客戶直接排列的解的表示方式，改進(jìn)了模擬退火算法，提高了求解VRPTW問題的效率。吳勇民將我國現(xiàn)行的生鮮農(nóng)產(chǎn)品網(wǎng)絡(luò)配送網(wǎng)絡(luò)與其他國家進(jìn)行比較，找出缺點(diǎn)，提出問題，并提出了一種新的物流模式。高斌、張仁顧 [9] 在針對(duì)物流中心選址問題上提出了更加全面的選址方式，更加貼合實(shí)際，加入了更多的影響決策的因素，并建立出了非線性規(guī)劃模型，將多種方法進(jìn)行了混合，從性質(zhì)和數(shù)量上都進(jìn)行了考慮，建立了更加完善的選址方式。索志林、王棟 [10] 在針對(duì)生鮮農(nóng)產(chǎn)品在配送過程中的表現(xiàn)性質(zhì)，提出了腐爛函數(shù)這個(gè)概念，并通過大量的實(shí)踐，提出了生鮮農(nóng)產(chǎn)品在相同條件下時(shí)間對(duì)生鮮農(nóng)產(chǎn)品自身價(jià)值的數(shù)學(xué)模型，并進(jìn)行了證明。史曉原 [11] 根據(jù)生鮮農(nóng)產(chǎn)品的固有特性，并參照相關(guān)腐爛函數(shù)，對(duì)其與時(shí)間的關(guān)系進(jìn)行了分析，發(fā)現(xiàn)了他們之間的規(guī)律，并建立了數(shù)學(xué)模型，以最低成本，降低貨損率為目標(biāo)，進(jìn)行了分析，并使用遺傳算法進(jìn)行了相關(guān)計(jì)算，并得出了相關(guān)的優(yōu)化方案。李明澤 [12] 針對(duì)城市內(nèi)農(nóng)產(chǎn)品車輛路徑問題進(jìn)行了探討，根據(jù)運(yùn)輸貨物的特性對(duì)配送路線進(jìn)行優(yōu)化研究。姜大立 [13] 構(gòu)造了車輛路徑問題的染色體表達(dá)，并以此建立了相關(guān)模型證明遺傳算法是求解該問題的較好方案。鐘惟鈺 [14] 通過對(duì)傳統(tǒng)遺傳算法求解過程進(jìn)行分析后，發(fā)現(xiàn)收斂速度較慢，嘗試采用新的雙層編碼方式對(duì)種群進(jìn)行優(yōu)化，提高了遺傳算法運(yùn)行時(shí)的收斂速度。周艷聰 [15] 同樣是針對(duì)車輛路徑問題的遺傳算法的收斂速度進(jìn)行改善，通過對(duì)交叉算子引入局部競(jìng)爭(zhēng)擇優(yōu)機(jī)制保證種群的多樣性，減少相似個(gè)體的出現(xiàn)。金仙力 [16] 利用遺傳算法對(duì)多目標(biāo)路徑優(yōu)化問題進(jìn)行探索，有效解決了服務(wù)點(diǎn)有序且?guī)r(shí)間窗約束條件的車輛路徑問題。

本文以某市配送中心為例，將所需要滿足的各個(gè)需求點(diǎn)抽象為一個(gè)點(diǎn)，假定每個(gè)需求點(diǎn)的需求量可一次配送滿足，每個(gè)需求點(diǎn)對(duì)應(yīng)不同的需求重量以及對(duì)應(yīng)的體積和時(shí)間窗約束，加入時(shí)間窗懲罰機(jī)制，并將懲罰成本加入到配送成本，同時(shí)考慮每個(gè)配送車輛的固定費(fèi)用，以最小成本為最終優(yōu)化目標(biāo)，探究基于遺傳算法的帶有時(shí)間窗約束的車輛路線問題。

2. 問題描述

本文采用石家莊某物流企業(yè)所急需解決的問題作為優(yōu)化目標(biāo)，將其企業(yè)提供的基礎(chǔ)數(shù)據(jù)輸入程序，由于該市物流企業(yè)當(dāng)前物流成本過高，客戶滿意度極低，使企業(yè)進(jìn)入虧損狀態(tài)，該物流企業(yè)的配送中心共有2個(gè)，共有需求點(diǎn)18個(gè)，每個(gè)配送車輛的固定費(fèi)用為150元，速度為40 km/h，每輛車每公里費(fèi)用為15元，超過每個(gè)客戶要求的時(shí)間窗后每個(gè)小時(shí)的系數(shù)為1000，每個(gè)客戶的服務(wù)時(shí)間為15分鐘，加入對(duì)每個(gè)配送車輛負(fù)重空余的懲罰系數(shù)以及配送車輛的體積限制。該企業(yè)的配送中心以及需求點(diǎn)如圖1所示。

Figure 1. Distribution point and demand point location

圖1. 配送點(diǎn)與需求點(diǎn)位置

并建立優(yōu)化模型如下：

目標(biāo)函數(shù)：

min

f

=

50

?

∑

i

=

1

z

(

volume

?

W

i

)

+

15

?

∑

i

=

1

z

D

i

+

Z

?

150

+

1000

?

∑

r

=

1

n

T

r (1)

約束條件：

∑

i

=

1

z

∑

r

=

1

n

a

i

r

=

1 (2)

W

i

=

w

i

?

a

i

r (3)

D

i

=

d

i

s

o

i

+

∑

i

=

1

n

∑

p

=

1

n

d

i

p

+

d

i

s

p

o (4)

t

r

=

d

i

s

o

i

+

a

i

r

?

∑

i

=

1

n

∑

p

=

1

n

d

i

p

v

+

0.25 (5)

T

r

=

∑

i

=

1

r

b

i

(

timewindow

?

t

r

) (6)

W

i

≤

volume (7)

a

i

r

?

∑

i

=

1

n

v

n

≤

V

o

l (8)

a

i

r 表示第r個(gè)需求點(diǎn)是否在第i條配送路線中，等于1時(shí)表示在該條路線上，等于0時(shí)表示不在該條路線上；

W

i 表示第i條配送路線上的需求點(diǎn)所需配送貨物的重量之和；

D

i 表示每條配送路線的距離；

d

i

s

1 表示從起點(diǎn)出發(fā)的距離；

d

i

p 表示同一條路線上各個(gè)需求點(diǎn)之間的距離；

d

i

s

o

i 表示車輛從配送中心o到達(dá)第一個(gè)需求點(diǎn)i的距離；

d

i

s

p

o 表示從最后一個(gè)需求點(diǎn)返回配送中心o的距離；

b

i 表示配送車輛到達(dá)需求點(diǎn)時(shí)是否滿足客戶要求的時(shí)間區(qū)間，等于1時(shí)不滿足，等于0時(shí)滿足客戶要求的時(shí)間區(qū)間；

t

r 表示每個(gè)需求點(diǎn)配送車輛的到達(dá)時(shí)間；

timewindow表示用戶滿意的達(dá)到時(shí)間的區(qū)間；

volume表示配送車輛最大貨物負(fù)載；

v

n 表示同一條配送路線上各個(gè)需求點(diǎn)所需貨物體積的總和；

V表示配送車輛最大可容納的貨物體積。

(2)表示每個(gè)需求點(diǎn)都在配送路線中，且只由一輛配送車輛進(jìn)行配送，(3)表示第i條配送路線上的需求點(diǎn)所需配送貨物的重量之和，(4)每條配送路線的距離，(5)表示每個(gè)需求點(diǎn)配送車輛的到達(dá)時(shí)間，(6)通過將到達(dá)時(shí)間與用戶要求到達(dá)時(shí)間進(jìn)行對(duì)比，(7)表示該配送路線未超過車輛額定載重，(8)表示配送路線上個(gè)需求點(diǎn)的貨物體積值之和未超過配送車輛最大可容納的貨物體積。

3. 遺傳算法運(yùn)算

遺傳算法主要通過五個(gè)步驟對(duì)復(fù)雜問題進(jìn)行運(yùn)算，包括編碼、適應(yīng)度函數(shù)、選擇、交叉、變異從而得到最接近最優(yōu)解的近似解，能夠?qū)Ψ蔷€性目標(biāo)問題進(jìn)行優(yōu)化，同時(shí)對(duì)多個(gè)個(gè)體進(jìn)行計(jì)算，有效避免陷入局部最優(yōu)的情況出現(xiàn)。

(一) 編碼

通過將目標(biāo)個(gè)體轉(zhuǎn)化為染色體的形式并以字符串表示，將該染色體放置在約束條件所形成的解空間中進(jìn)行運(yùn)算。編碼直接決定了后續(xù)步驟的實(shí)現(xiàn)方法，常用的編碼方法包括Grey編碼、實(shí)數(shù)編碼、多級(jí)參數(shù)編碼等等。本論文采用的是實(shí)數(shù)編碼，不需要進(jìn)行編碼的轉(zhuǎn)換。

(二) 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是評(píng)價(jià)群體中個(gè)體好壞的標(biāo)準(zhǔn)，是進(jìn)行自然選擇的唯一依據(jù)，一般是由目標(biāo)函數(shù)加以變化得到，根據(jù)求解最大值還是最小值問題的不同，適應(yīng)度的選擇也不同。

如6，3，11點(diǎn)需求量分別為4，1，2噸，車輛負(fù)重為6噸。

當(dāng)配送路線計(jì)算到11時(shí)，超過負(fù)重上限，此時(shí)得到第一條配送路線，對(duì)比第一個(gè)需求點(diǎn)與哪個(gè)配送中心的距離最接近后，以此為起點(diǎn)，同理尋找返回的配送中心點(diǎn)，并計(jì)算其里程，從點(diǎn)11開始計(jì)算第二條配送路線，重復(fù)上述過程。

(三) 選擇操作

選擇操作是從就群體中選擇優(yōu)良個(gè)體組成新的種群，得到下一代種群，個(gè)體的選擇概率與適應(yīng)度相關(guān)，個(gè)體適應(yīng)度值越高，被選中的概率越大。遺傳算法選擇操作有輪賭盤法、錦標(biāo)賽發(fā)等多種方法。

(四) 交叉操作

交叉操作指從種群個(gè)體中最近選擇兩個(gè)染色體，通過兩個(gè)染色體的交換組合，把優(yōu)秀的基因遺傳給子代，從而產(chǎn)生新的優(yōu)秀個(gè)體。因?yàn)閭€(gè)體采用實(shí)數(shù)編碼，所以交叉操作采用實(shí)數(shù)交叉法，第K個(gè)染色體

a

k 和第L個(gè)染色體

a

l 在j位的交叉操作方法，b為[0,1]區(qū)間的隨機(jī)數(shù)。

隨機(jī)生成2個(gè)染色體如下：

4 12 6 7 2 5 10 14 13 19 3 8 11

3 12 13 9 5 4 14 6 11 10 78 1 2

隨機(jī)生成[0,1]之間的數(shù)，當(dāng)這個(gè)數(shù)字小于交叉概率Pc時(shí)，與臨近的染色體進(jìn)行交叉，例如為0.3，然后在[1,5]之間隨機(jī)選取一個(gè)整數(shù)為1，就從染色體中位于第一位的基因進(jìn)行交叉，將兩者找到相同的基因進(jìn)行交換得到：

|3|126 7 2 5 10 14 13 1 9 |4| 8 11

|4|12 13 9 5 |3|14 6 11 10 7 8 1 2

然后從第二位的基因繼續(xù)進(jìn)行交換，循環(huán)10次，從而得到交叉之后的染色體，并將產(chǎn)生的個(gè)體存儲(chǔ)到子代的種群中，然后對(duì)產(chǎn)生的子代進(jìn)行適應(yīng)度計(jì)算，當(dāng)子代的適應(yīng)度比父代要差時(shí)，保留父代，保證不會(huì)出現(xiàn)退化解。

(五) 變異操作

變異操作的主要目的是保持種群多樣性。變異操作從種群中隨機(jī)選取一個(gè)個(gè)體，選擇個(gè)體中的一點(diǎn)進(jìn)行變異從而產(chǎn)生更加優(yōu)秀的個(gè)體，統(tǒng)稱下一代的群體為子代，上一代群體為父代。

將交叉后的子代進(jìn)行變異操作，隨機(jī)生成[0,1]之間的數(shù)，當(dāng)其取值大于變異概率Pm時(shí)，對(duì)該染色體進(jìn)行變異操作，隨機(jī)生成一個(gè)數(shù)組，將該數(shù)組的第一位和第二位的數(shù)字所對(duì)應(yīng)的交叉后產(chǎn)生的染色體的基因的位置進(jìn)行調(diào)換。

(六) 終止條件

一般情況下，有以下幾種情況發(fā)生時(shí)計(jì)算會(huì)停止：達(dá)到目標(biāo)時(shí)，達(dá)到設(shè)置的時(shí)間，達(dá)到設(shè)置的迭代次數(shù)，在相同多代內(nèi)沒有任何變化時(shí)，系統(tǒng)自動(dòng)停止。本文使用的方法是設(shè)置規(guī)定的迭代次數(shù)，當(dāng)未達(dá)到最大次數(shù)時(shí)會(huì)重復(fù)上面的運(yùn)算，然后選擇適應(yīng)度最好的個(gè)體進(jìn)行輸出。

4. 用遺傳算法研究配送中心路徑問題

其配送中心的坐標(biāo)分別為(40,50)、(60,40)，其他需求點(diǎn)的具體情況如下圖2、圖3所示。其中需求點(diǎn)的時(shí)間約束條件如表1所示。

Figure 2. Demand of distribution points and distribution time requirements

圖2. 配送點(diǎn)需求量及配送時(shí)間要求

Figure 3. Distribution of distribution point distance from demand point

圖3. 配送點(diǎn)距需求點(diǎn)距離分布

Table 1. Demand point time constraint

表1. 需求點(diǎn)時(shí)間約束

各個(gè)需求點(diǎn)距離配送中心的距離如圖3所示，如果與配送中心1的距離小于配送中心2的距離第三列為1，否則為2。

在求出各個(gè)配送點(diǎn)之間的距離之后，使用matlab進(jìn)行計(jì)算，設(shè)定種群大小為150，迭代次數(shù)為200次，交叉概率為0.8，變異概率為0.3。

通過運(yùn)算，迭代過程如圖4所示。

Figure 4. Calculation process

圖4. 迭代過程

得到優(yōu)化后路線如表2，表3所示。

Table 2. Before optimization

表2. 優(yōu)化前路線

Table 3. After optimization

表3. 優(yōu)化后路線表

優(yōu)化前、后路線如圖5、圖6所示。

Figure 5. Pre-optimization roadmap

圖5. 優(yōu)化前路線圖

Figure 6. Optimized roadmap

圖6. 優(yōu)化后示意圖

優(yōu)化前該市配送中心一共需要8輛車，但很大程度上無法滿足需求點(diǎn)的時(shí)間窗要求，加入懲罰成本后，總成本為64,124元，在通過是用遺傳算法進(jìn)行優(yōu)化之后，不僅沒有增加車輛的使用，而且能在很大程度上滿足客戶對(duì)于時(shí)間的要求，加上時(shí)間窗懲罰成本后總成本為24,541元，在配送成本上有顯著的降低，達(dá)到了對(duì)配送中心配送路線優(yōu)化的目的。

5. 結(jié)論

本文利用了遺傳算法的全局性和自適應(yīng)性對(duì)NP問題的最優(yōu)解進(jìn)行尋找，以石家莊市某物流企業(yè)所提供數(shù)據(jù)作為基礎(chǔ)數(shù)據(jù)，著重考慮用戶的滿意度，在相同成本的基礎(chǔ)上，盡可能的滿足客戶的需求，通過建立模型并進(jìn)行求解，科學(xué)地規(guī)劃配送路線，將優(yōu)化前后的路線方案進(jìn)行對(duì)比，結(jié)果表明獲得了較好的優(yōu)化方案。

本文目前只針對(duì)企業(yè)較突出的問題進(jìn)行研究，未來會(huì)通過加入更多約束條件和優(yōu)化算法完善內(nèi)容，比如應(yīng)用神經(jīng)網(wǎng)絡(luò)算法、數(shù)據(jù)分析模型進(jìn)行需求預(yù)測(cè)，幫助提前安排用車，利用改進(jìn)的遺傳算法提高路徑優(yōu)化效率等。

基金項(xiàng)目

石家莊鐵道大學(xué)青年項(xiàng)目(Z6612536)。

總結(jié)

以上是生活随笔為你收集整理的遗传算法配送路径优化java_基于遗传算法的配送中心路径优化问题分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。