（计算机软件与理论专业论文）单层搜索方法解决多埠与分离递送车辆路径优化问题.pdf

单层搜索方法解决多埠与分离递送车辆路径优化问题 摘要 单层搜索方法解决 多埠与分离递送车辆路径优化问题 硕士生 指导老师 计算机软件与理论 金涛 郭嵩山教授 本文研究的是车辆路径优化问题 v r p 的两个分支 多埠车辆路径优化 问题 m d v r p 和分离递送车辆路径优化问题 s d v r p 并阐述了两种解决策略 传统的双层搜索方法和新的单层搜索方法 双层搜索方法是将问题分成两个独立 的子问题 在两个阶段分别处理 相反 我们提出的单层搜索方法将两个阶段整 合在一起 根据问题的条件 配合禁忌搜索算法 取得了很好的效果 实验数据 表明 单层搜索方法明显优于传统的双层搜索方法 并在某些数据中 接近问题 的堆优解 另外 本文提出的单层搜索方法经过改进后 可以广泛地应用在其他 v r p 类问题中 关键词 车辆路径优化问题 单层搜索方法 双层搜索方法 禁忌搜索 单层搜索方法解决多埠与分离递送车辆路径优化问题 o n e s t a g es e a r c hf o rm u l t i d e p o tv e h i d er o u 6 n gp m b i 哪a n d s p l i td d i v e r yv e h i d er d u t i n gp r o b l e m c o m p u t e rs o f t i a ma n dt h e o r y n a m e j i n i 幻 s u p e i s o f p r o f g u os 0 n g s h a n a b s t r a c t t h i sp a p e rs t u d i e st w oe x t e n s i o np i d b k mo ft h ev b h i c l cr o u t i n gp r o b l c m v r p 一m u l t i d e p o tv 曲i c l cr o u t i n gp m b l e m m d v r p 柚ds p l i td e l i v e f yv 色h i c l e r o u t i l l gp r o b l e m s d v r p 柚dp f e s e n t st w ok i 丑d so fs 0 1 v i l l gm e t h o d o l o g i e s a c l a s s i c a lt w o s t a g es e a r c ha p p r o a c ha n dan e wo n c s t a g es e a r c ha p p r o a c h t h e t 钾o s t a g ca p p r o a c hd e c o m p o s e s t h ew h o l ep r o b l e mi n t ot w o i l l d e p e d e n t s u b p r o b l c m s a n dr e s p e d i v c l ys o l v e st h e mb yt w os l a g c s o nt h ec o m r a r y t h e o n e s t a g ea p p r o a c hi st oj n t e 口a t et h et w os t a g e s a l l do b t a i n sg o o dp e d b f m a n c eb y c o n c e r t i l l gt a b us c a r c h 柚df a c t o r s e x p e r j l e n t a l r e s u l t ss h o wt h a tt h c0 n e s t a g e a p p r o a c hi ss u p e r 王0 r t ot h ec l a s s i c a lt w o s i a g ea p p r o a c h a l l d 礼g e t sm o r ec l o s et o t h eb e s ts o l u t i o n i na d d i t i o n t h c0 n e s t a g ea p p r o a c hc a nb ew j d e l ya p p l i e di l lo t h e r v r p b yi m p r 0 v i l l g k e yw o r d s v e h i c l er o u t j l l gp r o b l c m o n e s t a g es e a r c ha p p r o a c h t w o s t a g e s e a r c ha p p f o a c h t a b us e a r c h 单层搜索方法解决多埠与分离递送车辆路径优化问题 l il 问题介绍 第1 章绪论 对于物流运输来说 现代社会中的货物运输和顾客需求越来越广泛 专业的 物流公司只有提供更优质的服务和更低廉的价格 才能赢得更多的客户 因此 在确定目标位置和顾客需求的情况下 如何设计运输路线是最重要的问题之一 这可以归结成为车辆路径优化问题 v e h i c l er o u t i n gp r o b l e m 简称v r p 车辆路径优化问题 v r p 是当今物流运输和供给链管理的核心问题之 是关于车站与顾客之间的货物 乘客或者信息的分配和运输的问题 具有很强的 现实意义和应用背景 例如公共汽车路线安排 邮政投递设计 货物装卸和货物 运输等等 在高速发展的后勤学中 决策支持系统的关键组成部分是 1 对于大量的供应商和消费者 在一定的条件下 怎样设计供应一消费的 分配 并给出详细的供给分配表 2 怎样选择仓库的位置 使得整个供给链达到最优的状态 在一般的v r p 问题中 有一个车站和若干名顾客 车站发出一组车辆去服务 顾客 满足顾客的所有需求 最后返回车站 其中 每一个顾客要求被且仅被服 务一次 在达到以上条件的情况下 问题要求最少的车辆使用数量和最优的车辆 运行路线 随着顾客数量的增加 车辆运行路线的数量成指数上升 计算量将大 大提高 使用精确求解的算法基本上不可能找到问题的最优解 因此 对于大规 模的v r p 问题 人们往往要求在一个可以接受的时间内 找到问题的较优解 并 且使找到的解尽可能的优 这个时候 通常采用的是一些启发式的搜索算法来求 解 例如模拟退火算法 s i m u l a t e da n n e a l i n g 遗传算法 g e n e t i ca 1 9 0 r i t h m s 和禁忌搜索算法 t a b us e a r c h 等等 在现实生活中 情况是十分复杂的 简单的v r p 模型是很难适应实际的情况 和要求 所以我们可以将v r p 进行一些扩展 如果对时间要求比较严格 顾客的 需求有时间限制 我们可以将问题扩展成有时间窗口的车辆路径优化问题 v e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w s 简称v r p t w 多埠车辆路径 优化问题 m u l t i d e p o tv e h i c l er o u t i n gp r o b l e m 简称m d v r p 则是考虑在 单层搜索方法解决多埠与分离递送车辆路径优化问题 有多个车站的情况下 如何安排顾客归属和车辆路线 如果有些顾客的需求特别 大 一辆车不能独立服务他 则允许多辆车来共同服务他 这就是分离递送车辆 路径优化问题 s p l i td e l i v e r yv e h i c l er o u t i n gp r o b l e m 简称s d v r p 多埠车辆路径优化问题 m d v r p 是 给定多个车站和一组顾客的位置 要 求车站派出车辆去满足顾客的需求 每个车站有且仅有一辆车运行 车辆从车站 出发 服务了所有属于该车站的顾客之后 返回原来的车站 每一个顾客被限制 服务一次 m d v r p 的目标是 在顾客需求总和不超过车辆容量的条件下 所有车 辆行驶的总路程最短 分离递送车辆路径优化问题 s d v r p 给定 队相同的车辆 全部都要从中 心车站出发 服务了若干个顾客之后 回到中心车站 所有顾客的需求都必须得 到满足 现在的问题是 有些时候顾客的需求量是非常大的 单独由一辆车来服 务并满足他的要求是不现实的 因此我们允许将顾客的需求分开运送 由多辆车 来服务一名顾客 这就是分离递送车辆路径优化问题 问题要求在使用最少车辆 的情况下 所有车辆路径的总长度最短 并给出详细的行车路线 1 2 研究目的与范围 在以往的文献中 大量的论文都是关注经典的v r p 问题的 却只有很少的文 章涉及v r p 的分支问题 皿v r p 和s d v r p 并且 在所有研究m d v r p 和s d v r p 的文章中 大部分都是使用双层搜索算法 t w os t a g ea p p r o a c h 或者其他的 一些方法 因此 在我的研究中 提出了新的单层搜索算法 0 n es t a g ea p p r o a c h 来解决这两个问题 这篇论文 对于多埠车辆路径优化问题 首先建立问题的数学模型 然后详 细阐述两种解决策略 双层搜索算法和单层搜索算法 在双层搜索方法中 问 题被分成两个子问题 顾客分组和路径优化 三种已有的分组方法被介绍 平行 分组 p a r a l l e la s s i g n m e n t 简单分组 s i m p l i f i e da s s i g n m e n t 和循环分 组 c y c l i ca s s i g n m e n t 另外 我们将为两层搜索方法的路径优化阶段设计一 个启发式的搜索算法 另一方面 一个新的单层搜索方法由我第一次设计并提出 这种方法将顾客分组阶段和路径优化阶段整合到了同一阶段处理 标准试验数据 表明 我们提出的单层方法明显优于已发表的双层方法 在2 5 个标准数据中 单层搜索方法解决多埠与分离递送车辆路径优化问题 单层搜索算法取得了1 9 个最好的结果 对于分离递送车辆路径优化问题 我们也是先建立问题的数学模型 然后将 双层方法与单层方法加以比较 d r o r 和t r u d e a u 在1 9 8 9 和1 9 9 0 年发表了关于 s d v r p 的文章 9 1 0 他们的工作是两阶段的方法 在第一阶段 先用结点交 换的方法建立一个v r p 的解 不允许将顾客的需求分开运输 然后在第二阶段 再加入分离递送这个操作 争取得到更好的结果 我们的策略却不同于d r o r 和 t r u d e a u 在这篇论文中 我们设计了一种新的单层搜索算法 不是把问题分成 两个子问题 而是将所有的操作放在同一个阶段完成 首先 我们定义了一些更 新解的操作 这些操作包括了结点交换和分离递送 然后 我们将建立一些初始 解 通过解变换操作配合启发式搜索算法来改进解的质量 最后 我们在所有扩 展出来的解中 找到问题的最好解 单层搜索方法解决多埠与分离递送车辆路径优化问题 1 3 研究流程 单辆跆 雠记f 褒麓 v r p 的两十静童置悬 睾薄喜潮鞲 蠢 j 池 日越e m 卧 舻 秘 挣离速避乍辆藏畿优化 j 邈ls 讲 p 辨抛由嗨 攀灌 图卜1 研究流程图 4 囱自囱 单层搜索方法解决多埠与分离递送车辆路径优化问题 第2 章文献综述 本章对国内外关于v r p 类问题的文献进行整理 介绍与讨论 特别分析一些 关于m d v r p 和s d v r p 的文献 另外 对于v r p 类问题的求解方法进行探讨 重点 介绍一下单层搜索算法涉及的一种启发式搜索算法 禁忌搜索算法 t a b u s e a r c h 2 1m v r p 文献介绍 在现有的文献中 关于多埠车辆路径优化问题的论文并不是很多 w r e n 和 h 0 1 l i d a y 提出了一种方法来解决肋v r p 7 这种方法由两部分组成 先建立初 始的解 再用一些启发式的方法来改进结果 具体的操作是 顾客首先被临时安 排到离它最近的一个车站 然后计算车站与顾客之间的角度 接着根据计算的角 度 顾客以顺时针的方向排序 最后根据顾客的先后次序来建立路线 建立好整 个路线以后 七种启发式的改进算法被应用到初始解上 直到解不能再优化为止 g o l d e ne ta 1 为了解决m d v r p 提出了两种方法 4 第一种是节省适应算法 第 二种方法则是针对大规模数据设计的方法 以便加快程序的速度 第二种方法其 实是一种两阶段的方法 是吐 先顾客分组 后优化路径 为思路的方法 根据 顾客所在位置到最近的车站和第二近的车站的距离比来将所有顾客分成邻接点 顾客和非邻接点顾客两组 c h a oe ta 1 使用一种简单的初始化算法 再组合一 个更有效的改进算法 1 5 在他的优化方法中 尝试将一条路线中的某个顾客插 入到另外一条路线中 检查是否能够得到更优的解 这种方法比之前的研究结果 提高了不少成绩 找到了更好的结果 最近 g i o s a 以两层方法为思路 总结并 建立了许多新的启发式算法 2 在他的研究中 很多基本的思路与方法是来源 于p o t v i n 1 6 用精确求解的方法来解决m d v r p 问题 仅仅有l a p o r t e 发表了 一种方法 5 他通过图表描述的方法 将m d v r p 和l r p 转化成等约束分配问题 然后再用一种分支定界的方法来解决m d v r p 2 2s d v r p 文献介绍 s d v r p 是在1 9 8 9 年被d r o r 和t r u d e a u 提出来的 他们说明了怎么利用分离 单层搜索方法解决多埠与分离递送车辆路径优化问题 递送操作来使得车辆数量和行车距离减少 9 1 0 因为v r p 是n 卜h a r d 的 而 s d v r p 是v r p 的一个变种问题 则s d v r p 也是n p h a r d 的 d r o re ta l 描述了 问题的数学模型与公式 并提出了一些问题的约束条件 9 1 0 同时 他们也 为s d v r p 设计了一种求最优解的分支定界算法 f r i z z e l 和g i f f i n 用网格距离 的方法研究了s d v r p 并且他们在第二篇发表的文章中加入了时间窗口的约束条 件 n 1 2 他们提出的启发式方法是专门针对用网格结构来解决s d v r p 的 m u l l a s e r i le ta 1 对于带时间窗口的分离递送乡村邮递员问题提出了一种启发 式算法 这种方法和d r o r 和t r u d e a u 提出的方法是类似的 并且这种方法被应 用到美国亚利桑那州的一个农场的运输卡车的实际管理中 1 8 b e l e n g u e re ta l 研究了s d v r p 的多项式模型 从而提出了一种新的约束不等式 同时也更新了问 题的下界 2 2 2 3 车辆路径问题 v r p 的求解策略 b o d i ne ta 1 1 9 8 3 将求解v r p 的方法分成七类 3 1 先分区再排路径 c l u s t e rf i r s t r o u t es e c o n d 根据距离或者时间窗口限制等关键因素 先将顾客简单分区 再按照各个分 区中成本最低的方案来构建车辆路径 2 先排路径后分区 r o u t ef i r s t c l u s t e rs e c o n d 首先将所有顾客求出单一的最佳路径 再依据车的容量限制条件分割成若干 个单独的路程 3 节省与插入 s a v i n g s i n s e r t i o n 在不违反限制条件的情况下 根据计算的节省值的大小或者符合插入规则的 顾客予以排入路径 4 改进与交换 i m p r o v e m e n t e x c h a n g e 这种方法是针对一个已知的可行路径进行改进 最常用到的操作 就是结点 交换法和路径交换法 5 数学规划法 m a t h e m a t i c a lp r o g r a m i n gb a s e d 应用数学规划的方式来求解 6 人机交互法 i n t e r a c t i v eo p t i m i z a t i o n 单层搜索方法解决多埠与分离递送车辆路径优化问题 结合使用者的反应与过去的经验 由决策者的知识和直觉进行程序参数的设 定与修正 7 最优求解法 e x a c tp r o c e d u r e s 求出问题的最优解 比较著名的有分支定界法 b r a n c ha n db o u n d 动态 规划法 d y n a l l l i cp r o g r a 唧i n g 和切平面法 c u t t i n gp 1 a n e 等等 这种求解 策略虽然可以求得问题的最优解 但是求解的时间相对大幅增加 七种求解策略分类中 前六种都是启发式算法 只有最后一种是精确求解的 方法 因为v r p 类问题求解复杂度高 很难在多项式时间内求得问题的最优解 所以通常利用启发式的算法在可接受的时间内尽量求出问题的尽可能好的解 这 也表明了目前求解v r p 相关问题多以启发式算法为趋势 而求解v r p 的启发式算 法主要以两阶段方法 t w os t a g em e t h o d 为主 第一阶段以传统的简单启发式 算法求得初始解 第二阶段再根据问题的指定条件与限制在初始解上进行改进 以达到问题的最好解 2 4 禁忌搜索算法 t a b us e a r c h 禁忌搜索 t a b us e a r c h 或t a b o os e a r c h 简称t s 的思想最早由g 1 0 v e r 1 9 8 6 提出 1 4 它是对局部邻域搜索的一种扩展 是一种全局逐步寻优算法 是对人类智力过程的一种模拟 t s 算法通过引入一个灵活的存储结构和相应的 禁忌准则来避免迂回搜索 并通过藐视准则来赦免一些被禁忌的优良状态 进而 保证多样化的有效探索以最终实现全局优化 禁忌搜索最重要的思想是标记对应已搜索到的局部最优解的一些对象 并在 进一步的迭代搜索中尽量避开这些对象 而不是绝对禁止循环 从而保证对不 同的有效搜索途径的探索 禁忌搜索涉及到邻域 n e i g h b o r h 0 0 d 禁忌表 t a b u l i s t 禁忌长度 t a b ul e n g t h 候选解 c a n d i d a t e 和藐视准则 a s p i r a t i o n c r i t e r i o n 等概念 对于禁忌搜索 这里需要指出的是 1 首先 由于t s 是局部邻域搜索的一种扩充 因此邻域结构的设计很关键 它决定了当前解的邻域解的产生形式和数目 以及各个解之间的联系 2 其次 出于改进算法的优化时间性能的考虑 若邻域结构决定了大量的邻域 单层搜索方法解决多埠与分离递送车辆路径优化问题 解 尤其对大规模问题 则可以仅尝试部分互换的结果 而候选解也仅取 其中的少量最佳状态 3 禁忌长度是一个很重要的关键参数 它决定禁忌对象的任期 其大小直接进 而影响整个算法的搜索进程和行为 4 藐视准则的设置是算法避免遗失优良状态 激励对优良状态的局部搜索 进 而实现全局优化的关键步骤 5 对于非禁忌候选状态 算法无视它与当前状态的适配值的优劣关系 仅考虑 它们中间的最佳状态为下一决策 如此可实现对局部极小的突跳 是一种确 定性策略 6 为了使算法具有优良的优化性能或时间性能 必须设置一个合理的终止准则 来结束攘个搜索过程 7 在许多场合禁忌对象的被禁次数 f r e q u e n c y 也被用于指导搜索 以取得 更大的搜索空间 禁忌次数越高 通常可认为出现循环搜索的概率越大 从上看来 禁忌搜索的基本思想是 给定一个当前解 初始解 和一种邻域 然后在当前解的邻域中确定若干候选解 若最佳候选解对应的目标值优于 b e s t s of a r 状态 则忽视其禁忌特性 用其替代当前解和 b e s ts of a r 状态 并将相应的对象加入禁忌表 同时修改禁忌表中各对象的任期 若不存在上述候 选解 则在候选解中选择非禁忌的最佳状态为新的当前解 而无视它与当前解的 优劣 同时将相应的对象加入禁忌表 并修改禁忌表中各对象的任期 如此重复 上述迭代搜索过程 直至满足停止准则 标准的禁忌搜索算法如算法l 住演r 糕潭绻聂张棠笪津谬豳醚澄隧鳞豳嘲鞫圈黼躐麟黼蕊黼黼镞粼黧融 给定算法参数 随机产生初始解 置禁忌表为空 w h i l e 算法收敛准则不满足d ob e g i n 有当前解产生邻域解 确定候选解 i f 满足藐视准则t h e nb c g i l l 将满足藐视准则的解作为当前解 对应的对象替换最早进入禁忌表的对象 单层搜索方法解决多埠与分离递送车辆路径优化问题 我们可以明显地看到 邻域函数 禁忌对象 禁忌表和藐视准则 构成了禁 忌搜索算法的关键 其中 邻域函数沿用局部邻域搜索的思想 用于实现邻域搜 索 禁忌表和禁忌对象的设置 体现了算法避免迂回搜索的特点 藐视准则 则 是对优良状态的奖励 它是对禁忌策略的一种放松 需要指出的是 上述算法仅 是一种简单的禁忌搜索框架 对各关键环节复杂和多样化的设计则可构造出各种 禁忌搜索算法 与传统的优化算法相比 t s 算法的主要特点是 在搜索过程中可以接受劣解 因此具有较强的 爬山 能力 新解不是在当前解的邻域中随机产生 而或是由于 b e s ts of a r 的解 或是非禁忌的最佳解 因此选取优良解的概率远远大于其他解 但是 t s 也有明显的不足 就是 对初始解的依赖性较强 好的初始解可以使t s 在解空间中搜索到好的 解 而差的初始解则会大大降低t s 的收敛速度 迭代搜索过程是串行的 仅是单一状态的移动 而非并行搜索 单层搜索方法解决多埠与分离递送车辆路径优化问题 第3 章多埠车辆路径优化问题 在这一章中 我们将讨论多埠车辆路径优化问题 m d v r p 的求解方法 首 先 我将阐述传统的双层搜索方法 t w os t a g ea p p r o a c h 这种方法的主要思 路是 先顾客分组 再优化路径 a s s i g n m e n tf i r s t r 0 u t i n gs e c o n d 将问 题分成两个子问题进行处理 降低问题的复杂性 易于求解 在分组阶段 我们 会提出三种已知的分组方法 并行分组 简单分组和循环分组 另外 我们将为 路径优化阶段设计一个启发式的搜索算法 之后 我们将介绍新的单层搜索方法 o n es t a g ea p p r o a c h 这种方法不同于两阶段搜索方法 是将顾客分组和路 径优化组合到一个阶段 不再单独处理两个子问题 这样 综合了整个问题的信 息与条件 将大大增强算法的求解能力 以便求得更好的结果 3 1 问题定义 现在 我们将m d v r p 重新定义如下 1 问题有村个车站 表示为集合d 个顾客 表示为集合c 每个车站七 有一辆车k 运行 2 所有的 个顾客都必须被服务一次 而且仅允许被一辆车服务 3 每辆车七有一条运行路线瓜 从相应的车站出发 服务了若干名顾客之后 最后回到出发的车站 4 每条线路风上的顾客的需求总和不能超过车辆的承载容量g 5 两点 包括车站点和顾客点 之间的距离d 鳓是根据f 和j 具体位置计算的 欧氏距离 m d v r p 的目标就是 决定每个顾客属于哪个车站的车辆服务 并且设计每一 辆车的详细行车路线 使所有车辆运行的总距离最短 m d v r p 的数学模型如下 f m 斟珊瑚 甜丢d 基0 涉鳓 五荟 3 1 w c 姜西茹郎9 肌 d 1 0 3 1 3 2 3 3 单层搜索方法解决多埠与分离递送车辆路径优化问题 磊 一虿 0 朋 c u d 墩 d 7y 坶 1 d 趔舄 柳 烈 j cu d v 七 d 3 4 3 5 3 6 这里 决定变量脚表示问题的解 如果珊 1 就表示在线路风中 顾客 j 是顾客 的直接前驱 f c u d t d 否则 蛳 0 在上面的数学模型中 公式 3 一1 表示问题的求解目标 公式 3 2 表示确定 每个顾客被安排到一辆车上 公式 3 3 表示车辆容量限制 公式 3 4 表示流守 恒约束 公式 3 5 表示任何一个车站最多只有一条线路 公式 3 6 表示决定变 量珊的取值范围 3 2 双层搜索方法 os t a g ea p p r o a c h m d v r p 的双层搜索方法 是将整个问题分成两个子问题 顾客分组和路径 优化 在两个阶段分别处理 按照两个子问题的解决顺序 先顾客分组 后优化 路径 先求出顾客分组的结果 再根据分组结果进行路径优化阶段的操作 双 层搜索方法的主要思想由图3 1 清晰的描述出来 对于m 个车站和n 个顾客 先 根据顾客分配算法将所有的顾客分配到m 个车站管辖中 再对每一个车站组 一 个车站和其管辖的顾客 用路径优化算法寻找最优路径 其实 在第二阶段 问题变成了一个车站和k 个顾客的最优路径问题 这也就是著名的t s p 问题 换 句话来说 就是先将n 个顾客分成m 个不相交的集合 每个集合对应一个车站 再在每个集合中 寻找最优的路径 单层搜索方法解决多埠与分离递送车辆路径优化问题 图3 1m d v i i p 双层搜索方法思路图 3 2 1 顾客分组算法 顾客分组阶段的目标就是确定每个顾客归属哪个车站 由哪个车站的车辆进 行服务 由于顾客分组是问题的第一阶段 路径优化阶段的算法是依靠顾客分组 的结果进行的 所以分组结果的好坏 对路径优化阶段的结果的影响是非常大的 这也就意味着 顾客分组算法的优劣 将直接影响整个问题的求解质量 好的分 组算法 将导致比较容易求得好解 相反 对于一个效果不好的分组算法 无论 路径优化阶段的算法多么优秀 甚至是精确算法 最后都无法得到好的结果 另外 顾客分组的算法可以分成两类 紧急度分组 u r g e n c ya s s i g n m e n t 区域性分组 g r o u pa s s i g 衄e n t 紧急度分组是强调分配顾客的次序 首先 为每一个顾客设置一个紧急度 然后以紧急度的高低为次序安排顾客分组 紧急度越高的顾客 越先安排到它想 归属的车站 紧急度越低的顾客 就越不着急将它分配到对它有利的车站 因此 对于紧急度低的顾客 常常因为车辆的容量限制 无法安排它到最适合它的车站 这时 可以退而求次 安排另外一个车站的车辆去服务它 区域性分组 是着重予按照区域性来分配顾客 每个车站都将形成一块管辖 区域 根据管辖区域的范围来吸收离车站近的顾客 直到所有顾客被分配到车站 为止 随著顾客加入车站 车站的管辖区域将不断变大 这导致可能一些原来不 属于某个车站的顾客 在车站的管辖区域改变之后 变成了属于这个车站 接下来 我们将阐述三种顾客分组算法 并行分组算法 p a r a l l e l a s s i g n m e n t 简单分组算法 s i m p l i f i e da s s i g n l i l e n t 和循环分组算法 c y c l i c 单层搜索方法解决多埠与分离递送车辆路径优化问题 a s s i g n m e n t 其中前两种算法是属于紧急度分组的方法 后一种算法是属于区 域性分组的方法 3 2 1 1 并行分组算法 在并行分组算法中 顾客的紧急度是每一个车站到顾客点的距离与最近的车 站到顾客点的距离之差的总和 公式 3 7 是顾客的紧急度的计算方法 c 如一一d 括却 3 7 乃 这里 是顾客c 最近的车站 如 是顾客c 与车站矿之间的距离 如 就是顾 客c 与车站 的距离 c 就是顾客c 的紧急度 根据公式 3 7 计算完所有顾 客的紧急度之后 按照紧急度的降序 依次安排顾客到可以接收它的最近车站 图3 2 表示顾客1 的紧急度的计算 图3 2 并行分组算法 3 2 1 2 简单分组算法 在简单分组算法中 顾客的紧急度只与其最近的两个车站有关系 顾客的紧 急度 c 等于顾客到最近车站的距离与顾客到第二近的车站的距离之差 请参 见公式 3 8 c d 括h 一d 括俐 3 8 这里 是顾客c 的最近的车站 w 是顾客c 第二近的车站 同样 在计算完所 有顾客的紧急度之后 按照紧急度的降序 安排顾客到可以接收它的最近车站 1 3 单层搜索方法解决多埠与分离递送车辆路径优化问题 图3 3 表示顾客1 的紧急度的计算 图3 3 简单分组算法 3 2 1 3 循环分组算法 c q l m 4 循环分组算法是按照区域距离的远近来吸收顾客 以达到分组的目的 循环 分组算法根据每个车站组的链头的位置和未分配顾客之间的距离 每次选择一个 离任意一个车站组链头最近的顾客 安排到相应的车站组中 直到所有的顾客分 组完毕 在算法初始 设置每个车站组的链头为车站 然后在所有未分组的顾客 中 选择距离任意车站组的链头最近的顾客c 并假设离顾客c 最近的车站组链 头为v 相应的车站为w 如果属于车站w 的车辆七的容量还能满足顾客c 的需 求 就将顾客c 分配到车站w 中 并且将车站w 的链头v 替换成顾客c 重复上 面的操作 直到所有顾客被分配完毕 图3 4 是顾客1 循环分配的例子 1 4 单层搜索方法解决多埠与分离递送车辆路径优化问题 m p 甜i 3 2 2 路径优化算法 j h n 营轴f 如 破l c b n n 图3 4 循环分组算法 当所有的顾客都确定属于哪个车站之后 路径优化阶段的任务就是 对于每 一个车站组 找到最优的行车路线 使得车辆行驶的距离最短 对于每一个车站 组来说 问题演变成了单车辆路径优化问题 s v r p 这也就是著名的旅行商问 题 t r a v e ls a l e s i i l a np r o b l e m 简称t s p 因为t s p 是n p h a r d 的 如果采用 精确算法来求解的话 时间复杂度是非常高的 因此 我们采用一种禁忌搜索算 法来尽可能地求得问题的最好结果 对于每一个车站组 第二阶段的路径优化算法都将运行一次 每次算法求出 的结果 就作为这个车站组的路径记录下来 当全部的车站组处理完毕以后 输 出最后的结果 算法2 是佃v r p 的路径优化算法的描述 首先 算法将循环 m a x i t e r a t i o n l 次 从m a x i t e r a t i o n l 个不同的初始解开始搜索 然后 对于每 一个初始解r w 算法将做m a x i n t e r a t i o n 2 次改进操作 每次改进操作将应用三 种邻域函数 交换 s w a p 插入 i n s e r t 和旋转 i n v e r t 交换函数 s w a p 是交换两个顾客被服务的次序 也就是交换两个顾客在路径中的位置 插入函数 i n s e r t 是改变一个顾客被服务的顺序 也就是将某一个顾客插入到另外一个 顾客被服务之前 旋转函数 i n v e r t 是将车辆路径中的某一段路径前后颠倒过 来 这个操作将改变多个顾客的位置 单层搜索方法解决多埠与分离递送车辆路径优化问题 算法2m d v r p 豹路径优倦算法 f o r l 1 t o m a m t e r a t l o n ld ob c g j l l g e n e r a t ei n i t i a ls o l u t i o nr w b e s t r w r w m 肌t a l d i s 惝幽 f o r j 1t om a i t e r a t i o n 2d ob e g i i l d c c r e 撇e a c hp o s i t i v ec l e m c n to f t a b ua r r a yb yl c a l ln e i g h b o r h o o d s w 叩 r 蜘 c a n e 远h b o r h o o d m s c n r w c a n n c i g h b o r h o o d i n v c r t r w e n d e n d p r o c c d u r en e i g h b o r h o o d o p e r a t o r r w f o rc 1 c 1b c b n g s t od e p o tw d o b e g i n f o r c 2 c 2 b c l o n g s t od e p o t w 柚dc 2 i ss e v c r c da r e r c l d 0b c g i n t o t a l d i s t h et o t a ld 证t a n c eo fr wa f i e fo p e r a t o r c 1 c 2 i ft b t a l d i s m i n l o t a l d i st h e nb e g i n m i i l l b t a l d i s t o t a l d i s u p d a t cb 髓t r wb yo p e n t e c 1 c 2 t a b u o p c r a t o r c 1 c 2 t a b u t e n i l f c e n d e l s e i f1 o t a l d i s 顾客j 的需求t h c nb e g i n i fd e p o t n u m b c r k 0t h c nb e g i l l i e p o t r n u m b c r k 是当前线路k 中已有顾客的数量 a d d d i s d 诲k 2 i f a d d d i s m i i 认d d d j st h e nb e g i l l m i n a d d d i s a d d d i s c u s j d 印 k p o s 1 e n d e n d e l s c 如rp 1t od e p o t n 哪b e r k d ob e g i n a d d d i s d r a f r o u t i n g a k p 用简单路径优化算法估计顾萄加入到路径k 的位置p 所增加的距离 i fa d d d i s 7 一一 图4 6 取消函数 6 路径函数 r o u t e 假设顾客i 和j 处于两条不同的路径中 r o u t e c u s t o m e ri c u s t o m e rj 表示交换顾客i 与顾客j 之后 包括顾客i 和顾客j 本身 的所有顾客 同样 在交换之后 要保证两条路径满足容量限制 图4 7 表示路径函数 图4 7 路径函数 单层搜索方法解决多埠与分离递送车辆路径优化问题 4 4 3 单层搜索算法描述 算法6 是s d v r p 的单层搜索算法的描述 算法重复 x i t e r a t i o n l 次禁忌搜 索算法 利用两种初始解策略 特定初始解策略只使用一次 来建立初始解 从 不同的初始解出发进行搜索 在禁忌搜索过程中 每次将六种不同的操作应用到 当前解上 然后选择最好的邻域解 其中 除非生成的解优于当前找到的最好解 达到 b e s ts of a r 状态 否则邻域函数操作受禁忌限制 选定邻域解以后 将邻域解更新为当前解 相关操作进入禁忌表 设置禁忌长度t a b u t e n u r e 更 新操作一共进行m a x i t e r a t i o n 2 次 蕊万 需黼翁荔鬻 戮黼豳麟瓣鳓溺黼霞 露算法6s d v r p 的单层搜索算法麟麟鬻黼豳爨醚鬻鬻露灞圜麟麟鬻黼鬻麟 f o r i 1 t o m a d t c f a t i o n ld o b c g i l l 通过特定初始解或者随机初始解策略建立初始解r w b e s t r w r w 禁忌数组清零 f o r j 1 t om a d t e r a t i o n 2 d o b e g i l l 禁忌数组中的所有正数全部减1 r w l n c i g h b o r h o o d s w a p r w r w 2 n e i g i i b o r h 0 0 d i n s e n r w r w 3 n e i g h b o r h o o d i l l v e n r w r w 4 n e 塘h b o r h o o d c h 柚g e r w r w 5 n e 远h b o r h o o d c t l t r w r w 6 n e i g h b o r h o o d r o u t c r w r w b e s t r o u t e r w l r w 6 设置禁忌数组中的生成r w 的相关操作为t a b u t c n u r e i f c o s t r w c o s t b e s t r w t h 蚰b e s t r w r w c n d e n d 输出最后的结果 单层搜索方法解决多埠与分离递送车辆路径优化问题 第5 章实验结果与分析 为了衡量我们提出的新的单层搜索方法的效率 我们在这一章进行数据测试 与实验结果分析 实验的数据主要来自两个方面 标准数据和随机数据 v r p 类 问题是一类著名的问题 多年来有很多人都在研究 所以存在一些经典的标准数 据以及当前发现的最好结果 随机数据则是我们根据不同的问题随机生成的数 据 实验的目的在于 比较我们提出的单层搜索方法和传统的双层搜索方法优劣 同时也将我们计算出来的结果和现在已经发现的最好结果进行比较 5 1 多埠车辆路径优化问题 粕v r p 5 1 1 数据来源 在多埠车辆路径优化问题 m d v r p 中 我们采用了c o r d e a u 发表的3 3 个m d v r p 标准数据 1 中的2 5 个不重复数据以及2 5 个非标准数据作为测试数据 在 c o r d e a u 发表的3 3 个m d v r p 数据中 有一些数据是允许多辆车从同一个车站出 发的 因此我们对他的数据进行了等价改动 如果数据允许有k 辆车从同一个车 站出发 则我们将在同一个位置增加相应数量的车站 并只允许一个车站只有一 辆车运行 5 1 2 实验结果 表5 1 和表5 2 分别显示了三种使用不同顾客分组算法的双层搜索算法以及 单层搜索算法关于2 5 个标准数据的测试结果和运行时间 表5 3 和表5 4 则列 举了四种方法在2 5 个非标准数据测试中的结果和运行时间 表5 1 四种算法在2 5 个标准数据测试中的实验结果 节号并行分组算法赫单分组掉法循环分组算法单层搜索算法 l9 6 9 1 2 39 5 8 9 9 26 9 0 2 6 87 2 2 1 9 l 26 9 0 0 6 76 7 4 2 5 85 8 9 7 3 65 2 26 4 9 31 0 4 3 4 2 21 0 0 6 3 9 77 4 62 6 87 7 0 4 4 6 41 9 0 2 5 2 91 9 0 9 8 51 3 1 5 1 3 71 2 9 9 7 51 5 1 7 4 4 61 4 9 7 1 9 99 4 4 3 5 51 0 0 0 8 3 61 6 5 3 4 9 71 5 6 4 6 1 61 0 3 9 17 51 1 5 92 9 2 兰星堡室查茔堡堡童堡兰坌塞堡堡兰塑堕堡垡垡塑墨 71 4 8 0 6 0 21 4 7 7 4 4 6 1 2 0 6 5 0 31 1 5 3 1 2 3 8 1 2 0 4 2 4 5 41 2 3 7 7 4 0 15 8 4 3 4 7 35 4 6 0 7 7 5 911 4 3 3 0 1 31 0 7 6 0 6 5 95 4 0 5 1 6 5 5 0 6 99 1 8 1 09 6 0 6 1 0 49 3 8 2 4 8 84 8 3 9 4 5 24 6 7 7 3 7 4 1 l7 6 9 1 1 8 37 3 5 3 3 3 2 4 7 3 4 1 6 64 5 2 46 9 5 1 23 2 2 8 4 13 1 9 0 8 5 81 5 7 4 2 6 41 5 7 8 8 5 5 1 35 6 5 8 2 8 46 3 8 1 7 1 73 1 9 4 6 6 82 9 7 5 7 9 8 1 49 0 4 4 6 8 29 5 7 2 5 7 54 8 5 7 1 3 24 4 4 7 0 5 1 51 3 1 9 0 2 0 21 4 3 5 8 8 6 27 2 8 0 1 56 5 5 3 4 6 2 1 68 9 1 5 3 88 9 i 5 3 89 6 2 4 9 79 5 6 8 4 8 1 7lq 7 5 7 3 61 8 0 4 5 9 21 6 0 5 21 4 8 69 4 4 1 83 3 1 0 4 4 53 1 3 4 6 0 42 1 5 7 9 4 32 2 3 4 2 9 6 1 93 9 6 7 1 93 6 9 3 5 1 12 7 2 2 1 t 82 7 5 4 3 3 2 04 7 0 6 2 7 34 4 0 1 9 4 43 3 0 9 0 7 l3 0 3 6 0 5 8 2 15 6 7 0 5 8 l5 5 4 3 1 7 43 8 2 5 5 9 33 3 7 6 7 8 5 2 21 1 8 4 6 2 8 4 6 21 3 6 2 9 81 1 8 i 7 0 9 2 3 2 5 0 4 9 2 9 2 3 3 9 5 2 42 2 5 3 9 7 92 0 5 1 1 l 2 43 6 0 1 13 4 7 67 4 82 7 3 1 2 9 52 7 1 9 8 3 8 2 55 1 4 86 7 34 9 6 42 0 64 2 3 4 6 6 84 0 6 9 9 4 4 表5 2 凹种算法住2 j 个标准数据测试中的运行叫阳 序号并行分组算法简单分组算法循环分组算法单层搜索算法 10 0 1 9 6 5 80 0 1 9 4 7 80 0 2 0 9 3 0o o 1 2 6 5 8 20 0 2 5 51 7o 0 2 4 8 5 50 o 2 3 4 8 4o 0 1 4 2 0 30 0 3 8 9 8 60 0 3 7 3 4 40 0 3 6 4 7 20 0 1 97 4 q 40 0 4 9 6 0 lo 0 4 9 3 7 1o 0 4 8 5 7 00 0 2 43 5 50 0 4 4 9 4o 0 4 5 6 6 50 0 4 8 3 1 00 o 2 9 9 3 4 60 0 4 6 8 0 70 0 4 9 2 0l0 0 5 1 2 1 3