（管理科学与工程专业论文）模拟退火算法在带时间窗的车辆调度问题中应用.pdf

模拟退火算法在带时间窗的车辆调度问题中应用 摘要 现代物流作为一种先进的组织方式和管理技术，被广泛认为是企业在降低 物资消耗，提高劳动生产率之外的重要利润来源，在国民经济和社会发展中发 挥着重要作用。在物流配送系统中，通过科学合理的方法确定运输路线和时间， 不仅可以降低运作成本，还可以加快物质配送速度、提高运营效益和保证客户 服务水平。 物流配送中的车辆调度问题( v e h i c l er o u t i n gp r o b l e m ，简称v r p ) 是一个 n p h a r d 问题，该问题由d a n t z i g 和r a m s e r 予1 9 5 9 年首次提出。由于很多问题都 可以抽象为这一问题，很快便引起运筹学、应用数学、组合数学、图论与网络 分析、物流科学、计算机应用等学科的专家以及运输计划制定者的极大重视， 并一直是运筹学与组合优化领域的前沿与热点问题。 在已有研究的基础上，本文研究了带时间窗的车辆调度问题( v e h i c l e r 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 t w 所具有的特点以及以往对该问题研究，在此基础上把模拟退火算法用到 该问题的求解中。首先采用s w e e p 算法构建初始路径，然后通过模拟退火算法 求得满意解，在解的改进过程中采用2 i n t e r c h a n g e 技术构建邻域。最后通过实验 测试说明该算法能够求解一定规模的v r p t w 问题，并对温度下降速度对算法的 影响作了分析。 关键词：v r p t w 模拟退火算法启发式算法 t h ea p p l i c a t i o n r o u t i n g o fs i m u l a t e da n n e a l i n gi nv e h i c l e p r o b l e mw i t ht i m ew i n d o w a b s t r a c t m o d e r nl o g i s t i c s ，a na d v a n c e d t e c h n o l o g yf o rc o m p a n i e s ，w h i c hp l a y sa s i g n i f i c a n tr o l ei nt h ed e v e l o p m e n to fe c o n o m ya n ds o c i e t y ，i sr e g a r d e da sa n i m p o r t a n tw a yo fl o w e r i n gc o s ta n de n h a n c i n gp r o d u c t i v i t y i nt h ed i s t r i b u t i o n s y s t e m ，as c i e n t i f i ca n dr a t i o n a lv e h i c l er o u t i n gm e t h o dw i l ln o to n l yr e d u c et h ec o s t ，b u t a l s oi n c r e a s et h ec i r c u l a t i o ns p e e d ，i m p r o v et h eo p e r a t i o ne f f i c i e n c ya n dr a i s et h es e r v i c e l e v e l i nt h ed i s t r i b u t i o ns y s t e m ，t h ev e h i c l er o u t i n gp r o b l e mi san p h a r dp r o b l e m ， w h i c hw a sf i r s tr a i s eb yd a n t z i ga n dr a m s e ri n19 5 9 a sm a n yp r o b l e m sc a nb e a t t r i b u t e dt ot h i sp r o b l e ma b s t r a c t l y ，m a n ye x p e r t sa n ds c i e n t i s t si nt h ea r e ao f o p e r a t i o nr e s e a r c h ，a p p l i c a t i o nm a t h e m a t i c s ，c o m b i n a t i o nm a t h e m a t i c s ，l o g i s t i c s s c i e n c e ，c o m p u t es c i e n c ea n dt r a n s p o r t a t i o np l a n n e ra t t a c hg r e a ti m p o r t a n c ea b o u t i t ，a n di ta l w a y sb et h eh o t t e s tp r o b l e mi nt h ea r e ao fo p e r a t i o nr e s e a r c ha n d c o m b i n a t i o no p t i m i z a t i o ni nr e c e n ty e a r s b a s e do nt h ew o r ka l r e a d ya c h i e v e d ，t h ev e h i c l er o u t i n gp r o b l e mw i t ht i m e w i n d o w s ( v r p t w ) i ss t u d i e di nt h i sp a p er v r p t wc o n s i s t so fd e s i g n i n gv e h i c l e r o u t e sa n ds c h e d u l e sf o ru s e r sw h oh a v es o m eq u a n t i t yo fg o o dt od e l i v e ra n da s e r v i c et i m ew i n d o w , t h eo b je c ti st os e r v ea l lu s e r sa n dh a v eal o w e s tc o s t s t h e p r o p e r t yo ft h i sp r o b l e mi sa n a l y z e da n dt h es i m u l a t e da n n e a l i n gi su s e dt os o l v e t h i sp r o b l e m f i r s t l y , t h ei n i t i a lf e a s i b l es o l u t i o ni sc o n s t r u c t e db yt h e s w e e p m e t h o da n ds e c o n d l y ，t h es i m u l a t e da n n e a l i n ga n d2 一i n t e r c h a n g et e c h n i c a la r e u s e dt oi m p r o v et h es o l u t i o n t h es i m u l a t i o no ft h i sa l g o r i t h mi s p r o c e s s e d ，a n di t c a ns o l v et h ev r p t wf o ran u m b e ro fc u s t o m e r s i nt h ee n d ，t h ea n a l y s i so ft h e p a r a m e t e ri sg i v e n k e y w o r d s ：v r p t w ；s i m u l a t e da n n e a l i n g ；h e u r i s t i c i i 图表清单 图1 1 一般供应链示意图1 图1 2 一般物流配送图2 图1 3 车辆调度问题一般示意图3 图3 1 ( o ，1 ) 交换19 图3 2 ( 0 ，2 ) 交换19 图3 3 ( 1 ，1 ) 交换。2 0 图3 4 ( 1 ，2 ) 变换2 0 图3 5( 2 ，2 ) 变换2 0 图3 - 6 2 一o p t 变换2 1 图3 7 2 - o p t + 变换2 1 图3 8o r - o p t 变换21 图3 - 9 禁忌搜索算法流程图2 2 图3 1 0 遗传算法流程图2 2 图3 1 l 模拟退火算法流程图2 3 图3 1 2 蚁群算法流程图2 4 图4 1节点f 和，时间关系图2 5 表4 - 1 测试算例2 8 表4 2 两阶段s a 算法测试结果2 9 图4 2 路径分配图2 9 表4 3 不同降温速度下运行结果( 1 ) 3 0 表4 3 不同降温速度下运行结果( 2 ) 3 0 表4 4 不同规模的测试结果3 1 表4 - 5 算法比较结果3l v i 独创性声明 本人声明所呈交的学位论文怒本人在导师指导下进行的研究工作及取得的研究成果。据我所 也不包含为获得金蟹王逃叁堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 韵麓志对本研究所傲的任何贡献均已在论文中作了明确的说明并表示谢意。 一貅产笔孥蹶幽月尹 学位论文版权使用授权书 本学位论文馋者完全了解垒壁兰墼塞堂有关保留、使思学位论文的觏定，有权保壁并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权佥妲王业厶 茎一可羧将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 各户獬 签字叠期：嘲年l 瑚彳嚣 学彼论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 厶滤已醛 签字嗽谢年嘲尸墨 电话： 邮编： 致谢 本文是在我的导师储诚斌教授的悉心指导下顺利完成。在整个研究生阶段， 无论是在课程学习还是在做课题研究中，始终得到了储老师的指导和帮助。储 老师广搏的学识、严谨与实事求是的治学态度、高深的学术造诣、敏锐的学术 洞察力、积极开拓创新与忘我的工作精神给我留下了深刻的印象，使我终身受 益，在此向储老师表示深深的感谢与崇高的敬意。 非常感谢左春荣老师和任明仑老师，他们在思想、学习、工作和生活等各 个方面都给予了悉心的指导和无微不至的关怀，使我在各个方谣有了很大的提 高，这将体现在我今后的工作和学习中。 感谢企业建模与优化研究所的老师在学位论文的撰写、修改和定稿过程中 提出的宝贵意见。同时感谢管理学院所有的老师在求学中给予的帮助。 感谢企业建模与优化研究所的所有同学，正是在和你们的交流中，我才得 以不断的提高，祝你们学业有成。 衷心地感谢我的父母、亲人和朋友，正是在他们无尽的关怀和支持下我才 得以成长，他们在背磊默默的支撑着我，鼓励我前进。 最后鞭一次对所有帮助过我的人表示感谢! i i i 作者：屈先锋 2 0 0 8 年l0 月2 0 日 第一章引言 1 1 研究背景 物流( l o g i s t i c s ) 是指在适当的时候以正确的数量把商品送到用户手中。物流 是一个不断发展的概念，它伴随之人类生产活动的存在褥存在，只要有人类存 在的地方就有物流活动。根据2 0 0 1 年颁布的中国国家标准物流术语对物流 的定义，物流就是商品从供应地向接受地的实体流动过程，根据实际需要将运 输、存储、装卸、搬运、包装、流通加工、配送、信息处理等基本功能实现有 机结合瑟1 。 在供应链篱理中，物流是连接生产与消费之间的一条桥梁，把处于不同时 空隔离的供给与需求联系在一起，物流是供应链管理的一个重要组成部分，如 图1 1 所示。 终端客户 图1 - 1一般供应链示意图 现代物流被誉为是企业的“第三幂| 润源 ，是企业在降低能源消耗和提供劳 动生产率以外的主要利润来源。企业要想在激烈的市场竞争中占据优势，控制 生产经营成本是其主要的手段之，因此有效的降低物流成本也成了企业在市 场角逐中一个重要的环节。因为据专家分析，在现代企业中物流成本约占企业 生产经营成本的2 0 3 0 。另外，一个有效的物流配送系统也能帮助企业降低 库存，提高准时交货率，从另一方面提高企业的市场竞争力。 现代物流系统中对原材料( 危险品、建筑材料等) 或者是商品( 消费品、 易腐烂商品等) 配送的时效性不管对消费者还是对企业都是菲常重要的一环。 有效的配送管理分为三个层次：战略层、战术层和操作层。其中物流配送中工 厂以及仓库的选址属于战略层，设施的配备、车辆的速度以及最大载运能力等 为战术层，对车辆的路线的选择与调度则属于操作层中非常重要的部分。 在物流系统中，物流配送是直接与消费者相连的一环，物流配送的本质是 运输，但又不同于一般的运输，它是根据顾客的要求，对物品进行拣选、加工、 包装、拆分、组配等一系列的操作后，按时把物晶运送到顾客指定酩位置，如 图1 2 所示。物流配送可以创造时空价值，完善运输系统，消除交叉运输，提 高终端物流的经济效益。 收集点配送点 i 工、包装、拆分和组配； 图1 - 2 一般物流配送图 物流配送中的运输成本在整个物流成本中占据很大的比重，据中国仓储揍 会的一项调查结果显示，在被调查的1 4 6 个生产企业中，原料物流中运输费用 占总物流费用的5 8 ，成品物流中运输费用簧占7 3 ，商业物流中占5 2 。可 见，控制运输成本在物流配送中是何等的重要。配送车辆调度的合理与否对配 送速度、成本、效益影响都很大，直接影响整个物流系统的运行。为车辆安排 好的路径以及进行合理的调度降低运输成本是降低物流成本的主要手段。 采用科学合理的方法对配送车辆进行调度，是物流配送中非常重要的一项 活动。对车辆调度优化理论与方法进彳亍系统研究是物流集约化发展，建立现代 调度指挥系统、发展智能交通运输系统和开展电子商务的基础。这种调度优化 理论的应用并不仅限于车辆运输领域，像水运、空运、通讯以及工业管理等都 可以应用这种理论。已经取得很好应用的有生产计划与调度、电力配送调度、 码头对货船的调度等。随着科学技术的进步以及调度优化理论的不断发展，将 来越来越多的行业将会用到这种理论与方法，进而促进这种优化理论向更高的 方离发展。 1 2 车辆调度闯题的提出 车辆调度问题( v e h i c l er o u t i n gp r o b l e m s ，v r p ) 最早是由d a n t z i g 和 r a m s e r 2 1 在管理科学杂志上发表的一篇论文中提出的，当时命名为车辆分派问 题( t r u c kd i s p a t c h i n gp r o b l e m ) 。所描述的是从一个油库为分布在不同位置的 加油站供给汽油，每个加油站之间的距离已知，每个加油站都指定一定的产品 2 与数量，问题是安排服务的货车以满足所有的服务并且使总的行驶距离最小。 作者又强加一些约束：每个加油站只能有一辆车来服务，并且在运输的过程 总的运输量不能超过车辆的载重。最早出现v r p ( v e h i c l er o u t i n gp r o b l e m ) 字 样的并且给出问题主要变量的是在t o t h 和v i g o 的著作i 3 1 。 车辆调度闯题是指存在一个车辆调度中心以及分布在不同位置的有待服务 的客户( 收集的服务或者是卸货的服务) ，安排可行的车辆路径使得所有的客户 得到服务，并曼使总的运输距离( 或时间) 最小化，其中，车辆都是由调度中 心出发并且最终返回到调度中心，每一个客户由辆车访问并且只能被访问一 次，在整个运输过程中车上总的运载量不能超过车辆的最大载重量。车辆调度 问题的一般示意图如图1 3 所示。其中方框表示调度中心或者称站点( d e p o t ) ， 各圆点表示客户所在的位置。 一般说的车辆调度问题指的是经典的车辆调度问题，即在车辆路径的安排 中只有容量约束，也称为有容量约束的车辆调度问题( c a p a c i t a t e dv e h i c l e r o u t i n gp r o b l e m ，c 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 ) ，v r p t w 问题是在一 般v r p 的基础上增加一个时间窗因的约束，郾每一个客户毖须在指定的时闻窗 口内被访问。带时间窗的车辆路径问题分为两类：一种是硬时间窗，是指客户 只能在指定的时间窗髓内被服务，车辆提前到达将会有等待时间，不允许延迟； 另一种是软时间窗，是指在一定程度上允许车辆延迟到达，但必须受到一定的 惩罚，一般为经济上的惩罚。 图i - 3 车辆调度问题一般示意图 自从车辆调度问题提出以后，很多学者从不同的角度，依据不同的理论思 想构建了车辆调度问题的算法，既有精确算法又有启发式算法。由于车辆调度 问题已被证明为n p h a r d 闻题，精确算法只能用来解决规模较小的闯题，当阕 题的规模较大的时候只能构建启发式算法来求解，当然启发式算法有时只能求 得阀题的满意解，恧无法得到闻题的最优解。 从文献 4 】的报道来看，根据最近3 0 年的研究，求解车辆调度问题的精确 算法在很多方面都是继承旅行商闯题( t r a v e l i n gs a l e sm a np r o b l e m ，t s p ) 的求 解算法，如基于弧的算法、基于点弧的算法、生成树法以及最短路径法等。 v r p 精确算法是沿着两条主线来发展的：一条是采用普通的分解算法来解决有 特殊约束的问题；另一条路线也是最近许多学者更加关注的，即分析和构建新 的算法。 求解车辆路径问题的启发式算法分为经典的启发式算法和现代启发式算法 ( 又称亚启发式算法) 。癌发式算法一般包括两个阶段：构建初始解和对解的改 进。经典启发式算法在进行解的改进时是按照一种降序的方式来搜索的，在每 一次迭代中搜索较优的解直到无法找到更优的解，经典扇发式算容易陷入局部 最优从而不能搜索全局更优解。现代的启发式算法相对两言，一般具有两方面 的特性：集聚性( 或者集中性，i n t e n s i f i c a t i o n ) 和分散性( 或者多样性， d i v e r s i f i c a t i o n s ) 。集聚性可以提高收算法的收敛速度，在较短的时闻内得到局 部最优解；分散性是指可以在解的改进程序中临时接受一些更坏的方案，跳出 局部最优进行全局搜索。 现在求解车辆调度问题的算法虽然很多，有些算法在求解过程中也表现出 较好的性笼，能够得到闻题想要的结果，但是较多的算法注重的往往是算法求 解精度或者是能够解决问题的规模。然而现实问题往往存在一定的复杂性与不 确定性因素，特别是在随机车辆调度问题中对实时性的要求比较强，因而应该 构建一种快速的算法能够用来解决实时问题。随着现代通信技术的发展，以及 车载信息系统等新技术应用，使得获得实时信息的能力加强，这就要求算法能 够做出快速的反应，在这一研究领域还会有很好的应用前景。 王。3 本文的研究内容 本文主要研究的是车辆调度问题中带时间窗的车辆调度问题，构建带时间 窗的车辆调度阏题的两阶段模拟退火算法，第一阶段采篇s w e e p 算构建初始路 径，第二阶段通过模拟退火算法进行改进，并通过实验来验证算法的有效性。 具体的结构安排如下： 第一章，引言。这一章主要介绍问题的研究背景，阐述了物流的概念以及 在供应链管理中的重要性，对物流配送在整个物流系统中的地位做了简要的说 明，最后介绍了车辆调度闻题的提出，并对求解车辆调度问题的算法分类及性 质进行阐述。 第二章，车辆调度闯题模型与算法。这一章首先余缨了车辆调度闯题是旅 行商问题的一般模式，然后对车辆调度问题的国内外研究现状进行介绍，阐述 了车辆调度闯题的一般模型及其约束条件，最后介绍了车辆调度闯题的分类以 及常用的求解算法。 第三章，带时间窗的车辆调度问题的数学模型。这一章主要针对带时间窗 4 的车辆调度问题的模型与算法进行分析，并对问题所具有的约束条件进行描述。 第四章，求解v r p t w 问题的两阶段模拟退火算法。本章是在前面对带时 间窗的车辆调度问题分析的基础上，设计了求解v r p t w 的两阶段模拟退火算 法，首先采用s w e e p 算法构建初始路径，在解的改进过程中采用基于点交换 的允一i n t e r c h a n g e 技术构建邻域，然后通过模拟退火算法求出闻题满意解。通过 实验证明算法在求解不同规模的问题时都能得到较好的满意解，并对温度下降 欧速度对算法麓影响进行了分析。最后，通过与禁忌搜索算法求得的测试实侧 的结果进行比较，得出本文构造的算法在求解这一问题时具有优越性。 第五章，结论与展望。本章主要对所做的工作进彳亍总结，并对以后的研究工作进 行展望。 第二章车辆调度问题基本模型与算法 2 1v r p 与t s p 的联系 旅行商问题( t r a v e l i n gs a l e sm a np r o b l e m ，t s p ) 可以描述为：一个商人要 到n 个城市推销商品，希望选择一条最佳的路线，经过所有的城市一次且只经 过一次，最后回到起点，目标是构建一条路径使得所走的路程最短。旅行商问 题已被证明是n p h a r d 组合优纯闯题。 用图论的形式描述旅行商为：在无向连通图g 一( v ，e ) 中，w 是点( 城市) 的集 合，e 是边的集合，e = ( f ，歹) | f ，j 乃。点f 句的欧氏距离为z ，设磊= a f t 。 目标是找到一个长度最小的闭合回路，使得访问每个点次且仅一次，这条闭 合回路也称作哈密顿回路。 车辆调度问题是旅行商问题能一般形式，车辆调度问题是指对一系列处于 特定位置和有着一定需求量的客户点，安排定数量的车辆，从调度中心出发， 选择最优的行驶路径，车辆有序酶访闯每个客户点并且只能访问一次，最终回 到调度中心，在满足一定约束条件( 如容量约束、最大行驶时间等) 的情况下， 使得货物尽快的到达客户点并且总的运输费用最低。 用图论的形式描述v r p 问题为：在无向图g = ( v ，a ) ，其中v = ，h ，心) ， v 代表顶点集合，a = ( t ，v j ) v t ，v ，v ，i 乒歹 ，表示连接两节点之间线段的集合， 顶点v 。表示调度中心，其他顶点则表示有待服务的客户的节点。在集合a 上可 以定义非负的距离矩阵或者成本矩阵d = 矗， ，此处以代表从顶点( 客户) f 到顶点( 客户) ，的距离或成本。 与旅行商问题相比，车辆调度问题有一定的车辆数，可以看作是多个旅行 商，另外每一个客户都指定定的需求量，每一辆车都有最大的载重，旅行商 也有能够背负商品的最大量。因此车辆调度问题可以放松约束的看作是多个旅 行商的旅行商闯题。宙予t s p 为n p h a r d 闻题，因瑟车辆调度闻题也是n p h a r d 问题。 2 2v r p 的研究现状 2 2 1 国外对v r p 的研究 自从车辆调度闻题由d a n t z i g 和r a m s e r 1 】于1 9 5 9 年首次提出以后，由于很 多问题都可以抽象为这一问题，因而引起整个学术界的关注。成为运筹学和组 合优化领域研究的热点，黧际上许多专家和学者从不同的研究角度以及基于不 同的算法思想对车辆调度问题作了深入地研究。 d e s r o c h e r s 5 】等于1 9 9 2 年以集合划分的方式攒述了v r p t w 闻题，并利用 动态规划对问题进行求解，利用分枝定界法给出问题下界；g e n d r e a u 6 1 等利用 禁忌搜索算法对v r p 问题进行了求解；a w j k o l e n 7 1 等采用空闻松弛的分枝定 6 界方法求解带有时间窗的车辆路径问题，目标是总的运输距离最小化，并给出 了求解上下界的方法。b a r d 等【8 j 利用g r a s p 方法搜索可行解，并用分枝切平 面法求得最优解；h e r m i n i ai 【9j 等采用目标规划方法求解带有软时间窗约束的车 辆路径问题，通过列举跟随优化的方法，即先计算初始可行路径再选择好的 路径。l a p o r t e 1 0 j 等对旅行购买者问题( t p p ) 进行了研究，将配送成本分成旅 行成本和购买费用两部分，采用两索引法构造模型，未考虑车辆启动成本的影 响，利用分枝切平面法( b & c ) 在2 0 0 个用户的规模上获得了最优解；n a b i l a 等【i l j 采用最短路径法求解单车多路径带时间窗的车辆路径问题，算法分为两 步：首先生成多条可行路径，然后根据车辆在一个工作日内的时间来选择一些 路径并进行排序。主要用来求解一些易腐烂商品短距离的运送路径问题。t v a n w o e n s e l 等1 1 2 1 使用排队论的思想来求解车辆调度问题中动态行驶时间的问题，是根据 时间段计算每条弧上的行驶时间，以应付潜在的交通堵塞。t a g m o u t i 等【l3 】采用列生 成法来求解根据时间确定服务成本的弧调度问题，首先把弧调度问题转化为节点路径 安排问题，然后由列生成法求解，主要问题是选择服务成本小的路径。c z h e n g 1 4 】等 基于进化算法和3 d 效果图求解无人驾驶飞机的路径规划问题。b r h y s y 等【1 5 】构造一 种快速的进化算法求解带有时间窗的车辆路径问题，在算法构造过程中把局部 搜索、跳出串、模拟退火以及进化算法结合起来，以提高算法的求解速度和质 量。通过实例证明算法的求解速度不亚于当时的其他算法。f l i s b e r g 等【l6 】采用 线性规划和禁忌搜索算法相结合来求解伐木场的收集与配送问题，由于每个需 求点的货物需要从不同的收集点进行收集，因此是一种特殊的收集配送问题。 第一阶段采用线性规划算法构建运输网点，每个网点描述为一个或者是多个收 集点和一个卸货点的满载运输，使所用的车辆最小化；第二阶段采用禁忌搜索 算法对各网点进行路径安排与优化，通过构建较大的邻域来求得满意解。 g e o r g e m 【l7 j 等基于分组和排序的思想使用混合遗传算法求解大规模的多约束 条件的车辆路径问题，遗传算法中的选择与替代机制运用到算法的求解中，直 到混合遗传算法能有效的解决此类问题，最后引进高执行率运算以保证在合理 的时间内得到近似解。h o n g 等【l8 】采用基于并行插入分组和连续线性目标规划 优化相结合的启发式算法求解双目标的带时间窗的车辆调度问题。l a u 等1 1 9 】采 用禁忌搜索算法求解有车辆数限制的带时间窗的车辆调度问题，给定一个可计 算的车辆数的上界，并允许接受惩罚的时间窗口松弛，客户是按照目标函数的 优化等级来插入的。b e n t 等【2 0 】构建两阶段的混合局部搜索算法求解带时间窗的 车辆调度问题，首先用模拟退火算法最小化车辆数，然后通过重置较大数量客 户的大邻域搜索( l n s ) 方法最小化运输成本。 2 2 2 国内对v r p 的研究 我国对v r p 的研究开始于上世纪九十年代，一开始仅限于少数高校的极少 7 数研究者从事这方面的研究。进入新世纪以来，随着我经济的快速增长，以及 物流业的迅速发展，车辆调度问题的研究得到了越来越多的重视，也取得了一 些较为满意的成果。 李军f 2 1 】等构建以分派算法为基础的启发式算法求解有时间窗的车辆调度 问题，麓够求解任务较多的情况。郭耀煌等1 2 2 1 根据贪心算法原理设计一种交互 式优化算法求解单车场满载问题。袁建等1 2 3 j 采用种改进的平均退火方法求解 随机需求v r p 问题，该方法将模拟退火算法与h o p f i e l d 神经网络解法稆结合， 加速了神经网络的收敛并具有与模拟退火算法相当的精度。谢秉磊等 2 4 1 采用模 拟退火算法求解配送收集旅行商阀题，采用放松必须完成所有配送需求后才服 务收集需求的约束，在扩展m e t r o p o l i s 接受准则的基础上，运用模拟退火算法 求得该问题较好的结果。李宁等【2 5 】采用粒子群算法求解带时间窗的车辆路径问 题；张丽艳等【2 6 】将粒子群优化算法与模拟退火算法楣结合，提出一种求解带时 间窗车辆调度问题的混合粒子群算，通过实验表明为一种有效的算法。张建勇 等f 2 7 1 构建一种由前蜃双向可推的推一碰过程确定最佳服务时间的插入式算法求 解具有模糊预约时间的动态v r p 问题，通过对顾客服务时间的前推或后推，确 定使顾客综合满意度最大的方案，同时考虑其它的约束条件，使由于新客户的 加入而引起的综合成本增加值得以最小，最后通过算例说明算法的有效性。张 媛媛等1 2 8 】分析多周鬻车队缀合及配送，建立起物流企业动态车队组合优化模型 采用d a n t z i g w o l f 分解方法对模型进行分解，结合动态规划和分枝定界算法设 计符合该模型的精确算法，并通过数值实验对不同的需求分布，得到了动态车 队组合的优化解。刘志硕等 2 9 】构建一种基于两阶段策略的自适应混合蚁群算法 求解具有硬时间窗的v r p 问题，第一阶段采用蚁群算法进行局部遍历构造一个 回路，第二阶段对前一阶段的回路采用近似解优化策略组成可行解，其中引入 基于时间窗的紧迫性因子和匹配度因子，并与节约算法和爬山算法有机结合， 实验表明自适应混合蚁群算法性能优良，能够有效地求解有硬时间窗的v r p 闯 题。张涛等【3o 】在求解带有能力约束的v r p 问题中，在不固定车辆数的情况下 把聚类和排序有视的结合起来，并用遗传算法和3 - o p t 算法相结合的混合算法 对问题进行求解，通过实验得到了问题的满意解。李全亮1 3 l l 构造一种基于分组 分配的亲和力计算的免疫算法求解带时间窗的车辆调度问题。霍佳震等 3 2 1 采用 修正的c w 节约启发式算法和最邻近算法为基础进行插入式排序来求解配送 收集旅行商问题，放松必须在完成所有配送需求后才服务收集需求这一约束条 件，并结合实际情况对模型的分析和处理，实验涯明算法能够很好的求解这类 问题。王雪峰【3 3 】等对定位一车辆路径问题进行了研究，利用禁忌搜索和蚁群算 法的两阶段c f r s 混合算法进行了求解； 8 2 2 3 车辆调度问题的分类 根据车辆调度问题中约束条件的不同可以把车辆调度问题细分为以下几种 类型的车辆调度问题： 1 经典v r p 经典v r p 即基本的v r p 问题，又称之为带容量约束的v r p ( c a p a c i t a t e d v e h i c l er o u t i n gp r o b l e m ，c v r p ) ，除了站点约束和访问唯一性约束以外，c v r p 只包含容量约束，即车辆从调度中心出发，访问每个用户一次且仅一次，然后 回到调度中心，在运输过程中每条路径上的用户需求量之和不得超过车辆的最 大载重量，通过选择合理的路径，使得总配送成本最小。 2 带时间窗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 , v r p t w ) ，是指在基本v r p 的基础上加上时间窗的约束，车辆必须在指定的时 间区间内访问用户，一般允许提前于最早开始时间到达，即允许存在等待时间， 但不允许滞后于最迟时间到达。其中严格不允许滞后于最迟时间的称为硬时间 窗v r p ，借助于惩罚函数允许滞后于最迟时间的称为软时间窗v r p ，即当车辆 滞后时将遭受相应的惩罚。 3 多站点v r p 多站点v r p ( m u l t i d e p o tv r p ) ，是指车库不是唯一的，所有车辆可以从不 同的车库出发，但是访问完客户以后需要回到原出发车库或者允许回到其它车 库以保证各车库的出发与返回车辆数一致。根据是否要求车辆回到原始车库， 多站点v r p 问题又可以分为固定目的地问题和不固定目的地问题。 4 开放式v r p 在v r p 问题中，如果车辆完成配送任务后不需要回到调度中心，这种v r p 就称之为开放式v r p 问题( o p e nv e h i c l er o u t i n gp r o b l e m ，o v r p ) 。开放式v r p 与其他v r p 问题相比，求解的是汉密尔顿路径而不是汉密尔顿回路。 5 带回程的v r p 问题 如果v r p 中车辆在回程时还需要装载货物带回调度中心，这种v r p 问题称之 为带回程的v r p 问题( v r pw i t hb a c k h a u l ) 。在这类问题的处理上，一般是将所 有用户分为两类，一类是顺向用户，一类是回程用户，这两部分用户都需要满 足容积约束，并且顺向用户的访问顺序要先于回程用户。 6 多车型v r p 问题 多车型v r p 问题是指服务用户的车辆种类不同、负载能力不同或是调度固 定成本不同等等，多车型v r p 问题中，总配送成本不但要考虑总的配送距离或 配送时间，还要考虑不同车辆的分配问题，首先考虑最小化路径数，再分配给 不同类型的车辆，使总的配送成本最小化。 7 切分配送v r p 问题 9 切分配送v r p ( v r pw i t hs p l i td e l i v e r y ) ，是指客户的需求量比较大无法由 一辆车单独完成时，允许用多辆车共同完成。 8 随机v r p 问题 经典v r p 问题研究的是确定性问题，即所有用户的需求在一开始就已经确 定下来了。如果我们在事先并不能确定某些元素，只能知道其分布规律或只能 临时确定，这种v r p 问题就称之为随机v r p 问题( s v r p ) 。这种问题一般分为 两类：一类是必须先确定下一个用户的需求才能决定是否将它包含到路径里来， 这种v r p 问题一旦确定了用户的需求，就可以当成确定性v r p 问题来处理；另 一类是通过对用户需求的预测来判断是否将它包含到路径里来，这种v r p 问题 是一种先验概率优化问题。这种问题的模型比较复杂，一般严格受实际问题的 限制。 9 多周期v r p 在多周期v r p 问题( p e r i o d i cv r p ) 中，调度中心和用户的位置、需求量、 车辆的类型以及车辆最大行驶距离( 时间) 等都已知，如何合理的分配车辆及 构造路径，使得在一个周期内用户的需求量都能被满足，且总配送成本最小。 p v r p 不必要求所有用户在同一天内都被访问，只要在周期内能够满足其配送要 求即可。对p v r p 问题的求解方法一般是先分配车辆，然后再构造路径，即先确 定周期内每一天访问的用户及分配哪些车辆，然后对每一天的车辆及用户采用 路径构造方法构造最优路径，从而使整个周期内的配送成本最小。 2 3 车辆调度问题的基本模型与求解算法 2 3 1 车辆调度问题的基本模型 v r p 问题中的目标函数一般为总的运输成本最小，常用的目标函数有以下 几种： ( 1 ) 使用的车辆数目最小化； ( 2 ) 使总的服务时间最小化； ( 3 ) 使车辆总的运输距离最小化； ( 4 ) 使客户不满意度最小化。 其中前三种是经常用到的目标函数，客户不满意度通常是客户等待时间和 超出正常服务时间的线性函数，其中超出正常服务时间是指实际运输时间和客 户期望运输时间的差，只在有特殊约束的v r p 问题中才会用到。 基本v r p 约束条件有： ( 1 ) 站点约束，是指所有车辆必须从调度中心出发，完成配送任务后再回 到调度中心。 ( 2 ) 容积约束，是指任何一条配送路径上所有用户的需求量( d e m a n d ) 之和不得超过车辆的最大载重。 ( 3 ) 访问唯一性约束，是指用户只能被一辆车服务且只能服务一次。 l o ( 4 ) 次回路消除约束，配送路径中除以站点为起止节点的回路称为次回路， 在v r p 问题中不允许出现次回路，即所有路径为以站点为起止节点的汉密尔顿 回路或汉密尔顿路径。 ( 5 ) 其他约束，最长行驶时间、司机最大工作时间等，视具体问题来添加。 v r p 问题数学模型可以采用两索引法或三索引法来构造【3 4 1 ，其中两索引法 不考虑车辆的差别，只考虑路径对是否出现于最优解中，配送成本只与路径对 的起止用户有关，故称两索引法；三索引法可以处理车辆类型不同的情况，除 了路径对以外，还引入了访问车辆作为决策变量。下面以两索引法为例介绍v r p 的基本数学模型。 首先对模型中要用的符号进行说明： c ，表示车辆在节点f 和，之间运输成本； 吼表示节点f 的需求量； ，z 为客户的数量； 为车辆的最大载重； r 1 ，如果车辆服务客户i 后服务客户j j 1 0 ，否则 为决策变量。 具体模型为： m i n c i j ( 2 1 ) s 1 x oj = 1 j e 村 x ，o = 1 ，eh q t x 盯w ，e 月e 疗 q f 0 ， v i n c v + c 畸c 口，v i j ，k n x ，= o o r l ， v i ，j 刀 ( 2 2 ) ( 2 3 ) ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) 其中式( 2 1 ) 为目标函数，式( 2 2 ) 和( 2 3 ) 为访问唯一性约束， 和( 2 5 ) 为容量约束，式( 2 6 ) 表示满足成本三角不等式。 2 3 2v r p 常用的求解算法 v r p 问题的求解算法有很多，但究其本质来讲，可以分为精确算法和启发 式算法两大类。 1 求解v r p 的精确算法 精确算法，就是指能够通过有限的计算和推理得到优化问题的最优解的算 法。在最优化问题中能由精确算法得出的解是最优的，没有比这更好的解了。 在车辆调度问题中，用精确算法求解就是找到一组车辆路径集合，使得其弱标 函数值比其它任何一组可行路径集合的目标函数值更好。精确算法的时间复杂 度一般沈较大，计算时间随着闯题规模的增大呈爆炸式的增长，所以精确算法 解决问题的规模不大，在实际问题中的应用范围有限。常用的精确算法有分枝 切平面法( b r a n c ha n dc u t ，简称b & c ) 、动态规划法( d y n a m i cp r o g r a m m i n g ， 简称d p ) 和列生成法( c o l u m ng e n e r a t i o n ，简称c g ) 、k 度中心树法以及拉格 朗鼯松弛算法等。 ( 1 ) 分枝切平面法( b & c ) 分枝切平面法是将切平面法与分枝技术结合而成的方法，算法的基本思想 是：首先将问题描述为一个凸集并确定凸集的各个侧面，然后通过分枝操作将 解空间分解为若干个子空间，通过切平面法对子空间进行削减，切去不包含最 优解的子空间，重复上述操作直至找到最优解为止。文献【3 5 】基于分枝切平面 法提出了一种精确算法求取最小所需车辆数，算法首先对问题进行松弛，求得 问题的下界，然后利用贪婪随枫性自适应搜索过程( g r a s p ) 求得阀题上界， 最后通过分枝切平面法求得最优解。 ( 2 ) 动态规划法( d p ) 动态规划法的基本思想是：首先将问题分解为若干个阶段( 子问题) ，然后 递烟求解子问题的最优解，最终求得整个问题的最优解。动态规划法一般有前 向递归和后向递归两釉方式，前向递归是指首先求解出第1 个子问题的最优解， 然后依次求解出下一个子问题的最优解，最终求得整个问题的最优解；后向递 归是指首先求解出最后一个子问题的最优解，然嚣逆推求得蓠一个子闯题的最 优解，最终获得整个问题的最优解。 ( 3 ) 列生成法( c g ) 。 列生成法是基于集覆盖( 集划分) 问题的一种求解框架，这种求解框架不 需要枚举所有路径，它只要求列举一部分的可行路径，然后针对部分路径集上 的线性规划松弛问题进行求解，最后利用这个解来确定是否还有可以削减圜标 值的路径没有包含进来。其基本流程可以描述如下： s t e p l 利用部分路径集上的最优化对偶变量，创建新路径并求解线性规划 松弛； s t e p 2 重复s t e p l 直至最优解被找到。 列生成法作为一种求解框架，在求解大规模问题时难以保证其求解效率， 一般和其他算法配合使用，如分枝定界法，列生成法框架可以为分棱定界法提 供较好的下界，然后利用分枝