（系统工程专业论文）基于GIS的快递网络系统研究.pdf

中文摘要 摘要：随着中国社会和经济的不断发展，快递业作为一个新兴的产业展现出 了蓬勃的生机，各种类型的快递企业在快递领域中迅速发展。市场竞争日益加剧， 国际快递巨头纷纷抢滩中国市场，使无论处于优势地位的中国邮政e m s 还是民营 快递企业，都面临着严峻的考验。快递企业如何在这场激励的“价格战一中生存， 政府部门出台怎样的适应时局变化的政策保护国内快递企业，都是亟待解决的问 题。成本控制和服务质量提升是影响快递企业发展的重要因素，本文通过对快递 网络的构建和路径优化来实现成本的降低。 本文首先阐述了g i s 在快递网络构建中的应用和必要性，基于6 i s 的快递网 络分析系统是实现可视化网络分析的重要手段，通过这种手段，使得对网络分析 的结果更加直观、准确。本文在研究地理空间数据拓扑关系的基础上，对三种主 要的网络模式，即点点直达、中转和h u b 模式进行了分析和比较，并对快递网点 布局及优化进行了初步探讨。 目前网络图的运算已有了相当的发展，对其算法的改进也较成熟。本文讨论 了最短路径算法的搜索策略，介绍了如何引入多线程方法来提高算法的速度，同 时探讨了如何管理和处理多线程。算法改进的主要思想是用线程替代递归算法， 从而增强算法的并发能力以降低算法的遍历时间，但这样的替换会导致大量线程 产生，所以对线程挂起和唤醒的控制很重要，通过反馈值来实现多线程的合理调 度，从而实现系统的稳定。 最后进行案例分析，以邮政快递为例，对其网络结构、混合网络模式实施的 可行性、网络节点选择、运输网络构建等方面进行了较为详细的论证。利用g i s 编程技术完成了网络交点的自动连接和错误处理，以及路段的自动断链技术，从 而实现了快递网络拓扑结构的自动建立。论文借助g i s 的二次开发工具m a p i n f o m a p x 及v b 编程，实现了改进的最短路算法。开发的系统不仅对网络路径进行选择， 通过参数的转换也可进行快递成本和快递时间的最小化选择。通过对路径快速选 择不仅可以提高对客户服务的响应速度，而且可以控制快递成本。 关键词：地理信息系统；快递系统；网络；最短路径；多线程 分类号： a b s t r a c t a b s t r a c t ：v a r i o u s e x p r e s se n t e r p r i s e sh a v eb e e nd e v e l o p e dw i t ht h ei n c r e a s e o fc h i n a s e c o n o m ya n ds o c i e t y w i t ht h ec o m i n go ft h ei n t e r n a t i o n a le x p r e s s e n t e r p r i s e s ，c o m p e t i t i o ni at h ee x p r e s sm a r k e ti sh e a t i n gu pv i s i b l y t h i sm a k e s d o m e s t i ce x p r e s sc o m p a n i e sn o to n l yc h i n ae m sb u ta l s oi n d i v i d u a l l y - r u ne n t e r p r i s e s s u b j e c tt ot h e i rb i g g e s tt e s t so fa 1 1 h o wt os u r v i v ef o re x p r e s se n t e r p r i s e sa n dh o wt o p r o t e c td o m e s t i cb u s i n e s s e sf o rt h eg o v e r n m e n ti sa l lu r g e n tp r o b l e m c o s tm a n a g e m e n t a n dc u s t o m e rs e r v i c ea r e t h em a j o re l e m e n t sd i n i n gt h eb u s ；m e s sw a r t h i se s s a yi s f o c u so nd i s c u s s i o na l lo r g a n i z e dt r a n s p o r t a t i o nn e t w o r kp a t hw h i c hc a n d r a m a t i c a l l y i m p r o v et h ee f f i c i e n c yo f c o s tm a n a g e m e n ta n dc u s t o m e rs e r v i c e t h i sd i s s e r t a t i o nf i r s t l yd e m o n s t r a t e st h en e c e s s i t yo fg i si nt h ea p p l i c a t i o no ft h e e x p r e s sn e t w o r kd e s i g n i n g i ti sa ni m p o r t a n tm e t h o dt oa n a l y z e e x p r e s sn e t w o r ku s i n g g i sb e c a u s eo fi t sv i s u a l i z e da n da c c u r a t er e s u l t s b a s e do nr e s e a r c h i n gt h eg e o g r a p h y s p e c i a ld a t a , t h i se s s a ya n a l y s e sa n dc o m p a r e st h r e ed i f f e r e n tn e t w o r km o d e s - n o d et o n o d em o d e 、t r a n s f e rm o d ea n dh u bm o d e t h e ni td i s c u s s e st h el a y o u to ft h es e r v i c e n o d e sa n di t so p t i m i z a t i o n d u et ot h ef a s t i n gd e v e l o p m e n to fn e t w o r kc a l c u l a t i o n ，a f t e rd i s c u s s i o nt h e s t r u c t u r ea n d p o i n to ft h es h o r t e s tr o u t e ，i n t r o d u c et h em u l t it h r e a dm e t h o dt oi n c r e a s i n g t h ec a l c u l a t i o ns p e e da n dh o wt om a i n t a i na n dm a n a g em u l t it h r e a dw o u l db et h en e x t t o p i c t h em e n do f n e t w o r km a p sa r i t h m e t i ci st ou s em u l t i - t h r e a d si n s t e a do f r e c u r s i o n m u l t i t h r e a d sc a l li m p r o v ee f f i c i e n c yo ft h ea r i t h m e t i c ，t or e d u c et i m eo ft h ea r i t h m e t i c r u n n i n g b u tt h em e t h o dw i l lc r e a t eal o to ft h r e a d s ，s on e x ti m p o r t a n tp r o b l e mi sh o w t oc o n t r o la n dm a n a g et h e s et h r e a d s w i t hr e a s o n a b l em a n a g e m e n tt h em u l t i t h r e a d s r e t u r nv a l u e sa l ei no r d e rt om a k et h es y s t e ms t a b i l i t y f i n a l l y , i ts e t sa ne x a m p l eo fe m sa n dh a sd e t a i l e dd e m o n s t r a t i o na n da n a l y s i s a b o u tt h es t r u c t u r eo fn e t w o r k ，i n c l u d i n gt h ei m p l e m e n t i n gf e a s i b i l i t yo ft h em i x e d n e t w o r kp a t t e r n ，t h ec h o i c eo fn e t w o r kp o i n ta n dt h ec o n s t r u c t i o no ft r a n s p o r tn e t w o r k t h ed e s i g no fa u t o m a t i cc h a i ns c i s s i o na n de r r o rh a n d i n ga b o u tc r o s s o v e rp o i n to f e x p r e s sn e t w o r kw a sc o m p l e t e d t h e r e b y , t h ea u t o m a t i cc o n s t r u c t i o no ft o p o l o g i c a l s t r u c t u r ef o re x p r e s sn e t w o r ka n dt h es e a r c ho ft h es h o r t e s tr o u t ew e r ea c h i e v e db a s e d o ng i s ( m a p i n f o ) t h es h o r t e s tr o u t ea r i t h m e t i cn o to n l yf o c u s e so ns e l e c t i n gt h eb e s t p a t h ，b u ta l s ol e tu sm i n i m i z et h ec o s ta n dt i m eb yt r a n s f o r m i n gt h ep a r a m e t e r s k e y w o r d s ：g e o g r a p h yi n f o r m a t i o ns y s t e m ；e x p r e s ss y s t e m ；n e t w o r k ；t h e s h o r t e s tr o u t e a r i t h m e t i c ；m u l t i - t h r e a d s c l a s s n o ： v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名： 签字日期：年月 日 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：涨f i 初习 签字日期：。哆年多月移日 f 导师签名：幺纠 签字日期：如口7 年石 、1j日 ?仍 阢 月 致谢 本论文的工作是在我的导师徐维祥教授的悉心指导下完成的，徐维祥教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两年来 徐老师对我的关心和指导。 徐老师悉心指导我完成了实验室的科研工作，在学习上和生活上都给予了我 很大的关心和帮助，对于我的科研工作和论文都提出了许多的宝贵意见，在此向 徐老师表示衷心的谢意。 在实验室工作及撰写论文期间，丁小兵、苏娟、武弦等同学对我论文中的研 究工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。 1 1 研究背景及意义 1 引言 快递是贸易的先行官、价值的转换器、经济的加速器n 1 。国际快递是国际贸 易的第一环节，没有快递服务，也就没有现代贸易嘲。随着经济全球化进程的不 断加快和现代信息技术的迅猛发展，物流行业已经成为一个极具发展前景、市场 潜力巨大的新兴产业。而快递作为物流产业的一个重要组成部分，正在成为第三 方物流的先锋与典范，日益渗透到社会经济的各个领域。研究快递网络系统既是 社会经济发展的需要，也是管理理论发展和管理实践的需要。 第一，快递业具有广阔的发展前景，我国快递业发展迅速。据测算，我国快 递市场规模与g d p 的增长关系密切，g d p 每增长1 ，快递市场规模将增长2 9 3 口1 。 1 9 9 5 2 0 0 4 年我国快递业务量变化趋势如图卜1 所示。 图1 - 11 9 9 5 - - 2 0 0 4 年快递业务量增长趋势图 f i g u r e1 - 1t h ei n c r e a s i n gt r e n do f t h r o u g h p u to f e x p r e s sf r o m1 9 9 5t o2 0 0 4 第二，网点正成为快递企业当前竞争和发展的焦点。目前，网点布局已经成 为各种所有制快递企业最主要的竞争领域。中外运一敦豪己在中国建立了最大的 合资快递服务网络，拥有5 6 家分公司，业务覆盖全国3 1 8 个主要城市；f e d e x 以4 亿美元的价格收购了大田持有的大田一联邦快递公司的5 0 的股份，拥有了 原大田全部的国内快递网点；f e d e x 及u p s 在中美航空协定签署后，立即增 发航班抢摊中国航空快件市场；t n t 另辟蹊径通过开展连锁经营扩大网点覆盖范 围，以提升其在汽车零部件快递市场的核心竞争力。中国邮政2 0 0 5 年在全国新 增连锁配送服务网点7 万个，使网点总数达到2 0 万个，覆盖了2 5 _ 3 0 的行政 村。中外运发展e 速公司2 0 0 6 年通过控股方式控股民营快递企业申通快运 公司，大大增强了自身的网点竞争力。中铁快运与中邮联合组建新时速运递公司， 不仅优化了网点布局，而且实现了双发网点的共享。民营企业也通过自建网络、 合作加盟等多种方式不断扩大网点数量和业务范围。顺丰速运公司以其密集的网 点数量奠定了其在民营企业中的优势地位，其在华南市场的业务已经领先于 e m s 申通公司通过加盟方式使自己的网点增加到1 4 0 0 多个，服务延伸到6 0 0 多个城镇；2 0 0 6 年通过出让5 1 的股份筹集资金，实现了合作网络的自由化。 第三，网点在快递企业运营中发挥着重要作用，研究网点布局及其优化对于 提高快递企业运营质量具有直接影响。快递企业最具有空间特性，它通过不同层 级的网点实现快递在发件人与收件人之间的转移，而网点的数量、层级及其在不 同空间的布局直接决定着企业的运营模式和运营质量。终端网点承担着市场开 发、操作运营和客户服务三大职能，它既是市场营销的前沿，又是客户服务的密 切接触点，因此终端网点布局具有更加突出的作用。目前，快递企业对网点的重 视程度明显加强，但是还没有意识到终端网点对于快递企业的重要意义，重市场、 轻运营和重业务收入、轻网点投资现象还很普遍，转手卖单、多次中转现象经常 发生，快件转移过程中晚点率、破损率、丢失率与国际快递公司相比还有一定差 距。运营质量的问题，很大程度上反映了快递企业网点布局的问题，这一方面需 要逐步提高对网点的重视程度，另方面需要快递企业网点布局的持续优化。 第四，快递业有其不同于传统服务业的特点和规律。快递业是服务业的一个 重要分支，所以传统的大多数理论在解决快递企业管理问题中发挥了很大的作 用。但是快递业个最基本的特点是上f - h 艮务，所以它不同于传统服务业，如酒 店、银行、商店等；同时快递业也不同于邮政业，快递随叫随到、门到门、手到 手、桌到桌，而邮政则是港( 邮箱) 到港( 邮箱) ；快递业还不同于物流业，快 递业要求速度更快、成本更低、时限更短、基本不具有仓储功能等。快递业的这 些特点决定了快递业在服务业中的独立地位。但遗憾的是目前理论界对快递的研 究屈指可数。因此，加快对快递业的理论研究，既是快递实践发展的要求，也是 快递理论发展的必然。 2 1 2国内外研究现状 1 2 1国外快递业网络现状 ( 1 ) d h l d h l 公司是一家具有全球服务网络的快递公司，作为全球最大的快递公司 叫h l 快递在欧洲大本营占据主场优势，在亚洲等新兴市场，d h l 由于很早进 入也占得先机。早在1 9 8 6 年d h l 和中外运就5 0 ：5 0 合资成立了中外运敦豪。 现在d h l 在中国的市场份额达到3 0 以上；在印度接近4 0 ；在俄罗斯则达到5 0 9 6 。 目前，在d h l 的全球运输路线图中，欧洲、亚洲和北美已经密密麻麻交织形成了 一张非常细的网络，d h l 在莱比锡、中国香港和美国的三大转运中心成为串接全 球网络的枢纽h 1 。作为货物的中转、分拣的处理中心，转运中心代表着一种快速 处理能力和网络管理能力。莱比锡转运中心的分拣系统是全球最大的比美国 以及其他国家的转运中心都要现代。比利时首都布鲁塞尔是d h l 荷比卢地区的区 域转运中心，并将继续作为欧洲及东欧、中东和非洲地区的协调中心。为了配合 欧洲整体的营运布局，d h l 还扩大了巴黎( 戴高乐机场) 、卢森堡和阿姆斯特丹 等地的业务，并在巴黎南部新设了一个分拣机构。 0 7 年底亚洲d h l 在上海建立了北亚转运中心，它将和d h l 在香港的亚洲转 运中心一起互为犄角，增强亚洲网络璐1 。值得一提的是，代表d h l 未来的是波恩 旁边的一个小镇的创新中心h 1 。一位顾客去沃尔玛购买衣服，她看好了某件衣服 却不需要带走它，她只需刷卡付款然后回家。电脑会搜寻出她需要衣服的尺寸和 型号，机械手根据无线射频的信息从仓库里自动抓取装有这件衣服的盒子，接着 它被送入一辆送货车，运输人员根据无线射频判断买衣服的这位顾客的住址，然 后在电脑面前根据电子地图找出最短的路线，如果最短路线发生了堵车，系统还 会生成最合适的路线。送货车将衣服送达社区中心的一个金属包裹站它类似 在中国商场门口存包的柜子送货人员将衣服放到了柜子里。购物者自动从手 机等移动设施中获得信息，她只要到这个储物柜面前输入密码，就能拿到自己的 衣服。这种利用现代物流技术和商业机构紧密合作的模式正在德国等一些地区开 始试验并预期推广到其他国家。这个模式就是d h l 创新中心研发出来并得以运用 的。 ( 2 ) u p s u p s 公司于1 9 0 7 年8 月2 8 日在美国西雅图成立，目前总部在佐治亚州亚特 兰大市，是全球最大快递公司之一，2 0 0 4 年营业额为3 6 0 亿美元( 其中物流2 0 3 多亿) ，全球员工达3 5 万多人，其中美国近3 2 万人。u p s 的网络覆盖世界2 0 0 多个国家和地区，全球有1 7 4 8 个货运枢纽和配送中心，各类运输( 投递) 车辆 8 8 0 0 0 辆，自有飞机2 6 8 架，租用飞机2 9 8 架，美国国内起降机场3 8 5 个，国际 4 6 6 个，国内航线9 7 2 条，国际航线8 7 3 条呻1 。u p s 在美国国内的航空网络由三 层组成：航空集散中心、航空通达机场和处理中心。 第一层：航空集散中心。位于路易斯维尔，是u p s 航空集散中心( 咖b ) ，主 要负责飞机的集散交换和散件分拣处理。 第二层：通航机场。全美3 8 5 个通航机场，主要负责辐射范围内各处理中心 与机场之间，航空运输邮件的集装箱转运、装卸两个通航机场间邮件量较大， 可以满足一架飞机装运的，采用直航的方式，不再绕经路易斯维尔集散，不够量 的全部集中到路易斯维尔集散接力运输。此外全美还有六个通航机场承担辅助集 散功能，分别是宾夕法尼亚州的费城、德克萨斯州的达拉斯、加州的安大略、伊 利诺伊州的洛克福德、南卡罗拉纳州的哥伦比亚市，康涅狄格州的哈特福德，区 别于其他通航机场的是，它们同时还承担周边支线飞机的集散，支线飞机到达这 六个辅助集散中心后，散件拼箱再发运。 第三层：处理中心。全美共有1 2 0 0 个处理中心，负责进出口邮件的散件分 拣处理，并将本中心分拣完毕的邮件按发运方式发运，陆运的直接装发干线卡车， 空运的装航空集装箱，通过航空趟车运输至机场发运，部分业务量小，场地条件 不具备的需要到机场散件装发集装箱。 u p s 在美国国内的航空网络结构示意图如图1 - 2 所示： 图卜2u p s 在美国的网络结构不意图 f i g u r e l - 2t h eu p sn e t w o r ks t r u c t u r ei nt h eu s a u p s 在选择网络节点时，以业务量为依据，并结合地理位置、交通条件、物 品传递时限、节点间的航程、当地的运行成本和自身资源等因素，建立起了以 h u b 、中转和点点直达多种模式混合的网络模式，在网络结构上形成了星状和网 状相结合的形式。以下就其集散中心路易斯维尔作简单介绍和分析： 4 j 匕塞交通太堂亟堂僮i 金塞互i 言 路易斯维尔集散处理中心1 9 8 1 年开始投入使用，到目前每天有1 2 6 架飞机 在机场集散，日均处理邮件8 0 万件，高峰约1 3 0 万件集散中心占地面积4 0 0 万平方英尺，由四部分组成：专用停机坪( 提供1 2 0 个远机位) 、分拣中心、三 条与分拣中心连通的并行廊桥( 提供4 4 个近机位) 、生产指挥楼。u p s 选择路易 斯维尔作为航空集散中心主要考虑地理条件、气候条件、机场流量和低成本等几 大因剥引。 ( 3 ) 日本 1 9 7 6 年1 月2 0 日，大和运输公司，在日本国内率先实施了以个人和家庭小 包裹为服务对象的快递业务陋3 在快递业运营之前，日本的小行李包裹等货物运 送，一直是国有企事业的邮电局和国有铁道的业务范围，属于公益性事业的独家 代理。由于小包裹属于轻型货物，量少且分散，收集货物效率低、利润较薄等原 因，民间汽车运送业对于此项业务也是敬而远之。但是，大和运输公司找到了邮 电局和国铁货物传送速度慢、业务效率低，而且必须到指定地点办理业务的弱点。 在货物配送速度与服务质量上找到了竞争的缝隙，向运输省交涉并申请了c t o c 的营业执照。开始以“黑猫宅急便为快递名称，对3 0 公斤以下的个人和家庭 之间的小行李货物运送业务。 为了提高货物的收集能力，扩大业务量，建立货物收集网点至关重要，关系 到输送全过程的服务质量，是快递业经营战略中的关键部分。大和运输公司的快 递业务首先以关东区域为基础，无论都市还是郊外，不断的按配送区域增加营业 所、搭建货物收集与配送的骨架结构；与此同时，以米店、酒店等家庭主妇常去 的场所，2 4 小时营业的连锁便利店等一般消费者经常利用的场所等作为货物集 中的服务网点，现有基础网点3 0 6 9 8 6 个。 形成了以点、线面向全国扩张形成网状结构，在此基础上确立如图1 - 3 所示 韵货物发货流程，逐步建立了全国的配送网络。一方面，通过在汽车货物分拣中 心导入大型自动分拣机械，提高工作效率；另一方面，为了避开交通拥挤，干线 道路运送的司机通常夜间进行工作，构筑了第2 天送货到门的服务体系。 5 削卜3 日本快递的基本配送单位流程 f i g u r e i - 3 t h e b a s i cd i s t r i b u t i o n f l o wc h a r to f e x p r e s s i nj a p a n 1 2 2国内快递业网络现状 我国快递市场的高速发展有目共睹，图卜4 显示了2 0 0 2 年至2 0 0 7 年中国快 递市场快递业务量的完成情况。快递服务业进入我国已经将近3 0 年了，基本 形成了三大业务市场即国际快递、国内异地快递、同城快递三大市场板块。根据 国家邮政局发布的2 0 0 8 年邮政业数据表明，去年4 月份快递业务收入为3 1 4 亿元，累计收入为1 2 8 4 亿元，同比增长5 5 ，其中同城、异地、国际及港澳 台快递业务量分别占全部快递业务量的2 5 7 、6 62 和8 1 各自收入比例分 别为7 5 、5 2 7 和3 6 1 。 圈l - 4 近五年我国快递业务量完成情况 f i g u r e l - 4 d o m e s t i c v o l u m e o f e x p r e s sb u s i n e s s i nr e c e n t f i v ey e a r s 6 中国快递业经营者被划分为两大部分：邮政快递( e m s ) 及非邮政快递，而 非邮政快递又分国内快递公司及国外快递公司，下面分别论述其发展现状。 ( 1 ) 中国邮政快递网络现状 中国邮政快递开辟了中国快递业之先河，为了发展这项新业务，邮电部于 1 9 8 5 年成立了邮政速递局。由于计划经济下的政策性保护，中国邮政快递长期 处于霸主地位。然而，进入2 0 世纪9 0 年代中期，情况急转直下。由于中国在运 输市场的迅速对外开放，世界快递巨头如u p s 、f e d e x 、d h l 及t n t 纷纷向中国投 入巨资，利用雄厚的资金及信息系统优势迅速在大中城市建立服务网点，使中国 快递公司的市场份额迅速下降n 训因此，研究中国邮政快递的网络迫在眉睫。 中国邮政快递具有先天的网络优势，它不仅拥有一个遍及全国各省、市、区、 县的服务网络，而且拥有连接世界各国的实物投递网络。除此之外，它还拥有健 全的传递网络、完备的设施、充足的人员、宽广的覆盖面、畅通的渠道及良好的 信誉。邮政快递还拥有自己独立和完整的快件处理( 分拣) 枢纽和中心、快件运 输车队和铁路邮车、邮政资讯处理网络、科研机构和快件处理设备制造企业。目 前，邮政快递拥有4 6 万台配送汽车，4 8 1 节火车邮箱，1 0 架飞机，2 3 6 个处理 中心，5 7 万多个网点及1 2 5 万人的投递大军。这个巨大的快递服务网络是任 何企业不可比拟的n 。 但是，在拥有如此得天独厚的网络的条件下，中国邮政快递依然面临严峻的 形势，原因有以下几点： 1 ) 政企不分的体制使邮政快递处于孤立无援的状态。这种官商一体的结构 与市场经济的自由竞争显得格格不入。 2 ) 信息技术的落后制约着e m s 的发展。目前e m s 的查询系统非常薄弱，用 户查询的快件在电脑上常常显示不出来，有时查询无记录、无答复，用户不满意， 致使快递的信誉受到影响。 3 ) 由于万国邮联各国邮政之间的合作是采取双边协议建立起来的，各自的 业务发展经营管理服务水平等状况有较大的差距，这影响了e m s 的竞争力。同时， e m s 在国际干线运输上自主性小，综合实力比私营公司弱，没有统一集中的管理 系统，使得许多国家的邮政e m s 在竞争中处于不利地位。目i j 中国e m s 发往欧洲 的快件都通过t n t 的运输网络递送。 4 ) 邮政e m s 内部财务结算体制落后。至今邮政保留着只看收入不计成本财 务体制，致使每件快件的成本、利润无法考核，更无法正确计算资本利润率。各 地方邮政机构为完成邮政总局下达的件数、营业收入的指标，自行降低快件的价 格，造成了快件市场的价格大战。由于投入产出无法量化，快递巨头都不愿意与 中国邮政快递有联盟或资本的投入。 7 5 ) 邮政快递网络效率低下。目前，邮政快递运输主要靠铁路和民航。干线 运输中至少有7 0 9 6 属于委办性质，邮件运输线路、作业时间等均受到铁路运行车 次、民航班次安排的影响，快递时限无法保证。尤其近几年，铁路提速使邮政快 递生产作业受到很大影响，充分暴露出邮政网受制于人的弱点对于快件而言， 时限就是生命，时限不能保证，意味着企业必然失去顾客、失去市场。另外，对 于长途快件，由于邮政航空运力少，飞行航线少，远不能满足快递的需要；而民 航飞机通常不能满足邮政网所需的夜航( 午夜到凌晨3 点) 的要求，同时邮政没 有自己的机场，民航机场不能昼夜开放，导致快递的衔接有问题。邮政快递被动 局面导致邮政快递无法实现次日递n o 】。 ( 2 ) 非邮政快递业的现状分析 非邮政快递又分为国有快递公司和民营快递。国有快递公司的主要代表包括 民航快递( c a e ) 、中铁快运( c r e ) 和大通快递( e a s ) 。目前，民航快递已设 立分支机构和控股公司3 0 多个，加上统一品牌和运作规范的网络成员单位4 0 多个，以及在周边城市扩展的营业网点，民营快递在全国大中城市的网点已达 2 0 0 多个，基本上形成了全国民航快递网络体系。中铁快运于1 9 9 7 年正式开办 国际货运代理业务，依托中国铁路健全的国内网络系统，分别通过北京、丹东、 上海、大连、珲春、深圳、阿拉山口等7 个口岸分别办理国际铁路联运快运、国 际空运、国际海运快件和内地与香港见直通联运快件业务u 引。 目前，我国民营快递市场发展较快的是以广州为中心的珠三角地区、以江浙 沪为中心的长三角地区和以北京为中心的华北地区。珠江三角洲快递业是中国快 递业的领头羊，珠三角民营快递公司蕴藏着巨大的潜能，竞争也异常激烈。比较 出名的民营快递公司有顺丰、宅急送、中远、全一等。广州顺丰速运有限公司于 1 9 9 3 年成立于广东顺德容奇镇，现总部设在深圳，有6 0 0 0 多员工，4 0 0 多台车 辆，5 万平米的封闭场地，2 0 余万客户，业务范围有国际国内货物的报关、报检 及货物的监装和储运，网络遍布香港、广东全境、福建、北京、天津、大连、哈 尔滨、江浙沪、武汉、成都、青岛、济南等地u 别。 1 3论文的研究内容 本文对基于快递网络的最短路径分析的各项关键技术进行了研究和验证，在 此基础上实现了快递网络最短路径分析，这些技术包括快递网络的矢量地图表 达、网络拓扑结构的提取和构建、最短路径算法的高效实现等。 在g i s 中多数的网络都是有向带权图，如快件只能由三级节点向二级节点递 送，反之则不可以。将实际的快递网络转化到地图的图层中去时，必须充分考虑 8 到这些情况，并且应方便于提取弧段和节点的信息，从而构建出正确的网络模型。 另外，g i s 中的数据( 如道路、管网、线路等) 要进行最短路径的计算，就必须 首先将其按节点和边的关系抽象成图的结构，这在g i s 中称为构建网络的拓扑关 系。由于在应用中对最短路径分析的实际处理要求很高，因此论文研究的关键和 主要技术难点也就集中在如何高效率地生成最短路线上。本文对最短路径算法进 行了深入分析，在原有算法的基础上对其进行了改进，以提高效率。 本文共分六章，各部分内容如下： 第一章：本章为绪论部分，主要介绍了论文选题的背景、研究意义、目前国 内外的研究现状和本文的主要研究工作。 第二章：对g i s 的基本理论知识以及空间数据拓扑关系进行了详细介绍。研 究了基于图论的快递网络的概念、物理构成及分类，并对快递服务网点的定义及 布局相关理论进行了初步探讨，为邮政快递网络系统的重构及优化提供了坚实的 理论参考依据。 第三章：研究了在快递网络分析过程中所用到的关键技术最短路径的搜 索。基于传统的d i j k s t r a 算法，提出了一种适合快递网络分析的改进算法，即 多线程最短路算法。实例证明该算法效率较高。 第四章：在最短路搜索关键技术研究的基础上，基于m a p i n f o 软件平台，重 构了g i s 环境下的邮政快递网络，运用系统工程的思想，设计了邮政快递网络分 析系统，首先对系统进行了需求分析，旨在为系统设计提供理论依据。研究了系 统的框架和功能，并对系统相关模型进行了描述。 第五章：实现了快递网络系统的功能，将m a p x 控件嵌入v b 程序中，进行了 系统界面设计，实现了对空间及属性数据以及最短路径的查询。 最后，对全文进行了总结，并提出了本论文尚未解决有待今后继续进行研究 的问题。 。 9 2g i s 中的拓扑关系和快递网络模型研究 对于快递行业点部的收派员来说，需要在特别短的时间内快速定位他所服务 网点的客户的位置，这往往通过电话沟通的方式，会出现位置上的偏差等。其实， 这种情形一再地在你我的日常生活中重演，位置、距离、相邻与否、最短路等许 多空间因素，早已是生活中常常需要思考的问题。于是在人们不断地寻求、探讨 之下，便出现了一种可用于描述并分析空间关系的事物地图。在信息爆炸的 今天，许多以往都需靠文字记载成册的资料，例如：姓名、地址、年龄等信息， 大都通过计算机加以管理n 羽。地理信息系统( 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 ， g i s ) 便是一种兼容、存储、管理、分析、显示与应用地理信息的计算机系统， 是分析和处理海量地理数据的通用技术n 钔。它在最近的4 0 多年内取得了惊人的 发展，并广泛地应用于资料调查、环境评估、重大灾害处理、区域发展规划、公 共设施管理、交通安全控制等领域。尤其是以地理信息系统、遥感、全球定位系 统三者有机结合的3 s 技术，使g i s 应用的深度和广度达到一个新水平，成为一 个跨学科、多方向的研究领域。 2 1g i s 发展概况 随着地理信息系统技术的不断完善，其应用已渗透到社会各个方面，涉及到 所有相关的空间信息领域，包括诸如土地、海洋、农林业、水利、矿产资源、自 然灾害预测、全球变化、环境保护等。在各个应用领域中，土地信息系统( l i s ) 、 城市信息系统( v i s ) 、自动制图与设施管理( a m f m ) 、环境信息系统( e i s ) 等占主 导地位。发达国家以g i s 应用于城市和设施管理为特征，而发展中国家则侧重于 资源管理n 5 1 。 g i s 是在地图学的基础上发展起来的，可分为以下几个阶段： ( 1 ) 开拓发展阶段引。2 0 世纪6 0 年代，由于计算机硬件系统功能较弱， 限制了软件技术的发展。这一时期的软件主要是针对当时的主机和外设开发的， 算法粗糙，图形功能有限。 ( 2 ) 巩固阶段。2 0 世纪7 0 年代，计算机硬件和软件技术飞速发展，为空间 数据的录入、存储、检索和输出提供了强有力的手段u7 1 。用户屏幕和图形图像卡 的发展增强了人机对话和高质量的图形显示功能，促使g i s 朝着实用方向迅速发 展。由于这一时期g i s 的需求增加，地图数字化输入技术有了一定的进展，采用 人机交互方式，易于编辑修改，提高了工作效率，并出现了扫描输入技术系统， l o 图形功能扩展不大，数据管理能力较小。这一时期软件最重要的进展是人机图形 交互技术的发展。 ( 3 ) 突破阶段。随着计算机软、硬件技术的发展和普及，g i s 也逐渐走向成 熟，这一时期是g i s 发展的重要时期。g i s 软件技术在栅格扫描输入的数据处理、 数据存储和运算方面有了很大的突破n 引。随着硬件技术的发展，g i s 软件处理的 数据量和复杂程度大大提高，许多软件技术固化到专用的处理器中，而且遥感影 像的自动校正、实体识别、影像增强和专家系统分析软件也明显增加。在数据输 出方面，与硬件技术相配合，g i s 软件可支持多种形式的地图输出。在地理信息 管理方面，除了d b m s 技术己经发展到支持大型地图数据库的水平外，专门研制 的适合g i s 空间关系表达和分析的空间数据库管理系统也有了很大发展。 ( 4 ) 社会化阶段。进入2 0 世纪9 0 年代，随着地理信息产业的建立和数字 化信息产品在全世界的普及，g i s 已经成为许多机构必备的工作系统n 钉，尤其是 政府决策部门在一定程度上受g i s 影响改变了现有机构的运行方式、设置与工作 计划等。而且，社会对g i s 的认识普遍提高，需求大幅度增加，从而导致g i s 应 用的扩大与深化。 最短路径问题在运筹学中有着许多重要的意义例，也是g i s 网络分析的重要 内容之一，且网络分析的其它优选问题诸如最小成本计算、位址选择模型、节点 连通性等都和图论中的最短路径问题等价，在方法论上它们有着很大程度的相似 性与一致性。 在求解最短路径问题的算法中，d i j k s t r a 算法是目前国内外一致公认的较好 算法。据统计，目前国内外提出的此类最短路径的算法大约有1 7 种瞳。f b e n j a m i nz h a n 等人对其中的1 5 种进行了测试，结果显示有3 种效果比较好，它们分别 是：t q q ( g r a p hg r o w t hw i t ht w oq u e u e s ) ，d i ( 。a ( t h ed i j k s t r a sa l g o r i t h mi m p l e m e n t e d w i t ha p p r o x i m a t eb u c k e t s ) 以及d k d ( t h ed i j k s t r a sa l g o r i t h mi m p l e m e n t e dw i t h d o u b l eb u c k e t s ) 。其中t q q 算法的基础是图增长理论，较适合于计算单源点到其 它所有点间的最短距离；后两种算法则是基于d i j k s t r a 的算法。 2 2g i s 在快递行业的应用 目前，包括邮政快递在内，快件只能在处理过程及投递过程中进行跟踪，但 运输中则无法实现及时跟踪。为了改变这种落后局面，快递公司必须配备先进的 计算机网络、先进的通讯系统、网络g p s ( g l o b a lp o s i t i o ns y s t e m ) 、条形码技 术及快递服务相关的系统软件恤3 。 g p s 起源于美国，7 0 年代后期美国国防部为彻底解决海上、空中、陆地运载 工具的导向和定位，投入2 0 年的时间，花费1 0 0 亿美元开发研制的。它是利用 卫星对锁定目标进行跟踪、监控，从而达到防御、求援的目的目前，g p s 已广 泛应用于国民经济和社会生活的各个领域，如航空、铁路运输、交通信息、机动 车辆管理、银行、特种车辆管理等。随着互联网的蓬勃发展，g p s 也进入了网络 时代，g p s 、g i s 、g s m ( g l o b a ls y s t e mf o rm o b i l e ) 等各项先进技术的强强联合 造就了网络g p s 。 网络g p s 的特点有：精度高、覆盖面广，在全球任何位置均可以进行车辆的 位置监控，保障网络g p s 所有用户的要求都能得到满足；定位速度快，保障运输 企业能够在业务运作上提高反应速度，降低车辆空驶率，降低运作成本；信息传 输采用g s m 公用数字移动通信网，具有保密性高、系统容量大、抗干扰能力强， 漫游性能好、移动业务数据可靠；开放度高、资源共享程度高嘞1 。 目前，跨国快递公司在每架飞机及每辆配送车上安装g p s 接受机，在接到 g p s 卫星定位数据后可自动计算出自身所处的地理位置坐标，然后通过g s m 通信 机发送到g s m 公用数字移动通讯网，并通过与信息系统连接的d d n 专线将数据送 到网管中心，中心处理器将收到的坐标数据及其他数据还原后，与g i s 系统的电 子地图相匹配，并在电子地图上直观的显示车辆实时坐标的准确位置以便得到快 件的即时信息。网络g p s 用户可在自己的权限内上网进行自有车辆信息的收发、 查询工作，一旦车辆出现意外事故时可进行遥控操作。 网络g p s 的作用是显而易见的，快递公司应按照重点竞争区域优先配置，全 面推广和利用网络g p s 。由于我国企业信息水平较低，e d i 技术应用也非常有限， 因此，网络技术的应用，特别在快递方面的应用还处于探索过程中。本文尝试利 用g i s 技术建立快递企业网络，形成初步的电子地图，为快递行业信息化建设提 供理论依据。 2 3地理空间数据模型 地理空间数据是g i s 的核心，整个g i s 系统都是围绕空i 、日j 数据的采集、加工、 存储、分析和显示展开的。表征地理空间内事物的数量、质量、分布、内在联系 和变化联系的图形、图像、符号、文字和数据等统称为地理( 空间) 数据。因此 设计和使用g i s 的第一步工作就是根据系统的功能，获取所需要的地理数据，并 创建地理空间数据库。 1 2 2 3 1地理空间数据类型及基本特点 g i s 中的数据来源繁多，概括起来主要有地图数据、遥感数据、统计数据、 实测数据及各种文字报告等几种类型。空间数据记录的是空间实体的位置、拓扑 关系和形态、大小等几何特征。表示地理要素的空间数据可分为如下7 种不同类 型： ( 1 ) 类型数据。如居民点、交通线、土地类型分布等。 ( 2 ) 面域数据。多边形中心点、行政区域界限和行政单元等。 ( 3 ) 网络数据。如道路交叉点、街道和街区等。 ( 4 ) 样本数据。如气象站、航线和野外样方的分布区等。 ( 5 ) 曲面数据。如高程点、等高线和等值区域。 ( 6 ) 文本数据。如地名、河流名和区域名称。 ( 7 )