（载运工具运用工程专业论文）基于遗传算法的配送路线优化研究.pdf

摘要 随着物流业在我国的不断发展以及物流专业化水平的不断提高，我国物流配送业近 年来也得到了迅速的发展。在物流配送活动中，配送车辆路线优化问题是配送合理化的 核心问题，时间窗约束在配送路线优化过程中具有举足轻重的作用。因此对带时间窗的 车辆路线问题进行研究具有一定的理论价值和现实意义。 本文对单站点、非满载带时间窗城市物流配送的车辆路线问题进行了研究。首先从 城市物流入手，分析了城市物流的特点和分类属性及车辆路线问题的主要应用领域。在 基本车辆路线问题模型的基础上建立了带时间窗车辆路线问题的数学模型。 对带时间窗的车辆路线问题设计了改进的遗传算法。论文采用自然数编码的方法， 初始群体的生成采用混合方式，即部分随机生成、部分根据初始解生成，选择策略采用 轮盘赌选择法和截断选择法相结合的方法，用改进的边重组法代替常用的p m x 、o x 、 c x 交叉法。根据设定的终止条件，最终取得满意解。 最后，通过c + + 实现了算法，用s o l o m o n 测试数据里c 1 0 1 中2 5 个客户集的数据 进行验证，并与不同算法所得解进行对比，其求解结果和计算时间都有明显改进。本文 所得结果，在基于遗传算法求解城市物流配送车辆路径问题领域和物流系统的开发中具 有一定的参考价值。 关键词：遗传算法车辆路线问题时间窗城市物流 a b s t r a c t w i t ht h ec o n t i n u o u sd e v e l o p m e n to fl o g i s t i c si n d u s t r ya n dt h ec o n s t a n t l yi m p r o v e m e n t o ft h es p e c i a l i z a t i o nl e v e lo fl o g i s t i c si no u rc o u n t r y , l o g i s t i c sd i s t r i b u t i o ni n d u s t r yh a sa l s o b e e nd e v e l o p e dq u i c k l y o fa l lt h ea c t i v i t i e si nd i s t r i b u t i o n ，t h ev e h i c l er o u t i n gp r o b l e mi st h e k e yp r o b l e m t h ew i n d o w si si m p o r t a n ti n t h eo p t i m i z a t i o na b o u tt h ev e h i c l er o u t i n g p r o b l e m t h eo b je c to ft h i sp a p e ri st or e s e a r c ht h es i n g l e d e p o tv e h i c l er o u t i n gp r o b l e mw i t hn o t f u l l l o a d e d f i r s t l yi t i n t r o d u c e sc i t yl o g i s t i c s ，t h e na n a l y s e st h ec h a r a c t e r i s t i c sa n dt h e a t t r i b u t e so fi ta n dt h em a j o ru s e da r e a so ft h ev e h i c l er o u t i n gp r o b l e m a b o v et h eb a s i c v e h i c l er o u t i n gp r o b l e m ，t h i sp a p e rf o u n d st h em a t hm o d e lo ft h ev e h i c l er o u t i n gp r o b l e m w i t ht i m e w i n d o w s t h i sp a p e ra d o p t si m p r o v e dg e n e t i ca l g o r i t h mt os o l v et h ev e h i c l er o u t i n gp r o b l e mw i t h t i m e - w i n d o w s t h eg e n e t i ca l g o r i t h mc h o o s e st h en a t u r ed a t ac o d i n gm e t h o d ，t h ei n i t i a lg r o u p a d o p t e dm i x e dm e t h o dw h i c hg e n e r a t e dp a r t l yb yr a n d o m l ya n dp a r t l yb yg e n e r a t i o n , s e l e c t i o ns t r a t e g ya d o p t e dt h em e t h o do fc o m b i n i n gr o u l e t t ew h e e ls e l e c t i o na n dt n m c a t i o n s e l e c t i o n ，a n dt h ei m p r o v e de d g er e c o m b i n a t i o nc r o s s o v e ri n s t e a dt h ec o m m o n l yu s e dp m x ， o xa n dc x i tg o tas a t i s f a c t o r ys o l u t i o na c c o r d i n gt ot h et e r m i n a t i o no ft h ec o n d i t i o n s f i n a l l y , t h ea l g o r i t h mr e a l i z a e db yc + + ，v e r i f i e dw i t ht h et e s td a t ai nt h es o l o m o nc 1 0 1 c u s t o m e r si n2 5s e t so fd a t a ，a n dc o m p a r e dw i t hd i f f e r e n ta l g o r i t h m ，f o n dt h a tt h ec o m p u t e r t i m ec o s ta n dr e s u l t sh a v em a k e di m p r o v e m e n to b v i o u s l y t h er e s u l t si nt h i sp a p e rw h i c h b a s e do ng e n e t i ca l g o r i t h mi nt h ec i t yl o g i s t i c sa n dd i s t r i b u t i o nv e h i c l er o u t i n gp r o b l e ma r e a s a n dt h ed e v e l o p m e n to ft h el o g i s t i c ss y s t e r nh a ss o m er e f e r e n c ev a l u e k e yw o r d s ：g e n e t i ca l g o r i t h m v e h i c l er o u t i n gp r o b l e mt i m e - w i n d o w sc i t yl o g i s t i c s 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研究 工作所取得的成果。除论文中已经注明引用的内容外，对论文的研究做出 重要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任 何未加明确注明的其他个人或集体已经公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名： 支球川年r 月矽e l 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权 利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成 果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名：良披 导师签名：2 佳易 俐年i - 月矽e l 础对罗日 长安大学硕士学位论文 1 1 引言 第一章绪论 在全球经济一体化的进程中，物流作为“第三个利润源泉 ，以其先进的组织方式 和管理技术，出现在一系列与高科技相结合和实行现代管理的新兴产业中。物流产业自 诞生以来就不断蓬勃发展，至上世纪9 0 年代，物流产业已经在发达国家和地区的国民 经济领域占据了十分重要的地位，譬如1 9 9 6 年英国的物流产值占g d p 的比重已经达到 l o 6 3 ，而欧洲工业化国家的社会物流总成本一般相当于国内生产总值的1 2 左右。 物流成为现代经济的重要组成部分，在国民经济和社会发展中发挥着重要作用。可以说， 发展现代物流对于提高国民经济运行的质量和效益，优化资源配置，改善投资环境，促 进企业结构调整，提高国家经济实力，具有十分重要的意义【h 】。 物流是指原材料、产成品从起点至终点及相关信息有效流动的过程。运输、储存、 包装、装卸搬运、流通加工、配送和信息是物流的基本功能，其中运输和配送是物流系 统最主要的功能，对整个物流系统的效率起着关键作用。黄晓英和张剑芳【5 】发表的文章 指出，根据一般综合分析计算社会物流费用，运输费占6 0 的比例，有些产品运输费用 甚至高于产品的生产费用。可见，运输成本是影响物流成本的重要因素，运输成本的大 小直接影响到物流总成本的大小。据一份来自世界银行的报告称：如果中国物流成本占 国内生产总值的比例，由目前的1 6 7 降低到1 5 ，每年将为全社会直接节省约2 4 0 0 亿元的物流成本。因此，控制物流总成本的根本是降低运输成本，这对我国经济建设有 着十分重要的意义。 物流已经发展成为我国经济发展中的热点之一，特别是由于城市经济快速发展和城 市化进程的不断加快，导致了以城市为依托的物流服务需求不断增长，城市物流发展成 为热点中的热点。由于在我国城市经济发展和城市化进程不断加快的过程中，产生了愈 来愈严重城市交通拥挤问题，特别是经济中心城市，交通效率问题比一般城市更为突出。 为提高城市交通的效率，几乎所有经济中心城市均出台了限制程度不同的禁止货运车辆 在交通流量较大城区通行的交通管制政策。虽然这种政策对部分解决城市的交通问题具 有一定作用，但是，随着城市在工业加工、商贸流通等产业发展集约化、规模化程度的 提升，以及城市居民生活水平的提高，城市生产、生活对优质、高效物流配送服务的需 求也越来越强烈，城市交通管制及管制范围的不断扩大，无疑对城市物流效率和满足城 第一章绪论 市的物流配送提出了更高的要求 6 - 7 1 。 1 2 课题的提出及研究意义 当前，物流的现代化水平不仅成为反映一个国家现代化程度和综合国力的重要标 志，也成为城市经济发展水平的体现。城市物流配送，它不但给供应者和需求者带来降 低物流成本、享受优质服务的直接效益，而且还能为社会节省运输车次、缓解交通压力、 减少运输污染、保护生态环境等作出贡献。 而今，由于小批量、多批次等及时配送方式的发展，运输费用正在逐年提升，许多 企业的运费已经超越了库存费用，城市交通与改善物流的矛盾也愈演愈烈，城市交通混 杂、阻塞、车辆噪音、尾气污染、车祸事故和能源浪费等现象更加严重，若物流路线选 择的不合理，还会使物流配送的行车路程变长，导致载运车辆增加，从而使本已拥挤的 城市交通加重负担。以上问题均需要选择合理有效的运输路线来减少重复运输、倒流运 输、迂回运输、单程运输和空驶等，这样不仅提高配送效率，控制了物流成本，而且还 可限制车辆在城市中的运行时间，有效缓解城市交通负担。 针对以上情况，本研究课题拟采用经典的车辆路线问题模型，结合配送时间窗要求 来优化配送线路，即运用v r p t w 使得配送体系合理化。 1 3v r p t w 国内外研究现状分析及待解决的问题 1 3 1 国外关于v r p t w 问题的发展及研究现状 自从1 9 5 9 年跳i g 和r a m s 一8 】首次提出车辆路径问题以来，车辆问题( v r p ) 一直 为众多的研究者所关注。有时间窗车辆路径问题( 强t w ) 是基本v r p 的一个特殊类， 按照集合论的观点，v r p t w 是v r p 的一个真子集。1 9 8 5 年，s a v e l s b e r g h t 9 】证明了v r p t w 是一个n p ( n o n - - l i n e a r p r o b l e m ，非线性规划) 问题，很难求得问题的最优解。目前， 国内外专家和学者对其求解主要集中在启发式算法，用以求得问题的近似最优解( 可行 解) 。 1 9 6 4c l a r k e 矛1 w r i g h t 1 0 1 提出一种较有效的启发式算法叫l a r k e w r i g h t s 乡4 j 算法。 p a e s s e n s i 1 等人通过使用适当的数据结构，降低了它的复杂度，c l a r k e w r i g h t 法随后成 为许多专家和学者研究v 】r j p t w 的基础。1 9 6 8 年，r a o 1 2 】等人在b a l i n s k i 的v r p 集分割【1 3 】 的基础上引入了列生成法进行求解，这种算法本质上是最短路径算法，同时结合了分枝 定界算法，d e s r o c h e 曾用它求解了有1 0 0 个客户的v r p t w 。1 9 8 1 年f i s h e d l 4 】等人针对带 2 长安大学硕士学位论文 能力约束、时间窗口以及无停留时间的v r p ，提出了三下标车辆流方方程。t h a n g i a h t l 5 l ( 1 9 9 1 年) 和j o e 1 6 】( 1 9 9 3 ) ，分别用遗传算法求解了v r p t w ，但是都存在“早熟收敛 的问题。1 9 9 4 年，r w a r k 1 7 】等人提出了重复匹配的方法，该算法在其模型里同时考虑了 时间约束和能力约束，因此适用于这类具有强约束的v r p ，另外，重复匹配算法也可求 解较大规模的v r p 。1 9 9 9 年，g a m b a r d e l l a 1 8 】等提出一种m a c s ( m u l t i p l ea n tc o l o n y s y s t e m ) 系统用来解决v r p t w ，是以蚁群算法为基础，主要设计用来解决2 个目标函数 的v r p t w ，一个是使车辆数最小，另一个是使时间最短，而最主要的目标是使时间最 短，该算法只在总体上优于其他算法，求解具体问题时优势不是很明显。2 0 0 3 年，b a k e r 1 9 】 等对不确定车辆数的v r p t w 进行了改进的遗传算法优化，取得了较为理想的效果。 1 3 2 国内关于v r p t w 问题的发展及研究现状 在国内，一些专家和学者也在尝试研究v r p t w 。1 9 9 8 年，李大卫【2 0 】等对适用于旅 行商问题的最近距离搜索启发式算法进行修正，构造出评价函数，并据此提出一个求解 v r p t w 的启发式算法。2 0 0 0 年，谢秉磊【2 1 】等将货运量约束和时间窗约束转化为目标约 束，设计了基于自然数编码的可同时处理有软、硬时间窗v r p 的遗传算法( g a ) ，得到 了较好的结果。2 0 0 1 年，周贤伟f 2 2 1 等根据车辆装载g p s 设备的特性，建立了v r p t w 的 数学模型，设计了相应的g a 。2 0 0 2 年，张丽萍【2 3 】等通过引入新颖交叉算子，构造了一 种改进的g a ，该算法摆脱了对群体多样性的要求，不存在标准g a 常见的“早熟收敛 问题，可用于解决v r p t w 。2 0 0 3 年，宋厚冰【2 4 】等针对v r p t w ，在标准g a 的基础上， 将分组信息与每一个染色体结合，并辅以交换局部搜索技术，构造了一种g a ，使得求 解结果更接近最优解。同年，宾松【2 5 】等用一种新的编码方法及交叉和变异概率的自适应 机制，构造了改进的g a 求解v r p t w 。2 0 0 4 年，刘小兰【2 6 】等为了克服原有大规模邻域搜 索算法不能有效求解时间窗较宽v r p 的缺陷，介绍了v r p t w 的通用数学模型，并通过 分析各主要变量之间的关系，设计了一种简单、快速的确定性初始算法，同时引入“短 路径优先策略 构造了改进的大规模邻域搜索算法，该策略也可嵌入到求解时间窗比较 窄的v r p 中，达到加速搜索的目的。2 0 0 5 年，刘诚【2 7 】等针对g a 在求解v r p t w 时初始种 群的单一性，提出一种并行遗传算法，该算法对不同的种群用不同的初始化方法一随 机初始化法和构造初始化法，效果比较理想。2 0 0 6 年，杨宇栋【2 8 】等引入客户直接排列的 解的表示方法，改进了模拟退火算法，提高了求解v r p t w 的效率。 3 第一章绪论 1 3 3 国内外研究中待解决的问题 从车辆路线问题提出，直到研究的重点已放在精确优化算法和新兴人工智能算法的 今天，国内外对于v r p t w 问题的研究都取得了很大的进步，广大学者对此也有了越来 越多的关注，但是从国内外的文献中都可以看出，在求解v r p t w 问题上还存在着许多 的缺陷： 1 ) 配送不但要满足客户的实物需求还要满足客户的时间需求，特别是在客户要求 尽量减少库存的前提下，及时配送变得越来越重要，所以满足客户的时间窗口是制定 车辆路线优先考虑的重点，但是目前的研究对于这一点还没有足够的重视和考虑。 2 ) 目前多数配送路线问题的研究都局限于具有确定性参数的模型，也就是固定路线 问题的研究。实际上，每一次配送客户的数量、需求、位置以及车辆的运输时间、道路 信息等事先并不一定知道，应把它们当作随机变量来看待，这一点还有待于进一步的研 究。 3 ) 现有的配送路线的研究多为开发静态的模型，很少分析参数随时间变化的特性。 例如，仓库位置的成本将随时间变化；在一定的时间范围内，公司需要根据情况的变化 来重新决策配送中心及销售网点的分布。因此，在配送路线模型中加入动态特性，实现 实时或在线物流管理，会极大地提高与现实接近的程度。 4 ) 车辆路线问题的求解方法现阶段以启发式为主，而人工智能这种未来发展方向 的方法却没有被很多的研究和采用。 5 ) 现有启发式解法多是针对某一类型问题求解，本质上不具有通用性，因此，今 后应设计高效的通用性启发式算法。 1 4 本课题的研究内容和研究方法 本研究课题重点研究大规模v r p t w 模型的智能方法。针对我国城市物流配送特点， 建立满足城市物流配送的v r p t w 模型并找出有效智能算法。由于v r p t w 问题属于 n p h a r d 问题，运用常规优化方法难以进行求解，故拟采用遗传算法对理论模型进行算 法设计，如对遗传算法中的参数进行数值模拟计算，找出较好的参数搭配，分析算法对 解的质量影响，并运用s o l o m o n 标准测试数据进行计算结果测试。通过计算机编程，在 可接受的计算时间内得到满足一定精度的相对最优化解，最终找出解该类问题有效的遗 传算法，为解决城市物流大规模配送问题奠定理论基础。 本项目研究的技术路线如图1 1 所示： 4 长安大学硕士学位论文 图1 1 技术路线 数据采用s o l o m o n 系列标准测试数据。大规模问题求解运用c + + 语言编程计算，并 将测试结果与国际上类似模型的计算结果对比，以验证模型和算法的有效科学性和先进 性。 5 第二章城市物流配送中带时间窗的车辆路径问题研究 第二章城市物流配送中带时间窗的车辆路径问题研究 2 1 城市物流特征及发展城市物流意义 2 1 1 城市物流 物流按地域范围可分为国际物流和区域物流，而区域物流研究的重点就是城市物 流。城市物流是以城市为主体的，围绕城市的需求所发生的物流活动，随着经济的发展 和城市规模的不断扩大，城市商品经济愈益繁荣，城市与城市之间，城市与周边地区以 及其他国家和地区之间的经济联系也更加紧密，可以说，城市物流是城市经济发展的产 物，同时，城市物流又服务于城市经济发展的需要，并且是城市经济的一个有机组成部 分。不论城市地域范围大小，物流活动都具有共同的属性。城市物流所包含的范畴可以 有两种理解： 种理解是包括城市内部的物流以及以城市为主体的城市外部物流，例如，城市的 输入物流及城市的输出物流，这是对城市物流广义的理解。 另一种理解是城市物流仅仅是城市内部范畴的物流，而城市的输入物流及城市的输 出物流是发生在若干城市之间的物流，已经属于区域物流的范畴，这是对城市物流侠义 的理解。 城市物流介于宏观物流和微观物流之间，是一种中观尺度的物流，属于区域物流。 从宏观物流网络的角色看，城市是全国物流网中的“结点”，而铁路、公路、航空线、 航海线、水运航道、管道等则是物流网中的所谓“线路，正是这些结点和线路织成了一 张硕大无比的物流网络。输入城市的宏观物流通过城市物流分散成成千上万的微观物 流；而企业微观物流又通过城市物流汇集成输出城市的宏观物流。事实上，城市物流对 于宏观物流的接续和延伸，对于微观物流的高效集散，对于城市及环境的影响，对于城 市规划及城市道路系统建设等都有着十分重要的意义。但长期以来。物流学只研究宏观 物流和微观物流，而对城市物流则很少涉足。 2 1 2 城市物流特征 城市物流具有以下几个特征： 1 ) 城市主体的一元性。城市物流的主要特点，是城市主体的一元化，所有的城市 都具有统一的政府行政组织，城市行政组织可以统筹和管理物流，因此，城市物流具有 非常强的可控性。 6 长安大学硕士学位论文 2 ) 城市物流以短程物流为主。受城市范围的制约，城市物流的短程性非常突出， 再大的城市，城市的最大直径无非在百公里以内，城市中心物流密度再大的部位，也要 远远低于这个数字。因此城市物流有非常明显的短程物流特征和短程物流派生的特性： 以公路网络为主要的平台。 以中小型的公路汽车为主要的物流工具。 以多批次、少批量、多用户物流为主要的物流形式，更强调物流服务，而很难 有效的降低物流成本。 物流的各个功能要素在城市物流中的轻重地位有所变化。主要是，装卸和搬运这两 个功能要素无论在物流时间的比重上还是在物流成本的比重上地位都有所上升，成为主 要功能要素。 3 ) 城市物流是高密集型物流。国际物流、区域物流的始发点和最终目的地基本都 是城市，因此在广泛区域运作的物流，最终都归结到城市之中，这是造成城市物流高密 度的重要原因。另外，城市本身的产业密度及人口密度也带来了高密度的物流需求。城 市物流的高密集性主要表现在以下两个方面： 首先是物流资源密集，表现在城市范围中有高密度的物流线路及物流结点，各种类 型的物流企业的经营性机构也集中在城市。 其次是物流活动的密集，在城市中，多点、多线、多面、多种、多发而且连续不断 的物流活动，已经是城市生命的一部分。 4 ) 城市物流存在着严重的人、物混流现象以及物流环境和人居环境互相影响的现 象。城市的物流平台，不仅支持物流，而且支持人流，虽然现代城市已经开始建立单独 的人流平台，但是，人流和物流混杂的现象还是很严重。同时，城市的物流系统存在于 城市的人居环境之中，物流环境与人居环境也是混杂在一起的。人、物混流以及与环境 混杂现象带来三个直接的后果： 影响效率。人的实体流动共同使用一个平台，争夺物流资源，而物流资源缺乏 专用性，因此效率不高。 容易出现混乱，后果之一是容易造成交通混乱和交通堵塞。尤其当物流影响了 城市中人的流动，会影响人们的生活和工作，扰乱正常的城市秩序。 恶化生存环境。人需要良好的生存环境，而物流又是对环境造成严重影响的重 要源头，这是不可调和的矛盾，而这种矛盾的结果又经常是物流破坏了人居环境。 5 ) 配送物流是城市重要的特征物流。由于物流的最终用户，例如，企业、商店、 7 第二章城市物流配送中带时间窗的车辆路径问题研究 个人等都集中在城市，所以配送这种物流形态和服务方式主要集中在城市，也成了支持 城市运行的、有特点的物流形态。 6 ) 精益化是城市物流的运作模式。城市是一个国家经济水平最高的地区，有进行 精益化运作的需求和条件。更重要的是，城市交通条件的制约和生态的脆弱性，不允许 进行粗放的物流活动。因此，低噪音、低排放、小吨位、封闭型的物流车辆是城市物流 的主要工具，执行的是准时、准确的物流方式。这种精益的运作，是城市物流的重要特 点。 2 1 3 发展城市物流的意义 随着城市化速度的加快，中心城市对周边地区的综合服务作用越来越大，建立一个 高效率的城市物流体系就越来越显得必要，城市物流对整个城市发展的促进作用十分明 显，主要表现在： 1 ) 促进区域产业结构的优化。一般来说，城市是商品集散和加工的中心，而且物 流设施和基础建设齐全，消费集中而且需求量大，交通与信息发达，城市水平己成为物 流业发展的一个重要条件。而物流产业发展带来的商流、资金流、信息流、技术流的集 聚，以及交通运输业、商贸业、金融业、信息业和旅游等多种产业的发展，又有助于城 市产业结构的合理化。此外，由于物流是对分散的货物流动进行集中处理，必然要求利 用现代化的物流设施、先进的信息网络进行协调和管理，真正的现代物流属于技术密集 型和高附加值的高科技产业，具有资产结构高度化、技术结构高度化、劳动力高度化等 特征。从这个角度来说，建立城市物流体系，发展城市物流，将有利于城市产业结构向 高度化方向发展。 2 ) 推动区域经济的快速增长。加强城市物流基础设施的建设，提高物流技术水平， 加快物流速度，无疑对区域经济的发展具有极为重要的意义。现代物流的实质是一种供 应链管理，中心城市发展现代物流，很大程度上是一个组织和理顺供应链关系的问题。 只有建立高效运作的物流系统，理顺各种供应链关系，才能解决好城市积聚的货物快捷 地发运到周边地区乃至更远的地方，使中心城市对周边地区的辐射功能和在经济上的龙 头带动作用才能真正得以发挥。最近十几年，上海、深圳、厦门、宁波等城市在发展物 流的过程中通过对基础设施的投资，对当地的经济拉动非常的明显。上海市的物流业以 每年2 1 3 的速度增长，为传统制造业、信息产业和全融业的快速增长奠定了坚实的基 础，为上海经济的发展做出了巨大的贡献。 长安大学硕士学位论文 3 ) 增强城市的综合竞争力。如提升城市功能，改善城市国民经济运行效率，提高 全社会经济效益，扩大吸引外资，增加就业机会，改善城市投资环境。 4 ) 促进城市的现代化。现在很多城市人流、物流混杂，交通、仓储、流通加工等 都集中在城区，城市污染严重。发展现代物流，改造城市的物流系统可以降低物耗和节 约能源。有效控制车辆污染，合理使用土地，及时处理废弃物，美化城市环境。国外在 城市建设中，都把物流系统重新规划、重新改造。例如日本就把城区里的流通加工、仓 库等等重新设计、规划，放到郊区交通发达的地方，建立物流中心。所以，建立合理的 城市物流系统是城市现代化的需要。 2 2 车辆路线问题 2 2 1 车辆路线问题简介 车辆路线问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 是指一定数量的客户，各自有不同 数量的货物需求，站点向客户提供货物，由一个车队负责分送货物，组织适当的行车路 线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本 最小、耗费时间最少等目的。它是一个经典的运筹学问题，关于这个问题，国内外学者 已经做了比较深入的研究。由于实际物流配送过程中，客户要求被服务的时间通常有一 定的限制，即时间窗要求，因此本文主要研究了带时间窗的车辆路线问题( v 】姆w i t ht i m e w i n d o w s ，v r p t w ) 。 2 2 2 车辆路线问题分类 自嫂提出后，许多学者对其从客户、车辆和配送中心三个不同角度，进行了多种 分类。 1 ) 带运力限制的车辆路径问题( c a p a c i t a t e dv r p ，简称c v r p ) 在这类问题中，车辆的装载能力有限制，即一次行车路线上客户的总需求不能超过 车辆的最大运载量，且所有客户的需求量都是已知的，每个客户只能被一辆车服务一次。 目标是使总路程数最小或总时间最短，这是一类比较基础的v r p 2 9 】。 2 ) 多配送中心的车辆路径问题( m u l t i p l ed e p o tv r p ，简称m d v r p ) 有多个配送中心对客户进行服务，将客户分配给配送中心，不同配送中心的车辆负 责完成分配给该配送中心的客户需求，最后返回到该配送中心【3 0 】。 3 ) 开放式车辆路径问题( 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 ) 9 第二章城市物流配送中带时间窗的车辆路径问题研究 这是一类比较难解决的v r p ，通常与多配送中心问题结合求解更有意义。它的主要 特点是车辆配送完成任务后有二种选择：或者停留在最后一个服务客户处，或者返回原 配送中心，或者返回就近的其他配送中心【3 1 1 。 4 ) 周期性车辆路径问题( p e r i o d i cv r p ，简称p v r p ) 在规定的天数内进行配送，一般的配送指在当天内完成，制定一天的配送计划，而 周期配送车辆路径问题是在指定的天数内完成配送，制定指定天数的配送计划。 5 ) 分割配送的车辆路径问题( s p l i td e l i v e r yv r p ，简称s d v r p ) 当顾客的需求超过车辆的最大载质量，或顾客需求多种类型的货物时，就是s d v r p 要解决的问题。允许多辆车对一个客户进行服务【3 2 1 ，每辆车完成客户的一部分货物配送。 6 ) 随机配送车辆路径问题( s t o c h a s t i cv r p ，简称s v i 冲) 在v r p 问题中，当客户数、客户需求量、服务时间或旅行时间等因素中有一个或多 个因素是随机变化时【3 讣，就变成了s v i 冲。这类问题的解决方案一般分为两个阶段，前 一个阶段是随机组件随机出现前先得到一个解，下一个阶段是当随机组件出现后对该解 进行重组和修正。 7 ) 带回程取货的车辆路径问题( 强w i t hb a c k h a u l s ，简称姆b ) 带回程取货的车辆路线问题是经典车辆路线问题的一种延伸，它将客户分为两类： 配送客户( 有一定的货物需要配送) 和取货客户( 有一定的货物需要收集到站点) 。在 v r p b 问题中，配送客户和取货客户之间存在一个优先约束：在一条服务两类客户的路 线上，所有的配送客户必须早于取货客户接受服务【3 甜。 8 ) 送货集货一体化的车辆路线问题( v r pw i t hp i c k u pa n dd e l i v e r y ，简称v r p p d ) 在送货集货一体化的车辆路径问题中，每一个客户都有一定的配送量和集货量，对 每一个客户，车辆不仅要为客户送货，还要从客户处把货物带走并配送到其指定的客户 或站点，于是存在下面的优先约束：任一客户f 当满足其配送需求的货物源点，不是站 点时，必须早于客户f 接受服务；客户f 集货再配送的目标客户，不是站点时，必须 晚于客户f 接受服务。 9 ) 带时间窗的车辆路径问题( 强谢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 可简单的描述如下：用于服务的若干车辆从配送中心出发，为处在不同地 l o 长安大学硕+ 学位论文 理位置、具有不同货物需求和不同服务时间窗要求的所有顾客提供服务，然后返回配送 中心，其中为每个顾客仅提供一次服务。其目标是在时间窗内为顾客提供服务时，使车 辆的行驶时间和等待时间之和最短。 根据时间约束的严格与否，v r p t w 分为两类：软时间窗的v r p 和硬时间窗的v r p 。 软时间窗的v r p 要求尽可能在时间窗内到达访问，否则将给予一定的惩罚【3 5 1 ，即车辆在 要求的最早到达时间之前到达时，必须在任务点处等待，这样损失了时间，造成成本浪 费，或者车辆在要求的最迟到达时间之后到达，被处以罚款等相应的惩罚；硬时间窗的 廿则要求必须在时间窗内到达访问，否则服务被拒绝。 2 - 3 一般车辆路线问题模型 表示客户集合，即j = 0 ，1 ，2 ，n ) ；其中0 代表站点。 k表示车辆集合，k = 1 ，2 ，朋 ； 勺表示从f 点到点的广义运输成本； r ( s ) 表示对集合s 中的所有客户提供服务所需的车辆数。 建立车辆路线问题的数学模型： m i n 勺嘞 i e jj e j ( 2 1 ) ( 2 2 ) ( 2 - 3 ) ( 2 4 ) = 优 ( 2 5 ) j e j 嘞，( s ) v s c _ j ，s ( 2 6 ) f t s j e s o ，1 v f ，j ( 2 7 ) 式( 2 1 ) 是目标函数，是要使所有车辆的总行驶距离或运行时间最短；式( 2 2 ) 和( 2 3 ) 保证每个客户恰好被访问一次：式( 2 4 ) 和( 2 5 ) 表示所有的车辆都从站点 出发并且最终回到站点；式( 2 6 ) 保证了不存在不含站点的子回路，即每条路线都必须 通过站点，不存在构成不完整线路的解；式( 2 7 ) 为0 、1 约束，车辆从f 到，时取1 ，否 ， ， v ， v m 1 1 = 4 旬 l l 。 嘞 b 鼍 埘彬甜 咄 第二章城市物流配送中带时间窗的车辆路径问题研究 则取0 。 2 4 车辆路线问题的求解算法 2 4 1 组合优化问题 组合最优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 是通过数学方法的研究去寻找离散时间的 最优编排、分组、次序和筛选等，是运筹学中的一个经典和重要的分支，所研究的问题 涉及信息技术、经济管理、工业工程、交通运输、通信网络等诸多领域。 最优化问题的数学模型的一般描述为 m i n f ( x ) ， x e f 其中，x 为决策变量，f ( x ) 为目标函数，为可行域，f 中的任何一个元素成为该 问题的一个可行解，满足( x ) = m i n 矿( j ) i x f ) 的可行解x + 称为该问题的最优解， 对应的目标函数值f ( x + ) 称为最优值。 组合最优化问题的特点在于，可行域f 表示的是有限个点组成的集合。通常情况下， 可行域f - - i 表示为扛i x d ，g ( x ) 阱，所以组合最优化问题的一般形式为 m i n f ( x ) ， s t g ( x ) 0 ， z d 。 因此，一个组合最优化问题可用三个参数( d ，厂) 表示，其中d 表示决策变量的定 义域，f = xlx ed ，g ( x ) o ) 表示可行解区域( 可行域) ，f 表示目标函数。组合最优化 的特点是可行解的集合f 为有限点集，决策变量的定义域d 通常也是有限点集。由直观 可知，只要将d 中有限个点逐一判别是否满足g ( x ) 的约束和比较目标值的大小，该问题 的最优解一定存在且可以得到( 除非可行域为空集) 。因为现实生活中的大量优化问题 是从有限个状态中选取最好的，所以大量的实际优化问题是组合最优化问题。 2 4 2 计算复杂性 优化问题的一个研究内容是算法复杂性研究，每一个组合优化问题都可以通过枚举 的方法求得最优解。但是，枚举是以时间为代价的，有时需要的时间可以接受，有时则 1 2 长安大学硕士学位论文 是不能接受的。因此算法可解的问题在实践中并不一定可解。算法的时间和空间复杂性 对计算机的求解能力有重大影响。在算法分析和设计中，把求解问题的关键操作，如加 减、乘、比较等运算指定为基本操作，算法执行基本操作的次数则定义为算法的时间复 杂性，算法执行期间占用的存储单元则定义为算法的空间复杂性。 如果求解一个问题需要的运算次数或步骤数是问题规模n 的指数函数，则称该问题 有指数时间复杂性；如果所需的运算次数是n 的多项式函数，则称它有多项式时间复杂 性。一般认为，具有多项式时间算法的问题是易解的问题；具有多项式时间复杂性的算 法是好的算法。在计算复杂性理论中，把具有多项式时间复杂性的问题类记为p 。在组 合学、图论、运筹学等领域存在大量这样的问题，我们并不知道对这些问题是否存在多 项式时间算法。特别需要指出的是，在现实中有一大类这样的问题，它们的计算复杂性 具有等效性，如果能用多项式时间解决它们当中的一个问题，则它们全部都能用多项式 时间求解。这样的问题类称为n p 完全问题类。 当一个问题的每一个实例只有“是 或“否”两种答案时，这个问题被称为判定问 题。在研究组合优化问题复杂性时，将给定的一类优化问题，转化为判定问题，使其对 每一个实例只有“是或“否”的回答。图灵机( t u r i n gm a c h i n e ) 一种理想的计算机， 具有无限读写能力，并可做无限个并行操作。如果该机每一步操作结果是唯一确定的， 则称它为确定型图灵机；如果每一步操作结果或下一步操作都可能有多种选择，则称该 机为不确定型图灵机。在确定型图灵机上可用多项式时间解决的问题，被认为是易解问 题，易解问题的全体称为确定型多项式时间可解类，记为p 。不确定型图灵机工作分猜 测与验证两个阶段，所谓一个问题在不确定型图灵机上可用多项式时间解决，是指若图 灵机猜测一个解，则它可以在多项式时间内验证此解正确与否，并不是指图灵机可在多 项式时间内求出正确的答案。在不确定型图灵机上可以用多项式时间解决的问题，称为 非确定性多项式时间( n o n d e t e r m i n i s t i cp o l y n o m i a l ，简称n p ) 可解问题。显然，p c - n p ， 因为在确定型图灵机上多项式时间可解的任何问题，在不确定型图灵机上也是多项式时 间可解的。当n p 类问题中任何一个问题至今未找到多项式时间算法，并且如果这类问题 中的任何一个问题有多项式时间算法，那么这类问题都有多项式时间算法时，把这类问 题记为n p c ( n p - - c o m p l e t e ) 。 对于v r p t w 问题，已经被证明是一个n p c 难问题。事实上，求一个v r p t w 可行解 也是n p c 难问题。 ： 1 3 第二章城市物流配送中带时间窗的车辆路径问题研究 2 4 3 精确优化方法 精确算法是基于运筹学的优化算法，通常运用线性规划( 包括经过了专门处理的分 枝定界法、割平面方法和标号法) 和非线性规划等数学规划技术，以求得问题的最优解。 在早期的v r p 问题研究中，主要是针对单源点( o n e p o i n t ) ( 即配送中心、车场等) 派 车，研究如何用最短路线( 或在最短时间内) 对一定数量的需求点( 即用户) 进行车辆 调度，通过运用最优算法，求出问题的最优解。 求解v r p 的精确算法可以分为以下五种： 1 ) 分枝定界算法( b r a n c ha n db o u n da p p r o a c h ) f i s h e r 最早提出了分枝定界法，分枝定界算法的核心思想是将解空间划分为若干个 小的子空间，然后依次搜索各个子空间。通过与当前最好的解进行比较，剪去不可能产 生最优解的分枝，只搜索能够产生最优解的分枝，比较适用于求解小型问题。 2 ) 切平面法( c u t t i n gp l a n e sa p p r o a c h ) 切平面法考虑所有可能的可行解子集，在此基础上进行重复优化求解，其算法本质 是最短路线算法结合分枝定界法。 3 ) 动态规划( d y n a m i cp r o g r a m m i n ga p p r o a c h ) 动态规划法针对固定车辆数的v r p ，通过递归方法求解。为减小问题的计算规模， 引入可行性规划或松弛过程减少状态的数量。算法的核心思想是最佳化原理，运用数学 逻辑来处理一连串相互关联的决策问题，并采取系统优化的步骤以求得对整体有利的方 案。 4 ) 网络流算法( n e t w o r kf l o wa p p r o a c h ) 网络流算法结合图论中的一些传统算法，如最短路径、宽度搜索算法等，经常可以解 决一些搜索与动态规划无法解决的非n p 问题。运用网络流算法解决具体问题时，没有现 成的模式可以套用，需要根据网络流的性质发挥创造性探索建立多种模型，通过分析、 选择、优化、确定适当的模型。 5 ) 三下标车辆流方程 三下标车辆流方程法针对带能力约束、时间窗口以及无停留时间的v r p 问题而提 出。该方法在模型中有效引入了代表时间窗口的变量，从而可适用于通用任务分配问题 ( g a j p ) 和带时间窗的( t s p ) 等。但精确算法的计算复杂度很高，随着运输系统的复 杂化和对调度的多目标要求，获得整个系统的精确优化解越来越困难，花费的时间和费 用太大，因此精确解法不能应用于规模较大的配送车辆路径问题的求解，仅用于运输调 1 4 长安大学硕士学位论文 度的局部优化问题。 在以上算法中，最为常用的是动态规划方法，而具体求解时效率最高的方法是分枝 定界法。它可以在不很长的计算时间内求解多至1 0 0 个结点的v r p 问题，但是采用分枝 定界法求解v r p 问题必须在其模型中限制设施的数量。一旦所涉及的v r p 问题