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

第 卷第 期太原科技大学学报 年 月 文章编号：（）收稿日期：基金项目：山西省自然科学基金（）作者简介：李琦翔（），女，硕士研究生，主要研究方向为车辆路径优化的理论及应用研究；通信作者：栗振锋教授，：基于多目标混合粒子群算法的车辆路径优化李琦翔，栗振锋，李兴莉（太原科技大学 交通与物流学院，太原 ；太原科技大学 应用科学学院，太原 ）摘要：针对车辆路径优化问题中的现实因素，考虑了时间窗约束和时变车速的情况，构建了以配送总成本最低和客户平均满意度最高为目标的数学优化模型。为了提高基本粒子群算法的搜索精度和搜索能力，将遗传算法中的交叉和变异操作引入到基本粒子群算法中，设计了一种多目标混合粒子群算法。选取 条实例在 软件上进行实验仿真，并与基本粒子群算法的优化结果进行对比。算例结果表明，相较于基本粒子群算法的优化结果，多目标混合粒子群算法减少了 的平均配送总成本，提高了 的客户平均满意度，其中平均配送车辆数量、平均行驶总路径长度、每辆车平均配送量的计算结果也都得到了优化。为多目标混合粒子群算法求解车辆路径优化问题提供了较好的理论依据。关键词：时间窗；车辆路径优化；粒子群算法；配送总成本；客户满意度中图分类号：文献标识码：车辆路径问题（，）于 年由 和 首次提出，可描述为：已知一个配送中心和一定数量的客户点及其地理位置、所需货物需求量等信息，在满足一定约束条件（如车辆数最少、路径最短、花费时间最少，成本最低等）的前提下，规划出一条或多条路径来满足客户的需求。证明带时间窗的车辆路径问题是一个 问题，在 的基础上，考虑时间窗限制，这类组合优化问题难以在合理的时间内得到最优解，因此学者们尝试采用智能优化算法求解该问题，如遗传算法 、禁忌搜索算法 、模拟退火算法 等，并得到了不错的效果。粒子群算法（，）由 和 于 年提出的一种新的进化算法，粒子群算法模拟了鸟类种群觅食的行为，它以操作简单、收敛速度快等优点被人们广泛应用于各类实际问题中。遗传算法由 教授 于 年首次提出，是借鉴了生物进化规律，随之衍生出的智能优化算法。因其具有良好的全局寻优能力、便于求解离散问题等特点，使得该方法得以广泛应用。由于单个智能优化算法解决实际问题存在一定缺陷，例如：收敛速度过快、易于陷入局部最优等，因此学者们将两种或多种算法相融合，设计出新的混合智能优化算法求解各类组合优化问题，比如廖良才等 将遗传算法和节约算法融合，提出一种混合遗传算法解决车辆调度优化问题；徐杰等 提出一种混合粒子群优化算法处理多目标离散问题；罗耀 将细菌觅食优化算法与粒子群算法结合，提出一种改进的粒子群算法用于求解车辆路径优化问题；熊昕霞等 提出一种混合粒子群优化算法解决移动机器人的路径规划问题。目前单目标车辆路径优化问题的研究较为成熟，但已有的大部分多目标优化问题研究都是基于理想的状态下，例如：车辆行驶速度一直处于匀速状态、车辆行驶总成本未考虑司机所服务的客户点数量不同等，这在实际应用中会产生较大的误差。针对现有研究存在的一些不足，本文考虑了在实际配送过程中，随着车辆服务的客户点数量的不同，其所产生的固定成本也产生一定的变化，以此构建了以车辆配送总成本和客户平均满意度为目标的多目标数学优化模型，在文献 的基础上考虑了配送过程中车辆速度随路况变化的因素，在不同的时间段，车辆的行驶速度不同，对于车辆配送总成本和客户满意度的计算更加贴合实际；将遗传算法中的交叉和变异思想引入到基本粒子群算法中，使得粒子可以有效跳出局部最优从而快速寻求全局最优解，设计出一种多目标混合粒子群算法求解物流配送中的多目标路径优化问题。针对 条实际案例进行实验仿真并对结果进行对比分析，验证了该算法的有效性，具有很强的实际意义。车辆路径优化问题模型构建 问题描述已知一个配送中心和若干个客户点，在配送中心和各个客户点之间的位置坐标及所需货物数量等信息已知的情况下，配送中心接收到客户点下达的订单数量，安排车辆从配送中心出发，向各个客户点配送货物，在满足车辆装载能力、客户服务时间限制等约束的前提下，设计合理的路线以达到降低配送总成本和提高客户平均满意度两个目标。模型假设（）物流配送中心数量单一，且配送中心的货物数量足够，不存在缺货现象；（）物流配送中心具有一定数量的同种类型车辆；（）各个客户点的地理位置、所需货物数量、时间窗限制等基本信息已知；（）配送车辆只负责将货物送至给顾客，不提供换货及退货服务；（）配送车辆的速度随路况的变化而变化。模型符号说明（，）：为无向图，其中 表示所有节点的集合，表示边集，表示配送中心，用表示，表示客户点集合，则 ，；（，），（，）为客户节点 的位置坐标；以下列出建立模型所需要的数学符号。：配送车辆的总数，车辆 （，）：客户点 到客户点 之间的距离：客户点 的货物需求量：配送车辆的最大装载量：配送车辆的单位距离行驶成本：单个车辆的指派成本：点位费：车辆 到达客户 的时间：车辆 在客户 的等待时间：车辆 在客户点 的服务时间：早到的惩罚成本系数：晚到的惩罚成本系数：车辆 在 、两个客户点之间的行驶速度 ：车辆 在 、两个客户点之间的行驶时间，：客户点 要求服务的时间窗，：客户点 可以接受服务的最早和最晚时间窗 模型建立综合考虑配送总成本最低和客户平均满意度最大的双目标优化模型，其中配送总成本由运输成本、固定成本及惩罚成本组成，运输成本需要根据车辆的行驶距离来确定；固定成本由车辆指派成本和运输车辆行驶的多点位费组成；且车辆提前或延迟到达客户点会产生一定的惩罚。如图 所示，在，中车辆到达客户点，不会产生惩罚，在其余时间内送达会产生相应的惩罚。FJMJ图 惩罚区间图 在车辆配送的过程中，由于道路拥挤、突发情况等诸多因素导致车辆无法在顾客所期待的时间内到达，就会降低客户满意度，客户满意度与车辆到达时间关系如图 所示。运输成本 为 （）固定成本 为 （）（）惩罚成本 为第 卷第 期李琦翔，等：基于多目标混合粒子群算法的车辆路径优化 IEJeJlJLJ图 客户满意度与时间关系图 ，（）顾客满意度函数为（），（）综上所述，建立配送总成本最小和客户满意度最大的多目标数学模型如下：（）（）（）约束条件：，（），（），（），且 （），（）（）（）（），（），（）其中，式（）表示车辆 所装载的一条路线上的客户总需求量不得超过车辆的最大载重量；式（）表示配送车辆从配送中心出发，在完成配送任务后返回配送中心；式（）表示到达和离开客户点的配送车辆是同一辆；式（）表示保证每个客户点都被服务到且仅有一辆车为其提供服务；式（）表示消除子回路；式（）表示能够提供配送服务的车辆数不得超过车辆总数；式（）表示车辆到达客户点 的时间点；式（）表示不同的时间段车辆的行驶速度不同；式（）和式（）表示决策变量。多目标混合粒子群优化算法设计 基本粒子群优化算法粒子群优化算法的基本思想是模拟鸟群寻找食物，通过群体中各粒子间相互合作，寻求最优解。粒子通过追寻个体极值 和群体极值 来更新个体的位置，粒子更新速度和位置遵循下列公式：（）（）（）（）（）（）其中，代表粒子的速度；代表粒子的位置；代表初始权重，可以用来调整粒子群算法的全局和局部搜索能力，当 的值较大时，算法的全局搜索能力较强，较小时，算法的局部搜索能力较强；（）是介于（，）之间的随机数；、是加速度因子，一般情况下 多目标混合粒子群优化算法将粒子群算法和遗传算法中的交叉和变异操作相结合，增强算法的搜索能力，防止算法易陷入局部最优。个体编码本文采用方便直观的自然数编码方式，具体方式为：在有 个客户点的实际问题中，表示配送中心，自然数 ，表示各个客户点，车辆从配送中心出发，依次经过各个有需求的客户点，最后返回配送中心。例如在有 个客户需求点的路径中，其中一条配送路径可以表示为（，），即车辆从配送中心 出发，依次经过 号客户点、号客太原科技大学学报 年户点、号客户点、号客户点，然后返回配送中心。粒子交叉个体粒子通过和个体极值与群体极值交叉进行更新，如图 所示，随机选取个体粒子和个体极值粒子的交叉位置为 和 ，交换这两组粒子的位置，然后检测粒子是否冲突，如果冲突，通过映射关系将粒子进行转换，直至没有冲突位置，形成新的个体粒子和个体极值粒子，通过计算适应度值，根据适应度值的大小判断粒子的优劣，从而保留比较优秀的粒子。图 交叉操作 粒子变异变异操作即在交叉后得到的新粒子上随机选取两个位置进行互换。如图 所示，随机选取变异位置 和 进行互换得到新的粒子。图 变异操作 多目标混合粒子群算法流程图图 多目标混合粒子群算法流程图 案例分析基于上述算法，以某物流公司提供的城市配送信息为例，其中配送中心地理坐标为（，），各个客户点的地理坐标、货物体积、门店服务时间及可接受的服务时间窗已知，由于配送的是电子产品，车辆装载能力根据货物的体积进行计算，客户点的具体信息如表 所示。表 客户点具体信息 客户编号经纬度坐标体积 服务时间 服务时间窗（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：（，）：，：相关参数值设置为：车辆指派成本为 元辆，车辆行驶的多点位费为 元 客户，单位运输成本为 元 ，车辆早到的惩罚成本为 元 ，晚到的惩罚成本为 元 ，若超过了客户所能接受的最晚时间限制，惩罚成本增加至 元，配送车型为金杯车，可容纳 货物。在实际配送过程中，由于道路拥堵、突发事项等诸多不确定因素，不同时间段车辆的行驶速度不同，本文将道路交通状态分为道路顺畅时段、道路轻微拥堵时段、道路拥堵时段，具体时间段和速度值设置情况如表 所示。第 卷第 期李琦翔，等：基于多目标混合粒子群算法的车辆路径优化表 不同时间段的行驶速度 时间段速度 ：，：，：，：，：，：，：，：，：采用基本粒子群算法及多目标混合粒子群算法分别对上述案例在 软件上进行实验，为了更好的对比两种算法的结果，将种群数量均设置为 ，最大迭代次数均设置为 ，分别进行计算，计算结果如表 所示，两种算法的目标函数迭代关系如图 和图 所示。表 基本 和多目标混合 的运行结果对比 基本 多目标混合 后者较前者平均配送车辆数量降低 平均配送总成本 减少 客户平均满意度 提高 平均行驶总路径长度 缩短 每辆车平均配送量 提升 从计算结果可知，多目标混合粒子群算法的优化结果明显优于基本粒子群算法，其中平均配送车辆数量相较于基本粒子群算法的优化结果下降了 ，平均配送总成本减少了 ，客户平均满意度提高了 ，平均行驶总路径长度缩短了 ，每辆车的平均配送量提升了 ，达到了降低配送总成本，提高客户满意度的两个目标。从图 配送总成本的迭代关系图中可以看出，基本粒子群算法迭代至约第 次时，成本函数趋于稳定，这时的配送总成本约为 元；多目标混合粒子群算法迭代至约第 次时，成本函数趋于稳定，这时的配送总成本约为 元；从图 客户满意度迭代关系图中可以看出，基本粒子群算法迭代至约第 次时，客户满意度函数趋于稳定，这时的客户满意度约为 ，多目标混合粒子群算法迭代至约第 次时，函数图像趋于稳定，此时的客户满意度为 图 配送总成本迭代关系对比 图 客户满意度迭代关系对比 从图 和图 两个目标的迭代关系曲线中可以得出，多目标混合粒子群优化算法的搜索能力和搜索精度明显优于基本粒子群优化算法，基本粒子群优化算法易于过早收敛，后期搜索能力下降，陷入局部最优，而多目标混合粒子群优化算法可以有效跳出局部最优，从而快速寻求全局最优解。结论本文以配送总成本最低和客户平均满意度最高为目标，构建了带时间窗车辆路径问题的多目标模型。在基本粒子群算法中引入遗传算法的交叉和变异操作，提高算法的搜索能力和搜索精度，设计了多目标混合粒子群算法。结合 条实例对设计的算法进行实验仿真，并与基本粒子群算法的优化结果做对比，可以得到以下结论：太原科技大学学报 年（）采用多目标混合粒子群算法计算得到的平均配送车辆数量下降了 、平均配送总成本减少了 、客户平均满意度提高了 、平均行驶总路径长度缩短了 、每辆车平均配送量提升了 ，计算结果均优于基本粒子群算法。（）多目标粒子群算法相较于基本粒子群算法解的质量得到了优化，能够快速寻求全局最优解，进而证明设计的多目标混合粒子群算法相较于基本粒子群算法有更好的寻优性能，能够有效地求解车辆路径优化问题。参考文献：，（）：，（）：罗苇杭 基于非支配排序遗传算法的时变时间窗多目标车辆路径问题研究 济南：山东大学，陈展，公建宁，刘媛媛，等 基于禁忌搜索的多 系统路径优化算法 计算机工程与应用，（）：裴时域，李元香 改进的模拟退火算法在物流配送中心选址中的应用 统计与决策，（）：，：，廖良才，王栋，周峰 基于混合遗传算法的物流配送车辆调度优化问题求解方法 系统工程，（）：徐杰，黄德先 基于混合粒子群算法的多目标车辆路径研究 计算机集成制造系统，（）：罗耀 基于改进粒子群算法的车辆路径问题研究 交通科技与经济，（）：熊昕霞，何利力 基于混合粒子群算法的移动机器人路径规划 计算机系统应用，（）：林灼强 带交通流的联盟运输调度问题禁忌搜索算法研究 广州：广东工业大学，（，；，）：，（），（）（），：，第 卷第 期李琦翔，等：基于多目标混合粒子群算法的车辆路径优化