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

陳疇鏞，鄭冬冬

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

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

陳疇鏞，鄭冬冬

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

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

物流配送；路徑優化；快速排序；遺傳算法；時間復雜度

一、引言

從數學角度分析，物流配送路徑優化是指，貨車從起點（配送中心）出發，向需求點運送貨物，其中已明確的條件是任意需求點所要求的數量、地理位置、車輛最大承重、最長路程，獲得送貨的最佳路線。

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

二、物流配送路徑優化的數學模型

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

本文主要參考文獻[3]所創建的車輛路徑問題的數學模型，根據實際情況，對模型進行修改，考慮到在配送過程的優化效果更顯著，增加兩個變量的約束范圍，即配送車輛和貨物的數量，使其趨于無窮，以此建立如下的數學模型。

假設1：O標記成起點，K為貨車數量，G個貨物，每輛貨車的承載量最多是Qk（k=1，2，…，K），路程最長是Dh，L個送貨點，需求點i的所要求數量為qi，配送中心O到需

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

假設2：nk為第k輛貨車所要送貨的需求點數量（nk= 0為第k輛貨車未被指派），Rk為第k條的路線，由rki構成，指需求點在路線k里排序是i（不含rki=0），令rki=0為起點，以此創建此類物流配送問題的數學模型：

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

式（2）～（10）為研究問題的約束條件；

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

式（3）表示必須滿足指派出的車輛小于等于最長路程；

式（4）表示必須滿足各個路線上的送貨點沒有超出總量；

式（5）表示任一需求點都安排車輛配送；

式（6）表示表示路徑所需要配送的需求點；

式（7）表示滿足任意一輛車能送多個點，但是每個客戶僅由某貨車負責；

式（8）表示起點具有足夠的貨車；

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

式（10）存在兩類情況，分別是貨車參與送貨，第k輛車運送需求點總數≥1，使sign（nk）=1；貨車沒有被指派，第k輛車送貨需求點總數＜1時，使sign（nk）=0。

三、算法

（一）遺傳算法的思想

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

（1）編碼：是指將求解問題的每個可能的解編碼形成向量（染色體），基因是構成染色體的元素，使計算機能辨別且可處理。

圖1 遺傳算法處理流程圖

（2）初始群體生成：初始種群個體是由隨機方式產生,種群的規模大小是由種群個體數目所決定，每個個體對應所研究問題的解。

（3）適應度評估：是指各自對周圍的順應能力，從而計算出適應度值來作為評估好壞的準則。需要按照問題本身需求，構建不同適應度函數，在遺傳算法中處于重要位置[7]。

（4）選擇：一般情況下，選擇是基于一定的概率，是使用種群中個體的適應度值大小作為標準，當個體的適應度值越大，被選取的可能性也更高。

（5）交叉：一般來講，交叉操作是以一定概率來替換重組兩個父代中個體的一部分結構而生成新個體，交叉最終目標是為形成新的一代，是孕育出新的良好個體的方法。通常情況下，一般選取較大的交叉概率值，取值范圍一般為0.4～0.9，交叉率越大，就會越早達到最優解。

（6）變異：一般情況下，變異是以一定概率進行變異。通常情況下，選取的變異概率值較小，區間是0.001～0.1，如果過高，會引起不穩定性。變異操作的思想來源是模擬人類遺傳基因的突變，根據人體的遺傳學，遺傳基因是相對穩定的，突變情況是相對較少，則變異概率應選取偏小值。變異操作是為防止過早收斂，保證種群多樣性，使染色體上基因發生突變。

（二）快速排序算法

通常，在遺傳算法的選擇操作中，個體的適應度值是進行從大到小的普通排序，時間復雜度大，則引入快速排序算法，降低時間復雜度。

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

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

一次劃分PARTITION的算法步驟：

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

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

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

Step4：從i位置開始由前向后比較（i++），找到第一個大于key（基準）的S[i]，S[i]與S[j]交換，同時，j--。

假設待排序的序列為{20，26，50，26，15，36，09}，通過表1和表2的運算可知，一次劃分之后為{15，09}20{26，50，36，26}，序列左進行排序得到{09，15}20{26，50，36，26}，序列右進行排序最終得到{26，26，36，50}，最終得到的結果為{09，15，20，26，26，36，50}。

表1 i=1的一次劃分過程

表2 以第一個數據為基準的排序結果

（三）結合快速排序的遺傳算法

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

對快速排序的效率分析得出，由很多的理論、實驗、對比表明，快速排序算法仍然是目前最好的和時間復雜度最低的方法[8]。當記錄較大時，則應選擇快速排序，從平均時間性能的角度，其他3種的排序方法略次于快速排序和歸并排序，這兩種方法當輸入規模龐大時，快速排序就占上風[9]。快速排序的特點在于排序極其快，數據移動少，最終使序列從小到大排序。快速排序算法是目前最實用的算法，很適合處理復雜問題，當問題規模越大時，運用算法的執行時間則更長，相對于其他算法，使用快速排序的效率更高，效果更顯著。通常用時間復雜度（Asymptotic Time Complexity）和空間復雜度來衡量算法的效率，對比算法的時間復雜度在保證相同存儲空間下，也就是保證S（n）的前提下，得到算法的運行的時間，快速排序算法的時間復雜度和空間復雜度分別為：

式（1）中，T（n）為算法執行時間，f（n）為問題的函數，其中n為研究問題的規模，T（n）是n的某個函數，T（n）和f（n）的增長率相同。

表3 快速排序算法的性能

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

則可知引入后的時間復雜度：

未引入的時間復雜度：

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

針對物流配送路徑優化問題的特點，構建解決此類現象的遺傳算法，包括選擇設計簡單和最為經典的適應度函數，在選擇操作中引入快速排序方法，主要是為遺傳算法的復雜度得到下降。

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

2.初始群體生成：由各個需求點隨機產生K條配送路

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

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

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

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

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

四、仿真實驗與結果分析

本文針對物流配送路徑優化問題進行仿真實驗分析，目標是總距離最短。

假設貨車為6輛，車輛的最大承載力為20噸，行駛的最長距離為65 km，根據模擬的10個坐標，如表4所示，求解各個距離，使用C語言和Matlab工具，在此使用引入快速排序的遺傳算法對物流配送路徑問題進行優化，求出配送需求點的順序。

表4 10個隨機點的坐標及需求量

在實驗當中采用以下參數值：遺傳代數：500，種群個數：100，交叉率：0.8，變異率：0.05，終止代數T為200。

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

圖2 優化前的配送路徑

針對此問題，在遺傳算法的選擇操作中引入快速排序算法及對遺傳算法的設計對此例優化，算法運算具體步驟如下：

（1）獲取表4需求點坐標，利用算法運算，求得距離值，具體運算過程如圖3所示。

圖3 算法通過獲取坐標后的運算

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

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

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

（3）適應函數：選取按比例的適應度運算方式，令適應度值為f（x），目標值為F（x），如公式（1）所示，當目標值越小，則適應度越好。

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）進行交叉，按照遺傳的交叉率0.8進行部分交叉。為防止過早收斂，引入變異操作，采用換位變異Mutation（int**P，int Num，int len，float Pm）進行變異，按照遺傳變異率0.05進行變異，最終例子的最優解。

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

圖5 優化后的配送路徑

通過遺傳算法優化后與優化前的配送總距離比較可得優化的距離差值D：

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

則通過算式（1）的計算得到差值D為25.727 7 km，可知10個需要的優化后的距離明顯減少很多。

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

五、結語

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

[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]姜大立，楊西龍，杜文，等.車輛路徑問題的遺傳算法研究[J].系統工程理論與實踐，1999，19（6）：40-44.

[3]郎茂祥，2002.基于遺傳算法的物流配送路徑優化問題研究[J].中國公路學報（3）：78-81.

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

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

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

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

[8]霍紅衛，許進，2002.快速排序算法研究[J].微電子學與計算機（6）：6-9.

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

（責任編輯：C校對：R）

F224.0；F252

A

1004-2768（2016）11-0001-05

2016-08-31

國家自然科學基金項目（71171070，U1509220）

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