陳智勇

青海師范大學(xué),青海 西寧 810000

基于IPSO算法的多目標(biāo)車輛配送路徑規(guī)劃研究

陳智勇

青海師范大學(xué),青海 西寧 810000

針對汽車零部件車輛配送路徑規(guī)劃問題，提出一種基于IPSO的多目標(biāo)車輛路徑規(guī)劃算法。以平均行駛成本、等待時(shí)間成本和懲罰時(shí)間成本為目標(biāo)函數(shù)，建立多目標(biāo)車輛路徑規(guī)劃模型。研究結(jié)果表明，選擇搜索成功率、平均行駛成本和搜索時(shí)間為評價(jià)指標(biāo)，IPSO算法在搜索成功率和搜索時(shí)間以及平均行駛成本方面，均優(yōu)于GA和PSO算法，同時(shí)避免局部最優(yōu)，對降低配送成本和提升企業(yè)競爭力具有重要意義。

粒子群算法;路徑規(guī)劃;多目標(biāo)函數(shù);數(shù)學(xué)模型

隨著經(jīng)濟(jì)和工業(yè)技術(shù)水平的快速發(fā)展，我國汽車工業(yè)持續(xù)高速發(fā)展，汽車零部件制造運(yùn)輸行業(yè)發(fā)展繁榮，競爭異常激烈，其零部件物流成本的高低直接影響其企業(yè)競爭力，車輛配送路徑直接影響企業(yè)成本和客戶服務(wù)水平，因此研究汽車零部件運(yùn)輸車輛的路徑規(guī)劃對降低企業(yè)成本和提高零部件供應(yīng)及時(shí)率具有重要的實(shí)際意義，對提升企業(yè)競爭力具有重要意義[1]。大量研究表明，智能啟發(fā)式算法對求解車輛配送路徑規(guī)劃具有很大優(yōu)勢，本文針對PSO算法存在局部最優(yōu)和早熟的問題，提出一種改進(jìn)的粒子群算法IPSO，并將其應(yīng)用于車輛配送路徑規(guī)劃。

1 改進(jìn)的粒子群算法

粒子群算法（Particle Swarm Optimization Algorithm，PSO）是受鳥群覓食行為啟發(fā)提出的智能搜索算法，通過群體間的協(xié)作和競爭，實(shí)現(xiàn)粒子位置和速度的更新，更新公式如下[2]：

其中，vid(t)和xid(t)分別表示在t時(shí)刻時(shí)第i粒子的速度和位置；rand1和rand2表示隨機(jī)數(shù)，處于[0 1]之間；c1、c2表示學(xué)習(xí)因子。

由于PSO算法存在局部最優(yōu)問題，將隨機(jī)搜索因子引入PSO算法，提出一種改進(jìn)的PSO算法，改進(jìn)模型如下：

其中，公式（4）表示粒子搜索的方向，保證IPSO在約束邊界內(nèi)搜索。公式（5）作用提高IPSO算法初期和后期粒子的全局搜索和局部搜索能力。α為控制參數(shù)，決定粒子分布。

2 汽車零部件車輛配送路徑規(guī)劃

2.1 問題描述

汽車零部件車輛路徑規(guī)劃問題可表述為[3,4]：假設(shè)一汽車零部件中心倉庫，其中心配備有K輛，車輛載重容量為qk(k=1,2,3…,K)，配送需求點(diǎn)有L個(gè)，第i個(gè)需求點(diǎn)的需求量為C，其中，，完成需求點(diǎn)任務(wù)i零部件裝載或卸貨的時(shí)間為Ti，其中任務(wù)i必須在時(shí)間段[ETi, LTi]內(nèi)完成，ETi,LTi分別表示任務(wù)i的最早開始時(shí)間和最遲開始時(shí)間。若配送車輛早于E Ti到達(dá)，則等待；反之，任務(wù)將被延遲。汽車零部件車輛配送示意圖和需求點(diǎn)空間分布圖如圖1和圖2所示。

圖1 配送示意圖Fig.1 The schematic distribution routes

圖2 空間分布圖Fig.2 The spatial distribution

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

針對汽車零部件車輛路徑規(guī)劃問題的描述，汽車零部件中心倉庫編號為0，需求點(diǎn)編號為1,2,3...,L，任務(wù)和中心倉庫均被編號為 i=(0,1,2,3...,L)，決策變量定義如下[5]：

汽車零部件配送車輛路徑規(guī)劃數(shù)學(xué)模型如下：

其中，cij表示由點(diǎn)i到點(diǎn)j的運(yùn)輸成本；Si表示配送車輛到達(dá)需求點(diǎn)i的時(shí)間；pE，pL分別表示車輛提前達(dá)到需求點(diǎn)i的單位時(shí)間內(nèi)的等待成本和滯后到達(dá)需求點(diǎn)i的單位時(shí)間內(nèi)的懲罰成本。

該數(shù)學(xué)模型要求需求點(diǎn)都有車輛進(jìn)行配送服務(wù)，并且每個(gè)需求點(diǎn)只能由一輛配送車輛負(fù)責(zé)完成，此外，同一條配送路徑上的需求點(diǎn)的需求量之和不能超過配送車輛的最大載重。

3 基于IPSO算法的車輛路徑規(guī)劃

3.1 構(gòu)造粒子表達(dá)

實(shí)現(xiàn)路徑的最優(yōu)規(guī)劃，構(gòu)造合適的粒子表達(dá)方式是解決該問題的關(guān)鍵。文中參考文獻(xiàn)[6]，構(gòu)造一個(gè)2L維空間對應(yīng)L個(gè)需求點(diǎn)任務(wù)的車輛路徑規(guī)劃問題，使得需求點(diǎn)任務(wù)對應(yīng)為2維。完成車輛被編號為k，此任務(wù)在車輛k的行駛路徑中的順序?yàn)閞，為了便于計(jì)算和表達(dá)，PSO每個(gè)粒子對應(yīng)的2L維向量X被劃分為兩個(gè)長度為L的向量Xv和Xr，二者分別表示任務(wù)對應(yīng)的車輛編號和對應(yīng)車輛的行駛路徑中的順序。

若需求點(diǎn)任務(wù)為7，配送車輛為3，此時(shí)若粒子位置向量X為：

需求點(diǎn)任務(wù)編號為：1234567

Xv:1 2 2 2 2 3 3

Xr:1 4 3 1 2 2 1

那么，該粒子對應(yīng)的車輛配送路徑為：

車輛1：0 1 0

車輛2：0 4 5 3 2 0

車輛3：0 7 6 0

3.2 算法步驟

Step1:種群初始化；（1）將粒子群劃分為若干個(gè)兩兩互相重疊的相鄰子群；（2）位置向量Xv每一維隨機(jī)取整數(shù)，，表示配送車輛的數(shù)量，Xr取實(shí)數(shù)，；速度向量Vv每一維隨機(jī)取整數(shù)，，Vr取實(shí)數(shù)，；（3）根據(jù)適應(yīng)度函數(shù)公式（12），計(jì)算粒子適應(yīng)度；（4）將適應(yīng)度初始值作為粒子個(gè)體的歷史最優(yōu)值Pi，以此為參照對象，尋找總粒子群體內(nèi)最優(yōu)解Pg和各粒子群體內(nèi)最優(yōu)解Pl。

Step 2:根據(jù)公式（1）更新Xv、Xr和Vv、Vr，其中Xv向上取整，若V，X超過約束邊界，則按邊界值取值；

Step 3:計(jì)算所有粒子適應(yīng)度函數(shù)值；

Step 5:將總粒子群體內(nèi)最優(yōu)解Pg和各粒子群體內(nèi)最優(yōu)解Pl與歷史最優(yōu)解進(jìn)行比較，若優(yōu)于歷史最優(yōu)解，則更新Pg和Pl；

Step 6:若滿足算法停止條件，則輸出最優(yōu)解；反之，返回Step 2。

4 實(shí)驗(yàn)分析

為驗(yàn)證本文算法的有效性和可靠性，將本文算法IPSO和PSO、GA算法進(jìn)行對比，選擇參考文獻(xiàn)[7～8]中實(shí)例為研究對象，其用戶需求如表1所示，其中心倉庫和各需求點(diǎn)的距離矩陣如表2所示。

表1 用戶需求Table 1 User's demand

表2 距離矩陣Table 2 Distance matrix

IPSO參數(shù)設(shè)置：最大迭代次數(shù)1200，種群規(guī)模20，學(xué)習(xí)因子c1=c2=0.5，尋優(yōu)結(jié)果（圖3～7）。

圖3 距離矩陣圖Fig.3 Distance matrix

圖4 IPSO配送路徑Fig.4 IPSO distribution path

圖5 IPSO尋優(yōu)收斂圖Fig.5 Chart of IPSO optimal convergence

圖6 PSO配送路徑Fig.6PSOdistributionpath

圖7 PSO尋優(yōu)收斂圖Fig.7ChartofPSOoptimalconvergence

圖8 GA配送路徑Fig.8GAdistributionpath

圖9 GA尋優(yōu)收斂圖Fig.9ChartofGAoptimalconvergence

表3 IPSO、PSO[8]和GA[9,10]對比結(jié)果Table 3 Comparison results of IPSO、PSO and GA

由圖4～9和表3可知，IPSO算法的搜索成功率為67%，遠(yuǎn)高于PSO和GA的46%和25%，同時(shí)在搜索時(shí)間和平均行駛成本方面，IPSO算法也優(yōu)于PSO和GA，從而驗(yàn)證IPSO算法。

5 結(jié)論

車輛配送路徑直接影響企業(yè)成本和客戶服務(wù)水平，因此研究汽車零部件運(yùn)輸車輛的路徑規(guī)劃對降低企業(yè)成本和提高零部件供應(yīng)及時(shí)率具有重要的實(shí)際意義，本文針對PSO算法存在局部最優(yōu)和早熟的問題，提出一種改進(jìn)的粒子群算法IPSO，并將其應(yīng)用于車輛配送路徑規(guī)劃。研究結(jié)果表明，IPSO算法在搜索成功率和搜索時(shí)間以及平均行駛成本方面，優(yōu)于GA和PSO算法，效果較好。

[1]胡麗麗,王戰(zhàn)備,趙峰.考慮駕駛員滿意度的高斯和聲搜索物流配送路徑優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究,2015,32(12):3622-3625

[2]張?jiān)獦?biāo),呂廣慶.基于混合粒子群算法的物流配送路徑優(yōu)化問題研究[J].包裝工程,2007,28(5):10-12

[3]王華東,李 巍.粒子群算法的物流配送路徑優(yōu)化研究[J].計(jì)算機(jī)仿真,2012,29(5):243-246

[4]潘國強(qiáng),胡俊逸,洪 敏.考慮GIS的物流配送區(qū)域劃分與路徑規(guī)劃算法[J].大連海事大學(xué)學(xué)報(bào),2015,41(1):83-90

[5]孫妮娜,盧才武,盧 娜,等.應(yīng)用群智能混合算法優(yōu)化救災(zāi)物資配送路徑[J].消防科學(xué)與技術(shù),2015(2):263-266

[6]王 華.一種物流配送最短路徑混合算法[J].測繪科學(xué),2014,39(9):135-137

[7]葉 勇,張惠珍.多配送中心車輛路徑問題的狼群算法[J/OL].計(jì)算機(jī)應(yīng)用研究,[2016-09-18].http://www.arocmag.co m/article/o2-2017-09-032.html

[8]馬祥麗,張惠珍,馬 良.帶時(shí)間窗物流配送車輛路徑問題的蝙蝠算法[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(11):254-258

[9]石 兆,符 卓.配送選址-多車型運(yùn)輸路徑優(yōu)化問題及求解算法[J].計(jì)算機(jī)科學(xué),2015,42(5):245-250

[10]韓李濤,牟乃夏,戴洪磊,等.一種基于分層結(jié)構(gòu)的最優(yōu)路徑算法[J].山東科技大學(xué)學(xué)報(bào):自然科學(xué)版,2013,32(3):77-82

Research on Multi-objective Vehicle Route Program Based on IPSO Algorithm

CHEN Zhi-yong
Qinghai Normal University,Xining 810000,China

In this paper,a multi-objective vehicle route program based on IPSO was proposed to solve the vehicle route problem.The multi-objective vehicle route model was established based on the objective cost,waiting time cost and penalty cost to select the search success rate,average travel cost and search time as the evaluation index.The results showed that the IPSO algorithm in the search success rate and search time and average travel cost was better than GA and PSO algorithm.It is important for avoiding the local optimum,reducing the delivery cost and enhancing the competitiveness of enterprises.

Particle swarm optimization;route program;multi-objective function;mathematical model

TQ018

:A

:1000-2324(2017)02-0255-04

10.3969/j.issn.1000-2324.2017.02.019

2016-10-11

:2016-11-25

陳智勇(1981-),男,碩士,講師,主要研究方向?yàn)榻y(tǒng)計(jì)自動化及其應(yīng)用.E-mail:chenzhiyong@qhnu.edu.cn