（机械电子工程专业论文）基于google+maps+api的物流配送车辆调度系统设计与研究.pdf

基于g o o g l em a p sa p i 的物流配送车辆调度系统设计与研究 摘要 在现代物流配送领域中，缘于降低运输成本、提高客户服务水平的要求， 车辆调度问题一直都是物流理论与实践所关注的焦点。在电子商务环境下，运 输调度者必须借助信息技术手段，全面及时地掌握运输各环节的动态信息，通 过车辆调度算法合理制定车辆运输策略，或实时调整在途车辆运输路线，以最 小成本完成运输任务。车辆调度问题目前尚有许多值得深入研究之处，例如如 何将网络地理信息系统w 曲g i s 技术融入到物流配送系统中，以提供车辆调度 过程中涉及到的地理信息，以及如何结合简单高效的车辆调度策略和算法来完 成物流配送任务。 本文针对课题的要求设计并实现了物流配送车辆调度系统。首先，通过对 车辆调度问题研究背景、国内外发展研究现状的分析阐述，确定研究内容；其 次，在界定本文需要解决的车辆调度问题并分析了解决该问题所需相关技术 后，确定了本系统的总体结构及工作原理，结合g o 0 9 1 em 印sa p i 技术设计出 了作为物流配送车辆调度的基础平台，包括基础信息数据维护功能和地理信息 分析、计算、显示等功能，实现了w - e b g i s 技术和物流系统的结合；再次，根 据课题任务建立了物流配送车辆调度的静态、动态数学模型，并提出了基于模 拟退火遗传算法的静态调度方案和根据实时客户需求信息调整车辆路线的动 态调度方案，并通过实验方法验证了调度方案的可行性；最后，给出了系统工 作内容、流程和展示操作界面。 关键词：物流配送车辆调度g o o g l em 印sa p i 模拟退火遗传算法 t d e s i g na n ds t u d yo fl o g i s t i c sd e l i v e r y v e h i c l ed i s p a t c h i n gs y s t e mb a s e do n g o o g l em a p sa p i a b s t r a c t i nt 1 1 em o d e m1 0 9 i s t i c sd e l i v e 巧f i e l d ，“et ol o w e r 仃a n s p o n i o nc o s t sa n d i m p r o v ec u s t o m e rs e r v i c e1 e v e l ，ac l a s so fd i 佑c u l tc o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m sk n o w na sv e h i c l er o u t i n gp r o b l e m ( v r p ) h a sa l w a y sb e e nt h ef o c u si n t h el o g i s t i c ss t u d ya n d p r a c t i c e a tt h ea g eo fe c o m m e r c e ，i t se s s e n t i a lf o rv e h i c l e d i s p a t c h e r st oo b t a i nr e a l t i m ei n f o m a t i o ni m m e d i a t e l yi nt h ee n t i r et r a n s p o n i o n 1 i m ( m r o u 曲c o 姗u n i c a t i o na n di n f o m a t i o nt e c h n o l o g i e s ，s oa st om a k ee f j f i c i e m t r a n s p o r t i o np l a n sw i mc o m p u t e r - a i d e dv e h i c l er o u t i n ga l g o r i t h m s ，o ra d j u s t i n - t r a n s i tv e h i c l e 咖n s p o r t i o nr o u t e si m m e d i a t e l yt os a t i s 矽c u s t o m e r s d e m 觚d s 1 1 1 e r ea r es t i l ls o m ea s p e c t so rp r o b l e m sw h i c ha r ew o n h y s t u d y i n g 如r d l e ri nv r p f i e l d ，s u c ha sh o w t oi n t e g r a t ew e b g e o g r a p h i ci n f o m a t i o ns y s t e m ( w 曲g i s ) w i m l o g i s t i c sd e l i v e 巧s y s t e mt op r o v i de f f e c t i v eg e o g r 印h i ci n f o m l a t i o nm a n a g e m e n t a n dg e o 鲫h i cd e c i s i o n - m a k i n ga n a l y s i sf o rv r p ，0 rh o wt od e s i g n s i m p l ea n d e m c i e n tv e h i c l er o u t i n gs t r a t e g i e sa n d a l g o r i t h j n st oa c c o m p l i s hl o g i s t i c st a s k s i nt h i st h e s i s ，l o g i s t i c sd e l i v e 巧v e h i c l ed i s p a t c h i n gs y s t e mh a sb e e n d e s i g n e d a 1 1 dd e v e l o p e du p o nt h er e q u e s to ft 1 1 i st h e s i st a s k f i r s t l y ，t h r o u 曲s u m m a r i z i n g a 1 1 da n a l y s i s i n gt h eb a c k g r o u n da n dd e v e l o p m e n ts t a t u so fv i 逻t h e s t u d yc o n t e n t l l o ft 1 1 i sm e s i si se s t a b l i s h e d s e c o n d l y ，a r e ra n a l y s i s i n gt h eb a s i ct h e o r i e so fv r p a n di n t l ? o d u c i n gv r p sr e l e v a l l tt e c l u l o l o g i e s ，t h eo v e r a us t m c t u r ea n dw o r k i n g p r i n c i p l eo ft h es y s t e ma r ep r e s e n t e d a c c o r d i n gt ot h es y s t e m sn e e d s ，c o m b i n e d w i t hg o o g l em a p sa p i t e c h n o l o g y ，t h eb a s i sp l a t f o m lo ft h es y s t e mh a sb e e n d e v e l 叩e d t h eb a s i ci n f o 功1 a t i o nd a t ao ft h es y s t e mi sm a n a g e dd a i l yo nm e p l a t f o m w h a t sm o r e ，w | e b g i st e c h n o l o g yh a sb e e nc o m b i n e dw i t ht h es y s t e m s u c c e s s 如1 1 y t o p r o v i d eg e o g r a p m ci n f o m a t i o n a n a l y s i s i n g ，c a l c u l a t i n g a n d d i s p l a y i n gm n c t i o n s t h i r d l y ，t h es t a t i ca n dd y n 锄i cm a t h e m a t i c a lm o d e l so f 心 h a v eb e e nc r e a t e dr e s p e c t i v e l y t h e ns i m u l a t e da r u l e a l i n gg e n e t i c a l g o r i t h mi s p r o p o s e dt o d e a lw i t i ls t a t i cv i 遇a n dt h e d y n a m i cp r o c e s ss t r a t e g i e sa r e p r o p o s e dt od e a lw 砒ld y n 锄i cv r pa c c o r d i n gt ot h er e a l t i m ed e m a n d so f r一 一， c u s t o m e r s 1n ep e r 士o m a n c eo 士t h e p r o p o s e ds o l u t i o n si sa s s e s s e di ns o m et e s t e x p e r i m e n t s ，2 l r l dt h ef i n a lr e s u l t so fm e s ee x p e r i m e m sd e m o n s t r a t e dt h ef e a s i b i l i t y o fm es t a t i ca n dd y n 锄i cv i 冲s o l u t i o n s f i n a l l y ，t h ec o n t e n t ，w o r k i n gp r o c e s sa n d o p e r a t i n gi m e r f a c e so ft h es y s t e ma r ei n t r o d u c e di nb r i e f k e yw o r d s ：l o g i s t i c sd e l i v e r ) r ；v r p ；g o 0 9 1 em a p sa p i ；s i m u l a t e da m e a l i n g g e n e t i ca l g o d t h m i i i 广西大掌硕士掌位论文 基于g 0 0 9 l em a p sa p i 的物流配送车辆调度系统设计与研究 1 1 课题背景 1 1 1 课题来源 第一章绪论 课题来源：广西科技厅攻关项目“物流运输信息管理系统与企业e i 冲系统集成技 术应用( 桂科攻0 8 1 5 0 0 3 3 ) 和广西制造系统与先进制造技术重点实验室项目“基于 g p s ( g l o b a lp o s i t i o n i n gs y s t e m ，全球定位系统) 、g i s ( g e o g r 印h i ci n f o 衄a t i o ns y s t e m ， 地理信息系统) 、g p r s ( g e n e r a lp a c k e ti 己a d i os e r v i c e ，通用无线分组服务) 的车辆监控系 统开发( 桂科能0 8 4 2 0 0 60 1 1z ) 。 本课题旨在开发一种结合了广西壮族自治区中小型物流运输配送企业基本特点的 物流运输信息管理系统，以及融合r f i d ( r a d i of r e q u e n c yi d e n t i f i c a t i o n ，射频识别) 、g p s 、 g i s 、g p r s 等信息技术手段实时准确地采集物流各环节的基本信息，制定物流解决方 案，监控运输配送状态( 包括跟踪车辆位置和货物信息等) ，达到对物流运输配送整个 过程进行有效的管理及降低物流运作成本的目的。同时，通过分析本系统和合作伙伴企 业e i 冲( e n t e r p r i s er e s o u r c ep l a i l ，企业资源计划) 系统的数据特点，搭建本系统与企业 e r p 系统集成应用平台，实现物流企业信息系统与其合作伙伴企业信息系统的集成一体 化管理。 本文主要承担“基于w 曲g i s 的流配送车辆调度系统设计与研究”这一部分的任务。 1 1 2 研究背景 当今世界物流业正向全球一体信息化的方向迅速发展，物流运输及配送在供应链中 占据重要的地位。中国物流学会会长、中国物流与采购联合会会长何黎明在2 0 1 1 年中 国物流发展报告会上总结了我国物流在近五年的发展取得的成效【1 】：一是自从2 0 0 6 年 “大力发展现代物流业被列入“十一五 规划纲要以来，物流产业持续快速发展，地 位显著提升并得到确立；二是物流市场规模快速扩张，2 0 1 0 年我国物流市场总规模达到 的4 9 万亿元是2 0 0 5 年的两倍多；三是物流企业讯速成长，并初步形成物流企业核心群 体；四是物流基础设施建设进度加快，五年物流设施累计投资超过1 0 万亿元，年均增 长2 7 7 ；六是物流信息化运用及技术创新应用取得实效，已有7 0 5 的企业建立了管 理信息系统；七是物流行业基础工作体系基本形成；八是物流业对外开放迈开新的步伐； 九是物流业政策环境有所改善。 但我国物流仍然存在许多不足之处：一是竞争力不够强，衡量物流业运行效率的指 标物流总费用与g d p 的比率，我国高出发达国家一倍左右，从表1 1 中可得知近 五年以来该比例高居不下；二是整合性不足，物流网络完整性、配套性、协调性差：三 是不平衡性较为普遍，公路运输、普通仓储等传统服务供大于求，供应链一体化的专业 服务能力不足；四是物流企业生存和发展环境没有根本性好转，人力、燃油、土地成本 等各项物流要素普遍短缺，成本持续攀升；五是相关政策有待落实，现行政策思路体制 设计与物流业运作模式存在不相适应的矛盾。 表l - l2 0 0 6 2 0 1 0 年中国物流运行情况物流总费用表( 亿元) t a b l e1 12 0 0 6 - 2 0 1 01 0 9 i s t i c ss i t u a t o ni nc h i n a t h et o t a lc o s to fl o g i s t i c s ( 资料来源：国家发展改革委中国物流运行情况分析1 2 1 ) 中国最大的物流供应链管理软件供应商博科资讯总裁沈国康在分析中国物流业现 状时指出三点【3 】：其一，中国经济增长速度很快，g d p 己占到世界的5 ，但中国经济 中物流所占比例将近2 0 ，美国经济中物流只占1 0 左右，物流成为中国迄今为止最大 的一个行业；其二，与发达国家相比，中国物流业发展仍比较缓慢，在很多方面成本较 高( 从表1 1 中得知，运输成本占物流总费用的5 0 以上) ，导致企业竞争力降低；其 三，企业之间真正的竞争体现在供应链与供应链之间的竞争，对供应链的优化可成为企 业另外一个利润来源。 鉴于我国物流总费用占g d p 比率大，以及运输费用占物流总费用的一半以上等问 题，本文针对企业供应链物流配送运输环节中的车辆调度问题( v r p ，v e h i c l er o m i n g p r o b l e m ) 进行研究是十分必要的。 自1 9 5 9 年v r p 问题被提出后，经过五十多年的发展，v r p 问题的应用已从运输领 域跨越到了城市规划、管网铺设、紧急疏散、生产调度、立体仓库货位管理等需要优化 2 堕查鲎堡主黉位论查 基于g o o g l em a p sa p i 的物流配送车辆调度系统设计与研究 组合的领域。目前v r p 的研究与探讨大多集中在该问题的理论模型和算法领域，且取 得了许多重大的研究成果。但v i 冲问题的研究主要集中在静态v i 冲( s t a t i cv i 冲，s v i 冲) ， 即确定性v r p 问题，该类问题在求解之前假定输入信息( 如客户信息、货物信息、车 辆信息、路况信息、行车速度等) 是确定的，且在车辆执行任务期间这些信息都不会随 着时间发生改变，显然静态v r p 存在理想化特征。 在现实的物流配送过程中，常常存在大量不确定的信息和实时事件，如客户需求变 更、路况变化、车辆抛锚、数据偏差等。而该信息或实时事件在s v r p 模型求解中被确 定化了或未被考虑，此时s v i 心模型和算法就难以解决该类v r p 。因此，动态v i 冲 ( d y n a i i l i cv r p ，d v r p ) 模型就被研究者提出，以根据实时信息及事件要求对已规划 好的车辆路径进行及时的调整，完成配送任务。 d v r p 更能满足实际配送过程中出现的需求，且信息技术的发展为车辆调度中信息 的快速处理提供了强有力的支持，使得v i 冲问题的研究重点逐渐转移到d v r p 问题上 来。其中g i s 、g p s 、g p r s 、i 江i d 、i i l _ c e n l e t 等技术的应用能够为物流配送车辆调度系 统提供实时信息的分析处理，以有效地解决物流配送车辆问剐4 】- 8 1 。 1 2 发展研究现状 1 2 1 发展演进 自v r p 问题被提出以来，其求解算法从精确算法演变到启发式算法( 构造启发式 算法、两阶段启发式算法、人工智能启发式算法) ；其研究的规模从小规模的几十个节 点发展到大规模的成百上千个节点；其研究的模型从静态模型延伸到贴切实际的动态模 型；其应用从路径规划扩展到各行各业，且融合了现代高新技术，成为研究的热点。车 辆调度问题演进年代历史如表1 2 所示。 表1 2 车辆调度问题演进年代表 t a b l e1 - 2t 1 l eh i s t o r i c a le v o l u t i o no fv e h i c l er o u t i n gp r o b l e m 年份人物成就 1 9 5 9 d a n t z i 昏l s e r首次提出冲，用整数规划方法求解1 0 2 0 个节点的问题 1 9 6 2 b a l i i l s l 【i 等提出v r p 的集分割，考虑可行解集合，建立简单v i 心模型 1 9 6 4 c i 棚( e 、w h g h t 采用节约算法来构造车辆配送路线 1 9 6 9c l l r i s t o f i d e s 、e i l o n 提出2 o p t 、3 o p t 算子求解3 0 1 0 0 个节点的问题 1 9 7 le i f o n 将动态规划法用于固定车辆数的v r p ，通过递归方法求解 3 堕查兰璺查竺竺丝奎 苎雯垒2 2 坐坚竺! 竺! 竺竺鎏! 呈兰查塑塑墨墨垒苎竺：皇竺壅 1 9 7 4g i l l e 位、m i l l e r 提出能在短时间内求得近似解的扫描法 1 9 7 6m o l e 和j 锄e s o n 提出插入法，选择最合适的未分配节点插入已构造的路线 1 9 7 7g o l d 等 指出两阶段启发式方法，可处理较大型问题 1 9 7 7r o s e n k 瑚t z 等 提出最邻近法，可以在较短时间内求得初始解 1 9 7 8 c 1 1 r i s t o f i d e s 等1 9 7 9 年提出了两阶段启发式算法，以改进构造算法的不足 1 9 8 0p s a r a r i s 提出动态车辆调度概念 1 9 8 l f i s h e r 、j a i k 啪盯 提出以数学规划方法来处理大约5 0 个顾客点的问题 1 9 8 5 j h 0 p f i e l d 等提出h o p f i e l d 神经网络法 1 9 9 0 r o b u s t e 等利用模拟退火算法求解车辆调度问题 1 9 9 1 g e n d r e 锄等 利用禁忌搜索算法求解车辆调度问题 1 9 9 1 d o r i g o 等 提出蚁群算法 1 9 9 2 d e s r o c h e r s 等利用列生成方法求解诤问题 1 9 9 4f i s h e r 提出k 树方法求解冲问题 1 9 9 6j la w r e n c e 提出遗传算法，可有效求解带时间窗口的冲问题 1 9 9 0 至今 提出符合实际的更复杂的v r p 模型，结合现代智能启发式算 法，以及现代高新技术，将冲应用到各行各业 早期的v r p 研究主要集中在求解算法领域，但2 0 世纪9 0 年代以来，人工智能启 发式算法( 禁忌搜索算法、遗传算法、蚁群算法、模拟退火算法、神经网络算法、粒子 群算法等) 的提出为求解更复杂v i 心问题提供了强有力的支持，且各种算法被不断地 被改进优化，或者几种算法被混合使用以取长补短提高求解效率。 当前，卫星定位导航技术、无线通讯技术、自动识别技术、信息处理技术、地理信 息系统技术和计算机网络技术的高速发展，为v i 冲系统的智能化和信息化研究提供了 强有力的技术支持。因此，“智能车辆调度系统”、“智能交通系统 、“智能配送调度系 统 等概念被相继提出，而且这些系统也正在被逐渐地实现。 1 2 2 国外现状 对于s v i 冲问题，国外学者多针对贴近现实的v r p 问题进行研究，例如多车场、 多类型车辆、送货与集货混合、客户服务时间限制、多目标优化、客户需求多周期等类 型的v r p 问题，并对这些v i 心问题进行建模，提出人工智能启发式算法的优化框架， 或者采用并行策略求解v r p 问题【9 】【1 3 】。而动态车辆调度问题多被用于实际中的应急事 件处理，如旅行修理工、快递送收、自然灾害救灾物流路径规划等问题，并结合g i s 、 g p s 、g p r s 等技术，采用动态的最邻近插入算法、局部优化算法等进行改造路径【1 4 】【1 6 1 。 4 国外研究者主要是结合各种v r p 算法和配送管理技术，开发了各式各样的车辆调度系 统软件，例如美国著名的u p s ( u 1 1 i t e dp a r c e ls e r v i c e ，美国联合包裹公司) 旗下的物流 科技公司研发的r 0 础l e t5 0 0 0v e r s i o n7 o 配送管理系统，其强大的功能可出色地胜任各 种配送任务；以及美孚和i n s i g h t 公司合作研发的h p c a d ( h e a v y - p r o ( h l c t c o m p u t e r a s s i s t e dd i s p a t c h ) 计算机辅助配送系统，该系能根据客户订单、路径和卡车资源 等信息生成配送方案，还提供了人机接口允许调度者共同制定决策计划【1 7 1 。 地理信息系统为车辆调度系统的开发提供了有力的空间地图数据分析支持。西方国 家在地理信息系统、数字地球、全球定位系统和遥感技术等领域始终处于领先地位，涌 现出许多具有代表性的g i s 软件，如心c g i s 、g e n 锄a p 、m g e 、c i a d 、s y s t e m 9 、m 印i n f 0 、 g e o m e d i 等。 由于在v i 心的实际应用求解策略中，许多的决策内容与空间地理信息有关，因此， 基于g i s 系统开发车辆调度系统是将v r p 模型付诸实际应用的必经之路。在车辆调度 系统中，g i s 强大空间数据分析处理能力发挥了重要作用，如美国e s r i 公司基于心c g i s 系统研发的觚l o g i s t i e s 系统，利用g i s 功能对配送中心选址、客户定位、客户节点间 路径数据、最佳配送路径、最优库存等方面进行有效地解决。 目前，国外一些大型g i s 公司相应地发布了其g i s 的a p i 应用程序编程接口函数 ( a p p l i c a t i o np r 0 伊a l i l i n i n gi n t e r f a c e ) ，以供其他开发设计人员通过该a p i 访问g i s 的各 种资源和功能，而无需访问g i s 系统的程序源码和理解其内部的运行机制，其中g 0 0 9 l e m a p sa p i 最具有代表性【1 8 】。g 0 0 甜em a p sa p i 由g 0 0 9 l e 公司于2 0 0 5 年开放发布，且各 种版本的a p i 在不断地持续升级中。g o 0 9 1 em 印s 拥有众多功能各异的a p i ，用户只需 按照a p i 开发文档和操作步骤，就可以通过使用h t m l 、j a v a s c r i p t 、a c t i o n s c r i p t 、x m l 、 k m l 、h t t p 等语言或链接技术，将各种地图功能嵌入到自己的网页或应用程序中【1 9 】。 1 2 3 国内现状 国内对车辆调度方法的研究起步较晚，最具有代表性的为西南交通大学的郭耀煌教 授及其带领的团队从1 9 8 9 年起对车辆调度问题展开的一系列研究：包括出版了车辆 优化调度、物流配送车辆优化调度理论与方法等专著，开发了基于g i s 的物流配送 车辆优化调度系统软件包，以及对不确定信息条件下的动态车辆路径问题进行研究 【2 0 】- 嘲。另外，还有清华大学但正刚将多代理两阶段理论应用到带时间窗的实时车辆调 度系统中，用改进的遗传算法求解第一阶段的静态计划；采用车辆之间的协商机制来处 基于g o o 酉em a p sa p i 的物流配送车辆调度系统设计与研究 理第二阶段中产生的实时订单，并设计了多代理v r p 系统【2 3 1 。上海交通大学夏鼎将车 辆访问的节点进行分组，再用改进蚁群算法解决车辆路径问题，最后在基于m a p x 软件 设计的w | e b g i s 上实现智能物流配送管理系统的开发【2 4 1 。同济大学郭凤鸣主要针对新需 求实时产生的情况，将车辆调度问题分为纯送货( 或纯集货) 问题、集送货一体化问题 进行研究建模，设计了节约算法来生成初始静态计划，利用插入算法求解产生动态需求 计划，并提出基于g i s g s m g p s 的动态v r p 系统设计方案【2 5 1 。北京交通大学柯昌正把 一个配送工作日分成若干个时间段，在每个时间段结束时，调用蚁群算法处理该时间段 内产生的客户订单需求，构造车辆配送路径【2 6 1 。华侨大学林玲运用贪婪算法将车辆调度 问题进行分步求解，形成k 条行驶路线，并利用改进蚁群算法来分别优化这k 条路线， 再基于a r c g i s 软件架构将g i s 功能引入到物流系统中【2 7 1 。 在地图a p i 应用研究方面，越来越多的国内人士将地图a p i 嵌入到自己的系统中进 行应用。例如，山东大学王厂基于g 0 0 9 l em a p sa p i 技术，将邮政系统数据与g o o g l em a p s 地图数据相结合，开发设计邮政运输调度系统【2 8 】；浙江师范大学马跃等基于g o o g l em a p s a p i 和a j a x 技术设计车辆监控管理系统以及数据通信模块，实现车辆在g 0 0 9 l em a p s 上的导航、定位以及轨迹回放等功能【冽；西南交通大学汪延彬等基于g 0 0 9 l em a p s 在空 间信息分析、计算和统计方面的强大优势构建京沪高速铁路沉降信息管理系统【3 0 1 。 国内在g i s 领域研究起步较晚，但经过近年来的发展，在g i s 理论研究、测绘技 术、实验设备、软件开发等方面都取得了重大进展。如1 9 9 4 年，我国成立了“中国g i s 协会 ，随后又成立“中国g i s 技术应用协会”，研制出了如s u p e m a p 、m a p g i s 、g e o s t a r 、 t 0 p m a p 、“我要地图 等具有自主版权的g i s 软件。国内一些g i s 公司也发布了其地图 a p i ，如m a p a b ca p i 、5 1 m a p sa p i 等，但其a p i 的开放性和灵活性不如国外的地图 a p i ，功能也较弱，在使用前需要申请a p i 密钥。 国内车辆调度软件发展较快，各企业针对我国城市道路的实际交通情况，构建车辆 调度模型以及结合相关算法，开发的车辆调度系统有：北京利四方物流信息技术服务有 限公司的g p s 车辆监控调度系统，沈阳华翰电子有限公司的g p s 公交客运车辆动态调 度管理系统，深圳航大通讯技术有限公司的g p s 车辆动态管理系统，北京四维赛洋出 租车调度系统等。这些系统一般都融合了g p s 、g p r s 、g i s 、互联网络等信息技术，且 根据各行业需求而开发，但没有统一的行业标准。系统一般由网络服务器、监控工作站、 车载终端和被监控调度的车辆组成，以及通过无线通信技术、数据库技术、电子地图分 析技术、车辆调度算法等，共同实现对移动目标进行全球卫星定位跟踪、调度管理、运 6 基于g 0 0 9 l em a p sa p i 的物流配送车辆调度系统设计与研究 营管理等功能。 1 3 研究意义 1 3 1 学术意义 1 、研究v i 心算法及动态v r p 问题的学术意义 目前，各种启发式算法注重快速寻求v i 心问题的近似最优解，各种算法在求解v r p 问题上会也表现出不同的求解精度和效率。因此，对算法的作进一步优化改进研究具有 一定的学术意义。此外，将静态v r p 问题延伸到动态v r p 问题进行研究，也可进一步 扩展v r p 问题研究的理论深度，充实v r p 组合优化问题研究领域。 2 、研究第三方g i sa p i 技术的学术意义 大多数车辆调度系统都采用功能强大的专业g i s 系统作为车辆调度的地图开发软 件，其对使用者的开发能力、开发成本要求都较高，因此造成其应用门槛也高。而类似 本文将采用的基于第三方g i s 的a p i 技术开发车辆调度系统的研究成果和文献则较少。 随着第三方g i s 开放的a p i 逐渐成熟和广泛应用，有理由相信它能为物流配送车辆调度 的研究指示一条新的方向。 1 3 2 应用意义 1 、动态v r p 问题的应用意义 本文考虑了车辆调度问题的动态情况，因而更接近物流企业的实际车辆调度情况。 随着顾客对企业配送准确性和及时性的要求逐步提高，增强企业对实时需求信息的快速 反应能力，迅速提出解决方案是企业提高市场竞争力的有效手段。所以本文研究的动态 v r p 问题的意义在于为企业解决实时需求信息提供参考方案。 2 、第三方g i sa p i 技术的应用意义 鉴于专业g i s 的高应用门槛性，第三方g i s 公司提供的g i s 应用服务成为了非专 业g i s 人员应用的首选。这些公司一般免费开放其地图a p i 供用户调用，用户只需简单 地学习其a p i 使用文档即可在自己的系统上实现专业g i s 系统所具有的功能。本文通过 g 0 0 9 l em 印s 提供的a p i 接口，将地理信息与物流信息紧密结合，设计简单可行、低成 本的物流配送车辆调度解决方案，可为物流配送企业解决v i 冲优化决策提供参考。 7 要查竺里主兰竺丝奎一一 基于g o o g i em 印sa p i 的物流配送车辆调度系统设计与研究 1 4 研究内容与本文结构 1 4 1 本文研究内容 根据课题要求，本文的任务就是设计一个可以解决物流配送车辆调度问题的管理系 统。首先要解决的是建立物流配送车辆调度问题模型，并据此设计出有效的求解算法； 然后，搭建一个可以完成这个算法的平台，一方面可以提供算法所需要的各种信息，另 一方面也可以直观展示调度的结果。因此，本研究的工作内容包括两大部分，一是物流 配送车辆调度问题建模与算法实现；二是搭建解决物流配送车辆调度问题所需的运行平 台，通过各种手段提供车辆调度搜索算法所需的数据，同时实现方案图形化分析显示的 功能。 为此，本文首先研究如何搭建物流配送车辆调度系统的运行平台。根据对车辆调度 问题的分析及本文研究任务的需要，该运行平台应该包括两部分：其一是基础信息数据 平台，包含以用于维护车辆调度所需的基础信息，如客户、订单、货物、车辆、司机等 信息；另一部分是地理信息系统平台，实现路径分析、计算、显示和提取地理数据等功 能来辅助车辆调度算法生成最佳配送方案。其次，要分析并建立物流配送车辆调度的模 型并采用有效的算法，根据客户下达的配送订单，结合基础信息数据和地理信息系统的 地理信息分析功能，求解最佳配送方案并将其展示在地理信息系统平台上，将来可直接 下达给配送车辆执行。本文研究内容如图1 1 所示。 物流配送率葡两度泵绣飞7 厂窜编；跨渣蹴刑弭甘铭娩瞄袖、l 订 l 千刑调掇仪坐及强辫敞供狄 夕 配 提供地 送 j l 蝴i 1 6 刀碌：r 一 理分柝 l 擎 荦提傲錾 任 接础数据 存储7 一一腱泳 务 t 妇 二l 越m 钎n l i i 辆 一l 气精摇平备、州l 蘸瑞平白地j 信息、 ： 默碥。、存储地理数据承狐四 图1 - l 本文研究内容 f i g 1 1t h ec o n t e n t so f t h i st h e s i s 8 1 4 2 本文组织结构 第一章：论述本文课题来源、研究背景、研究意义、v r p 演进发展史，并简要介绍 了v r p 问题的国内外研究现状，包括v r p 算法、v r p 模型、v i 冲系统的研究现状以及 g i s 技术在车辆调度中的应用研究情况。 第二章：提出本文研究的物流配送车辆调度问题，介绍系统涉及到的相关技术、系 统开发环境，最后给出系统的结构和工作原理。 第三章：提出系统基础信息模块的架构设计，建立系统的基本信息数据库平台，利 用a s p ：n e t 的三层架构模式实现数据库的连接操作。 第四章：分析探讨如何通过g o o g l em a p sa p i 技术实现w 曲g i s 与物流配送车辆调 度系统的集成，并重点设计w e b g i s 平台的各种功能。 第五章：将本文研究的v r p 问题分成静态调度和动态调度问题，并分别针对该两 个问题进行模型描述，建立数学模型，构建求解算法，给出算法算例分析。 第六章：提出系统的工作内容和流程，并介绍系统各功能模块的操作界面。 第七章：总结全文所做的工作，并提出了一些将来可以改进的研究方向。 1 5 本章小结 本章论述了课题来源、研究背景、研究意义、v i 冲演进发展史，并简要介绍了v r p 国内外研究现状，包括v r p 算法、模型、系统的研究现状以及g i s 技术在车辆调度中 的应用研究情况，最后简要给出本文的研究内容和本文结构。 9 第二章系统总体结构及相关技术 为了实现物流配送车辆调度系统的设计，本章首先对物流配送车辆调度问题进行简 要概述，并提出本文研究的v i 冲问题类型；接着介绍实现系统所需的相关技术和开发 环境；最后提出基于b s ( b r o w s e r s e n ，e r ，浏览器服务器) 模式的系统结构和系统工 作原理，为后续系统的详细模块设计奠定基础。 2 1 物流配送v r p 问题的提出 车辆调度问题或称车辆路径问题是从旅行商问题( t s p ，t r a v e l i n gs a l e s m a i l p r o b l e m ) 演变而来，世路线一般包括多条t s p 路线，如图2 1 所示。 ：冀毫嗲 。 给o 。匦p o o 。o 叫 穗既遴帆山 。餮产餮点 澎既遴车辆 一行驶络线 图2 lv r p 问题不慈图 f 埝2 1n l es c h e m a t i cd i a g r 锄o f v r p 物流配送中的v r p 问题指在满足一定的约束条件下( 如车辆容量、行驶时间限制， 配送客户节点服务时问限制等) ，调度人员根据配送中心的运力资源、客户订单需求、 配送节点之间的路线等信息，安排若干条行车路线，使配送车辆有序地通过路线上的一 系列配送节点，并达到预定目标( 如行车总费用最小、路程最短、车辆使用量最少、时 间最少等) 的问题【3 1 1 。 本文将v r p 问题分成两个阶段处理：一是根据已知信息制定初始配送策略的静态 v i 冲问题阶段，二是根据实时需求信息调整初始配送策略的动态v i 冲问题阶段。 2 2 1 静态v i 心问题 1 、静态v r p 问题定义 静态v i 冲( s t a t i cv i 理，s v i 冲) 问题指根据已知确定订单任务和配送资源制定初始 车辆调度决策，让配送车辆按照初始路线执行配送任务，而暂不考虑信息的变化。 2 、静态v r p 问题分类 l o 基于g 0 0 9 l em a p sa p i 的物流配送车辆调度系统设计与研究 在不同行业的应用中，s v r p 问题被分成不同种类。可按车场、车辆、货物、路网 的属性，以及约束条件、最优目标等对s v i 冲进行分类，具体如表2 1 所示。 表2 1s v r p 分类表 t l b l e2 1t h ec l a s s i f l c a t i o nc h a r to fs v r p 结合课题背景，提出本文的s v i 冲问题为单车场、单车型、无行车时间和里程限制、 非满载、无时间窗限制、封闭路径、非对称路网、多目标的配送多种货物的v r p 问题。 3 、静态v r p 问题求解方法 s v i 冲的求解方法大致分为精确算法和启发式算法，如图2 2 所示。 i 动态规划法分枝定界法拉格朗日分解法 精确算法一 ik 树方法网络流算法割平面法 列生成方法 i 最邻近法最近插入法 厂构造启发式算法一 l lc w 节约算法扫描算法 l ii2 - s w 印2 c x c h 锄g e2 0 p t 启发式算法 两阶段启发式算法一 i 3 o p t 4 0 p tl i n - k e m i g h 锄 、i ll 遗传算法禁忌搜索算法 l 人工智能启发式算叫蚁群算法 模拟退火算法 i 粒子群算法神经网络算法 图2 2s v r p 优化算法 f i g 2 2t h eo p t i m i z a t i o na l g o r i t h m so fs v r p i l 精确算法是指可精确地求出s v i 冲问题最优解的算法，但由于s v r p 问题属于n p 难题( n o n d e t e 肌i 1 1 i s t i cp 0 1 y n o m i a l ，多项式复杂程度的非确定性问题) ，其计算量会随 着问题规模的扩大呈指数倍增长，常常造成计算机c p u 超负荷运行和内存不足现象， 所以该类算法只适合求解小规模s v i o 问题【3 2 1 。 鉴于精确算法难以求得规模较大时的s v r p 问题最优解，以及大多数s v i 冲问题不 存在严格意义上的最优解( 例如多目标的s v r p 问题中目标之间存在矛盾) ，再者实际 应用中也常常没有必要花费过多的代价追求高精度的最优解，因此启发式近似算法被提 出用于求解中大规模的s v i 冲问题【3 3 】【3 4 1 。该类算法包括构造启发式、两阶段启发式和人 工智能启发式算法三种。 构造启发式算法常用于构造人工智能化启发式算法的初始解；两阶段启发式算法指 对线路内部的点或线路之间的点进行调整，以将新解改进优化到最优解。该两种启发式 算法在求解过程中，在始终保持可行解的前提下，只将求解的方向指向更优的方向，但 由于s v i 心问题的最优解也可能从不是可行解或劣质解的集合中产生，因此该两种算法 都容易陷入局部最优。 人工智能启发式算法往往允许劣质解出现，并可从劣质解集合中找到更优的解，从 而跳出局部最优解去接近全局最优解。该类算法通常受某种生物或自然原理的启发而被 提出【3 5 1 ，也常常被改进或相互混合使用求解s v r p 问题【3 6 】【3 9 1 。鉴于该类算法的在求解 s v r p 问题上的优势，本文将采用该类算法求解s v i 冲问题。主要几种人工智能优化启 发式算法的简要概述如表2 2 所示。 表2 2 几种人工智能化启发式算法 t a b l e2 - 2s e v e r a li m e l l i g e n th e u r i s t i ca l g o r i t h m s 1 2 通过分析各种智能化启发式算法的优劣性，本文将在第五章详细分析采用模拟退火 遗传混合算法s a g a ( s i m u l a t c d 加m e a l i n gg e n e t i ca l g o r i t h m ) 求解静态v r p 问题。s a g a 算法因遗传算法g a ( g e n e t i c 砧g o r i 廿l l l l ) 的强大全局搜索能力可快速地搜索出全局较优 解，同时在g a 主循环中插入模拟退火算法s a ( s i m u l a t e da 衄e a l i n g ) ，利用其良好的 局部搜索能力以弥补g a 的局部搜索能力较差不足，寻求全局最优解。 2 2 2 动态v r p 问题 1 、动态v r p 问题定义 在v i 冲问题中，如果车辆行驶的路线是随着实时需求和动态事件的出现而在原有 的路线上作相应调整的路线，那么该类问题为动态v r p 问题( d y n a m i cv r p ，d v i 冲) 【钓】。显然，与s v r p 相比，d v r p 更