基于快速排序和遺傳算法的物流路徑優(yōu)化研究

陳疇鏞，鄭冬冬

（杭州電子科技大學(xué)管理學(xué)院，浙江杭州310018）

基于快速排序和遺傳算法的物流路徑優(yōu)化研究

陳疇鏞，鄭冬冬

（杭州電子科技大學(xué)管理學(xué)院，浙江杭州310018）

為了使企業(yè)處理物流配送問(wèn)題更加高效、節(jié)約經(jīng)濟(jì)成本和時(shí)間、以及獲得更多的利潤(rùn)，則建立物流配送路徑問(wèn)題數(shù)學(xué)模型，在約束條件中增加配送車(chē)輛和貨物數(shù)量，在遺傳算法選擇操作中引入快速排序算法降低時(shí)間復(fù)雜度；使用M atlab工具和C語(yǔ)言對(duì)數(shù)學(xué)模型仿真，實(shí)驗(yàn)結(jié)果顯示，引入快速排序算法的遺傳算法，不僅能得到物流路徑問(wèn)題的最優(yōu)解，而且降低了時(shí)間復(fù)雜度，提高了配送效率、節(jié)約了時(shí)間。

物流配送；路徑優(yōu)化；快速排序；遺傳算法；時(shí)間復(fù)雜度

一、引言

從數(shù)學(xué)角度分析，物流配送路徑優(yōu)化是指，貨車(chē)從起點(diǎn)（配送中心）出發(fā)，向需求點(diǎn)運(yùn)送貨物，其中已明確的條件是任意需求點(diǎn)所要求的數(shù)量、地理位置、車(chē)輛最大承重、最長(zhǎng)路程，獲得送貨的最佳路線。

遺傳算法是在處理面對(duì)眾多送貨路線抉擇出最佳方案的方法當(dāng)中使用更為廣泛。美國(guó)的J.H.Holland教授最早構(gòu)想遺傳算法（Genetic Algorithm，GA）。最近幾年，遺傳算法不斷地發(fā)展，H.C.W.Lau認(rèn)為遺傳算法是解決多個(gè)倉(cāng)庫(kù)、多個(gè)需求點(diǎn)、多個(gè)物品車(chē)輛配送路徑優(yōu)化問(wèn)題的較好方法，通過(guò)模糊邏輯指導(dǎo)遺傳算法關(guān)于處理貨車(chē)行駛路線獲得最優(yōu)解[1]。姜大立認(rèn)為遺傳算法是解決車(chē)輛路徑優(yōu)化問(wèn)題的一個(gè)較好方案，構(gòu)建了經(jīng)典的數(shù)學(xué)模型，利用遺傳算法和染色體，以及針對(duì)向量采取了可行化影射[2]。郎茂祥認(rèn)為遺傳算法是解決復(fù)雜難題較好的方法，構(gòu)造包括對(duì)個(gè)體編碼、個(gè)體適應(yīng)值計(jì)算及選擇、交叉和變異，以此獲得物流配送路徑的滿(mǎn)意解[3]。張迅認(rèn)為遺傳算法使用比較靈活，具有較強(qiáng)的收斂性和穩(wěn)定性，特別是關(guān)于快遞配送問(wèn)題的處理如何分配車(chē)輛到各需求點(diǎn)送取貨，是一個(gè)很好的解決方法[4]。郭賽克通過(guò)對(duì)遺傳算法進(jìn)行設(shè)計(jì)、編程和數(shù)據(jù)仿真研究，以及多次測(cè)試，驗(yàn)證了遺傳算法的優(yōu)越性[5]?？傮w而言，遺傳算法在物流配送領(lǐng)域使用廣泛，具有隨機(jī)性、全局性的特點(diǎn)，可以求得滿(mǎn)意解，能夠解決復(fù)雜問(wèn)題。但是遺傳算法也有明顯的缺陷，它所具有的全局搜索性、迭代性，自由空間大，隨機(jī)選擇，也導(dǎo)致了運(yùn)算次數(shù)和時(shí)間復(fù)雜度高[6]。設(shè)計(jì)計(jì)算簡(jiǎn)便、時(shí)間復(fù)雜度低的遺傳算法，能提高物流處理速度，對(duì)于企業(yè)節(jié)省經(jīng)濟(jì)成本具有重要的意義。

二、物流配送路徑優(yōu)化的數(shù)學(xué)模型

物流配送路徑優(yōu)化問(wèn)題是指：以配送中心為起點(diǎn)，使用車(chē)輛向需求點(diǎn)送貨，當(dāng)車(chē)輛將貨物送到目地的時(shí)，則返回起點(diǎn)，且等待下一次運(yùn)送，需求點(diǎn)的所要求數(shù)量是已知的，需求點(diǎn)的地理位置是確定的，車(chē)輛具有最大的承載量和行駛最長(zhǎng)距離。目標(biāo)為總距離最短，總距離指車(chē)輛往返的長(zhǎng)度，約束條件為：（1）全部車(chē)輛只從僅存在的一個(gè)配送中心點(diǎn)出發(fā)；（2）起點(diǎn)具有充沛的貨物和足夠的貨車(chē)可以進(jìn)行調(diào)度；（3）每輛車(chē)不容許超出最大承載量運(yùn)行；（4）每輛車(chē)不允許超出限定的最長(zhǎng)路程；（5）每一送貨點(diǎn)的配送僅指派一輛車(chē)；（6）需求點(diǎn)所要求的數(shù)量和地理位置是確定的；（7）起點(diǎn)和需求點(diǎn)間的路程是已知的；（8）配送必須滿(mǎn)足需求點(diǎn)所要求的到貨時(shí)間。

本文主要參考文獻(xiàn)[3]所創(chuàng)建的車(chē)輛路徑問(wèn)題的數(shù)學(xué)模型，根據(jù)實(shí)際情況，對(duì)模型進(jìn)行修改，考慮到在配送過(guò)程的優(yōu)化效果更顯著，增加兩個(gè)變量的約束范圍，即配送車(chē)輛和貨物的數(shù)量，使其趨于無(wú)窮，以此建立如下的數(shù)學(xué)模型。

假設(shè)1：O標(biāo)記成起點(diǎn)，K為貨車(chē)數(shù)量，G個(gè)貨物，每輛貨車(chē)的承載量最多是Qk（k=1，2，…，K），路程最長(zhǎng)是Dh，L個(gè)送貨點(diǎn)，需求點(diǎn)i的所要求數(shù)量為qi，配送中心O到需

求點(diǎn)i的距離為doi，i和j之間的距離為dij（i，j=1，2，…，L）。

假設(shè)2：nk為第k輛貨車(chē)所要送貨的需求點(diǎn)數(shù)量（nk= 0為第k輛貨車(chē)未被指派），Rk為第k條的路線，由rki構(gòu)成，指需求點(diǎn)在路線k里排序是i（不含rki=0），令rki=0為起點(diǎn)，以此創(chuàng)建此類(lèi)物流配送問(wèn)題的數(shù)學(xué)模型：

式（1）表示建立數(shù)學(xué)模型，在約束條件下，最終目的是最小值化z；

式（2）～（10）為研究問(wèn)題的約束條件；

式（2）表示每輛車(chē)的貨物總重量小于等于最大承載量；

式（3）表示必須滿(mǎn)足指派出的車(chē)輛小于等于最長(zhǎng)路程；

式（4）表示必須滿(mǎn)足各個(gè)路線上的送貨點(diǎn)沒(méi)有超出總量；

式（5）表示任一需求點(diǎn)都安排車(chē)輛配送；

式（6）表示表示路徑所需要配送的需求點(diǎn)；

式（7）表示滿(mǎn)足任意一輛車(chē)能送多個(gè)點(diǎn)，但是每個(gè)客戶(hù)僅由某貨車(chē)負(fù)責(zé)；

式（8）表示起點(diǎn)具有足夠的貨車(chē)；

式（9）表示配送中心具有足夠的貨物；

式（10）存在兩類(lèi)情況，分別是貨車(chē)參與送貨，第k輛車(chē)運(yùn)送需求點(diǎn)總數(shù)≥1，使sign（nk）=1；貨車(chē)沒(méi)有被指派，第k輛車(chē)送貨需求點(diǎn)總數(shù)＜1時(shí)，使sign（nk）=0。

三、算法

（一）遺傳算法的思想

遺傳算法是模仿自然界優(yōu)勝劣汰的進(jìn)化狀況，將可能的解編碼形成向量，而基因是構(gòu)成向量的元素，通過(guò)不斷計(jì)算各染色體的適應(yīng)值，選擇最好染色體，求得滿(mǎn)意解或接近最優(yōu)解。遺傳算法優(yōu)化的是一定數(shù)量個(gè)體構(gòu)成的種群，優(yōu)化的做法分別是選擇、交叉、變異。在遺傳操作過(guò)程中，設(shè)置一些基本參數(shù)：包括染色體長(zhǎng)度、種群大小、實(shí)施交叉和變異操作的概率、最終結(jié)束運(yùn)算值T。該算法包含以下6個(gè)元素及遺傳算法流程圖（見(jiàn)圖1）。

（1）編碼：是指將求解問(wèn)題的每個(gè)可能的解編碼形成向量（染色體），基因是構(gòu)成染色體的元素，使計(jì)算機(jī)能辨別且可處理。

圖1 遺傳算法處理流程圖

（2）初始群體生成：初始種群個(gè)體是由隨機(jī)方式產(chǎn)生,種群的規(guī)模大小是由種群個(gè)體數(shù)目所決定，每個(gè)個(gè)體對(duì)應(yīng)所研究問(wèn)題的解。

（3）適應(yīng)度評(píng)估：是指各自對(duì)周?chē)捻槕?yīng)能力，從而計(jì)算出適應(yīng)度值來(lái)作為評(píng)估好壞的準(zhǔn)則。需要按照問(wèn)題本身需求，構(gòu)建不同適應(yīng)度函數(shù)，在遺傳算法中處于重要位置[7]。

（4）選擇：一般情況下，選擇是基于一定的概率，是使用種群中個(gè)體的適應(yīng)度值大小作為標(biāo)準(zhǔn)，當(dāng)個(gè)體的適應(yīng)度值越大，被選取的可能性也更高。

（5）交叉：一般來(lái)講，交叉操作是以一定概率來(lái)替換重組兩個(gè)父代中個(gè)體的一部分結(jié)構(gòu)而生成新個(gè)體，交叉最終目標(biāo)是為形成新的一代，是孕育出新的良好個(gè)體的方法。通常情況下，一般選取較大的交叉概率值，取值范圍一般為0.4～0.9，交叉率越大，就會(huì)越早達(dá)到最優(yōu)解。

（6）變異：一般情況下，變異是以一定概率進(jìn)行變異。通常情況下，選取的變異概率值較小，區(qū)間是0.001～0.1，如果過(guò)高，會(huì)引起不穩(wěn)定性。變異操作的思想來(lái)源是模擬人類(lèi)遺傳基因的突變，根據(jù)人體的遺傳學(xué)，遺傳基因是相對(duì)穩(wěn)定的，突變情況是相對(duì)較少，則變異概率應(yīng)選取偏小值。變異操作是為防止過(guò)早收斂，保證種群多樣性，使染色體上基因發(fā)生突變。

（二）快速排序算法

通常，在遺傳算法的選擇操作中，個(gè)體的適應(yīng)度值是進(jìn)行從大到小的普通排序，時(shí)間復(fù)雜度大，則引入快速排序算法，降低時(shí)間復(fù)雜度。

快速排序是由C.A.R.Hoare在1962年提出，是始于分治的戰(zhàn)略，其就像一個(gè)二叉樹(shù)，基本思想是將排序的序列分成兩個(gè)獨(dú)立的子序列，前面的子序列中任一數(shù)據(jù)都比后面的子序列中任一數(shù)據(jù)要小，使無(wú)序序列成為有序序列。具

體可描述為：假設(shè)這是一組無(wú)序序列K[1]、K[2]、…、K[n]，首先任取數(shù)據(jù)K[x]作為基準(zhǔn)；從序列的兩端向中間按照順序執(zhí)行比較和交換所處的位置，使排在前的子序列中只留下比K[x]小的數(shù)據(jù),排在后的子序列中只留下比K[x]大的數(shù)據(jù)，同時(shí)重復(fù)把排在前子序列中大于等于K[x]的數(shù)據(jù)同排在后的子序列小于等于K[x]的數(shù)據(jù)互換位置，全部數(shù)據(jù)遍歷之后，將K[x]放置在前面和后面兩個(gè)子序列的接壤地方i，則排在前的子序列中所有數(shù)據(jù)都小于等于K[x]，排在后的而是大于等于K[x]，也就是使前面的K[1]～K[i-1]中的每一個(gè)數(shù)據(jù)＜K[x]，K[i+1]～K[n]中的每一個(gè)數(shù)據(jù)＞K[x]，K[x]的目前位置是排序后的最終放置的地方；緊接著K[1]～K[i-1]和K[i+1]～K[n]兩組數(shù)據(jù)執(zhí)行快速排序，循環(huán)上面語(yǔ)句，存在任一序列為空或僅包括一個(gè)元素，則中斷并跳出。

一次劃分PARTITION的算法步驟：

Step1：首先定義兩個(gè)變量分別是i和j，對(duì)i和j進(jìn)行初始化，令i=a，j=b；

Step2：使從未排序列中選擇在第一位置的S[a]成為key，將K[x]值給pivot，則命令pivot=S[a]；

Step3：從j由后向前比較（j--），尋找到第一個(gè)小于key的元素S[j]，交換S[i]與S[j]，同時(shí)，i++；

Step4：從i位置開(kāi)始由前向后比較（i++），找到第一個(gè)大于key（基準(zhǔn)）的S[i]，S[i]與S[j]交換，同時(shí)，j--。

假設(shè)待排序的序列為{20，26，50，26，15，36，09}，通過(guò)表1和表2的運(yùn)算可知，一次劃分之后為{15，09}20{26，50，36，26}，序列左進(jìn)行排序得到{09，15}20{26，50，36，26}，序列右進(jìn)行排序最終得到{26，26，36，50}，最終得到的結(jié)果為{09，15，20，26，26，36，50}。

表1 i=1的一次劃分過(guò)程

表2 以第一個(gè)數(shù)據(jù)為基準(zhǔn)的排序結(jié)果

（三）結(jié)合快速排序的遺傳算法

在遺傳算法的選擇操作當(dāng)中，第一步是計(jì)算每條染色體的適應(yīng)度值，第二步是算出各自占總和的比例，第三步按照適應(yīng)度值從大到小排序。根據(jù)很多研究理論顯示，計(jì)算機(jī)使用算法處理數(shù)據(jù)，排序時(shí)間占總處理時(shí)間的25%，則提高排序時(shí)間能提高算法處理效率。在此，將快速排序引入遺傳算法的選擇操作中是比較合理的，并不會(huì)產(chǎn)生沖突。不僅能夠改善遺傳算法的排序時(shí)間，而且可以提高其整體時(shí)間。由很多的理論基礎(chǔ)、實(shí)驗(yàn)結(jié)果對(duì)比顯示，在復(fù)雜情況下，其他算法略遜于快速排序。

對(duì)快速排序的效率分析得出，由很多的理論、實(shí)驗(yàn)、對(duì)比表明，快速排序算法仍然是目前最好的和時(shí)間復(fù)雜度最低的方法[8]。當(dāng)記錄較大時(shí)，則應(yīng)選擇快速排序，從平均時(shí)間性能的角度，其他3種的排序方法略次于快速排序和歸并排序，這兩種方法當(dāng)輸入規(guī)模龐大時(shí)，快速排序就占上風(fēng)[9]。快速排序的特點(diǎn)在于排序極其快，數(shù)據(jù)移動(dòng)少，最終使序列從小到大排序?？焖倥判蛩惴ㄊ悄壳白顚?shí)用的算法，很適合處理復(fù)雜問(wèn)題，當(dāng)問(wèn)題規(guī)模越大時(shí)，運(yùn)用算法的執(zhí)行時(shí)間則更長(zhǎng)，相對(duì)于其他算法，使用快速排序的效率更高，效果更顯著。通常用時(shí)間復(fù)雜度（Asymptotic Time Complexity）和空間復(fù)雜度來(lái)衡量算法的效率，對(duì)比算法的時(shí)間復(fù)雜度在保證相同存儲(chǔ)空間下，也就是保證S（n）的前提下，得到算法的運(yùn)行的時(shí)間，快速排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度分別為：

式（1）中，T（n）為算法執(zhí)行時(shí)間，f（n）為問(wèn)題的函數(shù)，其中n為研究問(wèn)題的規(guī)模，T（n）是n的某個(gè)函數(shù)，T（n）和f（n）的增長(zhǎng)率相同。

表3 快速排序算法的性能

針對(duì)n個(gè)需求點(diǎn)的時(shí)間復(fù)雜度研究顯示，根據(jù)表3可知，當(dāng)需求點(diǎn)越多，快速排序發(fā)揮的作用越大，引入快速排序時(shí)，使用遺傳算法對(duì)n個(gè)需求點(diǎn)進(jìn)行物流配送路徑的優(yōu)化，需要計(jì)算n2次；然而，當(dāng)引入以后，僅計(jì)算nlogn次，總的降低了n2-nlogn次，當(dāng)n越大時(shí)，在運(yùn)算的時(shí)間上也明顯減少，同時(shí)運(yùn)算的次數(shù)得到很大的減少，最重要的是時(shí)間復(fù)雜度得到很大降低。

則可知引入后的時(shí)間復(fù)雜度：

未引入的時(shí)間復(fù)雜度：

（四）基于快速排序的遺傳算法

針對(duì)物流配送路徑優(yōu)化問(wèn)題的特點(diǎn)，構(gòu)建解決此類(lèi)現(xiàn)象的遺傳算法，包括選擇設(shè)計(jì)簡(jiǎn)單和最為經(jīng)典的適應(yīng)度函數(shù)，在選擇操作中引入快速排序方法，主要是為遺傳算法的復(fù)雜度得到下降。

1.編碼方法：本文選用自然數(shù)的編碼方式，0為起點(diǎn)（配送中心），其它的每個(gè)整數(shù)為每一個(gè)客戶(hù)點(diǎn)。假設(shè)有10個(gè)需求點(diǎn)，1到10分別表示10個(gè)不同的需求點(diǎn)，配送順序?yàn)?-2-1-3-5-6-4-10-9-8-7-0，這就是一條完整的配送路徑，以0為起始點(diǎn)，以0為結(jié)束點(diǎn)，代表的含義是車(chē)輛配送時(shí)從配送中心出發(fā)最終回到配送中心。

2.初始群體生成：由各個(gè)需求點(diǎn)隨機(jī)產(chǎn)生K條配送路

徑，然后由K條配送路徑構(gòu)成初始種群，初始種群的大小也就為K。

3.適應(yīng)度函數(shù)：本文選擇按比例的適應(yīng)度計(jì)算，原理是將該問(wèn)題的可行解代入模型方程計(jì)算，可得目標(biāo)值，假如其值越小，適應(yīng)度更優(yōu)，該方法比基于排序的適應(yīng)度計(jì)算更為簡(jiǎn)單，方便。根據(jù)資料顯示，適應(yīng)度函數(shù)可以根據(jù)解決問(wèn)題的需求進(jìn)行設(shè)計(jì)，目前存在較多適應(yīng)度函數(shù)，適應(yīng)度函數(shù)[8-9]（Fitness Function）的選取及設(shè)計(jì)盡可能簡(jiǎn)單，使計(jì)算的時(shí)間復(fù)雜度最小，由于適應(yīng)度函數(shù)會(huì)影響遺傳算法的收斂速度及是否可以找到滿(mǎn)意解，且是否體現(xiàn)遺傳算法“優(yōu)勝劣汰”的特點(diǎn)。

4.選擇：是根據(jù)適應(yīng)度函數(shù)的計(jì)算方法，第一步運(yùn)算出每條染色體的適應(yīng)度值，第二步所有的適應(yīng)度求和，接著計(jì)算出每條染色體的適應(yīng)度占總和的比例，最后按適應(yīng)度值從大到小快速排序，在此引入快速排序代替普通排序，其原因在于快速排序能降低遺傳算法運(yùn)算的時(shí)間復(fù)雜度。

5.交叉：本文選擇的是部分匹配交叉法（PartiallyMapped Crossover，PXM），原理是在兩條任意染色體上選取兩個(gè)點(diǎn)X、Y，對(duì)X、Y點(diǎn)之間的基因片段交叉，確定X，Y之間的基因映射關(guān)系，最后將未換部分按映射關(guān)系進(jìn)行映射，以此恢復(fù)合法性。假設(shè)染色體1為：8-7-10-|9-3-1-2|-6-5-4；染色體2為：3-4-5-|2-6-7-9|-10-8-1；對(duì)染色體1和染色體2雙切點(diǎn)之間的中間片段進(jìn)行交換，確定映射關(guān)系，最終按照映射關(guān)系將未換部分進(jìn)行映射得到：染色體1為：8-1-10-|2-6-7-9|-3-5-4；染色體2為：6-4-5-|9-3-1-2|-10-8-7。

6.變異：本文選擇的變異方法是換位變異，換位變異法是為避免問(wèn)題過(guò)早收斂，能保證多樣性；基本原理是按一定概率選中染色體的換位變異操作，任意選出兩個(gè)需求點(diǎn)交換位置。假設(shè)染色體1為：（13567842），若隨機(jī)選擇3和4兩個(gè)需求點(diǎn)進(jìn)行互換，則換位后的染色體1為（14567832）。

四、仿真實(shí)驗(yàn)與結(jié)果分析

本文針對(duì)物流配送路徑優(yōu)化問(wèn)題進(jìn)行仿真實(shí)驗(yàn)分析，目標(biāo)是總距離最短。

假設(shè)貨車(chē)為6輛，車(chē)輛的最大承載力為20噸，行駛的最長(zhǎng)距離為65 km，根據(jù)模擬的10個(gè)坐標(biāo)，如表4所示，求解各個(gè)距離，使用C語(yǔ)言和Matlab工具，在此使用引入快速排序的遺傳算法對(duì)物流配送路徑問(wèn)題進(jìn)行優(yōu)化，求出配送需求點(diǎn)的順序。

表4 10個(gè)隨機(jī)點(diǎn)的坐標(biāo)及需求量

在實(shí)驗(yàn)當(dāng)中采用以下參數(shù)值：遺傳代數(shù)：500，種群個(gè)數(shù)：100，交叉率：0.8，變異率：0.05，終止代數(shù)T為200。

經(jīng)計(jì)算，未優(yōu)化前得到最終的線路為：0-7-8-6-9-5-10-2-1-3-4-0，配送的總距離為：147.745 8 km，如圖2所示。

圖2 優(yōu)化前的配送路徑

針對(duì)此問(wèn)題，在遺傳算法的選擇操作中引入快速排序算法及對(duì)遺傳算法的設(shè)計(jì)對(duì)此例優(yōu)化，算法運(yùn)算具體步驟如下：

（1）獲取表4需求點(diǎn)坐標(biāo)，利用算法運(yùn)算，求得距離值，具體運(yùn)算過(guò)程如圖3所示。

圖3 算法通過(guò)獲取坐標(biāo)后的運(yùn)算

最后還需判斷基因是否在指定的區(qū)間isInArray（int value，int*s，int start，int end）。

（2）初始化種群：采用自然數(shù)的編碼方法，Num為個(gè)體數(shù)，初始種群長(zhǎng)度為len，初始化隨機(jī)操作getOneRandSolution（int*fR，int len），初始化種群的代碼流程如圖4所示。

圖4 初始化種群的代碼流程圖

（3）適應(yīng)函數(shù)：選取按比例的適應(yīng)度運(yùn)算方式，令適應(yīng)度值為f（x），目標(biāo)值為F（x），如公式（1）所示，當(dāng)目標(biāo)值越小，則適應(yīng)度越好。

f（x）=1/F（X）（1）

選擇：在選擇操作中引入快速排序算法QSort（float *R，int**P，int start，int end）排序代替普通排序方法，提高排序速度，代碼如下：

（4）交叉操作利用部分匹配交叉法Cross（int*f1，int*f2，int*s1，int*s2，int start，int end，int len）進(jìn)行交叉，按照遺傳的交叉率0.8進(jìn)行部分交叉。為防止過(guò)早收斂，引入變異操作，采用換位變異Mutation（int**P，int Num，int len，float Pm）進(jìn)行變異，按照遺傳變異率0.05進(jìn)行變異，最終例子的最優(yōu)解。

（5）遺傳算法優(yōu)化后的結(jié)果：通過(guò)（1）～（5）的算法優(yōu)化過(guò)程，也就是遺傳算法設(shè)計(jì)及引入快速排序遺傳算法的優(yōu)化過(guò)程，優(yōu)化后配送總距離為：122.017 3 km，最終的配送線路為：0-3-2-1-10-9-8-7-6-5-4-0，某公司的物流配送路徑如圖5所示。

圖5 優(yōu)化后的配送路徑

通過(guò)遺傳算法優(yōu)化后與優(yōu)化前的配送總距離比較可得優(yōu)化的距離差值D：

D=147.7458 km-122.0173 km=25.7277 km（1）

則通過(guò)算式（1）的計(jì)算得到差值D為25.727 7 km，可知10個(gè)需要的優(yōu)化后的距離明顯減少很多。

通過(guò)遺傳算法的設(shè)計(jì)得到此例的最優(yōu)解，及引入快速排序可提高遺傳算法的時(shí)間復(fù)雜度，從例子中10個(gè)需求點(diǎn)的時(shí)間復(fù)雜度研究顯示，在實(shí)驗(yàn)中，可知引入快速排序的遺傳算法比未引入快速排序遺傳算法的運(yùn)算時(shí)間復(fù)雜度更低，具體可以描述為：未引入快速排序時(shí)，遺傳算法對(duì)10個(gè)需求點(diǎn)優(yōu)化操作需要計(jì)算102次；引入快速排序時(shí)，遺傳算法優(yōu)化10個(gè)需求累計(jì)的計(jì)算次數(shù)達(dá)到10log10次，則運(yùn)算次數(shù)減少102～10log10次，大概約為90次，不僅提高計(jì)算的效率，而且減少運(yùn)算次數(shù)，降低其時(shí)間復(fù)雜度。

五、結(jié)語(yǔ)

處理物流配送路線優(yōu)化問(wèn)題，目前較多使用遺傳算法，這是由于其實(shí)此類(lèi)現(xiàn)象是NP難題，而且是企業(yè)比較關(guān)注的問(wèn)題，能夠?yàn)槠髽I(yè)帶來(lái)更多的利益，使企業(yè)能快速發(fā)展。為了企業(yè)在處理配送的時(shí)間帶來(lái)客戶(hù)滿(mǎn)意度的下降，則需要不斷提高配送的技術(shù)。研究發(fā)現(xiàn)遺傳算法具有可以擴(kuò)大搜索空間，限制性較小，較自由，不受約束的特點(diǎn)，但有運(yùn)算次數(shù)高和運(yùn)算效率低的缺陷。所以根據(jù)此問(wèn)題，構(gòu)造引入快速排序的遺傳算法來(lái)降低遺傳算法的時(shí)間復(fù)雜度，以及設(shè)計(jì)包括采用自然數(shù)的編碼、個(gè)體適應(yīng)值的計(jì)算及選擇、基于概率的交叉和變異操作。當(dāng)企業(yè)所需配送的需求點(diǎn)越多，引入快速排序的效果更明顯，效果不僅是配送的處理速度更加快速，當(dāng)企業(yè)配送員碰到交通高峰期的時(shí)候，急需選擇正確的道路，此方法可以為物流路徑問(wèn)題的滿(mǎn)意解。

[1]Lau H C W，Chan T M，Tsui W T，et al.Application of Genetic Algorithms to Solve the Multidepot Vehicle Routing Problem[J].IEEE Transactions on Automation Science and Engineering，2010，7（2）：383-392.

[2]姜大立，楊西龍，杜文，等.車(chē)輛路徑問(wèn)題的遺傳算法研究[J].系統(tǒng)工程理論與實(shí)踐，1999，19（6）：40-44.

[3]郎茂祥，2002.基于遺傳算法的物流配送路徑優(yōu)化問(wèn)題研究[J].中國(guó)公路學(xué)報(bào)（3）：78-81.

[4]張迅，劉海東，李丹，等，2013.基于遺傳算法的快遞配送車(chē)輛路徑問(wèn)題研究[J].物流技術(shù)（5）：263-267.

[5]郭賽克，劉成泳，2012.基于遺傳算法的物流配送路徑優(yōu)化問(wèn)題的研究[J].科技信息（10）：96-97.

[6]席裕庚，柴天佑，惲為民，1996.遺傳算法綜述[J].控制理論與應(yīng)用（6）：697-708.

[7]朱鰲鑫，1998.遺傳算法的適應(yīng)度函數(shù)研究[J].系統(tǒng)工程與電子技術(shù)（11）：60-64.

[8]霍紅衛(wèi)，許進(jìn)，2002.快速排序算法研究[J].微電子學(xué)與計(jì)算機(jī)（6）：6-9.

[9]淦艷，楊有，2010.五種排序算法的性能分析[J].重慶文理學(xué)院學(xué)報(bào)（自然科學(xué)版）（3）：45-50.

（責(zé)任編輯：C校對(duì)：R）

F224.0；F252

A

1004-2768（2016）11-0001-05

2016-08-31

國(guó)家自然科學(xué)基金項(xiàng)目（71171070，U1509220）

陳疇鏞（1955-），男，浙江紹興人，杭州電子科技大學(xué)管理學(xué)院教授，研究方向：供應(yīng)鏈與物流管理、信息管理與商務(wù)智能；鄭冬冬（1993-），女，浙江溫州人，杭州電子科技大學(xué)管理學(xué)院碩士研究生，研究方向：供應(yīng)鏈與物流管理。