（计算机软件与理论专业论文）gps数据挖掘技术在物流企业中的应用.pdf

摘要 摘要 从国民经济角度看，物流行业占有重要的地位，而在物流配送作业的各个 环节中，配送环节是非常重要的。配送计划合理与否对配送速度、成本、效益 影响很大。采用科学的、合理的方法来确定配送计划是物流优化、物流科学化 的关键一环。 本文围绕配送环节的关键点车辆调度问题进行论述。首先简要介绍了 传统车辆调度问题的概念，详细分析了北京朝批商贸有限公司( 简称朝批) 车 辆调度这一实际问题的复杂性。并以车辆工作时间为切入点，介绍了车辆调度 系统所依赖的各种运算依据它们独立于具体的车辆调度算法，目前主要依 赖人的经验进行估计，准确程度较低，已经对朝批人工或智能车辆调度的效果 造成了显著影响。如何获取科学、准确的运算依据已经成为亟待解决的问题。 本文提出了利用g p s 数据挖掘技术、从海量g p s 数据中挖掘上述运算依据的 方法、并用于指导车辆智能调度以及运输成本核算和绩效考核，取得了良好的 应用效果。 主要包括以下几方面内容： 1 首先介绍了用以获取车辆g p s 数据的g p s 数据接收系统的设计、实现。 2 随后讨论了g p s 数据处理过程中的一些重要细节，给出了“噪声”排除、 停留点捕捉和匹配以及车辆行驶里程计算等算法，介绍了基于这些算法的g p s 数据统计分析系统。 3 最后重点论述了如何在上述数据处理的基础上，通过建立各种线性回归数 学模型，计算分析得到车辆调度运算依据的方法。以大量翔实的数据，论证了 依靠该方法所获得的运算依据更具科学性、准确性，并能够有效提高朝批车辆 的综合利用率。 关键词物流配送；车辆调度；g p s 数据挖掘 a b s t r a c t l o g i s t i cp l a y sa ni m p o r t a n tr o l ei nn a t i o n a le c o n o m y d i s t r i b u t i o ni s v e r yi m p o r t a n ta m o n ge a c hp a r to fl o g i s t i c t h ed i s t r i b u t i o np l a nt a k e s g r e a te f f e c to ns p e e d 、e f f i c i e n c y 、c o s to fl o g is t i c s ar e a s o n a b l e d i s t r i b u t i o np l a ni sa ni m p o r t a n to p e r a t i o ni nl o g i s t i cd i s t r i b u t i o n t h i sd i s s e r t a t i o nd i s c u s s e ds u r r o u n d i n gt h ev e h i c l es c h e d u l i n ga n df i r s t i n t r o d u c e dt h ec o n c e p to ft h ev e h i c l es c h e d u l i n gp r o b l e m ( v s p ) ，a n a l y z e d t h ec o m p l e x i t yo fap r a c t i c a lp r o b l e mw h i c hc a l l e dc p _ v s p t ot h ew o r k i n g h o u r so fv e h i c l ea sab r e a k t h r o u g hp o i n t ，t h i sd i s s e r t a t i o ni n t r o d u c e d s e v e r a lp a r a m e t e rw h i c ht h ev e h i c l es c h e d u l i n gs y s t e md e p e n d e do n t h e y a r ei n d e p e n d e n to fs p e c i f i ca l g o r i t h m ，e s t i m a t e db yt h eo p e r a t o r s e x p e r i e n c e 。a n dn o ta c c u r a t e t h e yt a k eg r e a te f f e c to nt h e 心j s p h o w t og e ta c c u r a t ep a r a m e t e rb e c o m e sas e r i o u sp r o b l e m g e t t i n ga c c u r a c y p a r a m e t e rf r o mg p sd a t ar e l i e do ng p sd a t am i n i n gw a sp r o p o s e da s a s o l u t i o nt ot h ep r o b l e mi no r d e rt oe n h a n c et h ee f f e c to fc p _ v s pa n d e s t a b l i s ht h ed r i v e rp e r f o r m a n c ee v a l u a t i o ns y s t e m t h i sd i s s e r t a t i o nd i s c u s s e dt h ef o l l o w i n gt o p i c s ： 1t h i sd i s s e r t a t i o nf i r s ti n t r o d u c e dt h ed e s i g na n di m p l e m e n t a t i o no f g p sr e c e i v i n gp r o g r a mw h i c hi su s e dt og e tm a s sg p sd a t ao fv e h i c l e 2t h e n 。t h i sd i s s e r t a t i o nd i s c u s s t e ds o m ed e t a i l so fg p sp r o c e s s i n g ， h i g h li g h t e dt h e f o ll o w i n ga l g o r i t h m so rm e t h o d sw h i c ht h eg p sd a t a a n a l y s i ss y s t e mw a sd e p e n d e do n ：t h em e t h o do fi r r e g u l a rd a t ar e m o v i n g ， t h ea l g o r i t h mo fc a t c ha n dm a t c ho fv e h i c l es t o p p i n gp o i n t sa n dt h em e t h o d o fv e h i c l em i l e a g es t a t i s t i c s 3f i n a l l y ，t h i sd i s s e r t a t i o nf o c u s e do nh o wt og e ta c c u r a c yp a r a m e t e r o f c pv s pf r o mt h ed a t ab a s e do nt h ea b o v ea l g o r it h m st h r o u g ht h e e s t a b l i s h m e n to fav a r i e t yo fm a t h e m a t i c a lm o d e l s al a r g en u m b e r o f d e t a i l e dd a t aw a su s e dt os c i e n t i f i cp r o o fo ft h er e s u l t sr e l i e do nt h i s m e t h o dw h ic hc a ne n h a n c et h ee f f e c to fc p k e yw o r d sl o g i s t i cd i s t r i b u t i o n ；v e h i c l es c h e d u l i n gp r o b l e m ；g p sd a t a m i n i n g i l l 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究 所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：燮搦睦日期：鱼幽：曼! l 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的 全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 导师躲国! ：墨嗍刎划 第1 章绪论 _ _ l i d _ ii!i i_i_ 第1 章绪论 1 1 物流配送与车辆调度 在经济全球化和信息化的浪潮下，当代物流行业飞速发展。从国民经济角 度看，物流行业占有十分重要的地位。据中国物流信息网的权威统计数据显示： 2 0 0 8 年，全国社会物流总额达8 9 9 万亿元，比2 0 0 0 年增长4 2 倍，年均增长 2 3 ；物流业实现增加值2 0 万亿元，比2 0 0 0 年增长1 9 倍，年均增长1 4 。 物流业增加值占全部服务业增加值的比重为1 6 5 ，占g d p 的比重为6 6 。 2 0 0 9 年，物流行业被国家列入十大振兴产业。2 0 0 9 年2 月2 5 日，国务院 召开常务会议，审议并通过物流业调整振兴规划。会议指出，物流业是融合运 输、仓储、货运代理和信息等行业的复合型服务产业，涉及领域广，吸纳就业 人数多，促进生产、拉动消费作用大。但我国物流业总体水平落后，严重制约 国民经济效益的提高。必须加快发展现代物流，建立现代物流服务体系，以物 流服务促进其他产业发展。 在这种形势下，研究如何通过实施科学的物流管理，以提高物流效率、降 低物流成本、提高服务质量是十分必要的。而在物流配送作业的各个环节中， 配送环节是非常重要的。配送计划合理与否对配送速度、成本、效益影响很大。 采用科学的、合理的方法来确定配送计划是物流优化、物流科学化的关键一环。 配送计划主要包括：车辆路线、时间安排。通过科学的方法优化配送计划，可 以大大减少车辆行驶里程，降低油耗，减少司机工作时间，提高装载率，提高 服务准确率，提高客户满意率，从而带来巨大的经济效益。 1 2g p s gis 技术在物流企业的应用 g i s ( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，地理信息系统) 是以地理空间数据为 基础，对地理数据进行采集、储存、管理、运算、分析、显示和描述的计算机 系统，已经在测绘、制图、交通运输等方面广泛的应用，并取得了显著的效果 1 1 】 o g p s 是全球卫星定位系统( g l o b a lp o s i t i o n i n gs y s t e m ) 的简称【z 】。g p s 技 术是近年来开发的具有开创意义的高新技术之一。通过该技术可得到高精度、 全天候、全球覆盖的经纬度、速度、方向、时间等信息，因而被广泛应用于军 事和民用的各个领域。二十世纪8 0 年代后期，西欧、北美和日本等发达国家竞 相研究发展g i s g p s 技术【删。其中车辆及个人导航监控领域成为发展最迅速、 北京工业大学t 学硕十学位论文 前景最广阔的应用市场。而在物流领域中，利用g p s 技术灵活的精确定位功能 及g i s 技术强大的空间数据功能，可寻找物流网络中的最优路径，优化配送计 划，合理使用各种资源，降低运输费用，提高经济效益削。 在物流企业中，通过g i s g p s 技术，可将车辆轨迹显示在数字地图上，以 实现实时监控运输车辆的目的，并提高调度、管理水平，达到降低配送成本， 提高货物送达准确率，提高客户满意度阿。利用这些宝贵数据，可进行物流成 本分析、司机业绩分析、调度效率分析，并获得客户资料，帮助企业制定高效 的配送计划，提高企业决策分析的能力。 1 3 数据挖掘及回归分析 数据挖掘是计算机科学领域一个极具应用价值的研究领域。它是- i i 交叉 性学科，融合了统计学、数据库技术、机器学习、人工智能等多个领域的理论和 技术【7 】。数据挖掘的广义观点为：从大量的、不完全的、有噪声的、模糊的、随 机的实际应用数据中发现隐含的、规律性的、人们事先未知的，但又是潜在有用 的并且最终可理解的信息和知识的非平凡过程【8 l 。数据挖掘所能发现的知识主 要有如下几种：广义型知识( 反映同类事物共同性质的知识) 、预测型知识( 根 据历史和当前的数据推测未来数据) 、关联型知识( 反映事物之间依赖或关联关 系的知识) 等。若根据挖掘方法分类，数据挖掘可以分为统计学方法、机器学 习方法、神经网络方法和数据库方法。回归分析是数据挖掘技术中常用的一种 统计学手段。它通过一个或多个变量去解释另外一个未知变量的变化，并以历 史数据为基础，在某种精确度下预测未知变量的值p ”l 1 4 国内外相关问题研究 就笔者目前搜集的资料来看，与本课题相关的研究有相当一部分集中在交 通领域。 刘春等人在其论文中探讨了在采用g p s 技术获得的车辆数据的基础上，利 用多元线性回归模型模拟隧道通行速度，利用与隧道进出口连通的相关路段已 知通行速度，推估隧道内的车辆通行速度，并达到了实用的精度要求【1 刁。 杨兆生等人在的多篇论文中探讨了利用逐步回归分析方法预测公交站点客 流量集散，并利用广义回归神经网络方法预测站点间运行时间，并在长春市实 际应用中得到了验证【1 3 4 1 。c h a oh a n 、b r i a nl s m i t h 等人在多篇论文中研究了 基于非参数回归、神经网络等模型的交通流量预测方法 1 5 - 1 6 j 。 陈鹏在其论文中探讨了将在公交运营调度的历史数据和g p s 数据的基础 上，将b p 神经网络技术应用于智能公交实时调度研究，建立了基于b p 神经网 2 第1 章绪论 络的公交车辆运行时间预测模型，并在此基础上设计了公交智能实时调度算法 【1 7 1 。q i uy i n g 等人在其论文中探讨了基于实时g p s 数据的车辆调度算法1 1 8 】。 方列在其论文中探讨了利用分类树方法解决g p s 坐标匹配问题【1 9 l 。 徐占鹏、孙晋麟等人在其论文中探讨了基于浮动车g p s 数据及相关算法解 决复杂路径匹配、车辆路径优化的方法【2 0 _ 2 1 l 。胡明伟在其论文中探讨了基于浮 动车g p s 数据的实时交通信息采集方法【2 2 l 。葛晓锋、曹斌其论文中探讨了利用 g p s 获取高速公路实时路况的方法【2 3 i 。 杨新苗、李明等人分别在其论文中探讨了公交及轨道交通车站客流预测模 型【2 4 - 2 5 1 。 胡林、张涛、王楠分别在其论文中探讨了利用卡尔曼滤波等技术，探讨了 车辆导航中g p s 坐标地图匹配的相关模型及算法 2 8 - ： 8 i 。， q i nx i a o 、r u i m i nl i 等人分别在其论文中提出了利用数据仓库对智能交通 信息进行数据挖掘、数据联机分析处理的方法1 2 0 - 3 1 1 。曲大义等人在其论文中探 讨了如何利用数据仓库技术、聚类分析方法分析公交g p s 数据【3 2 1 。 1 5 课题来源与朝批运输管理系统 本课题来源于朝批商贸有限公司( 下文简称“朝批 ) 。朝批总资产达1 2 亿 元，是香港上市公司北京京客隆商业集团股份有限公司的主要成员，总部在北 京，拥有1 1 家子公司，是华北地区最大的快速消费品批发物流公司，其网络覆 盖北京、天津、唐山、青岛等地，并拥有总面积约1 8 万平方米的现代化物流配 送中心，年吞吐量达9 0 0 0 万件。2 0 0 8 年，朝批销售额近4 3 亿元人民币。 朝批e r p 系统( 下文简称c pe r p ) 是由北京工业大学计算机学院软件工 程实验室( 笔者所在课题组) 参与研发非常完整的企业e r p 系统。c p - - e r p 作 为支撑企业业务及促进企业信息化的平台，在企业的经营管理中起着至关重要 的作用。c pe r p 主要包括业务信息系统、财务信息系统、物流信息系统3 个 组成部分。物流信息系统又包括仓储管理系统和运输配送管理系统( 下文简称 c pt m s 系统) 两个主要部分。c pt m s 目前主要包括“基本信息管理”、“配 送车辆编排调度”、“实时车辆运行监控和“g p s 数据挖掘分析 四大部分。 该系统以先进的物流管理理念为指导思想，以全面优化配送业务流程、提升配 送整体运营效率为目标，现已成为朝批物流中心高效运转的重要支柱【3 3 1 。其中 “配送车辆编排调度 实现了车辆智能调度，只需几分钟便可完成手工时代多 个调度几个小时的工作。而g p s g i s 监控系统大大提高了车辆监控能力，g p s 数据挖掘分析子系统为进一步分析利用g p s 数据，指导车辆调度提供了有效方 法。 北京- e , _ l k 大学工学硕士学位论文 1 6 本文结构 本文的结构安排如下： 第一章为绪论部分。主要阐述课题背景及相关概念，国内外相关研究情况 及本课题的来源。 第二章为车辆调度问题。重点介绍了车辆调度问题的概念及其解决方法， 并分析了朝批车辆调度这一实际问题的复杂性，以车辆工作时间为切入点，介 绍了各种影响朝批车辆调度综合利用率的运算依据的不准确性。提出了本文的 方法及研究目标。 第三章为车辆停留点。提出了停留点的概念及停留点捕捉匹配算法的流程 及算法中某些重要的问题，对影响匹配成功率的因素作了定性分析，并对实际 应用效果进行了简要介绍。 第四章为g p s 数据挖掘。主要介绍了g p s 数据进一步分析发掘的方法，并 介绍了部分分析结果。简要介绍了司机绩效考核体系的建立。 第五章为实际应用效果。以大量翔实的数据论证了本文提出的方法的科学 性，利用该方法所得结果能够有效提高朝批车辆调度的综合利用率。 4 第2 章车辆调度问题 第2 章车辆调度问题 2 1 课题研究的必要性 本文的研究与物流企业的实际需求紧密相关。朝批对于g p s g i s 的运输管 理系统的需求可以总结为两大部分：第一，车辆实时监控、导航；第二，车辆监控 数据的深入分析、挖掘。 就笔者多方搜集的资料来看，无论是包括东软在内的各家g p s g i s 系统提 供商，还是各大科研机构的研究成果，均把重点放在利用g p s 技术对车辆进行 实时监控、导航、调度领域，主要包括：实时跟踪载货车辆，根据车辆信息在 电子地图上显示车辆位置及详细资料，确保运输安全，与司机进行语音、短消 息通信，并根据道路交通状况向司机发出实时调度指令，再辅以各种模型及算 法，计算出最佳物流路径，为车辆进行导航，减少运行时间。一些涉及g p s 数 据挖掘的研究大多局限于智能交通领域，在物流领域的研究和应用较少。 总之，无论是市场上各种产品还是各大科研机构的研究成果均不能完全满 足朝批的需求。本文的研究正是在这种背景下展开的。本文将介绍g p s 数据挖 掘技术在车辆调度问题及司机绩效考核问题上的应用。 2 2 车辆调度问题的概念 物流配送车辆调度问题最早是由d a n t i z g 和r a m s c r 于19 5 9 年首次提出刚， 一般是指：对一系列发货点和收货点，调用一定的车辆，组织适当的行车路线， 使车辆有序地访问它们，在满足特定的约束条件下，力争实现一定的目标 如车辆行驶里程最短、运输总费用最低、车辆按一定时间到达、使用的车辆数 最少等 a 5 1 。1 9 8 5 年s a v e l s b e r g h 证明了车辆调度问题属于n p 完全问题嗍。传统 车辆调度问题的主要约束条件包括工作时间约束，车辆载重约束，车辆行驶里 程约束，唯一性约束( 每一个客户只能被车辆服务一次) ，时间窗约束等。 由于这一问题的理论涉及多学科，而且具有很强的实践性，因而很快便引 起计算机、物流、管理科学与工程、交通等各个学科的专家的极大重视。国内 外专家对该问题进行了大量的理论研究及实验分析，取得了很大的进展。由于 启发式方法在求解这类大规模复杂问题具有很大的优越性，因而现阶段许多国 内外专家大都致力于设计各种启发式方法求解车辆调度问题。 5 北京工业大学工学硕士学位论文 2 3 朝批车辆调度问题的复杂性 朝批的车辆调度问题与传统的车辆调度问题相比，显得更为复杂。除了上 文中描述的车辆调度问题普遍共有的约束条件之外，针对朝批的实际情况，还 有如下复杂的约束以及不同于传统车辆调度问题的特点： 1 通行证约束。朝批的客户覆盖全北京，而北京交通状况又极其复杂，因 而车辆的地区通行证也是一个重要的约束条件； 2 商品比重差异。由于朝批的商品种类繁多，不同商品间的比重差别极大。 例如：同是1 0 0 k g 的商品，膨化类食品体积可高达1 2 立方米，而饮料 类商品可能仅是0 1 立方米左右d 7 ； 3 车辆规格、型号差异。与传统问题描述所不同的是，朝批实际配送车辆 并不是都具有相同的规格型号、载重量，基本上可以说因车而异，不同 的车辆有不同的载重量且载重容积比也差别很大，例如：同是3 吨车， 载重容积比最大到0 2 1 、最小到0 1 3 t 3 7 1 ； 4 大客户配送问题。一个客户的商品重量( 或体积) 可能大于所有车辆中 的最大载重( 或容积) ，因此一个客户可能需要多车联合配送或一车多 次配送。如何为大客户分配车辆本身就是一个n p 问题； 5 运力严重不足问题。相对于日益增长的业务规模而言，朝批的运力总是 处于严重不足的状态，每日可供调度的车辆数量有限，因而总是存在无 法为之安排配送的客户( 俗称“未排”客户) ，这与一些传统的、不考 虑车辆数的车辆调度问题大不相同； 6 客户收货流程不规范。根据北京市物流配送的实际情况，司机即使完成 同样数量的卸货任务，在不同客户处所耗费的时间大不相同，这是由于 各种客观原因和人为因素造成的嘲j 如是否长时间排队等待，卸货时 有无叉车协助、车辆能否停靠月台、验收方式及票据处理信息化程度等 等，使收货时间的估算不能简单依据商品品种和数量，这是目前中国城 市配送的特色，也是朝批车辆调度人员最大的困难。以科学的方法获取 其中的规则，用于指导物流管理，是本文讨论的核心问题。 可见，朝批车辆调度问题直接来源于企业生产、经营的实际，因而更加复 杂。上述几点是目前大多数算法不适用的主要原因。除此以外，朝批车辆调度 问题数据量很大，目前，朝批每日须完成3 0 0 至1 0 0 0 家客户的配送任务，使用 车辆数为5 0 至3 0 0 ，平均每日需配送2 0 万箱商品，像春节，元旦等业务高峰 期便会达到数据量上限值。随着朝批业务规模的不断扩大，原有的手工排车时 间长成为了效率提高的瓶颈，为了解决这个问题，朝批在2 0 0 6 年先后试用了包 括日立排车软件、北工大排车软件在内的多种软件，下面将简要介绍。 6 第2 章车辆调度问题 2 4 不同的解决方案与应用 2 4 1 配车计划支援系统刊e u p l a n e t 日立工程株式会社在日本物流管理行业，尤其在消减物流成本方面，有着 非常卓著的业绩。配车计划支援系统- n e u p l a n e t 是日立公司开发的物流系 统中最优秀的成果。n e u p l a n e t v i s i o n 系统将遗传算法应用于物流配送的路线优 化，无论在车辆台数、运输费用等方面都提高了5 一1 0 以上的效率【3 8 。3 9 。 鉴于朝批在国内物流配送行业的显著地位，日本日立公司于2 0 0 4 年秋开始 向朝批介绍n e u p l a n e t v i s i o n 系统，将朝批作为n e u p l a n e t v i s i o n 进入中国的重要 目标。根据中国国情和朝批的需求，日立公司对原系统进行了调整改进，于2 0 0 6 年初开发完成了微机版n e u p l a n e t v i s i o n 。 经过朝批对日立排车系统的试用，发现其在以下几个方面不能满足需求： 1 没有有效解决大客户配送问题； 2 没有解决车辆通行证问题； 3 计算时间过长。根据分析，像朝批这样的数据规模和设备条件，该系统 至少需要2 小时的计算时间才能达到预期的改善目标，这是朝批绝对不 能接受的【3 7 1 。 2 4 2 北工大排车系统 我课题组从2 0 0 4 年开始对朝批的车辆调度问题进行研究，从对朝批实际配 送业务流程的了解、需求分析、数据整理、建构模型，算法研究、软件开发到 最后的模拟数据测试，提出了一种解决城市现代物流配送车辆调度问题的算法。 该算法将约束规划与启发式算法相结合，全局与局部搜索相结合，融入聚类算 法、节约算法、最邻近法等多种方法的精华，解决了朝批的实际需求，特别是 解决了一些日立排车系统无法有效解决的问题，例如车辆通行证问题，大客户 配送问题等【3 刀。基于该算法的排车系统已于2 0 0 7 年8 月开始试用，并取得了较 好的效果。 但随着时间的增加，一些问题也逐渐显露。主要表现在车辆调度人员对于 部分智能调度结果不能完全认可、智能调度结果与调度人员的预期有一定差距。 针对该问题，经过大量的数据整理、分析，本文认为有两个原因，存在两 种解决方案： 1 算法本身局限性。不可否认，面对如此复杂的问题，目前已有的算法都 必然有其局限性。我课题组所提出的算法在全局搜索能力方面的确有所 不足。目前，我课题组已与其它科研机构合作，进一步进行算法的研究。 北京工业大学工学硕士学位论文 但由于朝批车辆调度问题复杂性，想要在算法上取得很大突破、并使智 能调度的综合利用率获得进一步提高的难度极大。 2 部分运算参数、运算依据的不准确性。无论采取何种算法解决朝批车辆 调度问题，都必须依赖一部分计算参数或者运算依据。而如果这部分数 据不准确，将极大影响车辆调度的结果。如果能获得更加准确，真实的 数据，将能够进一步提高车辆调度的结果。 2 5 运算依据 朝批车辆调度诸多约束中非常重要的一项就是车辆( 司机) 工作时间的约 束，即工作时间限制。车辆工作时间通过以下公式计算： 车辆工作时间= 客户停留时间+ 路程时间 路程时间= 仓库客户时间+ 客户间路程时间 车辆工作时间= 客户停留时间论库客户时间+ 客户问路程时间 客户停留时间反映的是车辆到达客户处开始，到最终完成送货任务并离开 所用时间。路程时间反映的是车辆为了完成配送任务在道路上行驶的时间，包 括往返于仓库及客户之间的路程时间，以及客户问路程时间。本文以仓库客户 时间表示车辆往返于仓库及客户之间所消耗的时间。若某车辆某日须完成客户 a 、b 、c 的配送任务，上述公式中相关时间可以由图2 1 表示。 i 仓库客户时间l l 仓库客户时间】 i 客户问路程时间1 【客户问路程时间】 图2 - 1 车辆工作时间 f i g u r e2 1w o r k i n gt i m eo fv e h i c l e 车辆从仓库出发，先后完成客户a 、b 、c 卸货任务。在客户处停留并完成 卸货任务所耗费的时间称为客户停留时间。车辆从仓库出发，到达a 客户所耗 费时间称为客户a 的仓库客户时间，从客户c 返回仓库所耗费时间称为客户c 第2 章车辆调度问题 的仓库客户时间。车辆在a 、b 之间、b 、c 之间的行驶时间称为客户问路程时 间。简而言之，仓库客户时间反映了车辆为了完成送货任务，耗费在往返于仓 库和客户之间的时间。此处以朝批某配送中心某车队2 0 0 8 年3 月至2 0 0 8 年5 月间车辆智能调度实际数据为例，说明客户停留时间、仓库客户时间、客户问 路程时间与车辆工作时间的关系，如表2 1 所示( 括号内为客户停留时间、仓 库客户时间、客户问路程时间在车辆工作时间所占比例) ： 表2 一l 车辆工作时间( 时间单位：小时) t a b l e2 - 1w o r k i n gt i m eo fv e h i c l e 影j 量譬窖1 车辆；。 矗t ：? 矗? ! ? ? 一一：t ；：i 一p j 嚣j ：j ? ：紫千囊孥：i 箩：j 谔 ；j 专一。一：e ：- ： j 譬毫l 蓉户i j i j! 秘j 量j - 仓库戋1 ：乏誓二7 ；j 誊毒：客户一冀了臻 鑫日期：赶_ 作? ： 鞋：j | ，| 誊，1 存舀时商i j 之妻曩客户时向_ ：；曼j ；蠢：! 伺路程时向，j 瀑 ! ：_ r正呼 鬈i ：1 9 ； ! t 时间。毫 ：爹i ! 鼍0 以j1 - - 。j ：j节! ：+ ：，7 i ? ，j ：- i ? o i -毒：1 1 ：o = 叠：。j 哥j - 彳j 糍 2 0 0 8 0 37 1 9 4 1 4 6 9 9 6 ( 6 5 3 3 )1 7 9 4 6 5 ( 2 4 9 5 )6 9 9 8 5 ( 9 7 2 ) 2 0 0 8 0 46 4 8 4 3 24 3 7 4 8 2 ( 6 7 4 7 )1 5 1 0 7 ( 2 3 3 )5 9 8 8 ( 9 2 3 ) 2 0 0 8 0 56 9 2 0 3 74 6 6 0 4 3 ( 6 7 3 4 )1 6 1 4 3 2 ( 2 3 3 3 )6 4 5 6 2 ( 9 3 3 ) 平均 6 8 6 6 2 64 5 7 8 2 8 ( 6 6 6 8 ) 1 6 3 9 8 9 ( 2 3 8 8 )6 4 8 0 9 ( 9 4 4 ) 进一步分析这组数据，可知，2 0 0 8 年3 月至5 月间，在车辆工作时间中， 平均6 6 6 8 的时间耗费在客户停留时间上。平均2 3 8 8 的时间耗费在仓库客 户时间上( 仓库客户时间在车辆工作时间中所占比例，与朝批在北京市的配送 中心的地理位置有很大关系) ，两者比重之和超过9 0 。经过统计，其他时间段 内的数据情况与该表接近。因而，准确的客户停留时间、仓库客户时间对车辆 调度的结果有很大影响。 2 5 1 客户停留时间 客户停留时间反映的是从车辆到达客户处开始，到最终完成卸货任务并离 开所用时间。根据北京市物流实际情况，客户停留时间包括车辆在客户处的卸 货时间以及卸货等待时间，计算公式如下： 客户停留时间= 卸货时间+ 卸货等待时间 卸货时间表示司机完成搬运货物、签收票据、货物验收等卸货任务所消耗 的时间。而卸货等待时间表示车辆到达客户后在完成上述卸货任务前排队等待 所消耗的时间。 卸货时间通过如下方法计算： 卸货时间= 标准卸货时间卸货难易系数 卸货难易系数、卸货等待时间均针对客户而言，随客户的不同而不同。卸 货难易系数反映的是车辆为客户送货的难度。而标准卸货时间的计算方法是调 9 北京工业大学工学硕十学位论文 度人员根据多年经验总结出来的。文字描述如下：每卸货1 0 箱需要1 分钟，每 增加1 个品种需要增加o 5 分钟。公式如下： 标准卸货时间= ( 商品箱数每分钟卸货箱数) + ( 品种数1 ) 品种加时数 那么，卸货时间= ( 商品箱数1 0 + ( 品种数1 ) 幸0 5 ) 卸货难易系数 经过整理后，客户停留时间计算方法如下： 客户停留时间= ( 商品箱数1 0 + ( 品种数1 ) o 5 ) 卸货难易系数+ 卸货等待时 间 本文将这种客户停留时间的计算公式称为经验公式，将该公式中两个关键 性的参数称为经验参数，因为目前它们也是调度人员根据经验为每个客户设置 的，并保存在了客户档案数据中。 那么，这里就产生了两个关键性问题： 第一，经验公式本身是否科学? 第二，经验参数是否准确? 要判断经验公式是否科学、准确，莫若提出另外一种停留时间的计算方法， 并将两种方法进行比较。本文通过另外一种计算方法及针对两种方法的多次分 析、比较后，认为经验公式比较准确( 将在本文第四章详细论述) 。 在经验公式准确的前提下，经验参数的准确设置就十分重要了，因为经验 参数的准确性对车辆调度效果的影响十分显著。在每个客户订货的品种数和箱 数已知的情况下，经验参数大小就决定了送货车辆在客户停留时间的长短。由 于存在时间约束，送货车辆在每个客户停留时间较短，每天就可以安排给更多 的客户送货；反之，送货车辆在每个客户停留时间过长，每天就只能安排给较 少的客户送货，这就直接影响着车辆调度的结果。经验参数的设置受到各种因 素的影响，且经验参数由卸货难易系数和卸货等待时间两个参数组成，依靠经 验则难于把握。此外，仅在北京地区，朝批就拥有数千客户，依靠调度人员的 经验无法精确设置每个客户的卸货难易系数和卸货等待时间。 车辆智能调度系统在经验参数的作用下产生司机工作量的均衡的配送计 划。但从朝批物流的实际角度看，司机们按照配送计划执行后的实际工作量却 极不均衡。部分司机工作强度低，卸货难度低，返回仓库早，而另外一部分司 机工作强度高，卸货难度高，大量超时工作却难以完成工作。这里就又产生了 一系列关键问题t 执行工作量均衡的配送计划为何产生这样的失衡结果? 这种实际情况出现 的原因到底是客户卸货没有规律可循还是经验参数存在偏差? 还需要指出的是，根据目前经验参数的设置，卸货等待时间在全部客户停 留时间中所占的比重很大，约为4 7 。表2 3 为5 个客户的经验参数。若等待 时间为1 5 0 分钟，表示车辆为了完成该客户的卸货任务需等待2 个半小时。 l o 表2 2 部分客户卸货难易系数、卸货等待时间( 时间单位：分钟) t a ble 2 2d i s c h a r g ed i f f i c u l t yl e v e la n dw a i t i n gt i m eo fs o m ec u s t o m e r s 客户编码卸货难易系数卸货等待时间 0 0 0 2 0 61 52 0 0 0 0 2 3 l 1 5 3 0 0 0 0 9 0 03 015 0 0 1 4 5 0 11 815 0 0 2 0 0 4 52 36 0 2 5 2 路程时间与仓库客户时间 由表2 1 可知，仓库客户时间是路程时间中最主要的部分。它决定于仓库与 客户间的距离。客户与仓库的距离不能按照两者位置的直线距离选取，而应该 完全按照车辆在二者间行驶的道路进行计算，这样才符合实际。车辆行驶路径 的选取有很多种方法，车辆配送的目的是找到最节约成本的方法，最常用的就 是使用最优路径。本系统中并非以纯距离衡量是否最优，而采用时间意义上的 最优【4 0 】。仓库客户时间即反映从仓库出发到达某客户所需要的最短( 最优) 时 间或者从客户返回仓库的最短( 最优) 时间。 无论采用何种最优路径算法计算这个时间，就必须先得到道路元数据。道 路元数据的选择，直接影响着结果的准确程度。本系统所拥有的道路元数据来 源于第三方地理数据公司，存在于5 个不同图层当中。经过对实际情况的大量 分析，最终选择了从“北京主干路”、“北京街道”、“郊区主干路 、“郊区次 干路 四个图层中提取道路图元信息。并在此基础上进行进一步的道路图元划 分、指定不同道路速度、绑定客户与道路图元交点等操作后，最终利用d i j k s t r a 算法计算得到了朝批所有客户的仓库客户时间，并以客户档案的形式存储在数 据库中，为智能车辆调度系统的实施提供了基础数据【4 0 1 。 但这种经典的最优路径的计算方法，受数字地图的精度、准确度影响很大。 随着北京市城市道路的飞速发展，原有的数字地图信息已不能完全反映当前北 京市实际情况，特别是远郊区县的路网已经发生了极大变化，这种变化使得数 据库中保存的部分客户的仓库客户时间已经不再准确，影响了车辆调度结果。 根据对车辆调度结果的长期统计、分析后发现郊区特别是远郊区县( 例如丰台， 房山，顺义等区县) 的客户的仓库客户时间显著偏大，严重降低了为这些远郊 区县送货的车辆的装载率，长期影响着智能车辆调度结果。 北京工业大学工学硕士学位论文 2 6 本文研究方法及目标 上文先后介绍了直接影响车辆调度结果的三个参数( 运算依据) 卸货 难易系数，卸货等待时间，仓库客户时间，并分析了这三个参数作用于朝批车 辆调度问题的方式，以及不准确的原因。更为重要的是，这些参数是独立于算 法的。无论采用何种算法解决该问题，都要满足车辆工作时间的约束，就要依 靠这些参数进行计算。 目前这三个参数均以客户档案的形式存储在数据库中，本文以“档案”代 称这三个参数。此外，本文中，“作业单”代指车辆配送计划。 本文的主要思路如图2 2 所示。 口一鲫一集卜g p s 原始数据 厂 i i i 笛一车辆调度) - 配送作业单+ ( 。茹僦，际停留数据圃 合利用率卜j 图2 2 解决方案 f i g u r e2 - 2s o l u t i o n 本文通过g p s 数据接收系统解决了如何获取车载终端的g p s 数据并积累海 量g p s 数据的问题。而g p s 原始数据的主要信息是车辆坐标、时间、速度，而 目标是为了获取车辆在客户处卸货的一些细节，例如何时到达客户，何时离开， 停留时间等，因而必须通过一定的方法对g p s 原始数据进行处理，这就形成了 停留点捕捉匹配算法。通过该算法可从g p s 数据中挖掘大量的车辆工作的细节 信息，即停留点数据。在这些数据的基础上，通过建立数学模型，并以回归分 析为挖掘手段，可以挖掘得到大量科学准确的运算依据、客户资料( 卸货难易 系数、卸货等待时间等) ，利用这些数据指导车辆调度，以提高车辆调度的综合 利用率。另外，本文介绍了如何利用g p s 原始数据、停留点数据建立司机绩效 考核体系。 本文的研究目标主要是： 其一利用相关数据挖掘方法，从海量g p s 数据中获取车辆调度问题相关参 数，这些参数与具体的算法无关，反映的是当前物流行业的实际情况，并依靠 这些参数，指导车辆智能调度，并使其综合利用率在现有算法上提高3 左右( 相 对于一定的评价体系而言) 。 其二进一步分析、挖掘g p s 数据，提高物流企业车辆监控能力，建立科学 1 2 第2 章车辆调度问题 的司机绩效考核体系。 2 7 本章小结 本章首先根据朝批实际需求分析了本课题研究的必要性。重点介绍了车辆 调度问题的概念及其解决方法，并分析了朝批车辆调度这一实际问题的复杂性， 以车辆工作时间为切入点，介绍了各种影响朝批车辆调度综合利用率的运算依 据它们独立于具体的算法，目前主要由人为估计，对朝批车辆调度的效果 造成了显著影响。本文提出了利用g p s 数据挖掘指导车辆智能调度的方法，并 提出在现有算法的基础上，将车辆智能调度的综合利用率提高3 左右的目标。 第3 章车辆停留点 鼍i一_一ei 一, i i ! 曼! ! 皇! ! ! 曼! 曼曼! 葛 3 1g p s 数据接收 第3 章车辆停留点 朝批作为华北地区规模最大的批发物流公司，其车队规模庞大。自2 0 0 7 年 1 0 月以来，仅在北京地区，朝批已先后为2 1 6 辆物流载货车辆安装了带有g p s 功能的汽车行驶记录仪。该设各的提供商为北京吉富通公司，每分钟会向该公 司的服务器发送一条包含g p s 信息的记录仪数据。对于朝批而言，为了进一步 分析、利用g p s 数据，首先必须将g p s 数据接收( 或下载) 到本地( 即企业内 部数据库) 。因此，如何实现接收g p s 数据成为了首先需要解决的问题。 3 1 1 通信协议 该公司提供了与服务器进行通信的通信协议。协议包括了对登录注销服务 器、保持连接、发送命令、历史数据下载等操作进行的定义。车辆g p s 数据的 传输以终端为单位进行。由该协议所定义的通信流程如图3 1 所示。 匡囹匡鲴 建互连馁，登陆请承 登陆请求回复 一 请求保持连接 保持连接回复 请求传输数据 数据条目回复 数据条目确认 发送数据 数据到达确认，继续请求数据 请求注销 注销回复 图3 - i 通信流程 f i g u r e3 1c o m m u n i c a t i o np r o c e s s e s 北京工业大学t 学硕十学位论文 3 1 2 概要设计 根据对协议流程的深入分析，选择了面向连接的s o c k e t 作为双方通信的工 具。s o c k e t 是一种应用程序访问通信协议的操作系统调用，它使程序员可以很 方便地访问t c p i p ，从而开发各种网络应用的程序f 4 1 i 。在数据库设计方面，设 计了以下两个表用来保存接收得到的g p s 数据，如表3 1 所示。 表3 - i 数据库设计 t a b l e 3 - 1d e s i g no fd a t a b a s e 黪j ；炭名称i鬟誊鼍i 警蠢j 。说明；誊鑫秘豫毫遘矗糕；霜 t m s g ps d b 与吉富通公司数据结构完全一致，保存下载后原始信息 t m s g p s _ r e c由t m s g p s d b 中数据过滤、转换后得来，系统的核心表 t m s g p s r e c 表结构如表3 - 2 所示。 表3 - 2t m s g p s _ r e c 表结构 t a b l e 3 2t a b l es t r u c t u r eo fm a s _ g p s _ _ r e c 序号 名称一 类型长度 _ j ? c ：。注释27 裂 1i dn u m b e