（机械制造及其自动化专业论文）电子商务环境下第三方物流企业车辆调度研究.pdf

硕士论文 电子商务环境下第三方物流企业车辆调度研究 摘要 随着电子商务的发展，“物流瓶颈”的限制作用愈发突显出来，必须对物 流系统进行优化以适应我国电子商务发展的需要。配送车辆调度系统优化是物 流配送系统优化的重要内容之。 本课题就是着眼于这一实际需要，利用先进的优化算法和地理信息系统的 集成，对适应于第三方运输物流企业的车辆调度系统进行相应的研究。研究的 一。个内容是车辆调度中的算法解决，车辆调度问题( v e h i c l es c h e d u l i n g p r o b l e m ，v s p ) 是一个典型的非确定性多项式算法问题( n p 问题) ，在本课 题中将采用遗传算法对问题进行求解。研究的另一个内容是开发基于g i s 的车 辆调度辅助系统。借助于g i s 系统，实现对车辆调度进行规划时的可视化管理 和辅助决策。并通过与定位技术g p s 、通信技术g s m 的集成对该系统进行扩 展。 关键词：车辆调度，遗传算法，地理信息系统( g i s ) 硕：仁论文 屯子商务环境下第三方物流企业车辆调度研究 a b s t r a c t w i t ht h e d e v e l o p m e n to ft h ee c ( e l e c t r o n i cc o m m e r c e ) ，t h er e s t r i c t i n g i n f l u e n c eo f t h e “l o g i s t i cb o t t l e n e c k ”i sb e i n gp r o m i n e n t 。w em u s to p t i m i z et h e p h y s i c a ld i s t r i b u t i o ns y s t e mt om e e t 、i mt h er e q u i r e m e n to fe c sd e v e l o p m e n t 。 t h eo p t i m i z a t i o no fd e l i v e r yv e h i c l ed i s p a t c hs y s t e mi so n ei m p o r t a n tp a r to ft h e o p t i m i z a t i o no f t h ep h y s i c a ld i s t r i b u t i o ns y s t e m 。 t h et h e s i sj u s tf o c u s e so nt h er e a l r e q u i r e m e n t ，t a k i n ga d v a n t a g e o ft h e i n t e g r a t i o no fa d v a n c e do p t i m i z ea l g o r i t h ma n dt h eg e o g r a p h yi n f o r m a t i o ns y s t e m ( g i s ) ，a n dd o e st h er e s e a r c ho nt h ed e l i v e r yv e h i c l ed i s p a t c hs y s t e mt h a ti sf i r e d i nw i t ht h et h i r dp a r tl o g i s t i c sc o m p a n y 。t h er e s e a r c hi n c l u d e st w o p a r t s ，o n ep a r t i st h er e s e a r c ho nt h ea l g o r i t h ms o l u t i o nt ot h ev s p ，t h eo t h e rp a r ti st h er e s e a r c ho n t h eg i s s y s t e m 。v s p ( v e h i c l es c h e d u l i n g p r o b l e m ) i sa t y p i c a l n p ( n o n d e t e r m i n i s t i cp o l y n o m i a l ) p r o b l e m 。i nt h et h e s i s ，t h eg e n e t i ca l g o r i t h mi s u t i l i z e dt os o l v et h ev s p 。t h es e c o n dp a r to fr e s e a r c hi s s e t t i n gu paa u x i l i a r y s y s t e mb a s e do n t h eg i ss y s t e m ，b yw h i c hw ec a nm a k et h ep r o c e d u r eo f t h ev e h i c l e r e a l t i m ed i s p a t c hm a n a g e m e n tv i s i b l e ，a n db e i n ge n l a r g e dt h r o u g ht h ec o m b i n a t i o n w i t ht h e l o c a t i n gt e c h n i q u e ( g p s ) a n d t h et e l e c o m m u n i c a t i o n t e c h n i q u e ( g s m ) 。 k e yw o r d s ：v e h i c l ed i s p a t c h ，g e n e t i ca l g o r i t h m ，g i s i i z 6 2 4 , 5 5 4 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历雨使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：避! 堡：上。啦年7 月，。日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：毖塾垦 3 神年年月f o 日 倾i ，论文 电予商务环境下第三方物流企、车辆调度研究 1 绪论 随着网络通信和信息技术的飞速发展，现代商业逐渐呈现出新的特征：不断增 长的供货能力、不断增长的客户需求、不断增长的全球竞争等。以信息技术为基础 的电子商务在全球迅速崛起，其本身所具有的开放性、全球性、低成本和高效率的 特点能够更好的满足现代商业的要求，推动社会经济的进步。但是，现阶段电子商 务的实施有着不可回避的“物流瓶颈”：首先，电子商务本身无法解决商品实体的 转移，除了一些电子产品可以通过互连网直接进行传递外，绝大多数的商品还是要 依靠传统的运输方式进行转移；其次，物流发展相对于电子商务的发展有较大的落 后，这种情况无论是外国还是我国都是存在的，而我国的滞后情况比较严重。“物 流瓶颈”严重制约了我国电子商务的发展。因此，我国国民经济和社会发展“十 五”规划，将“物流配送”作为重点支持发展的服务产业1 1 1 。 物流配送又称终端配送，就是在商品用户集中的区域，按照用户的订货要求， 将配好的货物采用汽车巡回运送的方式递交到收货人的一种小范围、近距离、小批 量、多品种、多用户的运输形式 2 1 。目前我国企业的物流配送主要采用三种方式： 自己组织配送：借助连锁企业进行配送；外包的专业配送公司。其中第三种方式是 最为广泛采用的口】。专业的配送公司也就是我们通常意义上的第三方运输物流企 业。 第三方运输物流企业运营成败的根本在于能否合理的对本公司的承运车辆进行 调度，以期能最大效力的发挥运力和降低成本。在电子商务环境下，已经不可能再 采用传统的手工调度方式，而是要借助先进的计算机辅助调度系统来进行车辆调 度。国外有一些先进的调度软件，如美国m o d u l a r ( 模块) 公司开发的d i s p a t c h 调度系统，能够采用先进的调度算法，较好的解决车辆调度问题。但是由于费用和 实施、维护问题，并不适应于我国刚刚起步的第三方运输物流企业。开发出适应于 小型企业的配送车辆调度系统是推动我国物流配送企业发展的当务之急。 1 1 电子商务与第三方物流 电子商务是信息时代商务模式的实质性变革，也是未来商务活动方式的发展方 向。当前电子商务方兴未艾，作为一种新的商务运作形式，已经逐渐成为推动经济 发展的关键。据资料显示，在2 0 0 3 年电子商务达到1 5 0 0 0 亿美元的交易额。我国也 大力推动电子商务的发展，并将1 9 9 9 年定为“政府上网年”，2 0 0 0 年定为“企业 上网年” 4 1 。同时，越来越多的企业将电子商务视为企业发展的新契机，纷纷建立 颂士论文 电子商务环境下第二三方物流企业车辆调度研究 自己的电子商务平台。随着计算机和网络的进一步发展，电子商务必将在商务活动 中占据更大的比例。 2 0 世纪8 0 年代，西方发达国家，如美国、法国和德国等，提出了“物流一体 化”的理论，用于指导物流发展，并取得了明显的效果。进而发展出第三方物流概 念，即由供货方和收货方之外的第三方来完成物流配送工作。第三方物流是一种社 会化物流形式，既可以降低企业白行组织运送所造成的资金积压，又能通过资源的 集中来提高运送的效率，因此也日渐成为物流运输行业的主导模式。 电子商务和物流具有无法割裂的关系，因此电子商务环境下的第三方物流企业 的发展水平不但直接影响企业的效益，而且也制约我国电子商务的发展，进而影响 了我国国民经济的快速增长。以下简单的介绍一。f 电子商务和第三方物流的相关知 识点以及电子商务和第三方物流之间相辅相成的关系。 1 1 1 电子商务 所谓电子商务( e l e c t r o n i cc o m m e r c e 或e l e c t r o n i cb u s i n e s s ) 就是利用现有的计算 机硬件设备、软件设备和网络基础设施，通过一定的协议连接起来的电子网络环境 进行各种各样商业活动的方式陋1 。它的具体含义就是指进行电子商务交易的供需双 方，通过网络平台，完成商务交易的过程。电子商务有广义和狭义之分：广义的电 子商务是指电子工具在商务活动中的应用；狭义的电子商务是指在信息社会中，掌 握信息技术和商务技术的人，系统化运用网络和计算机技术，高效率、低成本地从 事以商品交换为中心的各种商业事务活动6 1 。 电子商务的流程如图1 1 1 1 所示 寻找产品朋务信 息，发现产品信息 + 各种信息比较 + 价格、交货时间等问 题的谈判 + 订购 付款 发货、仓储、运输、 加工、配送、收费 + 消费者服务和支持 图1 1 1 1电子商务的流程图( t h ep r o c e s so f e c ) 坝十论文电子商务环境下第三方物流企业车辆调度研究 由流程图可见，电子商务是由商流、 流、信息流和资金流都可以由网络完成， 物流、信息流和资金流构成的，其中商 只有物流必须借助于现实中的运输来完 成，因此物流也就成为电子商务发展的现实基础和制约条件。电子商务环境下的物 流具有以下特点： 1 ) 信息化：物流信息化是电子商务的必然要求。物流信息化表现为物流信息的 商品化、物流信息收集的数据库化和代码化、物流信息处理的电子化和计算机化、 物流信息传递的标准化和实时化、物流信息存储数字化等物流信息化是物流现代化 管理的基础，没有物流的信息化，任何先进的技术设备都不可能应用于物流领域。 信息技术化及计算机在物流中的应用将会彻底改变物流面貌。 2 ) 自动化：自动化的基础是信息化，自动化的核心是机电一体化，自动化的外 在表现是无人化。物流自动化的设备很多，如条形码自动识别系统、自动分拣系 统、自动存取系统、自动导向车、货物自动跟踪系统等。这些设施在发达国家已普 遍用于物流作业中，而在我国由于物流业起步晚，发展水平低，自动化技术的普及 还需要相当长的时间。 3 ) 网络化：物流领域网络化的基础也是信息化，网络化的含义是物流配送系统 的计算机之问通信网络，包括物流配送中心与生产厂商的联系要通过计算机网络以 及零售商与物流中心之间的联系也要通过计算机通信的方式，借助于增值网上的电 子订货系统( e o s ) 和电子数据交换技术( e d i ) 来自动实现，配送中心通过计算机 网络收集零售商的订货过程也可自动完成。 物流的网络化是物流信息化的必然，是电子商务活动的主要特征之。当今世 界i n t e r n e t 等全球网络资源的可用性，以及网络技术的普及为物流的网络化提供 了良好的外部环境，物流网络化的趋势不可阻挡。 4 ) 智能化：这是物流自动化和信息化的一种高层次应用。物流作业过程中存在 大量的运筹和决策，如库存水平的确定、运输路线的选择、自动导向车的运行轨迹 和作业控制、物流配送中心经营管理决策支持等问题都要借助大量的知识才能解 决。在物流自动化的过程中，物流智能化是不可回避的技术难题。 5 ) 柔性化：柔性化是真正的根据消费者需求的变化来调节生产工艺，没有配套 的柔性化的物流系统是不可能达到目的的。2 0 世纪9 0 年代，国际生产领域纷纷推 出柔性制造系统。像企业资源计划以及供应链管理的概念和技术，它们的实质就是 将生产流通作为基础，根据需求组织生产、安排物流活动。因此，柔性化的物流正 是适应生产、流通和消费的需求发展起来的一种新型物流模式。这就要求配送要根 据消费要求的“多品种、小批量、多批次、短周期”的特点灵活的组织和实施物流作 、l k 。 颂 = 论文 电r 商务环境下第三方物流企业车辆调度研究 1 1 2 第三方物流 2 0 世纪8 0 年代，西方发达国家，如美国、法国和德国等，提出了“物流一体 化”的理论，用于指导物流发展，并取得了明显的效果。所谓物流体化就是以物 流系统为核心的，由生产企业、物流企业、销售企业和消费者组成的供应链的整体 化和系统化。物流一体化是以第三方物流充分发展和完善为前提的，同时又为第三 方物流的发展提供了良好的发展环境和巨大的市场需求。 第三方物流( t h i r dp a r tl o g i s t i c s ) 是指由物流劳务的供方、需方之外的第三方去 完成的物流服务的物流运作方式。第三方就是指提供物流交易双方的部分或全部物 流功能的外部服务者。从某种意义上讲，第三方物流是物流专业化的一种形式：第 三方物流是随着物流业的发展而发展的，而且第三方物流的占有率与物流产业的水 平之间有着非常规律的正比关系，即第三方物流的占有率越高，物流产业的发暮水 平越高。西方国家的物流业发展实证“只有当独立的第三方物流占社会的5 0 物 流产业才能形成” 7 1 。所以第三方物流的发展程度反映和体现了一个国家的物流业 发展的整体水平。 相对于大型企业在内部设立物流部门而言，选择独立的第三方物流企业有专如 下的优点【8 】： ( 1 ) 集中主业：生产企业使用第三方物流可以使企业实现资源的优化配置，将有 限的人力、财力集中于核心业务，进行重点研究，开发新产品来参与市场竞争增 强企业的核心竞争力。 f 2 ) 降低物流成本：专业的第三方物流提供者利用规模生产的专业优势和成五优 势，通过提高各环节能力的利用率实现费用节省。与建立自己的物流部门相比选 择第三方物流更能够降低成本。 ( 3 ) 减少库存：第三方物流服务提供者借助精心策划的物流计划和适时的运送手 段，最大限度地减少库存，改善了企业的现金流量，实现成本优势。 f 4 1 塑造企业形象：第三方物流服务提供者与顾客是一种战略伙伴关系，第三方 物流提供者利用完备的设施和训练有素的员工对整个供应链实现完全的控制，减少 物流的复杂性，通过自己的网络体系帮助顾客改进服务，不仅树立自己的品镡形 象，而且使顾客在竞争中获得更多的顾客价值。 1 1 3 电子商务和第三方物流的关系 第三方物流的发展可以促进电子商务的发展。首先，电子商务企业的物流配送 并非自己的强项，与其自行组织配送或是组建自己的物流配送中心不如将配送业务 硕士_ 睦文 电子商务环境下第三方物流企业车辆调度研究 对外发包，这样可以实现资源的优化配置，将主要资源集中在自己的核心事业上； 其次，第三方物流是专业化、社会化物流形式，有丰富的专业知识、专业人才和物 流经验，能够提供专业优质的物流配送服务，能够调动各种社会资源。电子商务企 业通过第三方物流企业可以提高自身的配送质量，提高产品对于客户的可得性，使 电子商务这种商业模式为大众所接受，推广电子商务：第三，作为非物流行业的企 业对于商品配送的成本难以进行准确的估算和控制，选择电子商务模式时可能出现 考虑不足，盲目上马的现象。如果选择第三方物流，可以通过签订合同明确配送成 本，全盘考虑项目运行的可行性，降低风险和资金沉淀。 同时电子商务推动了第三方物流的发展。首先，电子商务的蓬勃发展给第三方 物流带来了新的契机。电子商务环境下，商业空间的扩张要求企业能满足不断扩大 的供货需求和不断扩大的客户需求，外部市场环境的变化使企业的生产经营活动也 变得越来越复杂，要实现物流活动的合理化，仅仅将物流系统局限在企业内部已远 远不够。建立企业间、跨行业的物流系统网络，将原材料生产企业、制品生产企 业、批发零售企业等在生产流通过程中的上下游相关企业的物流活动有机结合起 来，形成一个链状的商品供应系统，是构筑现代物流大系统的要求。第三方物流企 业通过其掌握的物流系统开发设计能力，信息技术能力，成为建立物流系统网络的 组织者，能完成电子商务企业所无法实现的工作；其次，电子商务为第三方物流提 供了新的发展平台。电子商务环境要求对现有的物流体系进行电子化改造，第三方 物流企业采用先进的通信设备和计算机技术来实现管理和运营将提高效率，赢得更 大的市场空削。 综上所述，电子商务能推动第三方物流的发展，同时第三方物流能促进电子商 务的普及，电子商务和第三方物流的结合，必将实现电子商务和第三方物流双赢的 局面i 纠。 1 2 车辆调度算法 如何对物流系统进行优化，提高物流系统的运行效率，实现资源的优化配置， 是现代第三方物流企业所要考虑的主要问题。物流系统主要由存储和运输两部分构 成。相对而言，存储能力的提高更多的依赖于设备的自动化、智能化水平的提高， 而运输水平的提高则取决于调度和协调的能力的加强。车辆的优化调度是物流系统 优化的关键环节，也是电子商务活动必不可少的内容。通过车辆的优化调度，可以 在不追加或少追加投入的情况下提高经济效益。对车辆调度算法的研究是建立现代 调度指挥系统和开展电子商务的基础。 硕卜论文 电子商务环境下第三方物流企业车辆调度研究 1 2 - 1 问题的提出 车辆优化调度问题最早是由d a n t z i g 和r a m s e r 于t 9 5 9 年提出的。后来的学者 将车辆调度问题称为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 ) ；同时考虑空间位置和时间要求时称为混合问题【l 。 车辆优化调度问题一经提出就很快引起运筹学、应用数学、组合数学、图论和 网络分析、物流科学、计算机应用等学科的专家的极大重视，成为运筹学和组合优 化领域的前沿与研究热点问题。 为了简化车辆优化调度问题，常常应用一些技术将问题分解或转化为+ 个或几 个已经研究过的基本问题，再应用一些比较成熟的方法，得到原来问题的最优解或 者是满意解。 车辆优化调度中常见的基本问题有：旅行商问题、分派问题、运输问题、背包 问题、最短路线问题、最小费用问题、中国邮路问题等等。 常用的基本理论和方法有：分枝定界法、割平面法、线性规划法、匹配理论、 对偶理论、组合理论、线搜索技术、列生成技术、概率分析、统计分析、最差情况 分析、经验分析等【”j 。 1 2 2 常用的算法 车辆调度问题的求解方法非常丰富，m a g n a n t j ( 1 9 8 1 ) ，b o d i n 和g o l d e n ( 1 9 8 3 ) ，l a p o r t e ( 1 9 9 2 ) ，l a p o r t e 和o s m a n ( 1 9 9 5 ) 等许多学者对v s p 求解方 法进行研究，将算法分为精确算法和启发式算法两大类i 】o j ： 精确算法包括：分枝定界法( b r a n c ha n db o u n da p p r o a c h ) 、割平面法 ( c u t t i n gp l a n e sa p p r o a c h ) 、网络流算法( n e t w o r kf l o wa p p r o a c h ) 、动态规划法 ( d y n a m i cp r o g r a m m i n ga p p r o a c h ) 等。精确算法的计算量一般随问题规模的扩大呈 指数增长，因此在实际中其应用范围有限。 启发式算法是一种近似算法，根据一定的搜索规则逐渐逼近最优解。它包括禁 忌搜索算法( t a b us e a r c h ) 、模拟退火算法( s i m u l a t e da n n e a l i n g ) 、遗传算法 ( g e n e t i ca l g o r i t h m ) 和神经网络算法( n e u r a ln e t w o r k s ) 等。 禁忌搜索算法( g e n d r e a u 、h e n z 和l a p o r t e ，1 9 9 4 i l l j ；j i e f e n g 和j a m e s ， 1 9 9 6 1 2 1 ：d u h a m e l 、c h r i s t o p h e 和p o t v i n ，1 9 9 7 t 1 3 1 ；b a r b a r o s o g t u ，1 9 9 9 t 1 4 】) 和模拟 退火算法( o s m a n ，1 9 9 3 e 15 】；a l e xv a n ，1 9 9 5 怕1 ) 在求解v s p 中已经取得较好的效 6 硕士论文 电子商务环境下第三方物流企业车辆调度研究 果，但是由于这些方法过于复杂，运算量大，涉及复杂的邻域转换和求解策略，在 实际应用中不容易实现。 遗传算法( o l i v e r 和s m i t h ，1 9 8 9 1 7 】；f o g e l ，1 9 9 3 t 1 8 】) 在旅行商问题上的应用 已经有了一定的成果，已有文献利用遗传算法对v s p 问题进行求解( b e r t h o l d ， 1 9 9 5 t 1 9 1 ；m a l m b o r g ，1 9 9 6 【2 0 1 ；o c h i 和l u i z ，1 9 9 8 t 2 1 1 ) ，但仅仅是开始尝试阶段， 还有待进一步的研究。 神经网络的发展，也促进了旅行商问题t s p ( t r a v e l l i n gs a l e s m a np r o b l e m ) 的较 好解决( w i l s o n ，1 9 8 8 1 2 2 1 ) ，但在v s p 中的应用还刚刚开始( n y g a r dk 、j u e l lp 和 k a d a b an ，1 9 9 0 1 2 3 】t o r k i 和a d o l h a m i d ，1 9 9 7 l 2 4 1 ) 。 1 3g i s 系统 地理信息系统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 2 ”。 g i s 理论萌芽于2 0 世纪6 0 年代，是由加拿大的r o g e rf t o m l i n s o n 和美国的 d u a r ef m a r b l e 在独立的情况下分别提出的。我们通常所说的g i s 系统是管理信 息系统的一种，它的管理对象是事物的地理空间数据和信息。它能提供地理空间数 据的采集、存储、显示、操作、管理、分析和建模等功能。 g i s 系统作为一利，空间信息管理系统，与车辆调度有着必然的联系。车辆调度 是运输车辆空间位置的规划，是建立在各种空间信息基础上的，从各配送点的空间 位置关系到运送路线的选择，都不可避免的与空间地理信息相联系。因此，将g i s 系统引入到车辆调度系统中是十分自然的，也是十分必要的。2 0 0 0 年的国家自然科 学基金项目货运车辆调度优化理论及应用研究就对g i s 系统和车辆调度系统的 结合做了研究，并建立了基于地理信息系统的可视化物流配送车辆优化调度系统。 该系统采用的算法为c w 节约启发式算法，g i s 软件选择的是m a p i n f o 公司的 m a p l n f o p r o f e s s i o n a l 。 物流作为物体在空间和时间上的位移，对地理空间有着较大的依赖性，基于 g i s 技术的车辆优化调度系统对于实现车辆调度的可视化、实时动态管理和辅助决 策具有重大意义。g i s 技术和现代物流管理技术的飞速发展，使得两者集成成为其 发展的必然趋势。随着g p s 技术的民用化普及以及g s m 通信网络的完善， g p s g s m g i s 的集成必将为车辆的实时调度可行性提供坚实的技术支持。 硕匕论文 电亍= 商务环境下第三方物流企业车辆调度研究 1 ，3 1g i s 系统软件的发展 g i s 系统软件在6 0 年代开始研制，在8 0 年代得到迅速普及和推广，出现了 a r c i n f o 、s i c a d 、m g e 、g e n a m a p 、s y s t e m 9 、m i c r o s t a t i o n 等实用软件。到了 9 0 年代中期，随着计算机和软件操作系统的发展，又出现了一批易学易用的g i s 系 统，如m a p i n f o 、a r c v i e w 、g e o m e d i a 等。 从9 0 年代中期开始，g i s 技术得到飞速发展。信息技术的进步，特别是数据 库、网络、图形处理、面向对象开发方法等技术的成熟，为g i s 软件的发展提供了 广阔的发展空间。例如，商用的数据库管理系统( 如o r a c l e 、i n f o r m i x 、 d b 2 、s q ls e r v e r 等) 通过空间数据库引擎技术相继实现了对空间数据的管理， 其管理手段获得了显著的提高；随着面向对象软件方法论的成熟，将计算机软件本 身的新技术，如组件技术( c o m 、d c o m 、o l e ) 、面向对象软件技术( o o ) 引 入g i s 系统中。其中最突出的就是插件技术( p l u 旷i n ) 。软件系统组件化已经成 为一种趋势。国外主要的g i s 软件都开始进行组件化改造，并在9 0 年代末相继完 成。这样g i s 软件可以和主要的跨平台编程工具相结合，可以作为各种编程工具的 功能部件出现。其中m a p i n f o 公司的m a p x 插件就是得到普遍应用的g i s 插件。 现在的g i s 系统软件发展的几个主要分支是：时态g i s ( t g i s ) 、万维网g i s ( w e bg i s ) 、虚拟现实g i s ( v r g i s ) 、开放式g i s ( o p e ng i s ) 、面向对象 g i s ( o o g i s ) 、组件式g i s ( c o m g i s ) 、分布式g i s ( d g i s ) 等。 1 3 2m a p x 插件 m a p x 是m a p l n f o 二次开发中的强大工具，同时它可以独立于m a p l n f o 软件平 台，而作为一种基于w i n d o w s 操作系统的o c x 控件单独使用。利用m a p x 可以 简单快速的在系统中嵌入地图功能。 在有了电子地图的基础上，m a p x 具备了m a p l n f op r o f e s s i o n a l 几乎全部地图操 作功能，而且更加方便。m a p x 具有无缝嵌入、易于掌握、开发周期短、开发成本 低等优点。 使用m a p x 开发，编程人员在开发过程中并不需要掌握其他的专业编程语言， 便可以轻松将地图应用功能嵌入到系统开发中。而且应用可以脱离m a p i n f o 的软 件平台运行。相反在构建应用系统时。如果选用m a p i n f op r o f e s s i o n a l 作为地图化应 用的平台，则需要许多技巧来实现应用系统中的公用信息管理系统与地图管理信息 系统之间的信息交换和通讯。 倾士论文 电了商务环境下第三方物流企业车辆调度研究 1 3 3g p s 与g p s ，g s m 的结合 作为实时提供空间定位数据的技术，全球卫星定位系统( g p s ) 可以与g i s 系 统进行集成，而g p s 提供的位置信息可以通过全球移动通信系统( g s m ) 网络传递 给g i s 系统，这样可以建立一个基于g i s g p s g s m 集成的系统，来完成诸如定 位、测量、导航、监控等功能。 g p s 系统是美国继阿波罗登月计划后的又一太空计划。整个系统于1 9 9 3 年正 式投入使用，能提供通信、导航、定位、识别、授时等多种功能。系统的精度由伪 随机码的制式确定，采用p 码的定位称为精密定位服务，用于军方和一些有授权的 民用用户，精度较高；采用c a 码的定位服务称为标准定位服务，用于一般的g p s 用户。同时，为了保证自己的利益，美国采用“选择可用性” ( s e l e c t i v e a v a i l a b i l i t y ) 措施来人为的降低定位精度。大部分应用要提高精度都要使用差分技 术。随着2 0 0 0 年5 月1 日后s a 措施的取消，g p s 的民用化应用得到迅速发展。 g s m 蜂窝移动通信系统是现今发展最为完善的数字移动通信系统。1 9 9 5 年中国 移动和中国联通均采用g s m 建立通信网络。它提供多种业务，包括话音、数据和 短信息。其中短信息业务是g s m 网络所独有的业务。可以不通过建立连接，就能 够传递信息。其方式有两种：点对点和小区广播。g s m 网络现在已经遍布全国。 市场上已经出现了基于g p s g s m 的车辆监控系统软件，例如北京慧图信息科 技开发有限公司开发的“慧图g p s g s m 车辆监控调度系统”就可以很好的完成车 辆的定位监控功能。本课题将借鉴其比较成熟的技术架构一个完整的基于 g i s g p s g s m 的车辆优化调度系统。 1 4 本课题的研究内容和意义 在电子商务环境下，第三方物流企业得到长足的发展，每天需要处理的任务量 也在成倍数增长，如何提高车辆调度的效率，对车辆调度环节进行优化，以适应发 展的需要成为企业面临的重要课题。但是目前我国大多数的第三方物流企业的车辆 调度依然依赖于人工经验并采用人工安排的方式，从而导致企业运输资源无法充分 利用，运营成本过高，或者无法满足客户的要求。因此，对车辆调度的优化问题进 行研究，建立能够即时满足客户需求的车辆调度系统，是提升服务及资源利用率的 重要课题。同时车辆的优化调度是物流系统优化的关键环节，也是电子商务活动必 不可少的内容。通过车辆的优化调度，可以在不追加或少追加投入的情况下提高物 流经济效益。对车辆调度算法的研究是建立现代调度指挥系统和开展电子商务的基 础。 硕士论文 电子商务环境下第三方物流企业车辆调度研究 国外的车辆优化调度研究起步早，研究水平高，而且理论成果已经得到了广泛 应用。目前，国外的车辆优化调度研究已经广泛的应用于生产和生活的各个方面， 如报纸投递及线路的优化、牛奶配送及送达线路的优化、电话预订货物的车辆载货 和线路设计、垃圾车的线路优化及垃圾站选址优化、连锁店的送货和线路优化等 等。国外有一些先进的调度软件，如美国m o d u l a r ( 模块) 公司开发的d i s p a t c h 调度系统，能够实现先进的调度算法，较好的解决车辆调度问题。 我国的车辆优化调度问题也得到了国家的高度重视，国家自然科学基金在货运 车辆调度方面进行了立项研究。我国的研究者也在车辆优化调度理论方面取得一些 成绩，但是很多理论成果并没有取得实际上的应用，国内并没有出现普及化程度很 高的车辆优化调度软件。市面上常见的一些车辆调度系统将重点集中在车辆的监控 方面，而忽视了车辆优化调度中的规划方面。针对我国刚刚起步的第三方物流企业 而言，引进国外先进的车辆优化调度软件固然能起到良好的效果，但是其昂贵的价 格以及实施后系统维护的不便是无法回避的问题。尽快开发出适合于我国第三方物 流企业的车辆优化调度软件成为物流从业者和研究者的当务之急。 本课题正是基于这个目的而提出的。课题结合了近期的一些遗传算法在车辆调 度问题上取得的成果，采用遗传算法进行车辆优化调度问题的解决。并且基于地理 信息技术( g i s ) ，并结合现代卫星定位技术、通信技术和计算机技术，对基于g i s 的车辆优化调度系统整体框架进行了探讨。 本文研究的重点是车辆优化调度的算法。在实际应用中，车辆优化调度问题是 个典型的多目标多约束的优化问题，有众多的约束条件，如时间窗、载荷量等， 有多重的目标，如顾客满意度、成本最小等。车辆优化调度问题是一个n p 问题， 通常采用启发式算法进行求解。鉴于遗传算法对模型并无数学上的要求，即不要求 可导、可微、连续等，且在求解中具有高鲁棒性和并行性。因此本文采用遗传算 法。 首先对所研究的车辆优化调度问题建立数学模型，确立问题的目标函数和约束 条件方程，然后进行求解。为了降低运算的复杂程度，需要对约束条件进行松弛， 将约束条件以惩罚函数的形式加入到目标函数中。遗传算法是一种新兴的自适应搜 索算法，它对优化对象没有数学要求，运算过程中只使用适应度函数。因此将目标 函数和适应度函数联系起来成为使用遗传算法的前提条件，然后再对车辆调度问题 进行编码，设计相应的遗传操作算予，选择遗传算法参数等等。 本文采用自然数编码的方法，以一个自然数串作为车辆调度问题的解形式；初 始群体的产生采用随机键方法；结合几种交叉算子的优点，提出一种新型的交叉算 子；变异算予采用反转变异算子；遗传参数的选择采用自行决定的方式，可根据具 硕士论文电了商务环境下第三方物流企业车辆调度研究 体情况对参数进行选择。本文对算法问题编制了相应的程序，编程语言是v i s u a l b a s i c 6 0 。 本文还利用m a p i n f o 公司的m a p x 控件将电予地图功能添加到系统中，使各客 户及优化调度结果能在电子地图上直观的显示出来，实现可视化操作。并且结合了 卫星定位系统g p s 通信系统g s m 地理信息系统o l s ，开发出一个基于g i s 的车辆 优化调度的辅助系统的原型。系统的主体是基于g i s 的可视化车辆优化调度系统， 并在此基础上进行了扩展，对系统与g p s 的结合进行了理论和结构上的探讨。 1 5 论文的结构 本文一共分为六章 第。章绪论，对课题的背景、意义和论文情况进行简单介绍： 第二章遗传算法及其在车辆优化调度中的应用，对遗传算法进行了简单介绍， 并且对遗传算法在车辆调度问题中取得的一些成果进行介绍，如编码、常见交叉算 子、常见变异算子等： 第三章车辆优化调度问题的模型和算法，对第三方物流企业所涉及到的车辆优 化调度问题进行建模，并且采用遗传算法对模型进行求解。涉及到适应度的确定、 最优保留策略、算法终止条件等内容； 第四章g i s 及m a p x ，结合系统中的开发应用介绍了g i s 功能和m a p x 的相关 的知识； 第血章基于g i s 系统的车辆优化调度系统，重点给出了辅助系统的软件结构。 基于m a p l n f o 公司m a p x 控件的g i s 系统，对客户和车辆优化调度结果进行直观显 示。然后对系统的扩展进行了阐述，即结合现有的g p s 技术和g s m 技术，来实现 车辆的实时监控调度； 第六章总结和展望，对研究内容进行概括总结，并指出存在的不足和今后的待 完善的部分。 硕士论文 电子商务环境下第三方物流企业车辆调度研究 2 遗传算法及其在车辆优化调度中的应用 2 1 遗传算法 2 1 1 遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m ) 是一种基于生物自然选择和遗传机理的随机 搜索算法，它是由美国m i c h i g a n 大学的5 h o l l a n d 教授于1 9 7 5 年首先提出的2 6 1 。 由于遗传算法对所求解的优化问题没有什么太多的数学要求，而且能进行概率意义上 的全局的搜索求解，这使得它成为一种应用广泛的优化算法。 遗传算法是“生产+ 检测”的迭代过程的搜索算法。它的基本处理流程如图 2 1 1 1 所示。 伟磊h 确定字符串长度l 随机产生m 个初始个体 j = o 根据适应度选择复制个体 进行复制 将个体添加到新群体 = j + 1 又 p r + 终【l 条件否 计算群体中各个体的适应度 从左到右执行各遗传算子 选择交换个体 j l 一一 进行交抉 输出结果 y 一、 。开始 选择变异个体 j 【 进行变异 将个体添加到新群体 将个体添加到新群体 j _ j + l 又 p m + g e n = g e n + 1 图21 1 1 遗传算法的基本处理流程图 硕士论文 电子商务环境下第三方物流企业车辆调度研究 可见，遗传算法是一种群体性操作，它模仿自然界中适者生存的原理，以适应 度函数为选择的标准，以群体中所有染色体为对象，在问题的解空问作有向的搜 索。选择，交叉和变异是遗传算法的主要操作算子，它们构成了所谓的遗传操作， 使遗传算法具有了其他传统方法所没有的特性。 2 1 2 遗传算法的构成 遗传算法中包含了如下的五个基本要素【2 7 j ： ( 1 ) 参数编码； ( 2 ) 初始群体设定； ( 3 ) 适应度函数的设计： ( 4 ) 遗传操作设计； ( 5 ) 控制参数设定和终止条件选择。 这五个要素构成了遗传算法的核心内容。由于遗传算法不能直接处理解空间的 解数据，必须通过编码把它们表示成遗传空间的基因串结构数据。遗传操作的对象 是编码后的染色体，染色体的集合就是一些初始解的集合，即初始群体。因为初始 群体中不定包含有所要搜索的最优解，遗传算法想要收敛到最优解，就需要依靠 选择，交叉和变异这三个遗传操作算子进行搜索。 在遗传算法的搜索过程中，个体的生存能力取决于该个体的适应度。适应度越 高，该个体生存的机会越大，反之，机会越小。这种选择机制，使遗传算法成为有 向的搜索算法。 在自然界中生物进化过程中起核心作用的是生物遗传基因重组( 加上基因变 异) ，同样，遗传算法中起核心作用的是交叉算子。所谓交叉是指把两个父代个体 的一部分进行交互替换、重组而生成新个体的操作。通过交叉，遗传算法的搜索能 力得以飞跃提高，实现在全局范围内的搜索。 简单的交叉可以分三步进行： ( 1 ) 对配对库中的个体进行随机配对 ( 2 ) 在配对个体中随机设定交叉处 ( 3 ) 配对个体彼此交叉部分信息。 变异操作是按位进行的。即把某一位或某几位的内容进行变异。导入变异算子 的目的有两个： ( 1 ) 使遗传算法具有局部的搜索能力。当遗传算法提高交叉算子已接近最优解 对，利用交叉算子的这种局部随机搜索能力可以加速向最优解收敛。 ( 2 ) 使遗传算法维持个体的多样性，以防止出现未成熟的收敛现象。 烦+ 论文 电子商务环境下第三方物流企业车辆调度研究 遗传算法中交叉算子因其全局搜索能力而作为主要算子，而变异算子因其局部 搜索的能力而作为辅助算子。遗传算法采用交叉和变异这一对相互配合而又相互竞 争的遗传操作使其具备全局和具备局部搜索能力。 2 1 。3 遗传算法的特点 同传统的寻优算法相比，遗传算法具有以下特点： ( 1 ) 遗传算法对问题参数的代码集进行运算，而不是对参数本身进行运算。遗 传算法处理的对象是经过编码的染色体，因而要求将优化问题的基本参数转化为相 应的有限符号的染色体。 ( 2 ) 遗传算法是从初始群体开始搜索的，而不是从单点开始的。许多传统优化 算法都是从搜索空间的单点出发，通过某种规则确定下一点。这种点到点的搜索方 式在多峰值优化问题中，首先找到的可能不是最优峰值；而遗传算法是从点的集合 开始进行寻优过程的，初始群体是随机在搜索空间中选取的，这样在搜索过程中达 到最优峰值的概率要远远大于点对点方法的概率。 ( 3 ) 遗传算法在搜索过程中只使用适应度函数的信息，而不是采用导数及其他 辅助信息。对于不同类型的优化问题，传统的方法需要不同形式的辅助信息，没有 一种方法能够适应各类问题的要求。遗传算法在优化过程中放弃使用这些辅助信 息，因此具有广泛的适应性。 ( 4 ) 遗传算法使用概率转换规则而不是确定性规则。遗传算法使用概率转换 规则来调整其搜索方向，各代群体之间没有统一的联系规律。但使用概率转换规 则不一定意味着这个方法属于随机算法范畴，它只是使用随机转换作为工具来调 整搜索过程趋向于目标函数不断改进的区域。 同传统方法相比，遗传算法的优越性主要表现在：遗传算法具有极强的搜索能 力，能够实现概率意义上的全局搜