基于混合粒子群算法的車輛路徑優化問題研究

摘要：設計了一種引入了量子和遺傳算法思想的粒子群算法，該算法結合了粒子群優化算法的快速尋優能力和量子算法可以同時處理多個目標的優點，避免了基本粒子群算法易陷入局部最優的缺點，提高了求解速度。該算法用于解決車輛路徑問題，通過實驗表明了這種算法具有較好的性能。

關鍵詞：粒子群算法；量子；遺傳算法；車輛路徑問題

中圖分類號：U116.2文獻標識碼：A

文章編號：1002-3100(2008)09-0026-04

Abstract: The proposed particle swarm optimization(PSO)algorithm combines the fast optimum search ability of original PSO with the virtue of disposing many objects at the same time of quanta algorithm. It can avoid trapping to local minima as compared with original PSO and improve the speed of solution. The proposed algorithm was applied to the vehicle routing problem. The experimental results of QPSO on vehicle routing problem show the efficiency of the new algorithm.

Key words: particle swarm optimization; quantum; genetic algorithm; vehicle routing problem

0引言

物流配送是物流企業日常生產中一個非常重要的環節，其效率高低直接影響物流企業的運作效益，同時也是電子商務活動不可缺少的內容。在配送管理中，經常需要決策的一個問題就是如何尋找一組費用最小的車輛徑路，將貨物配送到每個客戶手中，也即所謂的車輛路線問題（Vehicle Routing Problem，VRP）。自1959 年由Dantzing 和Ramser 首次提出VRP 以來， 很快引起運籌學、應用數學、網絡分析、圖論及計算機應用等學科的專家與運輸計劃制定者和管理者的極大重視。因為配送路線是否合理，對加快配送速度、降低配送成本、提高服務質量及增加總體經濟效益影響較大。因此，采用科學合理的方法確定配送線路是配送業務中一項非常重要的工作。

VRP一般定義為：對一系列發貨點或收貨點，組織適當的行車路線，使車輛有序地通過它們，在滿足一定的約束條件（如貨物需求量、發送量、交發貨時間、車輛容量限制、行駛里程限制及時間限制等）下，達到一定的目標（如路程最短、費用最小、時間盡量少及使用車輛盡量少等）。配送路徑安排是一個NP-hard問題，很難找到此問題的精確解，常用的一類啟發式算法有：一般啟發式算法、神經網絡、遺傳算法、禁忌搜索及模擬退火等智能化啟發式算法。

粒子群優化算法是一種模擬鳥群飛行的群體智能算法，具有個體數目少，計算簡便，容易實現等優點，在連續空間的優化上取得了非常好的效果，由于VRP問題是一個離散的問題，因此本文設計了一種混合粒子群算法，通過實驗證明這種方法在解決VRP問題時有較好的效果。

1VRP問題的數學模型

VRP問題在現實中的一個物流系統可由這幾部分組成：服務區、倉庫、分布在服務區內的服務點。要把這樣的一個經典的VRP問題抽象成一個數學模型，需要設定一些前提：只有一個倉庫，所有車輛從這里裝載貨物出發，運送完貨物返回倉庫；所有的車輛的運輸能力都是一樣的；每一個服務點只能由一輛車提供服務。

設配送中心需向L個客戶送貨，每個客戶的貨物需求量是g，每輛車的載重量是q，cij表示從i點到j點的運輸成本，其含義可以是距離、費用、時間等，設配送中心編碼為0，客戶編碼為1，2，…，L，數學模型如下。

其中，目標式（1）保證了總成本Z 最小；式（2）為車輛的容量約束；式（3） 保證了每個客戶點的運輸任務僅由一輛車來完成，而所有的運輸任務則由K 輛車共同完成；式（4）和式（5）保證每個客戶能且只能被一輛車服務一次。

2粒子群算法簡介

2.1基本的粒子群算法

粒子群算法采用的是速度一位置搜索模型。在PSO 系統中，每個備選解被稱為一個粒子，多個粒子共存、合作尋優，每個粒子根據它自身的經驗和相鄰群體的最佳經驗在問題空間向更好的位置飛行，直至搜索到最優解。每個粒子代表一個候選解，解的優劣由最優化的目標函數決定。其計算公式如下：

V=w*v+c1*rand（）pbest-x+c2*rand（）gbest-x

x=x+v

其中w稱為慣性因子，控制以前速度對當前速度的影響，較大的w適于對解空間進行大范圍探查，較小的w適于進行小范圍開挖。c1和c2是正常數，稱為加速因子，rand是兩個獨立的（0，1）之間的隨機數。gbest是當前粒子的全局最優值，pbest是某個粒子個體最優值。

2.2編碼

編碼方式，初始解的設置對組合優化問題的求解都有很大的影響。一般情況下，客戶的編碼方式是用自然數表示，自然數i表示第i個客戶（0則代表倉庫）。本文采用一種新的編碼表示方式，即對于k個客戶、m輛車的VRP問題，在客戶序列中插入m一1個0，這樣把客戶序列分成m段，每一段代表一輛車的行走路徑。每個微粒即對應一個k+m—1維向量，也就是問題一個解。

例如，設VRP問題有車輛3輛，6個客戶，若某粒子的位置向量X為：5 3 0 6 1 4 0 2

表示的路徑為：第1輛車：0-5-3-0

第2輛車：0-6-1-4-0

第3輛車：0-2-0

這樣的編碼方式有效地解決了車輛的編碼， 而且將VRP轉成一個TSP問題， 便于采用傳統TSP問題處理方法來求解VRP 問題。

基本粒子群算法中，粒子下一個位置是通過速度的更新來進行的。本文中，下一個位置是通過與全局極值和個體極值的交叉，最后再變異產生的。同時經過變異還防止了算法陷入局部極值的可能。

3混合粒子群算法的介紹

3.1量子計算的基礎知識

3.1.1量子比特編碼

一個量子比特（quantum bit or qubit）不僅可以表示“0”或“1”兩種狀態，而且可以同時表示這兩種狀態之間的任意中間態。一般地，用m個量子比特就可以同時表示2m個狀態。

一個量子比特可能處于|1〉或|0〉，或者處于|1〉和|0〉之間的中間態，即|1〉和|0〉的不同疊加態，因此一個量子位的狀態可表示為：｜?鬃〉=?琢|0〉+?茁|1〉

采用量子比特系統編碼多態問題時， 雖類似二進制編碼，但卻可同時表達多個態的疊加， 具有更好的多樣性特征，3.1.2量子角

3.1.3量子門的更新

量子門（quantum gate） 是量子比特的調整元件，可根據具體問題選擇所需要的量子門，通用量子旋轉門調3.2混合粒子群算法的程序設計

（1）隨機產生初始種群，也即初始解，個數為n，給每個變量賦值，w，c1，c2，迭代次數T，每個客戶的需求量g，車輛載重q，客戶數目L，車輛數目m。

（2）計算初始粒子的適應值，記錄當前粒子的適應值為個體極值pbest，取其中最優值為群體極值gbest。

（8）將交叉后的結果進行變異，方法是，從粒子中隨機取兩個位置，然后將包括這兩個位置在內的子序列以反方向插入到原來位置。

（9）將交叉完后的粒子進行判斷，若滿足條件，則作為粒子的下一個位置，并計算適應值fi；若不滿足則回到步驟（5）。

（10）比較每個粒子新適應值與其個體極值的大小，若fi

4實例分析

本文用matlab7.1，采用文中方法對上述問題進行計算。粒子數n=60，w=0.7，c1=2，c2=2，迭代次數為50次，隨機進行20次計算，每次都達到最優值，平均用時只有1.2秒。得到的最優值為67.5，對應的配送路徑為：

車輛1：0-1-3-5-8-2-0

車輛2：0-6-7-4-0

與文獻[1]給出的結果進行比較，得到表2。

上述問題最優解進化情況如圖1所示，在15代左右就能收斂到最優值。

5總結

本文闡述了基于量子行為和遺傳算法的粒子群優化算法，以及如何運用該算法求解VRP問題，同時比較了這種算法與其他一些算法在求解相同問題的結果，通過以上運行結果的對比和分析可以看到，本文算法求解速度快，結果也是最優。因此在解決VRP問題時，該算法具有很好的優越性。

參考文獻：

[1] 馬慧民，葉春明，吳勇. 車輛路徑問題的并行粒子群算法研究[J]. 上海理工大學學報，2007，29(5):435-439.

[2] 吳建軍，劉軍. 物流配送路徑安排問題的混合蟻群算法[J]. 土木工程學報，2004，37(8):98-101.

[3] 郝會霞，郗建國. 改進的粒子群算法在VRP中的應用[J]. 現代交通技術，2007，4(4):62-64.

[4] 蔡榮英，李麗珊，林曉宇. 求解旅行商問題的自學習粒子群優化算法[J]. 計算機工程與設計，2007，28(2):261-263.

[5] 焦李成，杜海蜂，劉芳，等. 免疫優化計算學習與識別[M]. 北京：科學出版社，2006.

[6] 王翠如，張江維，等. 改進粒子群優化算法求解旅行商問題[J]. 華北電力大學學報，2005，32(6):47-51.