（计算机应用技术专业论文）基于蚁群算法的车辆调度问题研究.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 现代物流运输车辆调度过程复杂多变，如何有效地进行车辆调度，降低企业的 运输成本，从而在满足顾客日益多变的需求同时，给企业带来利润，引起了广大企 业决策者和研究者的兴趣。现有的数学方法在解决此问题时还很不完善，缺乏科学 的理论作指导。这些问题的解决，往往需要用现代优化算法做出决策和判断，追求 运输系统总体最优、总费用最低、总效益最大的最优解。本文总结并分析了现代物 流车辆调度问题，主要讨论了车辆调度问题的特点、问题的分类、问题的模型、并 概述了现今求解车辆调度常用的算法。 蚁群算法汹tc o l o n ya l g o r i t h m s ，a o q 是一种新兴的搜索寻优算法，它是从蚁 群行为的研究中产生的。蚁群算法根据蚂蚁个体产生的信息素，借助选择策略、信 息素更新等操作，逐步逼近最优解。本文描述了蚁群算法的一般求解过程，给出了 应用实例，并分析了一般蚁群算法在求解问题过程中容易出现收敛过早或停滞现 象，通过对蚁群算法进行了系数更新、信息素更新、选择算法等方面的改进，加快 算法的收敛速度，提高算法的搜索能力。 本文在现代物流技术基础，特别是车辆调度和蚁群算法的基础理论指导下，针 对现代物流运输车辆的调度优化问题，进行了理论、方法与模型的研究工作。本文 采用基于s w e e p 算法和蚁群算法的二阶算法来求解物流运输车辆的优化调度，对一 般车辆调度问题( 即无时间窗车辆调度问题) 、带时间窗车辆调度问题探求新的求 解方法，利用程序对算法进行了仿真试验，并结合4 s 一体化智能交通系统讨论了 算法在现实车辆调度中的应用。 本文研究成果对蚁群算法的研究有一定的参考价值，并对建立现代物流运输车 辆优化调度系统有现实的理论指导意义和应用价值。 关键词：物流运输；车辆调度优化；蚁群算法；车辆调度系统 硕士学位论文 m a s t e r st h e s i s a b s t r a c t m o d e m t r a n s p o n a t i o nv c h i d em u t i n gp r o c e s si sc o m p l e x i t ya n dc h a n g e f u l ，h o wt o s o l v et h ev e h i c l er 叫t i n gp r o b l e ma n dh o wt o 叩t i i i l i z et h ec o s “nt h e 仃a n s p o n a t i o no f p r o d u c t s ，s oa st os a t i s f yt l l ev a r i o u sd e m a n d so fc u s t o m e f sa l l dm d k et h ee n t e r p r i s e p r o f i t a b l e ，t i l e s cq u 幅t i o n sl l a d 印p e a l e dt om a i l ym a i l a g e r s 强dr e s e a r c h e r s b u tt l l e s o l u t i o n so fe x i s t i n gm a t h e m a t i c sm c t h o d sa r en o ts u i t a b l et os o l v et h e s ep r o b l e m sw l l i c h l a c ko fs c i e n t i f i ct h c o r yt og u i d e i no r d c rt os o l v et h e s ep r o b l c m s ，w eu s u a l l yu s et l l e m o d e mo p t i m i z a t i o na l g o r i t i l mt oh e l pu st om a k es c i e n t i f i cd e d s i o s ，a n dg e tm a 】【i m u m p r o f i t s ，m i n i m 咖c o s ti nt h e 位m s p o r t a t i o ns y s t e m h lt h i sp a p e r m o d c mv e h i c l er o u t i n g p r o b l e mi sc o n d u d c da i l d 蛆a l y s i s ，d i s c i l s d t h ec h 盯a c t e r i s t i c so fv e h i c l em u t i i l g p r o b l e m ，s o no fp m b l e m ，p r o b l e mm o d e l sa n dt h ec o m m o nu s e da l g o m h i i l st os o l v e v e h i c l er o u t i n gp r o b l e mn o w 盯eb r i e n yi t r o d u c c d t i l ea n tc o l o n ya l g o f i t h m ( a c a ) i san c wm c t h o df o ro p t i i i l i z a t i o n ，w h i c hi sb a s e d o nt h er e s e a r c h0 nt h ea n t l o n y i ti t c r a t e st ot h eb e s ta n s w e ra c r d i gt os e l e c t i v e s t r a t e g ya n dp h e r o m o n ew h i c hp r o d u c e db ya n ti n d i v i d u a l s g e e r a i l y l u t i o no f 柚t a l g o r i t l i li sd e s 面b e di nt l l i sp a p e r ，p r e s e n t e daa p p l i c a t i o ne x 锄p l e ，孤d 锄a l y s i st h e p r o b l e m so fe a r l yc o n v e r g e d0 rs t a g n a t i o no ft r a d i t i o n a la l g o r i t h m s a c c o r d i n gt o t h e i n l p r o v e m e n to fu p d a t ec o e f ! f i d e n t ，p h e m m o n ea n ds e l e c t i v es t r a t e g y ，a c c e l e r a t et l l e c o n v e r g e n ts p e e da n de n h a n c et h es e a r c h i n ga b i l i t y b a s e do nt h em o d e ml o 舀s t i ct e c h n o l o g y ，e s p e c j a l l yt h ev e h i c l es c h e d u l i n ga n dt h e a n ta l g o r i t h mt h e o r i e s ，t h i sp a p e rm a k ear e s e a r c hi nt 1 1 e o r i e s ，m e t h o d sa n dm o d e l s a j m i n ga tt h ep r e s e n tp r o b l e m s i nt h i sp 印e r ，as e c o n d o r d e ra l g o r i t h mb a s e do ns w e e p a n da n t c o l o n ya 培o r i t h m s i sa d o p t e dt os o l v et h eo p t i m i z es c h e d u l i n go fl o g i s t i c t m n s p o r t a t i o nv e h i c l e t bs e a r c hn e ws 0 1 u t i o nt og e n e r a lv e h i c l es c h e d u l i n gp r o b l e m ( n a m e l yv e h i c l es c h e d u l i n gp r o b l e mw i t h o u tt i m ew i n d o w ) ，v e h i c l es c h e d u l i n gp r o b l e m w i 山t i m ew i n d o w ，a n dm a k es i m u l a t i o n so ft h ea l g o r i t h m sw j t hp r o c e d u r e s ，c o m b i n e d t h e4 si n t e g r a t i v ei n t e l l i g e n tv e h i c l es y s t e mt od i s c u s st h ea p p l i c a t i o ni nr e a lv e h i d e s c h e d u l i n go ft h i sa l g o r i t h m t h ec o n d u s i o no ft l l i sp a p e ri sv a t u a b l et ot t l es t u d yo fa tc o l o n ya l g o r i t h m ，a i l d 硕士学位论文 m a s t e r st h e s i s h a sr e a lt h e o r yg u i d es i 印i 丘c a n c ea i l da p p l i c a t i o nv a l u a b l et oe s t a b l i s hm o d 锄l o 百s t i c t r 蛐s p o n a t i o nv e h i c l eo p l i m i z a t i o ns c h e d u l i n gs y s t e m k e y w o r d s ： l o g i s t i ct r a n s p o n a t i o n ；v e h i d er o u t i n go p t i m i z a t i o n ； a n tc o l o n y a l g o r i t h m v e h i d es c h e d u l i n gs y s t e m 硕士学住论文 m a s t e r s t h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的研 究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过 的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声明的法 律结果由本人承担。 作者签名：国氐；侈日期：刮年月占日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中师范大 学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。 作者签名：恿聋穿扣 日期：如咕年6 月6 日 导师签名：拟苏1 日期：驯伟莎月矿日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。回重盗塞遴銮唇溢卮；旦圭生；旦二生i 旦三笙筮查! 作者签名 日期：，呻6 年6 南 月彳 日 导师签名：烈 ， 日期：枷睁 日 项士学位论文 m a s t e r st h e s i s 1 1 课题来源 l 绪论 本课题来自武汉市科技局设立的“无线分组数据传输4 s 一体化智能交通系统” 项目。该项目主要是为物流运输车队、出租车、私家车以及长途客运车队提供一套 切实可行的车队监控调度的解决方案。本研究课题为该项目的子课题“基于蚁群算 法的车辆调度问题研究”。 1 2 课题背景及研究意义 物流( l o g i s t i c s ) 指在合适时间，将合适的物品以适当的数量准确地送到顾客 手中，它是供应链中最重要的组成部分。物流广泛存在于日常生活、企业经营等活 动中，它是社会化大生产和社会分工深化的产物，它连接生产与消费，使货畅其流， 物尽其用，促进生产不断发展，满足日益增长的社会消费需要。在现代社会中，物 流与商流、信息流并称为经济的三大支柱，系统化、合理化的物流管理将创造巨大 的经济利润，因此物流被认为是继劳动力、资源之后的“第三利润源”【1 】【2 】【3 】。 目前，发达国家的物流业在整个国民经济中已经占有重要的地位，企业对物流 越来越重视。据有关统计：欧洲物流营业额1 9 9 8 年和1 9 9 9 年分别为：1 4 6 0 亿美元、 1 5 4 0 亿美元。7 1 的德国企业和5 3 的美国企业把物流放在企业经营第一或第二的 位置。与发达国家相比，我国的物流产业效率较低，由于长期以来受“重生产，轻 流通”的计划经济思想的影响，我国的流通行业远远滞后于国民经济的发展。根据 中国物流与采购联合会统计，2 0 0 1 年，中国与物流相关的年总支出约1 9 0 0 0 亿人民 币。物流成本占g d p 的比重位2 0 左右。如果我国的物流成本从目前的2 0 降至 1 0 左右，这将是一个巨大的利润源泉。 随着电子技术与网络技术的高速发展，电子商务唧e c t f o n i cc o m m e r c e 简称e c l 作为一种新兴的商业模式应运而生。电子商务一般是指企业同客户、供销商及合作 伙伴等在i n t e m e t 或者i n t r a n e t 网络上进行的各种商务活动。电子商务具有商品信息 量大、透明度高、购买不受时间制约、省时、方便、快捷、产品生产商和终端用户 直接面对、交易环节和交易费用少等优点，使其成为一种发展非常迅速的商业模式。 电子商务能否成功，面临着要突破网上资金能否安全、便利地支付和物流配送能否 硕士拳位论文 m a s t e r st h e s i s 快速、准确地送达两大瓶颈。网上资金支付的安全性和便利性可以通过技术解决， 但物流配送却不能，因为网上购物的消费者地点分散、购物数量少，其配送费用无 疑与快速送达相矛盾。如何低成本、高速度、准确无误地将商品送达成为物流配送 所有研究的重要对象。 车辆调度是物流管理最重要的部分。随着社会的发展以及消费者对服务质量要 求的不断提高，高效的车辆调度不但有利于降低物流中货物库存的费用，缩短商品 上市周期，而且逐渐成为物流成败的关键。研究车辆调度，以提高物流效率、降低 物流成本、提高服务质量对于促进经济健康稳定的发展具有重要意义。 1 - 3 国内外研究现状 车辆调度问题最早是由d a n t z i g 和r 锄s e r l 4 j 于上个世纪5 0 年代末期在一篇学术 论文中提出的，该问题一般称之为v e h i c l er o u 血gp m b i e m ( 冲) 或者v c h i c l e s c h e d u l i i i gp p o b l e m f v s p ) ，本文将车辆调度问题一律简称为v r p 。v r p 提出后就很 快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等 学科专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前 沿与研究热点问题。各学科的专家对该问题进行了大量的理论研究及实验分析，取 得了很大进展。 国外对物流配送车辆优化调度问题作了大量而深入的研究，例如早在1 9 8 3 年 b o d i n ，g o l d e n 等人f 5 在他们的综述文章中就列举了几百余篇文献。在c h r i s t o f i d e s l 6 i g o l d e n 和a s s a d 【7 1 编辑的论文集，以及t i n k e m e r 和g a v i s h 【8 】，l a p o n e ns a l h i 【1 0 】 等的综述文章中都进行了详尽的阐述。该领域的代表人物有b o d i n ，c h r i s t o f i d e s ， g 0 1 d e n ，缸s a d ，b a l l ，b p o n e ，r i n n o o y k a n ，k n s l r a ，d e s r o s j e r s 和d e s r o c h e r s 等。 在国内，有关车辆调度问题的研究是在2 0 世纪9 0 年代以后才逐渐兴起的，比 国外相对落后。国内研究对象主要是旅行商问题r r r a v e l i n g s a l e s m a n p r o b l e m ，简称 t s p ) 、中国邮递员问题( c h i n e s e p o s t m a n p r o b i e m ，简称c p p ) 、有向中国邮递员问题 f d i r e c t e dc h i n e s ep o s t m a l lp f o b l e m ，简称d c p p l 等，系统性研究还很少见到。西南 交通大学的李军教授和郭耀煌教授【1 1 】对车辆优化调度的基础理论及各类问题进行 了系统的研究。李大为等【1 2 】以t s p 的最近距离启发式为基础，通过设置评价函数来 处理时间窗约束，求解了简单的v r p 。另外在利用现代优化算法( 如：遗传算法、 神经网络方法、模拟退火等) 对简单t s p 的求解取得了一定成果。蔡延光等【1 3 l 应用 硕士学位论文 m a s t e r st h e s i s 模拟退火法针对满载问题进行了求解。总体来说，目前我国对车辆调度问题的理论 研究仍相对薄弱，需要进一步研究。 v r p 问题是组合优化领域中的著名n p 难题。目前，国内外用来解决该问题的 方法主要有：精确优化方法、启发式方法、模拟方法和交互式方法。以往广泛采用 的是第一种方法，另外三种方法则代表了较近的研究思想。尤其是启发式方法，作 为一种逐次逼近的算法，虽然不一定得到最优解，但可以高效率地得到具有较高精 度的解，而且也易于考虑各种各样的实际问题，因此，现已成为解决物流配送问题 的重要方法。在本文的第二章会对上述的部分方法作更详细的叙述。 1 4 论文研究的主要内容 本文主要对带有时间窗的车辆调度问题进行描述，建模和提出解决方案。文章 的主要任务是将蚁群算法应用到v r p 1 w 上，对此应用加以探讨，因此本文的结构 如下安排： 第一章主要提出课题的来源，讨论了问题提出的背景和研究的意义，并分析了 该问题的研究现状。 第二章主要对车辆调度问题进行分析。本章依次对t s p 问题、一般车辆调度问 题和带时间窗车辆调度问题进行问题的描述，并建立数学模型，最后总结分析了现 今解决车辆调度问题的常用方法。 第三章主要描述蚁群算法。本章说明了蚁群算法的基本原理，借用一个应用实 例说明了蚁群算法求解决组合优化问题的模型和求解过程，讨论了蚁群算中参数的 设定。最后讨论了蚁群算法的优缺点和发展情况。本章是本文的重点。 第四章主要讲解基于s w e e p 算法和蚁群算法求解车辆调度问题的方法。本章是 本文的又一重点。 第五章主要介绍了车辆优化调度算法在无线分组数据传输4 s 一体化智能交通 系统中的应用。讲解了该系统的车辆优化调度子系统，并描述了车辆优化调度的流 程。本章是本文最后一个重点。 第六章对本文进行了小结，总结了论文的主要工作以及有待改进之处，并对进 一步的研究方向进行了展望。 本文的第三、四、五章是本文的核心内容。第三、四章主要是理论研究，第 五章是理论实际应用的初步尝试。体现了本文的工作价值与工作量。 硕士举位论文 m a s t e r st h e s l s 2 车辆调度问题分析 2 1 车辆调度问题描述及分类 车辆调度问题被定义为：对一系列装载点和( 或) 卸货点，组织适当的行车线路， 使车辆有序地通过它们，在满足一定的约束条件，如货物需求量、发送量、交发货 时间、车辆容量限制、行驶里程限制、时间限制等限制下，达到一定的目标，如路 程最短、费用最少、时间尽量少、使用车辆数尽量少等。 从图论的角度来看，v r p 可以描述为基于完全无向图g 一，4 ) ，其中 y = 饥，u ，匕 ，y 代表顶点集合；4 = 化，v ) i u ，v ，y ，f _ j ，爿代表连接两两顶 点的线段的集合，即边的集合。顶点h 表示配送中心的位置，其他顶点则表示待服 务的顾客集合。在爿上可以定义一个非负的距离矩阵或成本矩阵c = 托， ，此处c 。代 表从顶点( 顾客) f 到顶点( 顾客) ，的距离或成本。 在v r p 研究中，常见的约束条件有如下几种【1 4 j ： ( 1 1 能力约束。如每个顾客或城市对应的需求是个非负值，任意车辆路线的总 需求量( 该路线上用于服务的车的实际载重量) 不能超过该车的最大载重； ( 2 1 任意路线上所需服务顾客的数目的上限； ( 3 1 总时间约束。任意路线的某车行驶时间长度不能超过预先设定值：该长度 由车辆在顾客间的行驶时间和在该路线上的每个顾客处的停留时间所构成的； ( 4 ) 服务时间窗口。必须在顾客允许的服务时间段内对顾客进行服务，并允许 车辆服务顾客时可以等待； ( 5 ) 多个顾客间存在一定的服务优先次序。 为了便于描述和求解，许多专家、学者根据研究重点的不同对v r p 问题从不 同角度，按不同标准进行了如下多种分类： ( 1 ) 按任务特征分：有纯装问题、纯卸问题、装卸混合问题。 ( 2 ) 按任务性质分：有对弧服务问题( 中国邮递员问题) 、对点服务问题( 如旅行 商问题) 、混合服务问题( 如交通车线路安排问题) 。 ( 3 ) 按车辆载货状况分：满载问题( 货运量不小于车辆容量，完成一项任务需要 4 勰怒。 多辆车) ；非满载问题( 货运量小于车辆容量，多项任务用一辆车) 。 ( 4 ) 按车场( 或货场、配送中心等) 数目分：有单车场( 或货场、配送中心) 问题、 多车场( 或货场、配送中心) 问题。 ( 5 ) 按车辆类型数分：有单车型问题( 所有执行任务车辆容量相同) 、多车型问题 ( 执行任务车辆容量不相同) 。 ( 6 ) 按车辆对车场的所属关系分：有车辆开放问题阵辆可以不返回出发的配送 中心) 、车辆封闭问题( 车辆必须返回出发配送中心) 。 ( 7 ) 按优化目标数来分：有单目标问题、多目标问题。 v a nb r e e d a m 根据约束条件的不同将v r p 分为以下三类： ( 1 ) 与顾客相关的约束。这种类型的约束条件与顾客需求的本质特点相关，由 于企业的经营理念正在逐步向“以顾客为中心”的模式转变，所以这一类的约束往 往是车辆调度问题研究的重点与焦点。 ( 2 ) 车辆相关的约束。这种类型的约束条件与服务顾客所用车辆的特征相关。 ( 3 ) 与配送中心( 车场) 相关的约束。这类约束主要是配送中心的数目，一般 指单车场的车辆调度和多车场的车辆调度。 2 2 车辆调度问题数学模型分析 2 2 1t s p 数学模型 t s p - 般描述为：旅行商从驻地出发，经所要去的城市至少一次后返回原地，应 如何安排其旅行线路，才能使总的旅行距离( 或时间、费用等) 最少。对于现实问题， 由于限制条件的增加，t s p 可衍生出许许多多相关的问题。 一般的t s p 指一个旅行商访问所有的城市。为了便于说明问题，把旅行商问题 构造成网络图，用g = ，爿，c ) 表示，其中 y = 0 ，1 ，n 为点集，表示旅行商需要经过的城市，城市o 为旅行商出发的城市。 一= g 钏f ，；o 1 ，i n 为弧集，表示旅行商可能走过的线路段集合。 c ； q f | ( f j ) 由表示费用矩阵，c f f 表示旅行商经过对应弧段( f ，) 所花费的费用， 如时间、距离、花费等。 求解t s p 即要求在网络图g 中找到总费用最小的哈密尔顿回路，这里点o 为原 硕士学住论文 m a s t e r st h e s i s 点。定义变量如下： 南： ：瓤翳绷上 ( 2 _ 1 ) 一1 0否则 o 1 以总费用最小为目标，则目标函数为：m i n z ；勺嘞。 由于旅行商必须到达每个城市一次且只能一次，而且车辆必须回到出发点，因 此有式( 2 2 ) 和式( 2 3 ) 成立。 荟钉，1 ，川待j 而- 1 f - o 1 ，lj ，j 为了消除路径上的环路，有如下约束条件成立： 荟善陋l 一1 尺仙2 ，n 因此，t s p 完整的数学模型为： l i n z = 勺o o 磊。1 j = o ，1 ，。一，玎 篆嘞_ 1 扛0 卜。川 荟荟勺5 阱1 ，r 1 ，2 ，脚 ；0 或1 ( 2 2 ) ( 2 4 ) ( 2 6 ) 2 2 2 一般车辆调度数学模型 传统的旅行商问题( t s p ) 可以看作是一种最简单的车辆调度问题。通过扩展 旅行商数目就得到多旅行商问题( m t s p ) ，在m t s p 的基础上，给每个旅彳亍商( 车 辆) 加上容量约束( 即分配给每辆车服务顾客的需求量之和不能超过该车的载重量) 就得到了一般车辆调度问题( v r p ) 。一般车辆调度问题( v r p ) 也常常被称之为 带有容量限制的车辆调度问题( c a p a c i t a t e dv c h i c l er o u t i n gp f o b l e m ，简称c v r p ) 。 一般车辆调度问题数学模型如下： c 。：从任务点f 到任务点，的运输成本，目标不同，它的含义也有所不同，可 6 硕士学住论文 m a s t e r st h e s i s 以是距离、费用、时间等。 ，l ：n 个任务点，编号1 ，2 ，l ；编号o 作为车场的编号。 q ：代表车辆的容量上限，也可代表车辆规定的最大载重量； & ：代表任务点f 的货物运输量； 肌：m 代表完成任务需要的车辆，所可以由下式确定： + l ，其中【】表示不大于括号内数字的最大整数，a 表示车辆载重量 利用率；a 是对装车( 或卸车) 的复杂性程度及约束多少的估计，一般来讲，装( 卸) 车越复杂，约束越多，口应越小，表示一辆车所能容纳的货物量越少。实际中可通 过人机对话的决策支持系统来调整口的大小。 商n z 2 荟荟荟c _ | 酗钆“1 2 ，朋 荟，。t 一 磊强嘶，f 。1 ，2 ，川拈啦，朋 磊啄嘶，川，2 ，川拈啦，川 薹荟5 m ，胆鼢”朋 t n = 0 或lf ，= 0 ，1 ，。，l ；t = 1 2 ，一，n ，一o 或1 f = o ，1 ，- 一，n ；七= 1 2 ，” ( 2 7 ) ( 2 8 ) ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) ( 2 1 5 ) 么 。y 白 顾士学住论文 m a s t b r st h e s i s 其中z 表示总运输费用； f 1 车辆女由任务点( 或车场) f 驶向任务点( 或车场) ， 啷一1 0否则 f 1 任务点珀勺货运任务由车辆t 完成 “ l o否则 l 式2 7 表示运输费用最小的目标； 式2 8 表示车辆七承担的任务量之和不大于车辆的最大承载量； 式2 9 表示任务i 只能由一辆车完成； 式2 1 0 表示车场0 发出m 辆车； 式2 1 1 表示某一车辆最多只能到达某任务点一次； 式2 1 2 表示某一车辆最多只能从某一任务点出发一次； 式2 1 3 表示支路消去约束，即消去构成不完整的解； 式2 1 4 、2 1 5 表示整数约束。 2 2 3 带时间窗的车辆调度问题的模型 带有时间窗的车辆调度问题( v r p r w ) 是一般车辆调度问题( 冲) 的扩展问 题，即在v r p 问题的基础上给每个顾客加上服务所允许的时间段( 时间窗) 约束， v l 邛就扩展成了u 阿w 。在现实生活中，许多与时间相关的运输调度问题都可 以归结为v r p l w 问题来处理，如邮政投递问题、报童送报问题以及j r r ( j u s t i n n m e ) 模式下的物料配送问题等。由于v r p l w 具有重要的现实意义， 而其处理结果的好坏却直接影响着一个企业的效益和顾客的需求满足水平，所以近 年来v r p r w 问题受到许多领域的学者越来越多的关注【1 6 l 【1 7 】【1 8 j 。 v r p t w 可简单的描述如下：用于服务的若干车辆从配送中心出发，为处在不 同地理位置、具有不同货物需求和不同的服务的时间段( 即时间窗) 要求的所有顾 客配送货物( 提供服务) ，然后返回配送中心，其中为每个顾客仅提供一次服务。 带有时间窗的车辆调度问题的研究目标是：在为顾客提供服务时，在不违背车辆的 容量限制、顾客要求的服务时间窗口等约束条件的限制下，以最低的总成本( 通常 用路程或时间等度量) 满足所有顾客的需求。在v r p t w 问题中，时间窗是区分 v r p l w 与一般车辆调度问题的关键，为了进一步研究的需要，我们在此对时问窗 ( t i m ew i i l d o w s ) 定义如下：时间窗是指一个时间段f e l ，e 】，即顾客f 要求的最 早服务时间e z 和最晚服务时间皿；确定的一个时间区间。 硕士学位论文 m a s t e r st h e s i s 带有时间窗的车辆调度问题，由于时间窗的限制，使得该问题难度较之v r p 大大增加，如果严格按照顾客设定的服务时间为其服务，则可能使得企业的运输成 本迅速攀升；而如果允许适当地在某些顾客点有一定的延误，则可以降低运输成本， 即使对该延误现象给予一定惩罚。所以，我们可以根据企业管理决策者所要达到的 顾客服务水平和企业有限的资源两个方面加以权衡的侧重点，将带有时间窗的车辆 调度问题分为硬时间窗车辆调度问题( v c h i c l er o u l i n gp d 0 b l e mw i mh a r d1 h e w i n d o w s ，简称v r p m w ) 和软时间窗车辆调度问题( v c h i c l e r o u t i i l g p m b l e mw i t h s o f tt i m ew i n d o w s ，简称v r p s n v ) 两类。 硬时间窗车辆调度问题( v r p h t w ) 是指服务顾客的车辆在为顾客提供服务时， 不允许出现延误现象，必须在顾客设定的时间段内用尽可能低的成本满足顾客的需 求。在v r p h 1 w 中，服务顾客的车辆可以提前到达顾客所在地，即在顾客设定的 最早服务时间之前到达，但是该车辆并不能在到达时立刻为顾客提供服务，而必须 等待一直到顾客所要求的最早服务时间才能对其服务。此外，用于服务的车辆必须 在顾客设定的最晚服务时间之前到达顾客所在地，而决不允许晚于最晚服务时间。 此种问题在以j i t 模式运作的配送系统以及生产系统中是非常常见的问题，这些情 况不允许出现违背时间窗的情况。 软时间窗车辆调度问题( t p s l w ) 相对于硬时间窗车辆调度问题( v r p r r w ) ， 放松了对时间窗的约束，t p s t w 要求服务车辆应尽可能在顾客设定的时间窗内 用最低的成本为顾客提供服务，如果用于服务的某辆车在某个顾客点发生了一点延 误现象是顾客和企业可以接受的情况，则适当的延误可以降低企业的运输服务成 本。在v r p s l w 中，如果服务车辆在最早服务时间之前到达顾客所在地，那么该 车辆仍然要等待到顾客允许的最早服务时间时才能为其提供服务；而如果服务车辆 在顾客设定的最晚服务时间之后达到顾客所在地，则可能导致顾客的抱怨，影响企 业的声誉，削弱企业竞争优势。所以应尽量减少或消除延误，如果有发生，应对其 加以惩罚，惩罚的具体程度可由决策者设定。这在v r p s t w 的数学模型中，表现 为目标函数增加了一项惩罚项，它具体体现在服务成本的增加上。本文设定惩罚成 本函数为： f 凡+ a m ( e 五一薯) 毛 l 五 实际研究的带时间窗的车辆调度问题有很多种，本文研究的带有时间窗的车辆 调度问题描述如下：配送中心有若干车辆可以用来服务顾客，这些车辆从配送中心 顿士学住论文 m a s t e r st h e s i s ( 车场) 出发，对地理位置各异，货物需求量和所允许的服务访问时间( 即时间窗 【e z ，战f 】) 有一定约束的顾客进行服务，同时要求每个顾客只能用一辆车服务，同 一辆车可以服务多个顾客，且服务顾客的时间在该顾客所允许的范围内，各车辆在 服务顾客后返回车场的时间也要在车场所允许的最晚时间之前。此处我们假设配送 中心的用来服务这些顾客的车辆是同一种类型的车辆。带有时间窗的车辆调度问题 就是在以上这些约束和假设条件下研究如何最小化配送成本。 与一般车辆调度问题相比，带时间窗的车辆调度问题需要增加如下变量： s ，和巴：指到达任务点f 的时间和离开时间：f ，= e i s ；表示车辆在任务点f 的滞 留时间； 0 ：代表车辆从任务点f 到任务点j 所花费的时间。 相对于一般车辆调度问题的约束条件，对于软时间窗车辆调度问题，还需要增 加惩罚函数( 式2 1 6 ) ，硬时间窗车辆调度问题，有如下约束条件成立： q + 岛ss j f ，= 1 ，l ( 2 1 7 ) 硬时间窗车辆调度问题的目标函数与一般车辆调度问题的目标函数相同，软时 间窗车辆调度问题的目标函数需要增加惩罚函数，如下： 商n z 。荟磊荟勺+ 蔷p ( f ) ( 2 1 8 ) 以上给出的车辆调度问题的数学模型，在实际应用时可能会根据实际情况增加 新的约束条件。并且v r p l w 是一个多目标、多层次的问题，所以目标函数会根据 决策者的侧重而不同，所以应用时也会根据实际情况修正目标函数，这将在后续章 节中见到。因为车辆调度问题的多样性和复杂性，在此不一一详细的建立模型，只 是给出一个基本的数学模型。 现实生活中需要车辆调度的问题很多，如城市配送、公共交通车辆调度、动态 车队调度管理等等。不同的具体问题，车辆调度会有不用的具体要求，这些主要体 现在目标函数和约束条件上。在此不能一一描述，下面主要概述物流派送中的车辆 调度问题。 2 2 4 物流派送车辆调度数学模型 城市物流配送亦即在城市范围内的为众多用户提供的配送服务，是现代物流中 一种特殊的、综合的活动形式。城市配送中心的服务对象多是城市圈里的零售商、 硕士学住论文 m a s t e r s t h e s i s 连锁店和生产企业，一般辐射距离都不远且用汽车运输。城市配送系统是整个物流 系统的一个子系统，而且是直接对用户提供物流服务的子系统。由于服务的对象不 同，配送物品的性质不同，加上用户需求的多样化，特别是定制化服务的需求，使 得配送系统的网络结构、配送模式和服务方式业呈现多样化。正确地选择配送系统 模式和服务方式，对提高城市的物流效率和经济效益有着重要的影响【1 9 】。 在日常生活和生产实际当中，有很多物流配送问题的。如有一个中心货场，需 要向几个顾客运送货物，每个顾客对货物有一定的要求，运送货物的车辆在货场装 满货后出发，把货送到各顾客处，完成任务后返回货场，如何确定满足用户需求的 费用最小的车辆行驶线路，即送货车辆优化调度。又如，若干厂家生产一些产品， 需要运到中心仓库，车辆从仓库出发，到各厂家去装货，装满后返回仓库，在满足 厂家发货要求的情况下，按什么线路行驶，可使总费用最少，即集货车辆优化调度。 这两个问题实质是相同的，只有装货任务或只有卸货任务。在货物量较少的情 况下，用一辆车完成一项任务时，车辆不能满载，车辆的利用率低，因此可考虑用 一辆车完成多项任务。如图2 1 和图2 2 所示。 图2 1 传统运输示意图图2 2 配送运输示意图 图中正方形表示配送中心，圆圈表示货物需求点。这种将各分散用户组织起来，联 合送货的方式就具有了配送运输的基本特点，即联合送货的多用户的需求量的总和 不大于一辆车的额定载重量。现代物流业的发展，对配送过程的运输成本和时间的 有效控制越来越成为车辆调度的重要目标。配送运输具备了v r p 问题的一般特征 和优化调度条件。从上两图可见，配送运输实现了一辆车完成多个任务点的需求， 并使车辆选择优化的行车顺序，缩短运输距离，节约运输时间成为可能。 研究配送方式下的运输调度问题一般有几点前提条件： ( 1 ) 车场到任务点之间的运输距离己知； ( 2 ) 每一次车辆调度中任务点位置和任务量己知； ( 3 ) 被配送的物资可混装，不能混装需单独处理； ( 4 ) 车场有足够的运力( 可用车辆) ； 1 1 硕士学住论文 m a s t e r st h e s i s ( 5 ) 流通中心有足够的物资可配送； ( 6 ) 对带有时间窗问题的车辆调度问题，任务点的需要的服务时间范围已知； ( 7 ) 服务中的工作时间己知，即装、卸货时间已知。 配送运输调度的目标是使总的运输费用最小，其中影响总运费的最主要因子是 运输总吨公里数。配送计划中的最优派车路线，一般需符合下列基本约束条件： ( 1 ) 满足用户提出的到货时间范围的要求； ( 2 ) 满足所有任务点的品种、数量、规格需求； ( 3 ) 各配送路线的货物量不得超过车辆容积和载重量的限制，否则将会受罚； ( 4 ) 出于安全考虑，对发送车辆每天的总运行时间( 或总运行距离) 预设上限； ( 5 ) 在配送中心现有运力允许的范围内。 对实际问题，上述条件可能全部考虑，也有的考虑其中几项。配送系统有效的 调度方案应明确的得出符台实际约束条件下，应派出的车辆数量、车型、行车路线、 运行时间和到达时间。实施配送运输调度方案时，在保证服务质量的前提下，使总 的运输费用最小。 一般的物流派送车辆调度数学模型与前面所述的带时间窗车辆调度问题的数学 模型相同，不同要求或者不同侧重点的物流配送车辆调度数学模型主要在目标函数 和约束条件上不同，这些不同跟实际应用有很大的联系，有些直接体现实际应用要 求，所以在此没有必要一一描述。本文在后续讨论的车辆调度问题主要是物流派送， 讨论的数学模型也是基于物流派送问题的。因为本文只研究车辆调度，所以本文 在概念上不区分配送中心和车场、客户货物需求量和任务点运输量。 2 3 求解车辆调度问题的方法分析 车辆调度问题自提出到现在研究者已经给出了很多求解算法。下面对主要的算 法进行概述。 2 3 1 精确算法 精确算法指可求出最优解的算法，主要有：分枝定界法、割平面法、网络流算 法、动态规划法。精确算法的计算量一般随问题规模的增大而呈指数增长，所以多 用于规模较小的问题【2 0 l 。 2 3 2 启发式算法 启发式算法( h e u r i s t i ca l g o r i t h m ) 是相对于最优化算法提出的。启发式算法可以 这样定义：一个基于直观或经验构造的算法，在可接受的花费( 指计算时间、占用空 间等) 下给出待解决组合优化问题的一个可行解，该可行解与最优解的偏离程度不一 定事先可以预计。另一种定义为：启发式算法是一种技术。这种技术使得在可接受 的计算费用内去寻找最好的解，但不一定能保证所得解的可行性和最优性，甚至在 多数情况下，无法阐述所得解同最优解的近似程度。 在某些情况下，特别是实际问题中，最优算法的计算时间使人无法忍受，或因 问题的难度使其计算时间随问题规模的增加以指数速度增加，如t s p 问题，此时只 能通过启发式算法求得问题的一个可行解。启发式方法是对启发式算法的综合应 用。目前已提出的启发式算法很多，分类也相当多，但主要有以下两种： f 1 1 构造算法 根据一些原则，每一次将一个不在线路上的点增加进线路，直到所有的点都被 安排进线路为止。该类算法的每一步，把当前的线路构形( 很可能是不可行的) 跟 另外的构形( 也可能是不可行的) 进行比较并加以改进，后者或是根据某个判别函 数( 例如总费用) 会产生最大限度的节约的构形，或是以最小代价把一个不在当前 构形上的需求对象插入进来的构形，最后得到一个较好的可行构形。这类方法一般 速度快，也很灵活，但这类方法有时找到的解离最优解相差很远。 ( 2 ) 两阶段法 通过对构造算法的研究，认为由构造算法求得的解可以被进一步改进，为此学 者们提出了两阶段法。第一阶段是得到一可行解，第二阶段通过对可行解的调整， 在始终保持可行解的情况下，力图向最优目标靠近，每一步都产生另一个可行解以 代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为止。 一般第一阶段常用构造算法，在第二阶段常用的改进技术有2 一o p t ( u n ，1 9 6 5 ) 、3 - o p t ( l i nk e m i 吐a i i ，1 9 7 3 ) 【2 1 1 交换法，这是一种在解的邻域中搜索，对初始解进行某 种程度优化的算法，以改进初始解。 在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结合 到问题的求解过程中，其主要思想是：有经验的决策者具有对结果和参数的某种判 断能力，并且根据知识