




已阅读5页,还剩72页未读, 继续免费阅读
(企业管理专业论文)基于时间窗的车辆路径问题研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
at h e s i si nb u s i n e s sa d m i n i s t r a t i o n r e s e a r c ho nv 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 s b yp a nx i a o x i s u p e r v i s o r :p r o f e s s o rc a is h u x u n n o r t h e a s t e r nu n i v e r s i t y j u l y2 0 0 8 独创性声明 本人声明,所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外,不包含其他人己经发表或撰写过 的研究成果,也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示 谢意。 学位论文作者签名:灭每啦嚷 日期:0 2 肿芬,7 ,矽 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定:即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘,允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后: 半年口一年口一年半口两年耐 ,。 黧= :7 穗啦魄嚣誓。搿卅 签字日期:妒矿、 ,; 签字日期:一p 7 弓 ,y , p ,一 ,一 东北大学硕士学位论文摘要 基于时间窗的车辆路径问题研究 摘要 随着市场竞争的日趋激烈,企业传统两大利润源的不断萎缩,物流成本对企 业利润的影响程度也不断增大,尤其是在其中占有较大比例的物流配送成本对企 业获利能力的影响更是与同俱增。在与配送成本有关的各类问题中,车辆路径问 题是一个备受关注的焦点问题,尤其是从9 0 年代后期开始,车辆路径问题的重要 性被越来越多的国内学者和企业所认同。本文在分析车辆路径问题的基础上,对 基于时间窗的多目标车辆路径问题进行了研究,文章的主要研究内容如下: 首先,本文在阅读大量文献的基础上,指出了目前关于车辆路径问题的研究 中,在模型的建立和求解算法两个方面存在的问题。并对车辆路径问题的基本原 理进行了阐述,比较系统的总结了车辆路径问题的分类情况和常用的求解算法。 其次,针对目前在模型建立中存在的目标单一、约束条件与现实存在一定差 距的问题,本文将客户满意度作为一个新的目标函数引入到带有时间窗的车辆路 径问题的基本模型中,建立了多目标数学规划模型,并把现实中比较常见的多车 型约束条件加入到了建立的多目标数学规划模型中,在一定程度上增加了多目标 模型的实用性。 再次,针对建立的多目标数学规划模型进行了遗传算法的设计,对选择算子、 交叉算子和变异算子进行了一定程度的改进,改进了遗传算法的性能,在一定程 度上避免了算法的“早熟”问题。 最后,用m y e c l i p s c 软件对设计的遗传算法进行了编程实现,并选取了两篇 文献的算例数据进行了计算,对得到的结果进行了比较,对算法的有效性进行了 验证。 关键词:车辆路径问题:时间窗;多车型;遗传算法 i i ,l y 东北大学硕士学位论文a b s t r a c t r e s e a r c ho nv 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 a b s t r a c t t h em a r k e tc o m p e t i t i o nb e i n g i n c r e a s i n g l yf i e r c e ,t h et w om a j o rt r a d i t i o n a l s o u r c e so fe n t e r p r i s e sp r o f i t sa r cs h r i n k i n g t h e r e f o r e ,t h ei m p a c to fl o g i s t i cc o s t s b e c o m e sm o r ei m p o r t a n tt oe n t e r p r i s e sp r o f i t s ,e s p e c i a l l yt h ed i s t r i b u t i o nc o s t ,w h i c h o c c u p i e sal a r g e rp r o p o r t i o ni nt h el o g i s t i c sc o s t s t h ev e h i c l er o u t i n gp r o b l e mh a s l a r g e ri m p a c to nt h ed i s t r i b u t i o nc o s tc o m p a r i n gw i t ho t h e rp r o b l e m s ;t h e r e f o r e , p e o p l ep a y m o r e a n dm o r ea t t e n t i o n st ot h ev e h i c l e r o u t i n gp r o b l e m ( v r p ) p a r t i c u l a r l yf r o mt h el a t e1 9 9 0 s ,m o r es c h o l a r sa n de n t e r p r i s e sr e a l i z et h a tt h e i m p o r t a n c eo ft h ev e h i c l er o u t i n gp r o b l e mi nd o m e s t i c b a s e do nt h ea n a l y s i so f 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 rs t u d i e st h em u l t i o b j e c t i v em o d e lo ft h ev 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 t h e r ea r ef o u rm a i np a r t si nt h i sp a p e r : f i r s t l y , t h ep a p e ra n a l y z e sal o to fl i t e r a t u r e sa b o u tt h ev e h i c l er o u t i n gp r o b l e m , a n df i n d so u tt h ep r o b l e m si nb o t ht h em o d e lo fv r pa n dt h ea l g o r i t h mf o rs o l v i n gt h e v r p f u r t h e r m o r e ,t h ep a p e ri n t r o d u c e st h eb a s i cm o d e lo fv r pa n ds y s t e m i c a l l y c o n c l u d e si t st y p e sa n dc o m m o na l g o r i t h m sf o rt h ev r p s e c o n d l y ,t h e r ea r et w om a i np r o b l e m si nt h ec u r r e n tr e s e a r c ho fv r pm o d e l o n ei st h es i n g l e n e s so ft h eo b j e c t i v e t h eo t h e ri st h a tt h e r ea r cs o m ed i f f e r e n c e s b e t w e e nt h ec o n s t r a i n t sa n dt h er e a l i t y t h ep a p e re s t a b l i s h e sam u l t i - o b j e c t i v e m a t h e m a t i c a lm o d e lo fv r p t w b yi n t r o d u c i n gan e wo b j e c t i v ef u n c t i o nt oe x p r e s s t h es a t i s f a c t i o nd e g r e eo fc u s t o m e r sa n da d d i n gt h em u l t i t y p ev e h i c l e sc o n s t r a i n tt o s o l v et h et w op r o b l e m s t h i r d l y , t h ep a p e ru s e sg e n e t i ca l g o r i t h mt os o l v et h e m u l t i o b j e c t i v e m a t h e m a t i c a lm o d e l t oi m p r o v et h ep e r f o r m a n c eo ft h eg e n e t i ca l g o r i t h m ,t h ep a p e r s e l e c t sb e t t e rs e l e c t i o no p e r a t o r , c r o s s o v e ro p e r a t o ra n dm u t a t i o no p e r a t o r , a n dt h u s a v o i d st h e “p r e m a t u r e ”o ft h eg e n e t i ca l g o r i t h ma tac e r t a i ne x t e n t f o u r t h l y ,t h ep a p e ru s e sm y e c l i p s es o f t w a r et od e s i g nap r o g r a m m i n go ft h e d e s i g n e dg e n e t i ca l g o r i t h ma n ds e l e c t sd a t af r o mt w ol i t e r a t u r e st oc a l c u l a t et h e m b y c o m p a r i n gw i t ht h er e s u l t so ft h et w ol i t e r a t u r e s ,t h ep a p e re n s u r e st h ed e s i g n e d e f f e c t i v e n e s so fa l g o r i t h ma n dp u t sf o r w a r ds o m es u g g e s t i o n i i i 东北大学硕士学位论文 a b s t r a c t k e y w o r d s :v e h i c l er o u t i n gp r o b l e m ;t i m ew i n d o w s ;m u l t i t y p ev e h i c l e s ; g e n e t i ca l g o r i t h m i v , ,、r 东北大学硕士学位论文 目录 目录 独创性声明i 摘要1 l a b s t r a c t 。i i i 第1 章绪论1 1 1 选题背景1 1 2 国内外研究现状及存在的问题2 1 2 1 国外研究现状2 1 2 2 国内研究现状3 1 2 3 存在的问题。4 1 3 研究内容、目的和意义4 1 4 章节安排5 第2 章车辆路径问题的基本原理回顾7 2 1 车辆路径问题原理7 2 1 1 车辆路径问题的原始问题研究7 2 1 2 车辆路径问题的一般描述9 2 1 3 车辆路径问题的分类1 0 2 2 求解车辆路径问题的算法回顾1 2 2 2 1 精确算法1 2 2 2 2 启发式算法1 3 2 3 本章小结1 7 第3 章多目标v r p t w 模型的建立1 8 3 1 v r p t w 的基本模型描述及分类1 8 3 1 1 v r p t w 的基本模型描述1 8 3 1 2 v r p t w 的分类1 9 3 2 多目标v r p t w 模型的建立2 0 3 3 多目标v r p t w 模型的求解方案选择和目标函数处理2 3 v 东北大学硕士学位论文目录 3 4 本章小结2 6 第4 章多目标v r p t w 模型的遗传算法设计2 7 4 1 遗传算法的基本理论2 7 4 1 1 遗传算法的生物学原理2 7 4 1 2 遗传算法的数学理论基础2 7 4 1 3 遗传算法的基本概念2 9 4 1 4 基本遗传算法的步骤3 0 4 1 5 遗传算法的优缺点3 3 4 2 遗传算法的设计3 4 4 2 1 编码3 4 4 2 2 初始种群的生成3 5 4 2 3 约束条件处理与适应度函数的建立3 7 4 2 4 遗传算子的选择3 8 4 2 5 遗传算法的参数选择与终止条件4 4 4 3 本章小结4 5 第5 章算例分析4 6 1 ;11 辜1 8 i 91 4 6 5 2 算例2 。4 7 5 3 本章小结4 9 第6 章结论与展望5 0 6 1 研究结论5 0 6 2 研究展望5 0 参考文献5 2 附录5 5 致j 射6 3 攻读硕士期间发表的论文6 4 v i 东北大学硕士学位论文第1 章绪论 1 1 选题背景 第1 章绪论 随着中国在2 0 0 1 年成为了w t o 的正式成员国,众多外资企业纷纷加大了在 中国市场的运作力度,以争取在这块经济热土上获得更大的发展空间,这使得国 内市场的竞争不断升温,企业的利润空间被不断压缩,使得企业原有的利润源已 经无法满足企业在生存和发展方面的需要。在这种情况下,绝大多数企业为了能 在激烈的市场竞争中生存和发展而纷纷开始寻找新的利润源,其中很大一部分企 业将注意力放在了被德鲁克称之为“黑大陆”的物流领域。因为据资料显示【u ,现 在企业的物流成本已经占到了企业全部经营成本的3 0 5 0 ,如果能建立一个 有效的物流系统,并将物流系统与企业的其它职能系统有效的集成,那么可使企 业的仓储量下降5 0 ,交货的准时率提高4 0 ,营业收入增加1 0 以上。 由此可见,建立现代化的物流系统对于大幅度削减企业的经营成本,提高企 业的市场竞争力有着巨大的作用。正是在这种战略决策的推动下,国内的物流水 平在近几年有了迅猛地发展,物流在企业中的地位也有了显著的提高,其在增加 企业利润方面的作用有的时候甚至超过了降低资源消耗和提高劳动生产率这两大 传统利润源,成为了名副其实的第三利润源。 虽然国内的物流发展取得了可喜的成果,但与西方发达国家相比,在物流效 率等方面还存在着较大的差距。据全国第三产业普查资料显示,我国社会物流总 费用在g d p 中所占的比例达到了2 0 左右。而美国的社会物流总费用在其g d p 中所占的比例仅为1 0 左右。另一方面,从具体的行业来看这种差距也是十分明 显的,以汽车行业为例【2 1 ,国内汽车制造企业的物流成本占销售额的比例普遍在 1 5 以上,但该数据在欧美的汽车制造业企业中是8 ,日本的汽车制造企业甚 至仅为5 。 进一步从物流成本的组成及各组成部分所占的比例来看,物流配送活动的成 本在近十年中一直占据着物流总成本的半壁江山,可见配送环节的成本对总的物 流成本有着决定性的影响。而在物流配送活动的各个环节中,由于车辆路径问题 所涉及的环节和需要考虑的因素较多,对企业提高服务质量、降低物流成本、增 一1 一 l 一 东北大学硕士学位论文第1 章绪论 加经济效益有着较大的影响。因此,该问题逐渐成为了物流配送活动中的一个焦 点问题,进而也就成为了物流系统中的一个不可忽视的问题。在近年来,随着j i t 、 敏捷制造等生产理念的影响力不断加强以及客户对配送活动时间精确性的要求越 来越高,时间因素在配送活动,尤其是在车辆路径问题中的重要性显得越发突出, 从而使得对带有时间窗的车辆路径问题进行研究,有着比较重要的现实意义。 1 2 国内外研究现状及存在的问题 1 2 1 国外研究现状 车辆路径问题( v e h i c l er o u t i n gp r o b l e m , 简称v r p ) 最初由d a n t z i n g 和 r a m s e r 于1 9 5 9 年首先提出的,之后在众多领域中都受到了关注,尤其是数学和 运输领域,以g o l d e n 、a s s a d 、c h r i s t o f i d e s 为代表的众多学者对该问题进行了深 入的研究,对车辆路径问题的模型和求解算法进行了完善1 3 l 【4 1 。在2 0 世纪9 0 年 代,随着时间因素在车辆路径问题中的重要性的提高,人们开始更多的关注带有 时间窗的车辆路径问题( 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 9 8 7 年s o l o m o n 和d e s r o s i e r s 等人考虑将时间约束加入到一般的车辆 路径问题中,最早对带时间约束的车辆路径问题进行了研究【5 】1 6 1 ,1 9 8 8 年, d e s r o c h e r s 进一步对用于求解带有时间窗的车辆路径问题的各种优化方法做了简 明的总结概括【7 1 。 和简单的车辆路径问题一样,带有时间窗的车辆路径问题的求解也主要是基 于精确算法和启发式算法两大类方法。人们将各种精确算法如分支定界算法等应 用于v r p t w 的求解中,成功的解决了一些规模较小的v r p t w ,b r i a nk a l l e h a u g e 对精确算法在v r p t w 中的应用进行了总结【8 l 。但是由于v r p t w 也是n p h a r d 的问题,存在着求解时间随着规模增大成指数级增长的情况,这使得精确算法一 般只能用于求解小规模的v r p t w 。于是,人们开始将对求解方法的研究转到启 发式算法上,其中具有代表性的方法是节约法( s a v i n gm e t h o d ) 1 9 l 、扫描法( s w e e p m e t h o d ) i l o l 、两阶段法等等。 近几年,伴随着启发式算法的发展,诸如遗传算法、模拟退火算法、禁忌搜 索算法等现代优化算法也被应用到求解v r p t w 上。由于这些算法具有强大的全 局优化性能和通用性,因此研究遗传算法等现代优化算法求解v r p t w 己成为目 一 厶 东北大学硕士学位论文第l 章绪论 前研究者们关注的一个新领域。j l a w r e n c e 最早将遗传算法用于v r p 的研究l l u ; b a r r i em b a k e r 和m a a y e c h e w 对基本车辆路径问题进行了描述,运用遗传算法 和邻域搜索方法相结合的混合算法对车辆路径问题进行了求解,并指出这种混合 算法在求解时间和解的质量上同禁忌搜索算法、模拟退火算法相比一样具有竞争 力【1 2 l 。h o o n gc h u i nl a u 等在通过添加惩罚函数的方法放松了时间窗口的要求和 对多目标函数进行分层处理的基础上,用禁忌搜索算法对带有时间窗和车辆数限 制的车辆路径问题进行了研究i ”】。k c t a n 等用模拟退火、禁忌搜索和遗传算法 三种方法分别对v r p t w 进行了求解【1 4 l 。s i l v i am a z z e o 等应用蚁群算法求解带有 车辆容量限制的v r p ,并取得了良好的结果1 1 5 l 。 1 2 2 国内研究现状 国内对车辆路径问题的研究在9 0 年代后期才逐渐兴起,研究成果主要集中在 了对模型求解算法的研究上。1 9 9 9 年,姜大立、杨西龙等在分析v r p 的现有启 发式算法的基础上,构造了车辆路径问题的染色体表达,并对染色体进行了可行 化映射,建立了求解此问题的遗传算法。实验证明,此算法可有效求得v r p 的优 化解或近似优化解,是求解v r p 的一个较好方案i l 引。张涛、王光梦描述了带有 能力约束的车辆路径问题( c v r p ) ,在预先不固定车辆数的情况下,把聚类和排 序有机的结合起来,用遗传算法和3 一o p t 算法相结合的混合算法对问题进行求 解,实验结果表明算法获得的最好解、平均负荷率和计算成本都比较令人满意1 1 7 l 。 2 0 0 0 年,谢秉磊、李军将货运量约束和时间窗约束转化为目标约束,设计了 基于自然数编码的可同时处理软、硬时间窗约束的遗传算法,实验分析获得了较 好的结果【1 8 l 。2 0 0 2 年,张丽萍、柴跃进等通过引入新颖交叉算子,构造了一种改 进遗传算法,该算法摆脱了对群体多样性的要求,不存在传统遗传算法常见的“早 熟收敛”问题i ”】。2 0 0 5 年,朱树人、李文彬等采用最佳保留的轮盘赌复制法,最 大保留交叉法,交叉概率和变异概率自适应调整等技术,设计了基于自然数编码 的遗传算法,并取得了满意解【2 0 l ;叶志坚、叶怀珍等总结了求解多车型车辆路径 问题的5 种基于知识的算法,提出采用大旅程法和禁忌搜索相结合的混合启发式 算法,在搜索过程中通过增加惩罚因子的方法允许不可行解的存在,减少求解陷 于局部优化的可能性,采用g e n i u s 算法处理其中的t s p 问题,不仅能产生较好 的解,而且通过解的周期性扰动,进一步减少求解限于局部优化的可能性【2 。 一3 一 东北大学硕士学位论文第1 章绪论 2 0 0 6 年,张良智、何爱民等在传统遗传算法的基础上,加入了时间约束算法, 对算法的实时实现做出保证:同时根据客户点的位置改进初始种群,提高了变异 率,减少低效计算,为多计算点的遗传操作提供了有力的支持【2 2 1 。2 0 0 7 年,贺竹 磬、孙林岩为优化动态交通下物流配送成本及水平,依据交通流量将运输时间分 为不同时段的不同分布,建立了具有时间窗约束与物流配送成本最小的车辆路径 混合非线性模型,设计了自然数插值编码的遗传算法对模型进行求解,对不同交 通状态下配送方案选择进行了仿真比较,取得了较好的结果【2 3 1 。2 0 0 7 ,姜昌华、 戴树贵等针对物流配送中具有容量限制的车辆路径问题,设计了一种结合2 一o p t 子路径优化的混合遗传算法,提出了一种新的双层染色体编码方案,来确保子路 径满足车辆容量约束的可行路径,而且无需预先知道有容量限制的v r p 所需的最 小车辆数,更适合于求解实际中的车辆路径问题【2 4 1 。2 0 0 8 年,张庆华、刘新力等 综合考虑车辆数和行驶距离两种优化目标,提出了v r p s t w 的多目标优化模型, 同时提出了解决v r p t w 的一种改进遗传算法。在算法中,通过适应度的变化, 较好的解决了多目标优化问题;通过对交叉算子的改进,增加了算法的寻优能力, 同时又克服了算法对群体多样性的要求;针对局部搜索能力弱的问题,加入了2 一o p t 局部搜索方法,很好弥补了遗传算法的不足【2 5 1 。 1 2 3 存在的问题 ( 1 ) 目前国内外关于车辆路径问题模型的研究较多局限于单一目标的模型, 对于多目标车辆路径问题的模型的研究还不够深入,在现有的对于多目标车辆路 径问题模型的研究中,主要关注了车辆路径的安排( 即车辆的行驶成本) 和使用 的车辆数目两个方面的目标,对其他能影响物流效率的因素没有给予适当的关注。 ( 2 ) 在模型的求解算法方面,国内外学者将主要的精力放在了现代优化算法 的研究上,但是现有的算法都或多或少的存在一些问题,例如遗传算法的“早熟” 问题等,还没有寻找到比较理想的求解算法。 1 3 研究内容、目的和意义 随着商品经济的日益发达,企业生产产品的日趋同质化,物流作为“第三利润 源”的作用越来越得到显现,个企业物流效率尤其是物流配送效率的高低在很大 程度上决定了企业的命运。建立一个高效的物流体系,一方面可以使企业以更低 一4 一 东北大学硕士学位论文第l 章绪论 的成本获得原材料,在产品质量差别不大的情况下可以保证其在价格方面具有竞 争力;另一方面,也可以最大程度的满足客户对送货及售后服务等方面的要求, 使客户的顾客满意度达到较高的水平,为企业带来一个稳定地客户群。而车辆路 径问题可以说是对物流配送效率影响最大的几个重要问题之一,尤其是随着人们 的时间观念不断增强,时间因素在物流配送活动中的重要性也大幅度的提高,这 就使得带有时间窗的车辆路径问题成为了物流配送活动中的一个焦点问题,也成 为了运筹学、应用数学、图论及网络分析、物流科学、交通运输工程、管理科学 与工程、计算机应用等科学等众多学科共同关注的一个前沿热点问题。 本文的研究目的是在分析现有的相关研究成果的基础上,建立带有时间窗的 车辆路径问题的多目标数学规划模型,使新模型能与实际问题更加贴近,从而提 高模型对实际问题的指导作用;然后,选用遗传算法针对新模型进行算法设计, 来获得更接近于最优解的近似解,从而提高物流配送效率,降低物流费用。 论文的具体研究内容如下: ( 1 ) 分析综述车辆路径问题及其求解算法的基本原理、种类与研究现状。 ( 2 ) 在分析带有时间窗的车辆路径问题基本模型的基础上,建立带有时间窗 的多车型车辆路径问题的多目标数学规划模型。 ( 3 ) 针对建立的多目标数学规划模型,设计遗传算法进行求解,在一定程度 上避免遗传算法的“早熟”问题。 ( 4 ) 运用m y e c l i p s e 软件实现所设计的遗传算法,并对算法的有效性进行验 证。 1 4 章节安排 第一章绪论介绍了论文的研究背景、国内外研究现状及问题、研究内容、目 的和意义。 第二章是关于车辆路径问题的基本原理回顾,首先介绍两个构成车辆路径问 题的原始问题,对车辆路径问题基本模型和分类情况进行了描述;其次,对车辆 路径问题的求解算法进行了分类回顾,重点介绍了现代优化算法。 第三章构建了带有时间窗的车辆路径问题的多目标数学规划模型。首先,对 带有时间窗的车辆路径问题的基本模型进行了描述,并对带有时间窗的车辆路径 问题进行分类;其次,在约束条件里添加了多车型约束,使模型的环境更接近于 一5 一 i 东北大学硕士学位论文第1 章绪论 现实情况,将客户满意度作为一个新的目标添加到目标函数中,对目标函数进行 了调整;最后,对车辆行驶成本和客户满意度两个目标函数进行权重处理,将多 目标函数转变为单目标函数。 第四章是关于模型的遗传算法设计及实现。按照标准遗传算法的步骤,针对 所构建的多目标模型进行遗传算法的设计,对选择算子、交叉算子和变异算子进 行了一定程度上的改进。 第五章介绍了应用m y e c l i p s e 软件实现所设计的遗传算法的过程,通过对算 例的计算结果的比较,验证算法的有效性。 第六章结论与展望。 一6 一 东北大学硕士学位论文第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 ) 最早是由g d a n t z i g 和 j r a m s e r 于1 9 5 9 年提出的【2 6 1 ,n c h r i s t o f i d e s 在后来对该问题进行了总结深化【2 7 1 , 该问题产生于现实的公路交通运输系统规划,是一类典型的组合优化问题,也是 一个n p 完全问题。由于其与现实中的许多实际问题都有着相似性,例如运输线 路的选择,生产车间的零部件运输等等,故而对于v r p 的研究有着较大的现实意 义。 2 1 1 车辆路径问题的原始问题研究 从众多研究中可以看出,车辆路径问题与旅行商问题和背包问题密切相关, 它的可行解是多个满足背包限制的旅行商问题的回路1 2 引。换个角度来看,可以说 旅行商问题和背包问题是组成车辆路径问题的原始问题。 2 1 1 1 旅行商问题 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ,简称t s p ) 是数学领域中的著名 问题之一,其最早的描述是1 7 5 9 年欧拉研究的骑士周游问题,即对于国际象棋棋 盘中的6 4 个方格,走访6 4 个方格一次且仅一次,并且最终返回到起始点的问题。 t s p 由美国r a n d 公司于1 9 4 8 年引入,并且伴随着该公司的声誉以及线性规划 这一新方法的出现而成为一个知名且流行的问题。t s p 闯题在中国还有另一个描 述方法:一个邮递员从邮局出发,到所辖街道投邮件,最后返回邮局,如果他必 须走遍所辖的每条街道至少一次,如何选择投递路线,使邮递员所走的路程最短。 这个描述被称为中国邮递员问题( c h i n e s ep o s t m a np r o b l e m ,简称c p p ) ,是我国 学者管梅古教授于1 9 6 2 年提出的。 t s p 问题可以描述为:假设有一个旅行商人要拜访个城市,他必须选择所 要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的 城市。路径的选择目标是使得旅行商所走的路程最短。 一7 一 东北大学硕士学位论文第2 章车辆路径问题的基本原理回顾 t s p 的数学模型表示如下i z 叫: m i n 略嘞 b = 1 ,i = 1 , 2 - g n ; ( 2 1 ) ( 2 2 ) 善嘞- - 1 , _ 一1 ,玑,l ; ( 2 3 ) s 卅1 ,2 s 蜘忍一2 ,sc 1 , 2 ,z ) ; ( 2 4 ) o ,1 ) , f ,j = 1 ,2 ,l ; ( 2 5 ) 其中d o 表示城市f 到城市_ 的弧权重( 一般为城市间的距离) ,为决策变量; 当商人由城市i 去往城市j f 时,嘞一1 ,否则嘞= 0 。 式( 2 1 ) 表示总行走路径 的距离之和最小,是目标函数;式( 2 2 ) 限定商人从城市f 出来一次;式( 2 3 ) 限定商人进入城市j 一次( 即式( 2 2 ) 、( 2 3 ) 表示商人在每个城市只经过一次) ; 式( 2 4 ) 约束旅行商在任何一个城市的子集中不形成回路,其中s 表示n 个城市 的集合,h 表示集合s 的元素个数;式( 2 5 ) 中嘞为决策变量,当嘞= 1 时表示 商人走行的路径包括城市i 到城市j ,当嘞一0 时表示商人走行的路径中不包括从 城市f 到城市j 的路径。但由于走行的路径不同,略与d 不一定相等。当略一d 声 时,为对称的t s p 模型,当d o 乒d f 时为非对称的t s p 模型。 2 1 1 2 背包问题 背包问题可以描述为:有一个人带一个背包上山,其携带物品重量的限度为a 公斤。设有n 种物品可供他选择装入背包中,这疗种物品编号为l2 ,甩。已知第 i 种物品每件重量为彬公斤,在上山过程中的作用( 价值) 是携带数量鼍的函数 c f ( 薯) 。问此人如何选择携带物品( 各几件) ,使所起作用( 总价值) 最大。这就 是著名的背包问题,类似的问题有工厂里的下料问题,运输中的货物装载问题, 人造卫星的物品装载问题等等。 一8 一 东北大学硕士学位论文第2 章车辆路径问题的基本原理回顾 背包问题的数学模型如下: m 觚厂。善c f “) ( 2 6 ) j 善峨鲫 7 ) i 而o 且为整数 ( f ;1 2 ,咒) 若毛只取0 或i ,又称o 一1 背包问题。 2 1 2 车辆路径问题的一般描述 基本的车辆路径问题可以描述为如下的问题:给定一个配送中心点,一个顾 客集合( 送货点或取货点) ,还有一个车辆集合,每辆车有自己固定的载重量,确 定合理的配送车辆行驶路线,使配送车辆有序的通过各个顾客,每个顾客只能由 一辆配送车辆来进行服务,车辆从配送中心点出发,在完成任务后还要回到配送 中心点,在满足一定约束条件( 如车辆载重量限制、行驶里程限制、时间限制、 顾客需求量、交发货时间等) 的情况下,达到一定的目标( 如路程最短、费用最 少、时间尽量少、使用车辆数尽量少等) 。其数学模型建立过程如下: 定义变量: 。f 1 ,车辆,从客户f 行驶到客一 ( 2 8 ) 。0 。否则 y * 。p ,客户p 车辆七服务 ( 2 9 ) y 雎。10 ,否则 佗丹) 目标函数: m i n z 。荟荟荟勺箭匍舟v v 七 :叁,t t 。l 1 , ,i ,- 1 、, ,2 , 一9 一 ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) 吼 s 陡 yg f 向 ,s 东北大学硕士学位论文第2 章车辆路径问题的基本原理回顾 j = 1 ,;妣 i ;1 ,; v k v k + s + f : sf ,i = l ,;j = l ,;v k ( 2 1 3 ) ( 2 1 4 ) ( 2 1 5 ) ( 2 1 6 ) 上述模型中,c : 为客户i 到客户_ 的运输成本( 可以是距离、费用、时间等) ; 吼表示车辆七的最大载重量;幺表示到达客户i 的时间:岛为车辆从客户i 到客户j 的行驶时间;墨为车辆在客户i 处的停留时间;k 为车辆七的出发时间:k 为车辆 k 的要求返回时间。 式( 2 1 1 ) 为汽车最大载重量约束,即每辆车装载的货运总量不得超过车的 最大载重量;式( 2 1 2 ) 保证了每个顾客点的运输任务仅由一辆车完成,而所有 运输任务则由k 辆车协同完成;式( 2 1 3 ) 和( 2 1 4 ) 表示对任一由k 服务的顾 客点,必定有另一( 而且只有一个) 由k 服务的顾客点( 包括配送中心) f ,车 辆k 从顾客点f 到达顾客点,而对由k 服务的顾客点f 同样存在由k 服务的另一 顾客点,车辆k 是从该顾客点到达顾客点i 的,依此类推:式( 2 1 5 ) 表示每辆车 的行车路线的总耗时不超过一个事先定下的数值,比如有时候要求每辆车一天的 行驶时间不超过某一极限;式( 2 1 6 ) 表示对某个顾客点,车辆的到达时间限制 在某一时间段内。 2 1 3 车辆路径问题的分类 经过几十年的不断研究,v r p 被不断的细化,形成了多种典型的问题【3 0 】1 3 , 按照其构成要素的区别可以划分为不同的种类: ( 1 ) 按物流中心的数目划分,有单物流中心问题( 配送系统中仅有一个物流 中心) 和多物流中心问题( 配送系统中存在多个物流中心) 。 ( 2 ) 按车辆载货状况划分,有满载问题( 由于客户需求或供应的货物数量大 于或等于车辆的载重量,故完成一项配送任务需要一辆及其以上的配送车辆,配 一1 0 一 弦 量 蜘 = = 啄 啄 v 白v 甸 七r s 、一、墨 + 一玎 g 孓向 孓匀 + 吣 东北大学硕士学位论文 第2 章车辆路径问题的基本原理回顾 送车辆需要满载运行) 、非满载问题( 由于客户需求或供应的货物数量小于车辆载 重量,多项配送任务可共用一辆配送车辆,车辆在配送过程中经常处于非满载状 态) 以及满载和非满载混合问题( 由于一部分客户需求或供应的货物数量大于或 等于车辆的载重量,而另一部分客户需求或供应的货物数量小于车辆的载重量, 造成一些配送车辆需要满载运行,而另一些车辆则经常处于非满载状态) 。 ( 3 ) 按配送任务特征划分,有纯送货问题( 仅考虑从物流中心向客户送货, 也称为纯卸问题) 或纯取货问题( 仅考虑把各客户供应的货物取到物流中心,也 称为纯装问题) 及取送混合问题( 既考虑将客户需求的货物从物流中心送到各个 客户,同时考虑将客户供应的货物从客户取到物流中心,也称为装卸混合问题或 集货和送货一体化问题) 。 ( 4 ) 按任务性质划分,有对弧服务问题、对点服务问题和混合服务问题。 ( 5 ) 按车辆类型数划分,有单车型问题( 所有配送车辆的载重量相同) 和多 车型问题( 配送车辆的载重量不完全相同) 。 ( 6 ) 按车辆对车场的所属关系划分,有车辆开放问题( 即车辆完成配送任务 后可以不返回其发出车场) 和车辆封闭问题( 车辆完成配送任务后必须返回其发 出车场) 。 ( 7 ) 按优化目标数划分,有单目标问题( 仅考虑个优化目标) 和多目标问 题( 同时考虑多个优化目标) 。 此外,根据上述约束条件的不同组合,v r p 在学术研究上产生了许多不同的 延伸和形态,其中比较常见的有以下几类: ( 1 ) v r p l c ( 带有运行时间约束的v r p ) :每辆汽车运行的时间不能超过预 先给定的界l ,每辆汽车的运行时间由汽车在客户间的行驶时间和汽车为客户服 务的时间所构成。 ( 2 ) 分离配送的v r p ( s p l i td e l i v e r yv r p ,s d v r p ) :一个客户的需求可 以同时由若干辆汽车来满足,这样可以充分利用汽车的资源,减少配送车辆的使 用数目。 ( 3 ) 随机v r p ( s t o c h a s t i cv r p ,s v r p ) ,即某些值,如客户的数目、客户 的需求、客户的服务时间不是事先确定的,而是随机变化的。 ( 4 ) 车辆具有载重量限制的v r p ( c a p a c i t a t e dv r p ,c v r p ) 。 ( 5 ) 带有时间窗的车辆路径问题( v r pw i t ht i m ew i n d o w s ,v r p t w ) 一1 1 东北大学硕士学位论文第2 章车辆路径问题的基本原理回顾 ( 6 ) 优先约束的车辆路线问题( v e h i c l er o u t i n gp r o b l e mw i t hp r e c e d e n c e c o n s t r a i n t s ,v r p p c ) 。 ( 7 ) 相容性车辆路线问题( v e h i c l er o u t i n gp r o b l e mw i t hc o m p a t i b i l i t y c o n s t r a i n t s ,v r p c c ) 。 2 2 求解车辆路径问题的算法回顾 目前存在着多种求解v r p 的算法,这些算法大致可以分为精确算法和启发式 算法两大类。其中启发式算法又可以分为传统启发式算法和现代优化算
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年中国希伯胺原料药行业市场分析及投资价值评估前景预测报告
- 核电电焊工考试题及答案
- 2025年中国无线垂直鼠标行业市场分析及投资价值评估前景预测报告
- 用户行为分析-第149篇-洞察与解读
- 肿瘤免疫治疗专利布局-洞察与解读
- 2025国考常州市生态保护岗位申论必刷题及答案
- 2025国考福建金融监管局行测数量关系预测卷及答案
- 2025国考廊坊市法律事务岗位申论题库含答案
- 2025国考人社部行测数量关系易错点
- 2025国考丹东市纪检监察岗位行测题库含答案
- 师德师风证明材料
- 综合实践活动课程的设计与实施
- 机械制图习题集(第五版)习题解答
- 《影视鉴赏》教学课件 《影视鉴赏》第三章
- 市政工程监理平行检验表(套)
- 第六章金属合金的塑性变形
- 四议两公开工作法课件
- 供应链金融业务培训课件
- 幼儿教育政策法规解读-高职-学前教育专业课件
- DF4内燃机车电路图
- 《八段锦教学》PPT课件
评论
0/150
提交评论