一类最小-最大车辆路线问题的启发式算法研究.pdf

第 卷 第 期运 筹 与 管 理 ， 年 月 收稿日期：- - 基金项目：国家社会科学基金项目资助（电子商务物流配送体系优化研究 ）；教育部人文社会科学研究项目资助（非常规突发 事件下应急物流网络优化及快速反应机制研究 ） 作者简介：王晓博（- ），男，黑龙江省哈尔滨人，博士，副教授，硕士生导师，研究方向：物流系统仿真；任春玉（- ），女，朝鲜族，黑龙 江省哈尔滨人，硕士，副教授，从事电子商务，物流管理；元野（- ），男，朝鲜族，黑龙江省双鸭山人，博士研究生，从事物流与车辆调度。 一类最小- 最大车辆路线问题的启发式算法研究 王晓博 ， 任春玉， 元 野 （ 黑龙江大学 信息管理学院，黑龙江 哈尔滨 ； 哈尔滨工业大学 管理学院，黑龙江 哈尔滨） 摘 要：针对个性化和多样性的需求，建立以缩短最长子线路为目标的最小- 最大车辆路径问题模型， 并提出启 发式算法求解。 首先，采用自然数编码，使问题变得更简洁；用最佳保留选择法，以保证群体的多样性；引入爬山 算法，加强局部搜索能力；其次，对遗传算法求得的精英种群再进行禁忌搜索，保证算法能够收敛到全局最优。 最后，通过实例的计算，表明本算法均优于遗传算法和禁忌搜索算法，并为大规模解决实际问题提供思路。 关键词：运筹学与控制论；最小- 最大的车辆路径问题；遗传算法；禁忌搜索算法；启发式算法 中图分类号： 文章标识码： 文章编号：- （）- - Heuristic Algorithm for Min- Max Vehicle Routing Problem - ， - ， （ School of Information Management， Heilongjiang University， Harbin ， China； School of Manage- ment， Harbin Institute of Technology， Harbin ， China） Abstract： ， - - ， ， ， - ， ， Key words： ； - ； ； ； 引言 （ ，简称）问题是物流配送中的一项重要研究内容。 近年来，随着现代 物流的发展， 问题引起广泛重视。 对其进行优化，可以提高物流经济效益；满足客户多样化、个性化 的需求；从而实现物流的科学化、服务水平的现代化。 在实际情况中，存在这样的一类车辆路径问题，其目标不是要求整个行车路线的路程最短或费用最 少，而是要求整个线路中行程最长的子线路距离最短或时间最短，这类问题称为最小- 最大车辆路径问题 （- ， ）。 例如：巡逻车队的巡逻线路制定 ，紧急情况下空投物资 的运送线路安排 ，邮递员投送报纸线路安排 ，出于社会因素考虑的校车行车线路制定。 最小- 最大车辆路径问题是一个典型 难题。 其求解方法主要以现代智能优化算法为主。 先求出最大最小车辆路径问题目标函数的最低边界值，后用禁忌搜索算法求解 。 研究校车最小 最大行车线路问题，采用 和 - 交换法的禁忌搜索算法求解 。 为提高生存率，建立缩 短调拨距离 模型；采用基于贪婪邻域搜索的启发式算法求解 。 提出解决最小最大车辆路由 问题的近似算法。 该算法考虑有两部分构成：（）对每条路线长度给定约束中寻找最小路线；（）尽量较 少最大行驶距离 。 采用改进分支 定界的方法来求解最小 最大车辆路径问题。 该算法以 为基础，融合了 、割平面以及分布搜索算法优点 。 研究多目标校车路线安排问题，采用分 散式搜索启发式算法求解，该算法遵循构建，完善，然后再整合的进化式框架流程 。 刘霞首先建立最小 最大车辆路径问题数学模型，后提出禁忌搜索算法求解 ， 。 鉴于最小- 最大车辆路径问题的复杂性，本文提出用启发式求解。 即综合遗传算法和禁忌搜索算法的 优点，设计了对遗传算法求得的精英种群再进行禁忌搜索来求解该类问题的启发式算法。 通过实例验证 本文算法不仅可以计算结果优，且计算效率高，收敛速度快。 数学模型 Z iS jS kV Xijkdij（） 约束条件： kV Yik，i H（） iHjS qiXijk Wk，k V（） iS XijkYik，j S，k V（） jS XijkYik，i S，k V（） iS jS xijk m ，橙m 彻 ，n，k V（） kViS Xijkdij Dk，j H（） Xijk ， i，jS，kV（） Yik ， iH，kV（） 决策变量为： Xijk ，如果运输车辆 k 从节点 i 至节点 j，ijS，kV；否则 Xijk 。 Yik ，如果运输车辆 k 为节点 i 的运输工具，iH，kV；否则 Yik 。 式中：Ggrr ，R为一系列 R 处的配送中心集合（本文只有一个）；Hhi i R ，R N为 一系列 N 处的客户集合；SGH为所有配送中心和客户总和；Vvk k ，K为运输车辆 k 的集 合；qi为客户 i（iH）需求量；Wk为运输车辆 k 的载重量；dij为客户 i 到客户 j 的直线距离；Dk为运输车辆 k 的最大行驶里程。 式（）中，目标函数为不是要求整个行车路线的路程最短，而是要求整个线路中行程最长的线路距离 最短；约束条件（）确保每个客户仅由一个类型的一个运输车辆提供服务；约束条件（）为运输工具容量 的约束条件，满足在每条线路上行驶的车辆都不超过其载重量；约束条件（）确保车辆最多只能到达某个 客户点和配送中心一次；约束条件（）确保某一辆车最多只能从配送中心和某收货点发出一次；约束条件 （）确保车辆行驶线路的连通性，即车辆到达了一个客户节点，也必须从该点离开；约束条件（）运输工具 行驶里程的约束条件，满足在每条线路上行驶的里程都不超过其最大行驶里程。 第 期 王晓博，等： 一类最小- 最大车辆路线问题的启发式算法研究 遗传算法中各算子确定 2 1 遗传编码 用客户号自然数进行编码时，始终以“”表示配送中心，染色体就是指一条路径，染色体长度是指连 同起点、终点在内的所有节点个数。 当染色体长度为 ln时，则 n 以表示终点。 例如一条染色体 表 示从起点（编码为），顺序经过， 这两个节点到达终点（编码为），这条染色体长度为 。 2 2 初始解的形成 设 hk为车辆 k 所运送的客户点总数，集合 Rk yik ihk来对应第 k 辆车运送的客户点，Yik表示 车辆 k 服务于节点 i，Yk表示第 k 辆车的起始点为配送中心。 步骤如下： Step 1 令运输车辆的初始剩余装载量 w k wk，k ，hk ，Rk 。 Step 2 一条路线上第 i 客户点所对应的需求量为 qi，令 k 。 Step 3 如果 qiw k，则令 w k （w k qi），wk，否则转入 。 Step 4 如果 w k qiwk，且 Di DiDk；则 Rk Rki，hk hk ，否则转入 。 Step 5 如果 k K，则 k K，否则，k k。 Step 6 k k ，转入 。 Step 7 i i ，转入 。 Step 8 重复 Step ，K 记录所用车辆总数，Rk记录一组可行路径。 2 3 适应度函数 采用最佳保留选择法，要求适应度函数值非负，通过下面变化将目标函数转化为适应度函数。 fm kkz zm （） 其中 fm为第 m 个染色体的适应度，kk 为常数，z 为初始种群中最好染色体所对应的配送费用，zm为 目前染色体所对应的配送费用。 2 4 选择算子 本文提出了最佳保留选择法，具体步骤如下： Step 1 计算种群中每个个体的适应值 fi，令当前群体中适应值最高的为 fbest。 Step 2 计算种群的总的适应值 fi。 Step 3 计算种群中每个个体在该种群中的相对适应值 pif i fi。 Step 4 随机生成一个，之间的数 ，如果 p pi p pi pi，选择个体 i 进入 到下一代种群中，重复选择 n 次，生成下一代种群的 n 个个体。 Step 5 找出当前群体中适应值最高的个体 fnow和适应值最低的个体 fnow。 Step 6 如果 fnow fbest，则 fbest fnow，否则，用最好个体 fnow替换最差个体 fnow。 2 5 交叉算子 对顺序交叉操作进行了改进，步骤如下： Step 1 在两个父代的染色体上随机各选取一段作为交叉段； Step 2 如果染色体交叉点处的两个基因全都为 ，则直接进行顺序交叉操作； Step 3 如果染色体交叉点处的基因不全都为 ，则将交叉点左移（右移），直到左右两个交叉点处的 基因都为 ，再进行顺序交叉操作。 改进后的交叉算子更加能够使子代染色体继承父代的较多基因信息，保证算法能够收敛到全局最优。 2 6 变异算子 本文的变异策略采取- 交换变异策略，若基因串中连续出现 代码的情况，则将其中一个 代码与任 意一个位置上的非零代码互换，多次执行该步骤，直到新基因串成为合法的子代个体。 - 交换变异方式有利于跳出局部最优解，可以明显地改善整个算法的效率。 运 筹 与 管 理 年第 卷 2 7 爬山操作 在遗传算法中混入爬山法，对每代构造的解进行改进，以加快算法的收敛速度。 设交换前路线为 s ，xi，xi ，xj，xj ，将 xi，xj两点的位置交换后，得到路线 s ，xj， xi ，xi，xj ，。 如果距离d（xi ，xj） d（xi，xj ） d（xi ，xi） d（xj，xj ），则交换成功，保留 交换结果，否则，取消交换。 具体步骤如下。 Step 1 初始循环次数变量 t ，当前最优解 s 倡 s，其长度为 l（s 倡）。 Step 2 在最优线路中随机选择 个顶点 xi，xj，且 i j，xi，xj不相邻。 Step 3 计算节约距离 c d（xi ，xj） d（xi，xj ） d（xi ，xi） d（xj，xj ），如果 c ，则不进 行交换，t t ，转入 ，否则实施交换，相应解为 s ，则最优解为 s 倡 s ，t ，转入 。 Step 4 若 l（s 倡）在最后 x 个循环中没有减少，本算法结束，否则转入 。 Step 5 重复 ，直到达到一定的交换次数为止。 2 8 精英种群 Step 1 对每代的种群 Pi进行 N 次的选择、交叉和变异等遗传操作，得到最优解 xi。 Step 2 保存最优解 xi到精英种群 Pbest中。 Step 3 当进行 n 代进化后，得到精英种群 Pbest。 禁忌搜索算法参数设计 在本文中，禁忌搜索算法的解的编码方式以及评价函数与遗传算法中相同。 3 1 邻域结构 禁忌搜索算法是一种基于邻域搜索技术的算法，依据问题的特点，以最长的线路为中心，本文设计双 层随机操作构造邻域结构。 内层操作采用 move 或 opt 方法，外层操作采用 exchange 或 opt 倡 方法。 采用双层轮换迭 代地进行，可实现路径间和路径内同时优化的策略。 可以扩大解的搜索范围，避免局部优化、保证解的多 样性。 同时也加快收敛速度，提高搜索效率。 3 2 禁忌表 本文构造一个（n ） （n ）阶矩阵 T 来记录目前达到禁忌解的路径对。 T ，n tt，tn tt，tn ntntn，tnn 其中 tij数值表示： 禁止交换tij 允许交换tij 。 3 3 自适应禁忌长度 禁忌长度是算法中的关键参数，其任期的长短决定解的选取，任期越短，获得优良解的可能性相应增 大，但同时增加了迂回搜索，过长又会造成计算时间的增加。 为了保证禁忌表的有效性，在整个搜索过程 中，确定 Lmin，Lmax限定变化区间为榾aN，bN，其中 a b。 则禁忌长度 L 的变化范围为下式： L L （ ）L（） 式中：L和 L分别为禁忌长度动态变化的上下界，N 为客户数目，加权系数 。 3 4 藐视准则 本文采用基于适配值的准则。 即若候选集中所有的解都为禁忌解，则解禁候选集中的最好解。 第 期 王晓博，等： 一类最小- 最大车辆路线问题的启发式算法研究 3 5 终止准则 本文采用事先限定算法的迭代次数为终止准则，该准则是指给定一个充分大的正数，使总的迭代次数 不超过这个数。 事先限定算法的迭代次数能有效控制算法的运行时间，且易于操作。 3 6 算法步骤 按照禁忌搜索法原理设计启发式算法步骤如下： Step 1 给定算法参数，初始化禁忌表 T：Ti，j ，当前迭代次数 iter ，当前连续未找到更好解的 次数 unchangeiter ，初始可行解 R now，现行最优解 Rbest，目前最优函数值 f倡 f（Rbset）。 Step 2 如果tier iter 或者unchangeiter unchangeiter，停止计算，转入 ，否则，继续。 Step 3 在初始可行解 R now的邻域，交替执行 mover 和 opt 两种操作，在此邻域中选一个未被禁 忌或被特赦，并且解的评价值是最佳的解 R next，令 Rnow R next，并更新禁忌表 T。 Step 4 在初始可行解 R now的邻域，随机执行 exchange 或 op倡t 两种操作，在此邻域中选一个未 被禁忌或被特赦解，并且解的评价值优于 R next，令 Rnow R next，并更新禁忌表 T。 Step 5 重复 ，到 R now邻域中所有变换都被禁忌且无一被赦免。 Step 6 在 R now的邻域中搜索非禁忌的最佳候选解或优于当前的最好解，如果目标函数 f（Rnow）优于 f（R best），令 Rbest R now，unchangeiter ，转入 。 Step 7 如果 f（R now）不优于 f（Rbest），unchageiter unchangeiter ，转入 。 Step 8 更新禁忌表 T，iter iter ，转入 。 Step 9 输出最优解 f 倡。 实验计算与结果分析 实例1 本文数据取自文献。 已知 个车场和 个客户节点，随机产生每个节点的坐标和需求 量，如表 所示（其中车场编号为）；给定 台相同类型的车辆，车辆的装载容量为 ，各客户点之间的距 离为欧氏距离。 表 1 实例已知条件 编号坐标需求量编号坐标需求量 倐（，）槝 倐（，） 贩（，） 倐（，） 贩（，） 倐（，） 贩（，） 倐（，） 贩（，） 倐（，） 贩（，） 倐（，） 贩（，） 倐（，） 贩（，） 倐（，） 贩（，） 倐（，） 贩（，） 枛（，） 贩（，） 4 1 启发式算法求解 MMVRP 用语言编制 问题启发式算法程序，在 ，内存 的计算机上进行计算。 遗传算法部分采用以下参数：设群体规模 N ，最大迭代次数等于，交叉算子 pc ，变异算 子 pm ，禁忌搜索算法采用以下参数：最大迭代次数为 ，禁忌长度 ， ， ，候选解的 数量 。 随机求解 次，见表 。 运 筹 与 管 理 年第 卷 表 2 启发式算法求解 MMVRP 问题计算结果 计算次序 启发式算法求解（） 总里程最长线路车辆数 殚P 殚P 殚P 殚P 殚P 殚P 殚P 殚P 殚P P 平均值P 解的标准差 3 从表 中可以看出， 次求解中，都得到了质量较高的解，总里程的均值 （），平均使用车 辆 辆。 算法的计算结果相当稳定，最差解的总里程仅比最好的解多 。 从计算效率上看， 次求 解中有 次达到了最优解， 次达到次最优解，可见效率较高。 其中，最优解的总里程 ，具体行车路线见表 和图。 表 3 启发式算法求解 MMVRP 最优结果 线路编号行车路线行驶里程 寣- - - - - 排 寣- - - - - - 珑 寣- - - - 潩 寣- - - - - 排 寣- - F 寣- - - - 潩 整个行驶里程适 平均行驶里程抖 最长线路里程抖 图 启发式算法求解 问题最优路线 4 2 遗传算法求解 MMVRP 参考文献采用遗传算法求解，主要参数取值为：群体规模 N ，最大迭代次数 K ，交叉算 子 pc ，变异算子 pm 。 得到的最优线路见表 和图。 表4 遗传算法求解 MMVRP 最优结果 线路编号行车路线行驶里程 g- - - - - 牋 g- - - - - 牋 g- - - - - 殮 g- - - - - 牋 g- - ! g- - - - x 整个行驶里程 平均行驶里程憫 最长线路里程憫 图 遗传算法求解 问题最优路线 4 3 禁忌搜索算法求解 MMVRP 参考文献采用禁忌搜索算法求解，主要参数取值：邻域列表大小为 ，候选集取 ，禁忌列表为 ，终止时间为 秒。 得到的最优线路见表 和图 。 第 期 王晓博，等： 一类最小- 最大车辆路线问题的启发式算法研究 表5 禁忌搜索算法求解 MMVRP 最优结果 线路编号行车路线行驶里程 a- - - - rw a- - - - - - - 葺w a- - w a- - - - - 殮w a- - - - rw a- - - - yw 整个行驶里程煙 平均行驶里程媼 最长线路里程媼 图 禁忌搜索算法求解 问题最优路线 4 4 三种算法求解分析 从表 可以看出，本文设计的启发式算法，无论在寻优结果，计算效率上，以及算法的稳定性上均好于 单独使用遗传算法或是禁忌搜索算法。 表 6 遗传算法、禁忌搜索算法和本算法比较 GATS本文算法 平均总里程 解的标准差儋 平均车辆数*