基于改进型粒子群优化算法的VRP问题研究

改进的粒子群算法在ＶＲＰ中的应用

运输调度问题在理论和实践方面都是一个难题。粒子群算法是一种可以解决复杂组合优化问题的有效求解算法。提出了改变惯性权重的粒子群算法，并应用该方法用于求解典型的运输调度问题，结果表明，所提出的方法不仅能得到理想的结果，而且减少运算时间。

标签：粒子群算法;运输调度;惯性权重

1 VRP的数学模型

一般运输调度问题的文字描述：已知需求点的位置坐标和货物需求量，一个车队（有多个车辆）从一个供应点（配送中心）出发，每个需求点只被一辆车访问，且该车所访问需求点的需求量总和不能超过车辆的负载能力，应如何安排车辆的行走路线使得总路线最短。要求：每辆车运输完毕后回到出发点（供应点）。设供应点有K辆车，每辆车的载重为Qk（k=1,2…K）,需求点个数为L，每个需求点的需求量为qi（i=1,2...,L）;需求点i到j的距离为qi（i,j=0,1,2...,L,其中i=0或j=0表示该点为供应点）；第k辆车访问的需求点个数为nk(nk=0表示未使用第k辆车)；用集合Rk表示第k辆车的行驶路线，rki代表Rk中一个需求点，它在路线Rk中的顺序为i,rk0表示供应点。借鉴的数学模型：

minZ=∑kk=1nk-1i=0drkirk(i+1)+drknkrk0（1）

∑nki=1qrn≤Qk,0≤nk≤L（2）

0kk=1nk=L（3）

Rk=rki｜rki∈1,2…，L，i=1,2 …nk,Rk1∩Rk2=,k1≠k2(4)

sign(nk)=1nk≥10其他(5)

其中式（1）为目标函数；式（2）保证每条路径上各需求点需求量之和不超过汽车的重量并表明每条路径上的需求点数不超过总需求点数；式（3）表明每个需求点都得到配送服务；式（4）为每条路径的需求点的组成并且限制每个需求点仅能由一辆汽车送货；式（5）表明当第K辆汽车服务的客户数大于或等于1时。该车参加了配送，此时取sign(nk)=1,当第K辆汽车服务的客户数小于1时，表示未使用该车，取sign(nk)=0。

车辆路径问题（Vehicle Routing Problem，简称VRP）是指在满足一定条件下，一批需要送货的客户，使得送货车辆的路线总长度最小或者送达所有客户的总成本最小的问题。VRP的研究在物流管理、智能交通系统等领域具有重要意义。粒子群算法（Particle Swarm

Optimization，简称PSO）是一种优化算法，它模拟鸟群或鱼群中个体之间的信息共享和合作，通过群体中个体的协作来寻找最优解。本文将探讨如何利用粒子群算法解决车辆路径问题，并对其研究进行深入分析。

一、车辆路径问题的基本概念

1.1 车辆路径问题的定义

车辆路径问题是指在满足一定条件下，一批需要送货的客户，使得送货车辆的路线总长度最小或者送达所有客户的总成本最小的问题。该问题最早由Dantzig和Ramser于1959年提出，随后在实际应用中得到了广泛的关注和研究。

1.2 车辆路径问题的分类

车辆路径问题根据不同的约束条件和优化目标可分为多种类型，常见的包括基本车辆路径问题、时间窗车辆路径问题、多车型车辆路径问题等。

1.3 车辆路径问题的解决方法

针对不同类型的车辆路径问题，可以采用不同的解决方法，常见的包括启发式算法、精确算法、元启发式算法等。其中，粒子群算法作为一种元启发式算法，在解决VRP问题中具有一定优势。

二、粒子群算法的基本原理

2.1 粒子群算法的发展历程

粒子群算法是由Kennedy和Eberhart于1995年提出的一种优化算法，其灵感来源于鸟群或鱼群中个体之间的信息共享和合作。该算法通过模拟群体中个体的协作来寻找最优解，在解决多种优化问题方面具有良好的性能。

2.2 粒子群算法的基本原理

粒子群算法模拟了鸟群或鱼群中个体之间的信息共享和合作过程，其中每个个体被称为粒子，它们以一定的速度在搜索空间中移动，并通过个体最优和群体最优来不断调整自身的位置和速度，最终找到最优解。

2.3 粒子群算法的应用领域

粒子群算法解决VRP代码（matlab）

particle_swarm_optimization.m文件：

function PSOforTSP

%初始化

Alpha=0.25; %个体经验保留概率

Beta=0.25; %全局经验保留概率

NC_max=100; %最大迭代次数

m=80; %微粒数

CityNum=14; %问题的规模（城市个数）[dislist,Clist]=tsp(CityNum);

NC=1;%迭代计数器

R_best=zeros(NC_max,CityNum); %各代最佳路线

L_best=inf.*ones(NC_max,1);%各代最佳路线的长度L_ave=zeros(NC_max,1);%各代路线的平均长度

%产生微粒的初始位置

for i=1:m

x(i,:)=randperm(CityNum);

L(i)=CalDist(dislist,x(i,:));

end

p=x; %p为个体最好解

pL=L;

[L_best(1,1) n_best]=min(L);

R_best(1,:)=x(n_best,:);

L_ave(1,1)=mean(L);

%初始交换序

v=ones(CityNum-1,2,m)*(round(rand*(CityNum-1))+1);

figure(1);

while NC<=NC_max %停止条件之一：达到最大迭代次数for

i=1:m xnew(i,:)=changeFun(x(i,:),v(:,:,i));

A=changeNum(x(i,:),p(i,:));

Arand=randFun(A,Alpha);

xnew(i,:)=changeFun(xnew(i,:),Arand);

B=changeNum(x(i,:),R_best(NC,:));

Brand=randFun(B,Beta);

xnew(i,:)=changeFun(xnew(i,:),Brand);

改进的量子粒子群算法求解车辆路径问题

李娅;王东;杨跃武;周燕

【期刊名称】《计算机与数字工程》

【年(卷),期】2013(041)006

【摘 要】A quantum-behaved particle swarm optimization based on Tent

chaos is proposed for vehicle routing problem(VRP).Based on classical

Quantum-Behaved Particle Swarm Optimization algorithm,the initial status

of particle swarm is produced by Tent chaos.When the algorithm is

trapped in local optimum,tent chaotic search is used for the optimal

particles to enhance the ability of the algorithm optimization,avoid getting

into local optimum and premature convergence.This algorithm is applied

to vehicle routing problem to achieve good results.%提出一种基于Tent混沌映射的改进的量子粒子群优化算法求解车辆路径问题,该算法在基本量子粒子群优化算法(QPSO)的基础之上,采用Tent映射对粒子群的状态进行初始化,在算法进入早熟时,选用Tent映射对最优粒子进行混沌搜索,从而提高了算法的寻优能力,有效避免算法陷入局部最优和过早收敛.采用该算法应用于车辆路径问题取得了较好的效果.

【总页数】5页(P870-873,886)

【作 者】李娅;王东;杨跃武;周燕