基于多目标混合粒子群算法的车辆路径优化

2023-12-13李琦翔栗振锋李兴莉

太原科技大学学报 2023年6期

李琦翔,栗振锋,李兴莉

(1.太原科技大学交通与物流学院,太原 030024;2.太原科技大学应用科学学院,太原030024)

车辆路径问题(Vehicle Routing Problem,VRP)于1959年由Dantzig和Ramser[1]首次提出,可描述为:已知一个配送中心和一定数量的客户点及其地理位置、所需货物需求量等信息,在满足一定约束条件(如车辆数最少、路径最短、花费时间最少,成本最低等)的前提下,规划出一条或多条路径来满足客户的需求。Savelsbergh[2]证明带时间窗的车辆路径问题是一个NP-hard问题,在VRP的基础上,考虑时间窗限制,这类组合优化问题难以在合理的时间内得到最优解,因此学者们尝试采用智能优化算法求解该问题,如遗传算法[3]、禁忌搜索算法[4]、模拟退火算法[5]等,并得到了不错的效果。

粒子群算法(Particle Swarm Optimization,PSO)由J.Kennedy和R.C.Eberhart[6]于1995年提出的一种新的进化算法,粒子群算法模拟了鸟类种群觅食的行为,它以操作简单、收敛速度快等优点被人们广泛应用于各类实际问题中。遗传算法由John Holland教授[7]于1975年首次提出,是借鉴了生物进化规律,随之衍生出的智能优化算法。因其具有良好的全局寻优能力、便于求解离散问题等特点,使得该方法得以广泛应用。由于单个智能优化算法解决实际问题存在一定缺陷,例如:收敛速度过快、易于陷入局部最优等,因此学者们将两种或多种算法相融合,设计出新的混合智能优化算法求解各类组合优化问题,比如廖良才等[8]将遗传算法和节约算法融合,提出一种混合遗传算法解决车辆调度优化问题;徐杰等[9]提出一种混合粒子群优化算法处理多目标离散问题;罗耀[10]将细菌觅食优化算法与粒子群算法结合,提出一种改进的粒子群算法用于求解车辆路径优化问题;熊昕霞等[11]提出一种混合粒子群优化算法解决移动机器人的路径规划问题。目前单目标车辆路径优化问题的研究较为成熟,但已有的大部分多目标优化问题研究都是基于理想的状态下,例如:车辆行驶速度一直处于匀速状态、车辆行驶总成本未考虑司机所服务的客户点数量不同等,这在实际应用中会产生较大的误差。

针对现有研究存在的一些不足,本文考虑了在实际配送过程中,随着车辆服务的客户点数量的不同,其所产生的固定成本也产生一定的变化,以此构建了以车辆配送总成本和客户平均满意度为目标的多目标数学优化模型,在文献[12]的基础上考虑了配送过程中车辆速度随路况变化的因素,在不同的时间段,车辆的行驶速度不同,对于车辆配送总成本和客户满意度的计算更加贴合实际;将遗传算法中的交叉和变异思想引入到基本粒子群算法中,使得粒子可以有效跳出局部最优从而快速寻求全局最优解,设计出一种多目标混合粒子群算法求解物流配送中的多目标路径优化问题。针对23条实际案例进行实验仿真并对结果进行对比分析,验证了该算法的有效性,具有很强的实际意义。

1 车辆路径优化问题模型构建

1.1 问题描述

已知一个配送中心和若干个客户点,在配送中心和各个客户点之间的位置坐标及所需货物数量等信息已知的情况下,配送中心接收到客户点下达的订单数量,安排车辆从配送中心出发,向各个客户点配送货物,在满足车辆装载能力、客户服务时间限制等约束的前提下,设计合理的路线以达到降低配送总成本和提高客户平均满意度两个目标。

1.2 模型假设

(1)物流配送中心数量单一,且配送中心的货物数量足够,不存在缺货现象;

(2)物流配送中心具有一定数量的同种类型车辆;

(3)各个客户点的地理位置、所需货物数量、时间窗限制等基本信息已知;

(4)配送车辆只负责将货物送至给顾客,不提供换货及退货服务;

(5)配送车辆的速度随路况的变化而变化。

1.3 模型符号说明

G=(V,E):G为无向图,其中V表示所有节点的集合,E表示边集,V=D∩N,D表示配送中心,用0表示,N表示客户点集合,N={1,2,3,…,n},则V={0,1,2,…,n};E={(i,j)|i,j∈V},(xi,yi)为客户节点i的位置坐标;以下列出建立模型所需要的数学符号。

K:配送车辆的总数,车辆k(k=1,2,…,K)

dij:客户点i到客户点j之间的距离

qi:客户点i的货物需求量

Q:配送车辆的最大装载量

c:配送车辆的单位距离行驶成本

gk:单个车辆的指派成本

g0:点位费

α:早到的惩罚成本系数

β:晚到的惩罚成本系数

[ei,li]:客户点i要求服务的时间窗

[Ei,Li]:客户点i可以接受服务的最早和最晚时间窗

1.4 模型建立

综合考虑配送总成本最低和客户平均满意度最大的双目标优化模型,其中配送总成本由运输成本、固定成本及惩罚成本组成,运输成本需要根据车辆的行驶距离来确定;固定成本由车辆指派成本和运输车辆行驶的多点位费组成;且车辆提前或延迟到达客户点会产生一定的惩罚。如图1所示,在[ei,li]中车辆到达客户点,不会产生惩罚,在其余时间内送达会产生相应的惩罚。

图1 惩罚区间图Fig.1 Punishment interval graph

在车辆配送的过程中,由于道路拥挤、突发情况等诸多因素导致车辆无法在顾客所期待的时间内到达,就会降低客户满意度,客户满意度与车辆到达时间关系如图2所示。

图2 客户满意度与时间关系图Fig.2 Relationship between customer satisfaction and time

运输成本C1为

(1)

固定成本C2为

(2)

惩罚成本C3为

(3)

顾客满意度函数为

(4)

综上所述,建立配送总成本最小和客户满意度最大的多目标数学模型如下:

minZ1=C1+C2+C3

(5)

(6)

约束条件:

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

其中,式(7)表示车辆k所装载的一条路线上的客户总需求量不得超过车辆的最大载重量;式(8)表示配送车辆从配送中心出发,在完成配送任务后返回配送中心;式(9)表示到达和离开客户点的配送车辆是同一辆;式(10)表示保证每个客户点都被服务到且仅有一辆车为其提供服务;式(11)表示消除子回路;式(12)表示能够提供配送服务的车辆数不得超过车辆总数;式(13)表示车辆到达客户点j的时间点;式(14)表示不同的时间段车辆的行驶速度不同;式(15)和式(16)表示决策变量。

2 多目标混合粒子群优化算法设计

2.1 基本粒子群优化算法

粒子群优化算法的基本思想是模拟鸟群寻找食物,通过群体中各粒子间相互合作,寻求最优解。粒子通过追寻个体极值Pbest和群体极值Gbest来更新个体的位置,粒子更新速度和位置遵循下列公式:

(17)

(18)

其中,Vi代表粒子的速度;Xi代表粒子的位置;ω代表初始权重,可以用来调整粒子群算法的全局和局部搜索能力,当ω的值较大时,算法的全局搜索能力较强,ω较小时,算法的局部搜索能力较强;rand()是介于(0,1)之间的随机数;c1、c2是加速度因子,一般情况下c1=c2=2.

2.2 多目标混合粒子群优化算法

将粒子群算法和遗传算法中的交叉和变异操作相结合,增强算法的搜索能力,防止算法易陷入局部最优。

2.2.1 个体编码

本文采用方便直观的自然数编码方式,具体方式为:在有N个客户点的实际问题中, 0表示配送中心,自然数1,2,…,N表示各个客户点,车辆从配送中心出发,依次经过各个有需求的客户点,最后返回配送中心。例如在有4个客户需求点的路径中,其中一条配送路径可以表示为(0,2,1,4,3),即车辆从配送中心0出发,依次经过2号客户点、1号客户点、4号客户点、3号客户点,然后返回配送中心。

2.2.2 粒子交叉

个体粒子通过和个体极值与群体极值交叉进行更新,如图3所示,随机选取个体粒子和个体极值粒子的交叉位置为4和7,交换这两组粒子的位置,然后检测粒子是否冲突,如果冲突,通过映射关系将粒子进行转换,直至没有冲突位置,形成新的个体粒子和个体极值粒子,通过计算适应度值,根据适应度值的大小判断粒子的优劣,从而保留比较优秀的粒子。

图3 交叉操作Fig.3 Crossover operation

2.2.3 粒子变异

变异操作即在交叉后得到的新粒子上随机选取两个位置进行互换。如图4所示,随机选取变异位置3和6进行互换得到新的粒子。

图4 变异操作Fig.4 Mutation operation

图5 多目标混合粒子群算法流程图Fig.5 Multi-objective hybrid PSO flow chart

2.3 多目标混合粒子群算法流程图

3 案例分析

基于上述算法,以某物流公司提供的城市配送信息为例,其中配送中心地理坐标为(113.832 1,34.700 393),各个客户点的地理坐标、货物体积、门店服务时间及可接受的服务时间窗已知,由于配送的是电子产品,车辆装载能力根据货物的体积进行计算,客户点的具体信息如表1所示。

表1 客户点具体信息

相关参数值设置为:车辆指派成本为210元/辆,车辆行驶的多点位费为40元/客户,单位运输成本为2.5元/km,车辆早到的惩罚成本为5元/h,晚到的惩罚成本为15元/h,若超过了客户所能接受的最晚时间限制,惩罚成本增加至350元,配送车型为金杯车,可容纳8 m3货物。

在实际配送过程中,由于道路拥堵、突发事项等诸多不确定因素,不同时间段车辆的行驶速度不同,本文将道路交通状态分为道路顺畅时段、道路轻微拥堵时段、道路拥堵时段,具体时间段和速度值设置情况如表2所示。

表2 不同时间段的行驶速度

采用基本粒子群算法及多目标混合粒子群算法分别对上述案例在MATLAB软件上进行实验,为了更好的对比两种算法的结果,将种群数量均设置为100,最大迭代次数均设置为400,分别进行计算,计算结果如表3所示,两种算法的目标函数迭代关系如图6和图7所示。

表3 基本PSO和多目标混合PSO的运行结果对比

图6 配送总成本迭代关系对比Fig.6 Total distribution cost iterative relation comparison

图7 客户满意度迭代关系对比Fig.7 Customer satisfaction iterative relationship comparison

从计算结果可知,多目标混合粒子群算法的优化结果明显优于基本粒子群算法,其中平均配送车辆数量相较于基本粒子群算法的优化结果下降了20%,平均配送总成本减少了10.59%,客户平均满意度提高了5.30%,平均行驶总路径长度缩短了24.73%,每辆车的平均配送量提升了4.48%,达到了降低配送总成本,提高客户满意度的两个目标。

从图6配送总成本的迭代关系图中可以看出,基本粒子群算法迭代至约第245次时,成本函数趋于稳定,这时的配送总成本约为2 361元;多目标混合粒子群算法迭代至约第200次时,成本函数趋于稳定,这时的配送总成本约为2 353元;从图7客户满意度迭代关系图中可以看出,基本粒子群算法迭代至约第247次时,客户满意度函数趋于稳定,这时的客户满意度约为0.95,多目标混合粒子群算法迭代至约第197次时,函数图像趋于稳定,此时的客户满意度为1.

从图6和图7两个目标的迭代关系曲线中可以得出,多目标混合粒子群优化算法的搜索能力和搜索精度明显优于基本粒子群优化算法,基本粒子群优化算法易于过早收敛,后期搜索能力下降,陷入局部最优,而多目标混合粒子群优化算法可以有效跳出局部最优,从而快速寻求全局最优解。