（管理科学与工程专业论文）车辆路径优化的应用研究.pdf

摘要 随着市场经济的深入发展，作为“第三利润源泉”的物流在我国的生产、分 配、流通和消费的各个领域起着越来越重要的作用。配送是物流系统中很重要的 一个环节，在物流的各项成本中，配送成本占了相当高的比例。配送线路合理与 否对配送速度、成本、效益影响很大，特别是多用户配送线路的确定更为复杂。 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，简记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 ) 的研究更加具有实际 意义。 本文研究的主题，就在于提出模拟退火蚁群算法，使求解问题的速度更快、 结果更好。主要研究工作如下： ( 1 ) 从配送中心的角度，通过对v r p t w 模型的复杂性分析，构建合理的 v r p t w 数学模型。 ( 2 ) 通过对s a ( 模拟退火蚁群算法) 和a s ( 蚁群算法) 分析，概括总结出两 种算法的优劣，提出模拟退火蚁群算法，为快速、有效地求解v r p t w 开辟了蹊 径，这是本文的核心部分。 ( 3 ) 通过对模拟退火蚁群算法的分析，结合实例利用w i t n e s s 仿真软件对算 法进行测试，实验结果表明该算法能在一定范围内自动搜索所需的最优车辆数。 本文提出用模拟退火蚁群算法求解汽车物流中的v r p t w ，提高了物流配送 的科学化效率，对物流配送的发展具有一定的理论意义与应用价值。 关键字：模拟退火算法，蚁群算法，时问窗，路径优化，w i t n e s s a b s t r a c t w i t ht h ed e v e l o p m e n to ft h em a r k e te c o n o m y ，l o g i s t i c s ( t h i r dp r o f i ts o u r c e ) p l a y s a n i n c r e a s i n g l yi m p o r t a n t r o l ei n p r o d u c t i o n ，d i s t r i b u t i o n ，c i r c u l a t i o n a n d c o n s u m p t i o n d i s t r i b u t i o ns y s t e m i sa ni m p o r t a n tp a r to ft h el o g i s t i c s i t sc o s t s a c c o u n tf o rav e r yh i g hp e r c e n t a g ei nl o g i s t i c s v e h i c l er o u t i n gp r o b l e mh a db e c o m e f o c u so fm a n ys c h o l a r st os t u d y i nt h ed e v e l o p e dc o m m e r c i a ls o c i e t y , t i m ew i n d o w b e c o m e sm o r ea n d m o r ei m p o r t a n ti ng o o d sd i s t r i b u t i o ns ot h a td e l i v e r yd a yf o r m e r l y h a dt u r n e dt od e l i v e r yh o u rn o w o b v i o u s l y , l o w e r i n gd i s t r i b u t i o nc o s t ，t r a n s p o r t i n g g o o d st i m e l y , i m p r o v i n gt h es e r v i c eq u a l i t y , o p t i m i z i n gv e h i c l er o u t i n gp r o b l e mw i t h t i m ew i n d o w si se x i g e n tt oe n t e r p r i s e s t h e r e f o r et h er e s e a r c ho fv r p t wi sm o r e p r a c t i c a ls i g n i f i c a n c e t h et h e m eo ft h i sp a p e rw a st h a tab e t t e ri m p r o v e ds aw i t hs h o r ta n dg o o dr e s u l t w a sp r o p o s e dt os o l v et h ev r p t w ：t h em a i n l yr e s e a r c h e dc o n t e n tw a sa sf o l l o w s ： ( 1 ) t h r o u g ht h ec o m p l e x i t ya n a l y s i s ，t h em o d e lw a sb u i l ti nt h es t a n d p o i n to ft h e d i s t r i b u t i o nc e n t e r ( 2 ) t h r o u g ht h ea n a l y s i so fc u r r e n ts a ( s i m u l a t e da n n e a l i n ga l g o r i t h m ) s y s t e ma n d a s ( a n tc o l o n ys y s t e m ) ，t h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h ea l g o r i t h mw e r e s u m m a r i z e d t h es a a ss y s t e mw a sp r e s e n t e dt os o l v ev r p t we f f i c i e n t l ya n d e f f e c t i v e l y ( 3 ) t h r o u g ht h ea n a l y s i so ft h ep r i n c i p l eo fs a - a s ，a ne x a m p l ew a s t e s t e du s i n g w i t n e s ss i m u l a t i o ns o f t w a r e t h er e s u l ti n d i c a t e dt h a ts aw a se f f i c i e n ti ns o l v i n g 矿r p t 彤 t h i st h e s i sp r e s e n t sas i m f i l a t e da n n e a l i n ga l g o r i t h m f o rl o g i s t i c si nt h ea u t o m o t i v e v r p tw i ti si m p r o v e dt h a t t h i sa l g o r i t h mi sm o r ee f f i c i e n c yf o rd i s t r i b u t i o nh a s s o m et h e o r e t i c a ls i g n i f i c a n c ea n dv a l u e k e y w a r d s ：s i m u l a t e da n n e a l i n ga l g o r i t h m ，a n tc o l o n ys y s t e m ，t i m ew i n d o w s ， r o u t i n go p t i m i z a t i o n ，w i t n e s s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得云鋈王些太堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示了谢意。 学位论文作者签名：吕蕉钇 签字日期：加海月衫日 学位论文版权使用授权书 。本学位论文作者完全了解丞姿王些太堂有关保留、使用学位论文的规定。 特授权丞洼王些太堂可以将学位论文的全部或部分内容编入有关数据库进行 检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：吕垄妃 导师签名： 气邢 签字日期： 伽舻年7 月形e t 签字日期： dg 年月1 o e 1 学位论文的主要创新点 一、针对v r p 的目标及其约束条件建立了数学模型； 二、针对模拟退火算法在求解到一定范围时做大量的冗余迭代和 求精确解的效率低的缺点以及蚁群算法计算初期信息素匮乏，求解速 度慢的缺点，提出了模拟退火蚁群算法：首先采用模拟退火算法来构 建问题的一个初始解：然后应用蚁群算法对得到的初始解进行精确求 解。并对算法进行了改进： 1 对解的优化策略进行了改进。 2 提出了蚁群算法的接收准则，扩大了解的搜索范围，使解容 易跳出冗余迭代，提高了寻求精确解的效率。 第一章绪论 1 1 研究背景及意义 1 1 1 研究背景 第一章绪论 物流( l o g i s t i c s ) 是2 0 世纪中期发展起来的一门新兴学科，也是现代较有影响 的学科之一。它是指为了实现顾客满意，连接供给主体和需求主体，克服空间和 时间阻碍的有效、快速的商品、服务流动经济活动过程，以现代信息技术为基础， 整合运输、包装、装卸、搬运、仓储、流通加工、配送、回收加工及物流信息处 理等各种功能而形成的综合性物流活动模式。物流作为一种经济活动被誉为“未 开发的黑色大陆”，企业的“第三利润源泉”。以信息技术为基础的物流服务在全 球迅速崛起，其本身所具有的开放性、全球性、低成本和高效率的特点，能够更 好地满足现代商业的要求，推动社会经济的进步。世界各国都已经意识到物流的 重要性，尤其是在工业发达国家，物流管理与物流技术己经得到了广泛的应用与 发展，己成为适合于市场经济发展的基础产业之一。 物流配送是货物从物流结点送达收货人的过程，其流程如图1 1 所示。配送 是物流系统中很重要的一个环节，是国际物流业创造的最佳的一种服务形式，也 是我国物流业今后相当一个时期发展的重点。随着生产劳动生产率的提高，人们 逐渐认识到了配送在流通和物流过程中的增值潜力，加之生产经营模式变革产生 的工业配送需求、商业连锁产生的商业配送需求、消费方式变化产生的大众需求 和电子商务产生的实物配送需求都促使了配送活动的快速发展。企业都将配送作 为发展的战略手段，将其看作是企业活动的主要部分。 幽l l 配送流稃图 第一章绪论 物流配送车辆路径问题是现代生产企业和物流管理中最重要的一个环节，据 统计，各国运输成本占国民生产总值的1 0 1 5 左右【1 1 。这就意昧着运输系统的 效率提高一点就可以节约很多成本。只要我们能够将现有运输成本降低，我们的 国民经济总体水平就能出现一次新的飞跃，一次真正的飞跃。 但是，目前我国现阶段物流服务的实施有着不可回避的问题：物流技术、基 础设施和装备条件还不够完善；物流效率低下：物流业发展比发达国家落后；“物 流瓶颈严重制约我国产业的发展等等，这些问题迫切需要加以重视和研究。在 这种严峻的形势下，大力推进现代物流产业发展，降低运输成本，增强物流环节 的服务质量，是提高物流效率的迫切需要。有效的车辆调度，不仅可以提高物流 工作效率，而且能够为生产工序之间的物料传送得到运输上的保障，从而实现物 流管理科学化。 1 1 2 课题研究意义 随着我国经济的高速增长，当前物流活动呈现出前所未有的频繁，2 0 0 7 年 全国货物周转量达到7 7 6 0 7 2 9 亿吨公里，物流业已成为我国困民经济新的增长 点。但是目前我国物流管理仍然比较落后，物流行业普遍面临着专业化程度低、 高耗低效等问题。另外，随着新世纪的到来，电子商务的蓬勃发展与中国加入 w t o ，市场竞争进一步加剧，企业要保有和争得市场，不仅要在产品的质量、 功能上下功夫，更重要的还是要在优质服务上下功夫。 据统计我国车辆的运输成本是欧洲或美国的3 倍，全国运输汽车的空驶率约 3 7 ，其中汽车物流企业车辆空驶率达3 9 ，存在着回程空驶、资源浪费、运输 成本高等问题。可见，减少运输费用是有效减少物流成本的重要方面。对于物流 中心和第三方物流企业的货物配送，运输车辆调度和线路优化足工作的重点，正 确合理的调度可以有效减少车辆的空驶率，实现合理路径运输，从而有效减少运 输成本，节约运输时间，提高经济效益。 车辆路径问题( v e h i c l er o u t i n gp r o b l e mv r p ) 是物流配送过程中的关键问题 之一，该问题作为网络优化的基本问题之一而一直受到学者们的关注。v r p 一 般指对一系列的客户点，组织适当的行车路线，使车辆有序地通过它们，在满足 一定的约束条件( 如货物需求量、车辆容量限制和时间窗限制等) 下，达到一定的 目标( 如运距最短、费用最少、车辆数尽量少和客户满意度最佳等) 。v r p 的研究 作为发展敏捷后勤的一个重要组成部分，是实现物流现代化的基础和前提条件， 不仅有助于改变我国物流管理落后的现状，也有助于解决城市交通拥挤、能源短 缺、大气污染等困扰人们的社会问题，实现效率、资源、环境和价值观念各方面 的内在统一，促进物流业的进步和社会经济的可持续发展。 第一章绪论 有时i a j 窗的车辆路径问题( 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 ) 是在v r p 的基础之上增加了时间窗口的限制，即要求车辆必须在时间 窗以内到达客户点。随着物流配送行业竞争同益激烈和客户对物流配送时效性要 求越来越高的今天，对v r p 的研究，尤其是对v r p t w 的研究，不仅可以帮助 运输企业提高服务水平，为顾客提供快捷、准时、安全、舒适的服务，解决发展 电子商务中速递这一“瓶颈”约束，而且有助于企业节约运输成本，改善车辆利 用效率，缩短生产周期，加速资金周转，实现资源的合理配置，汲取“第三利润 源泉”的财富，因此更加具有实际意义。 本课题立足于实际情况，建立了针对v r p t w 的较为实用的数学模型。以启 发式算法为基础，深入研究了模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 禾i 蚁群算法 ( a n ts y s t e m ，a s ) ，提出了模拟退火蚁群算法，其合理性通过v r p t w 实例得到 较好的验证，为此类问题的解决提供了一种有效途径，也将丰富模拟退火算法在 v r p t w 中的应用成果。本课题建立的模型对于其他一些实际问题具有较好的通 用性，通过对本课题约束条件的弱化或强化，就可以应用于其他类似问题。因此， 本课题的研究具有广泛的应用范围和一定的实用价值。 1 2 研究综述 1 2 1 v r p t w 的国内外研究进展 国外关于车辆路径问题的研究最初由d a n t z i g 和r a m s e r 于1 9 5 9 年首先提出 的，由于其应用的广泛性和经济上的重大价值，很快引起运筹学、应用数学、组 合数学、网络分析、图论、计算机应用等学科的专家与运输计划制定者和管理者 的极大重视，并取得了很大进展。由于带时间窗的车辆路径问题在竞争激烈的当 今社会具有十分现实的意义，近几十年来已经出现了许多关于带时间窗的车辆路 径问题的研究文献。 1 9 8 7 年s o l o m o n 最早将用于求解简单v r p 的路径构造启发式算法扩展应用 于v r p t w 的解中，他的研究结果表明这些启发式方法求解v r p t w 问题的复杂 度为0 ( n ) ，n 为有待访问的客户的数目，即可在多项式时间内得到问题的近似最 优解，说明了启发式方法求解v r p t w 的可行性和有效性。t a n 等人将多种新提 出的遗传算法的技术，比如新的交叉算子，适应性变异概率等结合到一起，并将 爬山算法融合到该遗传算法中，数值实验验证了该算法可以用较少的时间得到 v r p t w 较好的解【2 】。h o m b e r g e r 和g e h r i n g 设计了一个两阶段的求解v r p t w 的 混合算法，该混合算法有效的集成了进化算法和禁忌搜索算法的优点，实现了并 行计算并克服了重复搜索的问题【3 】。b r a y s y 等人提出的多起始点局部搜索算法 第一章绪论 ( m u l t i s t a r tl o c a ls e a r c ha l g o r i t h m ) 来改进v r p t w 的初始解，应用该算法对成百个 v r p t w 的b e n c h m a r k 问题进行计算的结果表明了它的高效性【4 l 。c h i a n g 和 r u s s e l l 结合模拟退火算法和禁忌搜索算法的禁忌表求解带有硬时间窗的v r p 问 题，并以s o l o m o n 的5 6 个算例验证，其计算结果优于单一的s a 求解方法【5 j 。 我国对车辆路径问题的研究在9 0 年代以后才逐渐兴起，比国外相对落后。 随着客户物质需求的多样性和不规则性以及经济全球化趋势的发展，运输规划的 重要性同益显著，近年来我国理论界逐渐丌始关注车辆路径问题的解决方法，已 经取得了较为显著的成果。 1 9 9 8 年，李大卫等人对适用于t s p 的最近距离搜索启发式算法进行修正， 构造出评价函数，并据此提出一个求解v r p t w 的启发式算法【6 】。1 9 9 9 年，李军、 郭耀煌等采用了网络启发式算法，对带有时间窗要求的集货送货一体化满载车辆 路径规划进行了研究，并提出了考虑到每项任务，由其集货点至送货点为重车行 驶，故将一项任务由两个点看成是一个点，称为重载点，从而简化了模型的规模 7 1 。2 0 0 0 年，谢秉磊等人将货运量约束和时间窗约束转化为目标约束，设计了基 于自然数编码的可同时处理软、硬时间窗约束的遗传算法，实验分析获得了较好 的结果哆j 。2 0 0 2 年，张丽萍等人通过引入新颖交叉算子，构造了一种改进遗传算 法。该算法摆脱了对群体多样性的要求，不存在传统遗传算法常见的“早熟收敛” 问题，可用于解决v r p t w i 9 1 。2 0 0 4 年，支f j d , 兰等人为了克服原有大规模邻域搜 索算法不能有效求解时间窗较宽v r p 的缺陷，介绍了v r p t w 的通用数学模型。 通过分析各主要变量之间的关系，构造了一种简单、快速的确定性初始算法，并 通过引入“短路径优先策略”，构造了改进的大规模邻域搜索算法，该策略也可 嵌入到求解时问窗比较窄的v r p 中，达到加速搜索的目的【m 】；陈火根、丁红钢 等对带时问约束的物流配送中心车辆调度问题，采用混合整数规划方法进行建 模，分析了该模型用精确算法进行求解的复杂性，提出了遗传算法与启发式算法 相结合的求解方法，将该问题分解为车辆分配和单一车辆路线安排两个相互关联 的子问题进行求解】：霍佳震、张磊通过对模型的分解和过滤，结合实际情况， 以修币的c l a r k e w r i g h t 节约启发式算法为基础进行插入式排序，以解决带有时 间窗e 1 的集货和送货一体化路径规划问题i l2 】；张炯、郎茂祥在对有时间窗配送 车辆调度问题进行描述的基础上，建立了该问题的基于直观描述的数学模型，通 过设计一种新的解的表示方法构造了求解该问题的禁忌搜索算法，并以2 1 个节 点的运输网络为例进行了实验计算【l 引。 1 2 2 s a 的国内外研究进展 在实际应用中，由于s a 在解决局部极小问题上的突出表现迅速得到大家的 4 第一章绪论 青睐，也引起了众多学者广泛的研究兴趣，使模拟退火算法也得到了突飞猛进的 发展。国内引进模拟退火算法的历史较短，而且大多数都是关于模拟退火在工程 等方面的实际应用以及考察算法的实际效果和效率，较少对其理论性有深入的研 究。模拟退火算法有其在寻找全局极小方面的优越性，但也存在着收敛速度较慢 的缺点【1 4 】。模拟退火模型一经提出，便引起学术界的广泛关注，许多学者对其 产生了浓厚的兴趣，并成功地应用到了许多领域，如在解决典型的n p h a r d 组合 优化问题t s p 问题，并在此基础上提出了许多改进的算法，如有记忆的模拟 退火算法，带返回搜索的模拟退火算法，快速模拟退火算法，适应性的模拟退火 算法，并行模拟退火算法，单纯性模拟退火算法，遗传一模拟退火算法等。通过 这些算法，一些比较复杂的大规模组合优化问题得到了很好的解决。 不能忽略的是，每种算法的提出都与其应用范围紧密结合，这样才使得改进 的算法在其应用领域具有较好的适用性。由于模拟退火算法( s a ) 从理论上可以达 到全局极小值，所以对该算法的研究才更有实际意义，众多学者j 下在努力钻研将 其一般化，使其具有普遍适用性。 近年来o s m a n 、a l e xv a n 、t e o d o r o v i c 、蔡延光、刘浩等人都曾利用模拟退 火算法求解车辆路径问题，并耿得了一些研究成果。胡大伟，朱志强等人在车辆 路经问题的模拟退火算法中采用路径间调整和路径内优化方法，结合模拟退火算 法策略对该问题进行求解。重点阐述了v r p 模拟退火算法的设计思路，详细分析 和编制了求解程序框图，并实现了计算机求解【l5 。杨宇栋，郎茂祥，胡思继在有 时间窗车辆路经问题的模型及其改进模拟退火算法研究中通过对有时间窗车辆 路径问题的描述，建立了该问题的基于直观描述的数学模型，还根据有时间窗车 辆路径问题的特点构造了求解该问题的改进模拟退火算法l l 6 j 1 2 3 a s 的国内外研究进展 蚁群算法作为种新型的模拟进化算法，是由意大利学者m d o r i g o ，v m a n i e z z o ，a c o l o r i n i 等，在2 0 世纪9 0 年代初首先提出的，并称之为蚁群系统 ( a n ts y s t e m ，a s ) 。与其它优化算法相比，蚁群算法具有正反馈、分布式计算以及 贪婪的启发式搜索等主要特点，正反馈过程使得该算法能够发现较好解；分布式 计算使得该算法易于并行实现，更快得到较好解；与启发式算法相结合，使得该 算法易于发现较好解，这些特点为更好解决复杂的组合优化问题提供了可能。蚁 群系统模型一经提出，便引起学术界的广泛关注，许多学者对其产生了浓厚的兴 趣，并成功地应用到了许多领域，如在解决典型的n p h a r d 组合优化问题叫s p 问题时，和遗传算法等其它进化算法相比，蚁群算法获得了更好的实验结果。受 其影响，蚁群系统模型逐渐引起了更多学者的注意，并在此基础上提出了许多改 第一幸绪论 进的算法，通过这些算法，一些比较复杂的大规模组合优化问题得到了很好的解 决。 国内学者自l9 9 8 年开始对蚁群算法进行研究，且发展较快，现在已成为 相关领域的热门研究方向，新模型、新方法、新应用层出不穷。崔雪丽、马良、 范炳全等提出车辆路径问题( v r p ) 的妈蚁搜索算法，提出了一种可快速求解v r p 的蚂蚁搜索算法。通过定义基本人工蚂蚁的状态转移概率，并结合局部搜索策略 ( 2 - o p t 交换策略) ，用迭代次数控制算法的运行时间，而使该方法具有良好的实用 意义和可操作性。经过一系列数据测试和验证，获得了较好的结果【1 7 】。刘云忠、 宣慧玉等提出蚂蚁算法在车辆路径问题中的应用研究在大规模( 10 0 个节点以 上) ，该算法表现出明显的优势，其结果明显好于其他启发式算法【l 引。 1 3 论文的主要工作 论文的主要思路是构建以配送成本最小、所用车辆数目最小、顾客满意度最 大为目标的新模型，通过深入学习和了解了模拟退火算法( s a ) 和蚁群算法( a s ) 的核心和精髓的基础上，同时参阅了大量的固内外文献，提出了模拟退火蚁群算 法，为带有时间窗的车辆路径问题的求解提供一个切实可行的算子设计，求得一 个较优的可行解，并说明其有效性。 本论文的主要研究工作如下： ( 1 ) 以第三方物流配送中心的角度，通过对v r p t w 模型的复杂性分析，构 建合理的v r p t w 数学模型。 ( 2 ) 首先通过收集国内外相关资料，阅读了相关文献的基础上，理解了模拟 退火算法的思想及算法；蚁群算法的主要思想和理论进行了系统的学习。最 后，针对一些基础性的模型和算法进行较为认真的研究和学习。 ( 3 ) 在全面了解模拟退火算法和认真细致地学习了蚁群算法的基础上，本文 提出了将二者结合起来，取二者之长的一种新的模拟退火蚁群算法，并将其应用 于求解典型的n p 问题t s p 问题，同时进行了仿真实验，通过对o l i v e r 3 0 和a t t 4 8 的数掘进行测试，该算法具有良好的性能。 ( 4 ) 通过对新算法的分析，结合实例利用w i t n e s s 仿真软件对算法进行测 试，实验结果表明模拟退火蚁群算法能在一定范围内自动搜索所需的最优车辆 数。最后对本文的研究工作做了总结，并指出了进一步的研究方向。 第一二章v r p t w 问题描述 第二章v r p t w 问题描述 2 1 车辆路径问题及其分类 2 1 1 车辆路径问题 在配送中心的同常配送活动中，存在着这样的问题：需要向几个客户运送货 物，每个用户对货物有一定需求，运送货物的车辆在配送中心配装发车后，把货 物送到各用户处，如何确定费用最小的车辆行驶路线，或者路径最短的车辆行驶 路线? 零售商收集若干生产商生产的产品并运到配送中心，车辆从配送中心出发， 到各个厂家去装货，装满后运到配送中心，在满足厂家发货要求的情况下，按什 么路线行驶，可使总费用最小? 这两个问题的实质是相同的，如果货物量大，车 辆为完成任务需满载运行，则按最短路行驶即可。若货物量较少，用一辆车完成 任务时，车辆不能满载，车辆容量利用率低则可以考虑用一辆车完成多项任务。 这种将各分散用户组织起来、联合送货的方式就是配送运输的基本特点。在配送 运输方式下，通过将多个用户联合在一条路线上，并为车辆选择绕行次序可以 降低成本提高效率这就是典型的v r p 问题。 车辆路径问题问题一般可以这样描述：从某物流配送中心用多辆配送车辆 向多个客户送货。每个客户的位置和货物需求量一定，每辆车的载重量一定，其 一次配送的最大行驶距离一定。要求合理安排车辆配送路线，使目标函数得到最 优。 研究v r p 一般要求满足以下几个i j 提条件： ( 1 )被配送的是可混装的物资： ( 2 )各个用户的所在地已知； ( 3 ) 从配送中心到各个用户间的运输距离己知； ( 4 ) 配送中心有足够的资源以供配送，并且拥有足够的运输能力： ( 5 ) 所有的配送车辆以配送中心为起点并最终回到配送中心： ( 6 ) 每条配送路径上各需求点的需求量之和不超过车辆的载重量： ( 7 ) 每个需求点的需求由且仅由一辆车一次送货满足。 图2 1 描述了v r p 问题。( 其中矩形表示场站，小圆圈表示需要服务的顾 客，箭头线表示车辆行驶路径) 。 第_ 二章v r p t w 问题描述 2 1 2 v r p 问题的模型 图2 1 车辆路径问题 k ：k 辆车，k = l ，2 ，k ； q ，：客户i 的需求量； “：从点i 到j 的成本； q ：车辆的装载能力，q ：4 ； x 眦：决策变量，表示第k 辆车是否从i 出发后开向j ，如果是，x 瞰值为1 ，否 则，其值为0 ： 圪：决策变量，表示销售点i 的任务是否由车辆k 完成，如果是，坛值为1 ， 否则，其值为o ； 目标函数： 月nk m i n z = c 揣 ( 2 - 1 ) i = 0j = 0k = 0 约束条件： eq ，y 膻q k = i ，2 ，k( 2 2 ) k yv=k ( 2 3 ) 厶_ k = l jo k 荟虬2 1 i = 1 ，2 , - - - - - n ( 2 4 1 第一二章v r p t w 问题描述 x 。女= l k = i ，2 ，一k i = l 委2 y 肚j = l 2 n - k - l 2 ，k z ，：。x , j 2 y 聩i = l ，2 ，n ：k = l ，2 ，k 以上各式简要说明如下： 式( 2 1 ) 为目标函数，表示成本最低： ( 2 - 5 ) ( 2 - 6 ) 式( 2 2 ) 车辆k 装载的货物总量不大于车辆的限定容量； 式( 2 3 ) 每辆车都从物流公司出发： 式( 2 4 ) 每个销售点的需求量只由一辆车配送且所有客户都得到服务； 式( 2 5 ) 车辆对销售点服务完毕后，返回物流公司； 式( 2 6 ) ，式( 2 7 ) 表示到达某个物流公司的车辆惟一性约束； 车辆路径问题的流程图如下图所示： ( 2 - 7 ) 2 1 3 v r p 问题的分类 幽2 2 v r p 流程图 各种复杂的v r p 问题是在经典v r p 加入各种约束条件后而形成的。如： 9 第二市v r p t w 问题描述 根据约束条件分类，有带时间窗的车辆路径问题( v r ew i t ht i m ew i n d o w s ， 简记为v r p t w ) ；加入需求约束形成的需求随机的车辆路径问题( s t o c h a s t i c v r p ， 简记为s v r p ) ；加入距离约束的距离约束的车辆路径问题( v r pw i t hd i s t a n c e ，简 记为d v r p ) ； 根据己知信息的特征分类，有确定性v r p 和不确定性v r p 。其中不确定性 v r p 可进一步分为随机v r p ( s v r p ) 和模糊v r p ( f v r p ) ； 根据配送中心的特征分类，有单车场问题( s v r p ) 和多车场问题( m d v r p ) ； 车辆开放问题( 车辆可不返回车场) 和车辆封闭问题( 车辆必须返回车场) ； 根据其它条件的不同，还有可切分的车辆路径问题( s p l i td e l i v e r yv r p ，简 记为s d v r p ) 、先配送再收集车辆路径问题( v r pw i t hb a c k h a u l s ，简记为v r p b ) 、 配送收集车辆路径问题( v r pw i t hp i c k u pa n dd e l i v e r i n g ，简记为v r p p d ) 等。 2 2v r p t w 问题 2 2 1v r p t w 的概念及基本描述 时间窗是一个时间段 e ，厶】，是由客户i 要求的最早服务时间e ，和最晚 服务时间厶确定的一个服务时间区间。在v r p 问题的基础上给每个顾客加上服 务所允许的时间窗( t i m ew i n d o w s ) 约束，v r p 就扩展成了v r p t w 。 所谓带有时间窗的车辆路径问题是指假设有n 个等待服务的客户，一个出 发点，k 辆有一定载重量的汽车，己知：每个客户的位置坐标、货物需求量、出 发点的位置坐标、每辆汽车的最大载重量，允许服务的时间窗口( 时间窗口是指 配送车辆或顾客希望服务或被服务的时间范围。一方面，汽车可以在时刻e ，之 - f i ；j 至f j 达该客户所在地，但它必须等待直到e i 才可以为该客户服务，并且不允许 迟于到达。另一方面，汽车也必须在出发点开门后才可以离开，在关门前返回 出发点) 。要求设计每辆汽车的行驶路线满足约束条件： ( 1 ) 每个客户必须而且只能被服务一次； ( 2 ) 每条路线必须起始于出发点，为最后一个客户服务完后返回出发点； ( 3 ) 每条路线的总负荷不能超过该辆汽车的最大载重量； ( 4 ) 每个客户必须在它的时间窗口内被服务，如果汽车提前到了客户所在 地，也必须等待，直到允许为该客户服务为止l l 圳。 由于j i t 理论和实践的成熟，消费者需求趋于多样化，对送货时间的要求日 趋严格，除了因缺货造成的机会成本的损失外，由于配送不及时也会造成货物价 值的大大降低。在配送运输上，时间窗口显得越来越重要。 根据决策者在对客户满意和成本二者权衡时偏好的不同，时间窗问题还可分 第一二章v r p t w 问题描述 为硬时间窗( v e h i c l er o u t i n gw i t hh a r dt i m ew i n d o w s ，简称v r p h t w ) ，软时间 窗( v e h i c l er o u t i n gw i t hs o f tt i m ew i n d o w s ，简称v r p s t w ) 和混合型时间窗三种 情况( 如图3 2 所示) 。 硬时间窗要求配送车必须在特定时间区段( e j ，l i ) 内将货品送达客户手 中，不论是迟到或早到都完全不予接受； 软时间窗要求配送车辆如果无法将货物在特定的时间段内送到客户手中，则 必须按照违反时间的长短施以一定的罚金或其它惩罚法则。 混合型时间窗指客户往往软、硬两种时| 白j 窗混合使用。配送车辆若在( a ，e ，) 或( 厶，b ) 时段内才送达，则施以一定的罚金或其它惩罚法则；若在( 一o 。，a ，) 或 ( 6 ，0 0 ) 到达，客户不接受货物。 在实际规划中，决策者往往需要利用有限的资源优先服务重要客户，很难做 到使所有的客户都满意。因此决策者就要在客户满意度和成本最小化之间找到一 个理想的切入点，这在模型中通过惩罚函数来体现。b a l a k r i s h n a n 对软时间窗的 车辆路径问题进行了研究，结果表明允许在某些客户处发生延误现象可以大量节 约总成本。本文只讨论软时问窗的问题，因为实际中这种情况最多见。 p ( t ) m 2 2 2 问题的界定 图2 - 2 时间窗示意图 对本文研究的问题做如下界定： ( 1 ) 从一个配送中心向多个客户送货，不考虑道路的实际交通情况，且认为 所有客户之间、客户与车场之间均存在可连通的道路。 ( 2 ) f i e 送中心和客户的位置一定，配送中心能够满足所有客户的需求，且配 送中心车辆充足。 ( 3 ) 各个客户需求的货物均可以相互混装，即可以装在同一配送车辆内：每个 客户的货物需求量不超过配送车辆的最大载重量：每个客户的送货要求必须满 第一：章v r p t w 问题描述 足，且仅能由一台车辆完成，不允许分批配送。 ( 4 ) 每台配送车辆的最大载重量一定，不允许超载：配送时每台车辆都从配送 中心出发，向一些客户提供配送服务后，最终返回原配送中心。 ( 5 ) 各个客户的时间窗限制为软时间窗。对于客户要求将需求( 或供应) 货物送 到( 或取走) 的时间，有时间限制，但可以不遵守，不遵守时要对配送企业给予相 应的惩罚。客户在订货时，经常会规定货物到达的时间，如何安排配送，以达到 客户对时间的要求，这个是最重要的目标。 ( 6 ) 假设车辆始终保持同一速度行驶。 ( 7 ) 所有客户的需求形式均相同，即全部为送货问题。 ( 8 ) 要求合理安排车辆路线，在满足所有客户需求且不违反限制的情况下， 使得车辆总运行成本尽可能少，车辆总运行成本用路线长度来代表。 第三章组合优化j 启发式算法 第三章组合优化与启发式算法 3 1 基本模拟退火算法 模拟退火算法是8 0 年代发展起来的一种用于求解大规模优化问题的随机搜 索算法。它以优化问题求解过程与物理系统退火过程之间的相似性为基础，利用 m e t r o p o l i s 准则并适当地控制温度的下降过程实现模拟退火，从而达到求解全局 优化问题的目的。目前，该类优化方法被认为与其它方法一样具有竞争力，现已 在工程中得到较广泛应用，如旅行商问题、生产调度、机器学习、图像处理等领 域。 3 1 1 物理退火过程 退火是一种物理过程，一种金属物体在加热至一定的温度后，它的所有分子 在其状态空间中自由运动。随着温度的下降，这些分子逐渐停留在不同的状态。 在温度最低时，分子重新以一定的机构排列。统计力学的研究表明，在同一个温 度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。当温度 相当高时，每个状态的概率基本相同，都接近平均值。当温度趋向0 时，分子停 留在最低能量状念的概率趋向于l 。 简单而言，物理退火过程由以下几部分组成： ( 1 ) 加温过程。当温度足够高时，固体将熔解为液体，从而消除系统原先可 能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。熔解过程与系 统的熵增过程相联系，系统能量也随温度的升高而增大。该过程的目的是增强粒 子的热运动，使其偏离平衡位置。 ( 2 ) 等温过程。物理学的知识告诉我们，对于与周围环境交换热量而温度不 变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达 到最小时，系统达到平衡态。 ( 3 ) 冷却过程。目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下降， 从而得到低能的晶体结构。在这个过程中，系统的熵值不断减小，系统的能量也 随温度的降低趋于最小值。但是冷却时急剧降低温度，会引起淬火效应，即固体 只能冷凝为非均匀的亚稳态，系统能量也不会达到最小值。 模拟退火算法是一种基于上述退火原理建立的随机搜索算法。它的一个主要 特性就是能以一定的概率接收成本值高的状态。即算法不但往好的方向走，而且 第三市组合优化j 启发式算泫 偶而也往差的方向走。这使得算法即使落入局部最优值的陷阱中，经过足够长的 时问后也可跳出来，收敛到全局最优解。 1 9 8 2 年，k i r k p a t r i c k 等首先发现了固体退热过程与组合优化问题之间存在 的相似性，将m e t r o p o l i s 等对固体在恒定温度下达到热平衡过程的模拟与组合优 化问题相结合，提出了一种对m e t r o p o l i s 算法进行迭代的组合优化算法一一模拟 退火算法，该算法基于物理中固体物质的退火过程与一般组合优化问题间的相似 性。对于组合优化问题来说，解空间中的每一点都代表一个解，不同的解有着不 同的成本函数值。所谓优化，就是在解空间中寻找成本函数值最小( 或最大) 的解。 若把函数看成能量函数，把控制参数视为温度，解空间作为状态空间，那么模拟 退火算法( s a ) 寻找基态的过程就是求目标函数极小值的优化过程，因此，基于 m e t r o p o l i s 接受准则的最优化过程与物理退火过程存在一定的相似性。表3 1 为 组合优化问题同物理退火类比表。 表3 一l 组合优化问题同物理退火类比表 组合优化物理退火组合优化物理退火 设定初温熔解过程 费用函数能量 控制参数的 m e t r o p o l i s 下降 冷却等温过程 抽样过程 能量最低状 解粒子状态最优解 态 3 1 2 m e t r o p o i is 准则 固体在恒定温度下达到热平衡的过程可以用m o n t e c a r l o 方法进行模拟，但 由于必须采用大量采样才能得到比较精确得结果，因此计算量很大。鉴于物理系 统倾向于能量较低的状态，而热运动又妨碍它准确落入最低状态的物理现象，采 样时着重提取那些有重要贡献的状态则可以较快地得到较好的结果。 因此1 9 5 3 年m e t r o p o l i s 等提出了重要的采样法，即以概率接受新状态。设 l ( s ，f ) 为优化中的一个实例，s 表示解空间，f ：s r 表示解空间到实数域的映 射，t 为s a 过程中温度的控制参数。假定l ( s ，d 存在着邻域以及相应解的产生机 制，f ( i ) ，绚) 分别为对应于解“j 的目标函数值。由解i 过渡到解j 的接受概率 用以下的m e t r o p o l i s 准则确定： 第三章组合优化0 启发j 弋算法 i l ，f ( i ) ( ) 以- p ( f 州卜i e x p ( 竿p 卜八力 。 3 1 3 s a 算法的结构 模拟退火算法的基本思想是：从选定的初始解开始，在借助于控制参数递 减时产生的一系列m a p k o b 链中，利用一个新解产生装置和接受准则，重复进行 包括“产生新解计算目标函数差判断是否接受新解接受抛弃新解” 这四个步骤的过程，不断对当前解进行迭代，当t 值趋于0 时，整个系统趋于平 衡状态，从而使目标函数达到最优。基本的s a 算法详细步骤如下： s t e p l ：任意选取一个初始状态i ( 初始解f o ) ，令迭代次数k = 1 ；并设定一个 较高的起始温度t ； s t e p 2 ：求目标函数f ( x i ) 的函数值； s t e p 3 ：如果该函数值在该温度下满足内循环停止条件转s t e p 4 ，否则在当前 状态i 的一个邻域内随即选一个新状态x j ，若蜕= f ( x j ) - f ( x , ) 0 ，将x ，取代薯 成为新状态，若蜕0 ，以e x p ( 一馘) r a n d o m ( o ，1 ) 的概率接受新状态x ，。若不 接受新状念，重复s t e p 3 ； s t e p 4 ：按照退火时间表降低温度t ，迭代次数k = k + l ，若满足外终止条件。 输出结果，否则回到s t e p 2 ； 第三章组合优化j 启发式算法 图3 1 基本模拟退火算法流程图 3 1 4 模拟退火