（计算机科学与技术专业论文）城市物流配送车辆调度问题的研究与应用.pdf

独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究 所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 签名：哗睨蛆 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的 全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 日期：垄臣! ：2 摘要 摘要 随着世界经济的快速发展和现代科学技术的进步，物流产业作为国民经济中 一个重要的服务行业，逐渐成为国民经济发展的动脉和基础产业。车辆调度问题 作为物流配送中的一个重要环节，引起了广泛关注。车辆调度问题主要研究物流 配送中路线优化以降低物流成本。 本文首先介绍了车辆调度问题的国内外研究现状：包括车辆调度问题的构成 要素和分类，当前研究较多的车辆调度问题的模型，以及当前求解车辆调度问题 的主要算法。当前大多数研究都是基于比较简单的经典车辆调度模型和少量的实 验数据，真正适合实际物流企业的有效算法和实用软件并不多见，因此本文结合 物流企业的实际情况对车辆调度问题进行研究。实际的车辆调度问题具有复杂的 约束，除了客户的时间窗、车辆的载重以及车辆的工作时间限制等基本约束外， 车辆类型众多、包含满载客户、运力不足、客户对车型的限制以及地区通行证的 限制等都使它比一般的车辆调度问题更为复杂，因此求解也更加困难。 本文的重点是研究复杂约束条件下的车辆调度问题的算法。车辆调度问题是 一个n p 难题，针对规模较大和约束复杂的实际问题，本文选择启发式算法来求 解车辆调度问题的近似最优解。提出基于多次聚类的路线划分和车辆分配算法来 求解复杂约束条件下的车辆调度问题，该算法结合了聚类算法与节约算法的优 点，同时使用改进的时间窗算法来提高车辆的利用率、使用单路线优化算法对送 货顺序进行优化，并解决了大客户分配多车次以及多车次客户商品精确分装等问 题。论文在s o l o m o n 经典数据上对算法进行了测试和分析。 本文最后描述了复杂约束条件下的车辆调度算法的软件实现。该软件在实际 物流企业中得到了应用并取得了良好的效果，本文选择企业的一个典型案例对该 软件的实际应用结果进行了分析。 关键词物流配送；车辆调度；复杂约束；聚类算法；节约算法 a b s t r a c t 蔓曼皇ii i 曼曼皂! 曼曼曼曼皇曼曼曼! ! 曼! 鼍曼鼍曼皇皇 a b s t r a c t a c c o m p a n i e dw i t ht h er a p i dd e v e l o p m e n to ft h ew o r l d se c o n o m ya n dt h eg r e a t p r o g r e s so fm o d e ms c i e n c ea n dt e c h n o l o g y , l o g i s t i c si n d u s t r yh a sb e c o m et h ea r t e r y a n df o u n d a t i o nt ot h ed e v e l o p m e n to fn a t i o n a le c o n o m y a sa ni m p o r t a n tp a r to f l o g i s t i c s ，t h ev e h i c l es c h e d u l i n gp r o b l e m s p ) h a sa t t r a c t e dw i d ea t t e n t i o n v s p m a i n l ys t u d yh o w t op l a nt h ev e h i c l er o u t ei no r d e rt or e d u c et h et r a n s p o r t a t i o nc o s t t h i sd i s s e r t a t i o nf i r s t l yi n t r o d u c e st h er e s e a r c hs t a t u so fv s p ：t h ec o m p o s i t i o n e l e m e n t so fv s pa n dd i f f e r e n tc l a s s i f i c a t i o n so fv s pa r ep r o v i d e d ，t h ev s pm o d e l s m o s t l yr e s e a r c h e da n dt h em a i nv s pa l g o r i t h m sa r ei n t r o d u c e d m o s to ft h ec u r r e n t r e s e a r c h e sa r eb a s eo nr e l a t i v e l ys i m p l ec l a s s i cv s pm o d e l sa n das m a l la m o u n to f e x p e r i m e n t a ld a t a t h e r ea r er a r ee f f e c t i v ea l g o r i t h m sa n dp r a c t i c a ls o f t w a r ef o r a c t u a ll o g i s t i c s c o m p a n i e s s ot h i sd i s s e r t a t i o nc o m b i n e st h e a c t u a ls i t u a t i o no f l o g i s t i c se n t e r p r i s et os t u d i e sv s et h ep r a c t i c a lv s ph a v em o r ec o m p l i c a t e d r e s t r i c t i o nt h a ng e n e r a lv s p , i na d d i t i o nt ot h ec u s t o m e r st i m ew i n d o w , v e h i c l e s c a p a c i t ya n d w o r kt i m el i m i tr e s t r i c t i o n , i ta l s oh a sr e s t r i c t i o n sl i k em u t i - t y p ev e h i c l e s ， f u l l - l o a d e dc u s t o m e r s ，i n s u f f i c i e n tc a p a c i t y , v e h i c l et y p er e s t r i c t i o n , t r a f f i cp e r m i to n ， a n ds oo n i ti sm o r ed i 街c u l tt os o l v ea c t u a lv s p 、 f o c u so ft h i sd i s s e r t a t i o ni st o s t u d yt h ea l g o r i t h mf o rv s p 、 ，i t i lc o m p l i c a t e d r e s t r i c t i o n s a sv s pi sn pc o m p l e x i t y , t h i sd i s s e r t a t i o nu s e s h e u r i s t i ca l g o r i t h mt o f m da p p r o x i m a t eb e s ts o l u t i o nf o rt h i sp r o b l e m t h i sd i s s e r t a t i o np r e s e n t sar o u t e d i s t r i b u t i o na n dv e h i c l ea l l o c a t i o na l g o r i t h mb a s e do nm u l t i p l ec l u s t e r i n g ，w h i c h c o m b i n e st h ea d v a n t a g eo fc l u s t e r i n ga l g o r i t h mw i mt h ea d v a n t a g eo fs a v i n g a l g o r i t h m t h ea l g o r i t h ma l s op r o v i d e sa d v a n c e dt i m ew i n d o wa l g o r i t h mt oi m p r o v e t h eu t i l i z a t i o no fv e h i c l e sa n db s e ss i n g l er o u t eo p t i m i z a t i o na l g o r i t h mt oo p t i m i z et h e d e l i v e r yo r d e ra n dt h ea l g o r i t h ms o l v e st h ep r o b l e m 丽t l lb i gc u s t o m e r sn e e ds e v e r a l v e h i c l et r i p sa n dd i s t r i b u t et h e i rg o o d sp r e c i s e l yt ot h e s et r i p s t h ea l g o r i t h mi st e s t e d a n da n a l y z e do ns o l o m o nb e n c h m a r kp r o b l e m s f i n a l l y , t h i sd i s s e r t a t i o ni n t r o d u c e st h ei m p l e m e n to ft h es o f t w a r ef o rv r pw i t h c o m p l i c a t e dr e s t r i c t i o n su s i n gt h ea l g o r i t h mp r e s e n t e d t h es o f t w a r eh a sb e e na p p l i e d i na c t u a ll o g i s t i c sc o m p a n ya n do b t a i n e ds a t i s f i e dr e s u l t s t h i sd i s s e r t a t i o nc h o s ea t y p i c a lc a s eo ft h i sc o m p a n yt oa n a l y z et h er e s u l to ft h i ss o f t w a r e k e yw o r d sl o g i s t i c sd i s t r i b u t i o n ；v e h i c l er o u t i n gp r o b l e m ；c o m p l i c a t e dr e s t r i c t i o n ； c l u s t e r i n ga l g o r i t h m ；s a v i n ga l g o r i t h m i i i i v 目录 曼! 曼蔓舅璺曼i i ；i ；i i i i n i l 一_ 一一一i 目录 摘要i a b s t r a c t i i i 第1 章绪论1 1 1 研究背景l 1 1 1 物流1 1 1 2 配送2 1 2 课题来源。3 1 3 论文主要工作：3 第2 章车辆调度问题综述5 2 1 车辆调度问题。5 2 2 车辆调度问题的构成要素与分类一5 2 2 1 车辆调度问题的构成要素5 2 2 2 车辆调度问题分类8 2 3 车辆调度问题的模型。9 2 4 车辆调度问题算法研究综述_ 1 1 2 4 1 精确算法1 1 2 4 2 启发式算法1 2 2 4 3 亚启发式算法13 2 5 本章小结15 第3 章复杂约束条件下车辆调度问题算法的研究1 7 3 1 问题提出1 7 3 2 数学模型：17 3 3 算法研究：o 2 0 3 3 。1 传统节约算法。2 0 3 3 2 传统聚类算法2 3 3 3 3 基于多次聚类的路线划分和车辆分配算法2 4 3 3 4 聚类算法的应用2 4 3 3 5 改进的时间窗算法乙2 6 3 3 6 单路线优化算法2 6 3 3 7 大客户车辆分配优化算法2 8 3 3 8 商品分装算法2 9 v 北京工业大学工学硕士学位论文 3 3 9 算法实例分析2 9 3 4 本章小结3 8 第4 章复杂约束条件下车辆调度问题软件实现3 9 4 1 软件开发概述- 3 9 4 2 软件功能3 9 4 3 软件设计与实现4 0 4 3 1 软件与外部接口4 0 4 3 2 软件类设计：一j 4 1 4 3 3 软件总流程4 2 4 3 4 时间计算：。4 4 4 3 5 改进的时间窗算法的实现一4 6 4 3 6 大客户车辆分配优化算法的实现。4 7 4 4 本章小结。：4 8 第5 章实际应用4 9 5 1 朝批车辆调度问题4 9 5 2 典型案例分析4 9 5 2 1 案例数据：4 9 5 2 2 计算结果5 3 5 2 3 与手工排车比较5 8 57 3 软件实际应用分析5 9 5 3 1 车辆数预测方法一5 9 5 3 2 实例分析一6 0 5 4 本章小结6 6 结j 仑6 7 参考文献6 9 攻读硕士学位期间取得的研究成果7 3 致j 射。7 5 v i 第1 章绪论 1 1 研究背景 1 1 1 物流 第1 章绪论 物流活动的历史也许和人类的历史一样长，但对物流研究的历史却很短。在 我国国家标准物流术语的定义中指出：物流是“物品从供应地到接收地的实 体流动中，根据实际需要，将运输、储存、装卸、搬运、包装、流通加工、配送、 信息处理等基本功能实施有机结合来实现用户要求的过程。 它的目的是提高企 业的收益，它的任务是以尽可能低的成本为顾客做出最好的服务，它的方法是在 恰当的时间、在恰当的地点、以恰当的方式向顾客提供恰当数量的服务。 随着世界经济的快速发展和现代科学技术的进步，物流产业作为国民经济中 一个重要的服务行业，正在全球范围迅速发展，并逐渐成为国民经济发展的动脉 和基础产业，其发展程度已成为衡量一个国家现代化程度和综合国力的重要标志 之一。在经济日益全球化的今天，物流作为“第三个利润源泉 正受到日益广泛 的重视，并面临着前所未有的发展机遇。 目前我国的物流业尚处于起步阶段，与发达国家存在很大差距，最突出的问 题是物流成本较高。国家发展与改革委员会、国家统计局和中国物流与采购联合 会联合发布的 2 0 0 9 年全国物流运行情况通报显示，2 0 0 9 年全国社会物流的 总费用为6 0 8 万亿元，同比增长了7 2 ，与g d p 的比率为1 8 1 ，同比持平【1 1 。 这意味着我国实现1 0 0 元g d p 的产值，就需付出1 8 1 元的物流成本。而美国、 德国、日本等发达国家物流的总费用与g d p 的比率只有8 左右，这说明中国物 流业的整体水平严重落后于发达国家。过高的物流成本，制约了国民经济的发展， 削弱了企业的市场竞争能力。按2 0 0 9 年g d p 总量3 3 5 3 5 3 万亿元计算，我国物 流成本占g d p 的比重每降低1 个百分点，则可以节约资金3 3 5 3 亿元，如果我国 能逐步达到发达国家的平均物流成本( 物流成本占g d p 的1 0 ) ，那就意味着将 带来近2 7 万亿元的社会效益。因此通过提高物流管理水平和效率，降低物流成 本，可以为企业及社会带来可观的经济效益，改善国民经济运行效率，提高国际 竞争力。 在经济全球化和信息化的浪潮下，当代物流行业飞速发展，已成为促进国民 经济发展的重要新兴行业。现代物流相对于传统物流来说是一种革命性的突破， 现代物流追求的目标是高质量高效率的服务。采用高科技手段，实现物流配送的 信息化、智能化和自动化是必然的发展方向。 北京工业大学工学硕士学位论文 1 1 2 配送 物流配送是物流中一个重要的直接与消费者相连的环节，是货物从物流结点 送达收货人的过程。配送是在集货、配货基础上，按货物种类、品种搭配、数量 和时间等要求所进行的运送，是“配 和“送”的有机结合。物流配送过程主要 包括：从生产工厂进货并集结的集货作业；根据各个用户的不同需求，在配送中 心将所需要的货物挑选出来的配货作业；考虑配送货物的重量和体积，充分利用 车辆的载重和容积的车载货物的配装以及配送路线的确定【2 1 。优化物流运输，降 低运输成本，提高物流配送水平是企业尤其是物流配送企业提高企业竞争力的有 效途径之一。 在物流的各项成本中，配送成本占了相当高的比例。物流费用包括运输费用、 保管费用和管理费用三部分，2 0 0 9 年全国物流的总费用中运输费用3 3 6 万亿元， 占社会物流的总费用的比重为5 5 3 ；保管费用2 万亿元，占社会物流的总费用 的比重为3 2 8 5 ；管理费用o 7 2 万亿元，占社会物流的总费用的比重为1 1 9 。 可见运输费用是影响物流成本的重要因素。美国的运输成本仅占到其g d p 的不 到6 ，日本也仅为6 5 ，而我国运输成本占到g d p 的1 0 。因此降低运输成 本对于节省物流费用，提高经济效益具有重大的作用。 车辆调度是物流企业完成物流配送过程中的一项重要工作。配送车辆调度的 合理与否对配送速度、成本、效益影响很大。采用科学、合理的方法来进行配送 车辆调度，是物流配送中非常重要的环节。近年来，由于订单更小、更频繁、需 求不断变化且更加用户化，大型物流企业传统的手工模式车辆调度已经无法适应 现代物流小批量、多批次的发展需求。如何按时按量、经济高效地配送商品，在 很大程度上取决于有效的车辆调度安排。 长期以来，我国的物流配送多以人工调度为主。人工调度不能满足现代物流 企业的需求是因为人工调度具有以下不足：首先，人工调度对于调度人员来说， 工作强度很大，同时随着物流公司规模的不断壮大，客户的需求和配送车辆数都 不断增多，到一定规模人工就难以完成整个公司的车辆调度；其次，调度人员对 所有车辆的状态，以及整个城市的交通状况把握不是很准，难以对所有的资源进 行全局优化，车辆的时空利用率不高；第三，人工调度还容易出现超载超时等违 反约束现象；另外，人工调度还受人员的限制，一旦调度人员不能工作，将会影 响整个公司的运营【3 】。因此越来越多的物流公司致力于建立智能车辆调度系统来 取代手工调度。 作为物流配送优化系统中的关键一环，车辆调度问题( 又称车辆路径问题) 的 研究受到人们广泛关注。该问题由d a n t z i g 和r a m s e l ：于1 9 5 9 年首先提出，经过 近五十年的研究，已成为运筹学与组合优化领域的前沿和研究热点课题。多年来， 2 第1 章绪论 国内外数学、计算机、运输、物流等各方面的专家学者都在致力于车辆调度算法 的研究和软件的开发，并在理论上和实际应用中取得了很大进展，但由于实际问 题的复杂性，大多数研究都是基于比较简单的经典调度模型和少量的实验数据， 真正适合实际物流企业的有效算法和实用软件并不多见，特别是国内大型物流企 业在这方面的应用至今几乎还是空白。 1 2 课题来源 本课题的研究来自己于北京朝批商贸有限公司( 以下简称朝批) 的实际需求。 朝批是华北地区最大的副食品批发公司，拥有1 1 家子公司，其网络覆盖北京、 天津、唐山、青岛等地，并拥有总面积约1 8 万平方米的现代化物流配送中心， 年吞吐量达9 0 0 0 万件。它处于供应链的中间环节，上游是遍布国内2 9 个省市自 治区的名优商品生产厂家和十余个国家和地区的世界知名品牌生产厂家，经营品 牌4 0 0 余个，品种9 0 0 0 余种，下游的销售网络覆盖了北京地区的大中型零售连 锁企业及3 0 0 0 余个人口稠密社区的小型店铺。在立足北京的前提下，朝批也逐 渐开发各地物流市场，先后在天津、石家庄、青岛、唐山等地建立子公司，在环 渤海地区开拓更大的物流业务。在这种发展势头下，朝批目前手工排车时间长已 经成为物流工作的瓶颈。 本课题来源于一家真实的物流企业，目的在于研究开发适合于实际物流企业 车辆调度问题的有效算法和实用软件。 ， 1 3 论文主要工作 本章介绍了课题的研究背景与课题来源。在研究背景中给出了物流、配送以 及车辆调度的相关概念和联系，以及它们对于增强经济效益的重要作用。在课题 来源中介绍了课题研究基于的企业北京朝批商贸有限公司。本论文的研究内 容以及其它章节的安排如下： 第2 章主要介绍车辆调度问题的概念、构成要素、分类以及国内外研究现状。 首先给出了车辆调度问题的定义；详细介绍了车辆调度问题的构成要素；对车辆 调度问题的各种分类方法进行了概述。接着介绍了当前国内外研究较多的车辆调 度问题的模型。最后对车辆调度问题的算法进行了综述，包括精确算法和启发式 算法两大类，并介绍了比较常见的亚启发式算法。 ， 第3 章研究复杂约束条件下车辆调度问题的算法。首先介绍复杂约束条件下 的车辆调度问题，归纳了该问题的复杂约束。接着介绍了该问题的数学模型。最 后对该问题的算法进行了研究：首先介绍了传统节约算法与传统聚类算法，提出 使用基于多次聚类的路线划分和车辆分配算法来求解复杂约束条件下车辆调度 北京工业大学工学硕士学位论文 问题；接着对多次聚类的路线划分和车辆分配算法中使用的聚类算法、改进时间 窗算法、单路线优化算法、大客户车辆分配算法以及商品分装算法分别进行了阐 述；最后在经典的s o l o m o nb e n c h m a r kp r o b l e m s 上对算法进行了实例测试和分 析。 第4 章介绍复杂约束条件下的车辆调度问题软件的实现。首先介绍该软件要 实现的功能。然后描述该软件的设计和实现：包括软件与外部接口设计，软件的 类设计，软件的总流程，以及软件的部分具体实现：即路程时间和客户停留时间 的计算方法，改进时间窗算法的实现，以及大客户车辆分配算法的实现。 第5 章主要介绍复杂约束条件下车辆调度软件的实际应用结果，该软件在朝 批得到应用并取得了不错的效果。首先介绍了朝批车辆调度问题的特点。接着选 择朝批车辆调度中的一个典型案例来说明朝批车辆调度问题的特点以及该软件 的运行效果，并与手工排车结果进行了比较。最后对该软件在实际应用中的结果 进行分析，提出了一种车辆数的预测方法，并使用该方法对朝批7 0 个批次的自 动排车数据以及投入数据进行分析。 论文最后给出了研究的结论和对后续研究工作的展望。 4 第2 章车辆调度问题综述 1|,mi i i i 一o ! ! 曼! 曼! ! 曼! 曼苎曼! 曼鼍曼曼! 曼曼皇曼曼皇皇! 曼曼曼曼曼曼蔓曼曼曼曼皇曼鼍皇! 曼曼曼曼蔓毫 第2 章车辆调度问题综述 2 1 车辆调度问题 车辆调度问题是由d a n t z i g 和r a m s e r 4 】于1 9 5 9 年首次提出的，通常指的是： 对一系列发货点和收货点，调用一定的车辆，组织适当的行车路线，使车辆有序 地访问它们，在满足特定的约束条件( 如：货物的需求量与发货量、交发货时间、 车辆载重限制、车辆行驶里程限制、车辆行驶时间限制等) 下，力争实现一定的 目标( 如车辆行驶里程最短、运输总费用最低、使用时间最少、使用的车辆数最 少等) 【5 j 。一般来说，不考虑时间要求仅根据空间位置安排线路的问题，称为车 辆路径问题( 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 es c h e d u l i n gp r o b l e m ，简称v s p ) 。对于v r p 与v s p ， 也有不区分两者的，有具体约束时则加上定语，如将有时间要求的车辆调度问题 称为v e l l 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 。本文将这两类问题统称为车辆 调度问题。 2 2 车辆调度问题的构成要素与分类 2 2 1 车辆调度问题的构成要素 车辆调度问题主要包括客户、货物、车辆、配送中心、运输网络、约束条件 和目标函数等要素1 6 1 7 1 。 1 ) 客户 客户可以是实际车辆调度问题中任意类型的服务对象，例如零售商店、分销 点等。客户的属性包括需求货物的数量、需求货物的时间及需求货物的次数等。 在某次配送计划中，某个客户需求货物的数量可能小于车辆的最大装载量， 也可能大于车辆的最大装载量；全部客户总的货物需求量可能低于全部车辆的总 装载量，也可能超过全部车辆的总装载量。当客户的货物需求量超过车辆的最大 装载量时称为满载客户，当全部车辆的总装载量大于全部客户总的货物需求量时 表示配送中心运力充足。当前研究的车辆调度问题一般都假设配送中心运力充足 以及没有满载客户。 某个客户需求货物的时间，是指要求将货物送到的时间，对配送时间的要求 可以分为以下几种： a ) 无时间限制； 北京工业大学工学硕士学位论文 b ) 硬时间窗限制：要求在指定的时间区间( 也称为时间窗) 内完成配送任务， 否则客户将不接受服务； c ) 软时间窗限制：有时间限制，但可以不遵守，不遵守时要给予一定的惩 罚。 某客户需求货物的次数可能仅有一次，即只需一次配送服务；也可能为多次， 即需要多次配送服务。 客户的其它属性可能还包括客户对送货车辆型号的限制等。 2 1 货物 货物是配送的对象；可以将每个客户需求的货物看成一批货物。每批货物包 括名称、包装、重量、体积、要求送到的时间和地点、能否分批配送等属性。 货物的名称和包装，是选用配送车辆的类型以及决定该批货物能否与其它货 物装在同一车内配送的依据。例如，一些货物因性质特殊需要使用专用车辆配送； 一些货物因性质特殊不能与其他货物装在同一车内。 货物的重量和体积是进行车辆装载决策的依据。当某个客户需求的货物的重 量或体积超过配送车辆的最大装载重量或容积时，则该客户需要多辆车进行配送 或者一辆车多次配送。 帮货物要求送到的时间和地点是制定车辆的出行时间和配送路线的依据。 允许货物分批配送，。是指即使某个客户的货物需求量小于车辆的装载量，也 可以把该客户的货物拆分成多批，使用多辆车分批配送。 e3 ) 车辆 车辆是运载货物的工具，其主要属性包括：车辆的类型、装载量、成本、一 次配送的最大行驶距离或最长工作时间、配送前的停放位置以及完成任务后的停 放位置等。 车辆的类型有通用车辆和专用车辆之分，专用车辆适于装运一些性质特殊的 货物，通用车辆适于装送大多数普通货物。也可以根据车辆的大小、装载能力或 不同的使用成本把车辆划分为不同的类型。 车辆的装载量指的是车辆的最大装载重量和最大装载容积，是进行车辆装载 决策的依据。 车辆的成本包括使用车辆的固定成本以及可变成本，可变成本可以是单位公 里的费用或单位时间的费用等。 对每台车辆一次配送的行驶距离或工作时间的要求可以分为以下几种情况： a ) 无限制； b ) 有限制； c ) 有限制，但可以不遵守，不遵守时需给予惩罚，如另付加班费等。 车辆在配送前的停放位置可以在某个停车场、配送中心或客户所在地。 6 第2 章车辆调度问题综述 i i u l 曼蔓曼曼曼曼曼曼曼曼! ! ! ! 篡曼苎曼曼! ! 苎! 曼曼! ! 曼曼曼! ! 曼! 曼鼍曼曼皇曼鼍曼曼曼曼曼曼曼曼皇曼曼曼! 曼曼曼曼鼍 车辆完成配送任务后，对其停放位置的要求可以分为以下几种情况： 幻必须返回出发点； b ) 必须返回某停车场； c ) 可返回任意的停车场； d ) 可停放在任何停车场、配送中心或客户所在地。 4 _ ) 配送中心 配送中心是进行集货、分货、配货、配装、送货作业的地点，也可以指具有 相似功能的物流中心、仓库等。 在某配送系统中，配送中心的数量可以只有一个，也可以有一个以上； 某个配送中心供应的货物数量可能能够满足全部客户的需求，也可能仅能满 足部分客户的需求。 5 ) 运输网络 运输网络是由顶点( 指配送中心、客户或停车场) 、无向边和有向弧组成，边 或弧表示客户与车场或者客户与客户之间的道路连接。边、弧的属性包括方向、 权值和交通流量限制等。 某运输网络中可能仅包含无向边；也可能仅包含有向弧；还有可能既包含无 向边，又包含有向弧。有向弧表示车辆仅可以向一个方向行驶的道路，比较典型 的是城市交通网络中单向行驶的车道；无向边表示车辆可以在两个方向上行驶的 双向车道。 ， 运输网络中边或弧的权值可以表示距离、时间或费用。根据节点间双向费用 权重是否相等，可以将车辆调度问题分为对称车辆调度问题和非对称车辆调度问 题。边或弧的权值变化分为以下几种情况： a ) 固定，不随时间和车辆的不同而变化； b ) 随时间不同而变化； c ) 随车辆不同而变化； d ) 既随时间不同而变化，又随车辆不同而变化。 对运输网络权值间的关系可以要求其满足三角不等式，即两边之和大于第三 边；也可以不要求。 对运输网络中顶点、边和弧的交通流量要求分为以下几种情况： a ) 无流量限制； b ) 边、弧限制，即每条边、弧上同时行驶的车辆数有限制； c ) 顶点限制，即每个点上同时装、卸货的车辆数有限制； d ) 边、弧和顶点都有限制。 6 ) 约束条件 约束条件是进行车辆调度时必须考虑和满足的一些限制条件。车辆调度问题 7 北京工业大学工学硕士学位论文 应满足的约束条件主要包括： a ) 满足所有客户对货物品种、规格和数量的要求； b ) 满足客户对货物送达时间范围的要求； c ) 车辆在配送过程中的实际载货量不得超过车辆的最大允许装载量； d ) 车辆的行驶距离或者工作时间满足要求； e ) 在允许通行的时间进行配送( 如有时规定某个时段某些路段货车不能通 行等) ； f ) 在配送中心现有运力范围内。 7 ) 目标函数 对于车辆调度问题，可以只选用一个目标，也可以选用多个目标。经常选用 的目标函数主要有以下几个： 配送的总里程最短。配送里程与配送车辆的耗油量、磨损程度以及司机 的疲劳程度等直接相关，它直接决定运输的成本，对配送业务的经济效 益有很大影响。由于配送里程计算简便，它是确定配送路线时用得最多 的目标； 配送车辆的吨位公里数最少。该目标将配送距离与车辆的载重量结合起 来考虑，即以所有配送车辆的吨位数( 最大载重吨数) 与其行驶距离的 乘积的总和最小作为目标； 使用车辆数最少。许多车辆调度问题都把使用车辆数最少作为首要目标； 层次化优化目标函数，以车辆数最少作为首要的优化目标，在此基础上 优化对应的车辆行驶距离； 准时性最高。由于客户对交货时间有较严格的要求，为提高配送服务质 量，有时需要将准时性最高作为确定配送路线的目标； 运力利用最合理。该目标要求使用较少的车辆完成配送任务，并使车辆 的满载率最高，以充分利用车辆的装载能力； 劳动消耗最低。即以司机人数最少、工作时间最短作为目标； 综合费用最低。降低综合费用是实现配送业务经济效益的基本要求。在 配送业务中，相关的费用包括：车辆维护和行驶费用、车队管理费用、 货物装卸费用、有关人员工资费用等。 2 2 2 车辆调度问题分类 车辆调度问题涉及的因素众多，在目标和范围方面有很大差别，根据研究的 目标和限定条件不同，车辆调度问题可以进行多种分类。自从车辆调度问题被提 出以来，l i n u s ( 1 9 8 1 ) 【3 】，b o d i n 和g o l d e n ( 1 9 8 1 ) t g i ，b o d i n ( 1 9 8 3 ) 1 1 0 1 ，a s s a d ( 1 9 8 8 ) 1 ， 8 曲 m d d d d 酚吣 第2 章车辆调度问题综述 曼曼曼曼! 曼基曼曼鼍曼曼皇i i i 一_ 一_ 一一 一i i i i 一一, 曼曼皇曼曼皇皇曼蔓蔓曼皇! 曼曼曼蔓曼蔓曼曼曼曼曼! 曼量 l e n s t r a 和s a v e l s b e r g h ( 1 9 9 0 ) t 1 2 】等许多学者对车辆调度问题从不同角度，按不同 的标准进行了分类。 1 ) 按任务特征分，有纯装货问题( 仅考虑把客户的货物送到物流中心) 或纯 卸货问题( 仅考虑把货物从物流中心送到客户处) 及装卸混合问题( 既要把 货物从物流中心送到客户处，还要从客户处提取货物送回物流中心) ； 2 ) 按车场( 或货场、配送中心) 数目分，有单车场问题和多车场问题： 3 ) 按车辆类型分，有单车型问题( 所有车辆容量相同) 和多车型问题( 执行任 务车辆的容量不全相同) ； 4 ) 按车辆对车场的所属关系分，有车辆开放问题( 车辆可以不返回其出发车 场) 和车辆封闭问题( 车辆必须返回其出发车场) ； 5 ) 按客户对接受服务时间的要求分，分为无时间窗约束的车辆调度问题和 有时间窗约束的车辆调度问题( 客户要求在规定的时间内把要求的货物 送达或者将供应的货物取走) ； 。 6 ) 按优化目标数来分，有单目标问题和多目标问题； j 7 ) 按车辆载货状况分，有满载问题( 客户的货运量大于车辆的容量，完成一 项任务需要不只一辆车) 、非满载问题( 客户的货运量小于车辆容量，完 成一项任务只需一辆车或者多项任务共用一辆车) 以及满载和非满载混 合问题( 部分客户的货运量大于车辆容量需要多辆车配送，另一部分客户 的货运量小于车辆容量只需一辆车完成配送，造成一些配送车辆需要满 载运行，而另一些车辆则处于非满载状态) ； 8 ) 按客户、车辆、运输网络等属性信息是否确定，可分为静态问题( 客户、 车辆或运输网络等属性全部已知并且固定不变) 和动态问题( 客户、车辆 或运输网络等属性中，有的信息未知或会发生变化) 。 2 3 车辆调度问题的模型 按照不同的研究重点，车辆调度问题可以分为不同的模型1 1 3 】： 1 ) 有能力约束的车辆调度问题( c a p a c i t a t e dv 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 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 , v r p ”聊 此模型在c v r p 模型的基础上加入了客户时间窗约束，使得该问题更贴近实 9 北京工业大学工学硕士学位论文 际情况，同时也增加了问题的求解难度。该模型是目前研究最多的模型，许多亚 启发算法都是针对该模型提出的。客户时间窗约束是指每个客户接受车辆服务的 最早服务时间和最晚服务时间，分为软时间窗和硬时间窗两种。 3 ) 带取送货的车辆调度问题( v e h i c l er o u t i n gp r o b l e mw i t l lp i c k - u pa n d d e l i v e r y , v r p p d ) 这种模型又分好两种情况：一种是客户不仅需要货物，还要返回货物( 如物流 行业中的客户退货) ，通常假设返回的货物不在客户间交换，而是直接返回仓库； 另一种情况是需要从取货点的客户那里取得货物，并送到相应的送货点客户，这 些客户要配对出现在同一辆车上，同时客户间的顺序有前驱后继关系。 4 ) 周期性的车辆调度问题( p e r i o d i cv e h i c l er o u t i n gp r o b l e m ，p v r p ) p v r p 问题是对v r p 问题的扩展，v r p 问题研究的是对车辆的日安排，而 p v r p 研究的是对车辆一个周期内多个日期的安排。在一个周期内，客户在满足 需求的情况下，可以被多次服务，但至少被服务一次。 5 ) 多仓库车辆调度问题( m u l t i d e p o tv e h i c l er o u t i n gp r o b l e m ，m d v r p ) 在城市物流体系中，往往存在多个配送中心，多个配送中心分布在不同的区 域，其求解比单仓库的车辆调度问题要复杂。通常假设从某个仓库出发的车辆仍 返回该仓库。对该问题的求解主要包括两种方法：一种是将多仓库车辆调度问题 转化为单仓库车辆调度问题，另一种是直接将多仓库车辆调度问题看作一个复杂 的组合优化问题进行求解。目前的研究主要集中在前一种方法上，该方法的研究 重点是多仓库的分离策略( 如何把客户分配给各个仓库) 和最后解的优化组合方 案选择上【1 4 1 。 6 ) 多车型车辆调度问题( m u l t i p l ev e h i c l er o u t i n gp r o b l e m ，m v r p ) 一般的车辆调度问题为了研究方便，、都假设所有车辆为同一类型，而在实际 生活中，一个公司往往拥有多种类型的车辆，各种类型的车辆具有不同的装载能 力、不同的单位运行费用，使用不同的车辆具有不同的固定成本，因此多车型车 辆调度问题比一般的车辆调度问题更为复杂【1 5 】。 7 ) 动态车辆调度问题( d y n a m i cv e h i c l er o u t i n gp r o b l e m ，d v r p ) 动态车辆调度问题是指在车辆、客户需求以及道路网络状态等信息实时更新 的情况下，安排车辆配送路径的车辆调度问题。由于客观世界存在着大量的不确 定性，反映在车辆调度问题中，主要有不确定的货物需求量、不确定的货物需求 时间、交通拥堵、车辆故障等。这些不确定的信息随着时间的推移而出现，影响 已安排好的车辆配送路径，需要做出及时的调整。因此动态车辆调度问题更符合 实际情况，对该问题的研究也引起了更多学者的关注。 8 ) 其它模型 除了以上几种基本模型外，还包括其它一些衍生模型，如：随机车辆调度问 l o 第2 章车辆调度问题综述 题、模糊车辆调度问题、非对称网络车辆调度问题、开放式车辆调度问题、动态 网络车辆调度问题【1 6 】等； 2 4 车辆调度问题算法研究综述 自从车辆调度问题提出以来，国内外对车辆优化调度问题作了大量而深入的 研究。早在1 9 8 3 年b o d i n ，g o l d e n 等人在他们的综述文章中就列举了7 0 0 余篇 有关文献。在c h r i s t o f i d e s ( 1 9 8 5 ) ，g o