（计算机软件与理论专业论文）基于gis的物流配送系统的研究与应用.pdf

浙江大学硕i 论文 摘要 物流是近年来我国新兴的朝阳产业，随着社会的发展，物流行业重要性逐渐 显现出来，它作为第三利润的源泉，越来越受到各个行业的重视。如何安排作为 物流核心的路径规划问题已成为降低成本、增加效益的重要研究课题。 配送路线安排的合理性直接关系到一个物流系统的实用性和整体效益，本文 在对地理信息系统( g i s ) 在物流中的应用阐述的基础上，对基于道路网络的配送 j i ! i l 划算法进行了研究，对传统物流配送模型进行了改造和提升，提出了遗传和蚁 群算法相结合的改进模型，对算法参数进行了实验验证，并在实际系统中付诸实 现。 本文根据配送问题的特点，提出了适合物流配送的网络拓扑结构，构建了本 系统的抽象拓扑图。在基于抽象圈的配送区域划分方法阐述的基础上，应用聚类 算法对配送区域进行划分。在此基础上，将路径规划问题抽象为旅行售货商( t s p l 问题的一种模式，并在抽象模式上提出了遗传、蚁群算法的改进方法和具体实现。 系统在配送中心运行后，大大降低了车辆运输成本，将对物流行业的配送模 式产生积极作用。 关键词：物流配送系统，地理信息系统，k - m e a n s 聚类算法，遗传算法，蚁 群算法 浙江人学硕i j 论文 a b s t r a c t r e c e n ty e a r s ，l o g i s t i c sh a sb e e nd e v e l o p i n gr a p i d l yi no u rc o u n t r y w i t ht h e d e v e l o p i n go ft h es o c i e t y , a st h e “t h i r dp r o f i ts o u r c e ”，l o g i s t i c sh a sb e e nm o r ea n d m o r ei m p o r t a n tf o rm o s tc o r p o r a t i o n s a n dt h ed e l i v e r yr o u t i n gp r o b l e mw h i c hi st h e c o r eo f l o g i s t i c ss y s t e mh a sb e c o m et h em o s ti m p o r t a n tr e s e a r c ht ol o wt h e d i s t r i b u t i o nc o s t t h er a t i o n a l i t yo fs o l u t i o nf o rv e h i c l er o u t i n gp r o b l e m ( v r p ) i sv e r yi m p o r t a n t f o rt h ep r o f i to fc o r p o r a t i o n s e l a b o r a t i n go nt h eu s a g eo fg e o g r a p h i ci n f o r m a t i o n s y s t e m ( g i s ) i nt h el o g i s t i cd i s t r i b u t i o n ，t h i sp a p e rf i r s tl a y se m p h a s i so nt h eu s a g eo f g i sa n dg p si nt h e l o g i s t i c ss y s t e ma n dt h ei m p l e m e n t a t i o no fg i sa n dg p s s e c o n d l y ，t h i sp a p e rs t u d i e st h es o l u t i o nf o rt h ea b s t r a c t i o na n dc o n s t r u c t i o no ft h e t o p o l o g i c a ls t r u c t u r eo fn e t w o r k a sa ne x a m p l e ，t h i sp a p e rt a k e st h ec i g a r e t t ed e l i v e r yp r o j e c tt os o l v et h e d e l i v e r yr o u t i n gp r o b l e m s t h ep r o b l e mo fc u s t o m e r sc l a s s i f y i n gi ss o l v e d b y k - m e a n sc l u s t e r i n ga l g o r i t h m t h ev e h i c l er o u t i n gp r o b l e mi sa b s t r a c t e da st s p p r o b l e mw h i c hh a sn p - c o m p l e t ep r o p e r t ya n dt h et s p p r o b l e mi ss o l v e db ye n h a n c e d g e n e t i ca l g o r i t h ma n da n ta l g o r i t h m k e y w o r d s ：l o g i s t i c s ，d e l i v e r yr o u t i n gp r o b l e m ，t s p ，k - m e a n s ，g e n e t i c a l g o r i t h m ，a n ta l g o r i t h m i l 浙江人学硕j ：论文 第一章引言 1 1 物流配送的概念2 3 最初的物流概念( p h y s i c a ld i s t r i b u t i o n ) 是美国学者克拉克在二十世纪2 0 年代 提出的，作为传统意义的物流，是指发生在商品流通领域中的在一定劳动组织条 件下凭借载体从供应方向需求方的商品实体定向移动。随着经济社会的不断发 展，现代物流己逐渐从传统的运输服务，发展成为以现代科技、管理和信息技术 为支柱的综合物流系统。1 9 8 4 年，美国物流管理协会正式将物流概念改为 l o g i s t i c s ，并将物流定义为“为了符合顾客的需求，将原材料、半成品、完成品 以及相关的信息从发生地向消费地流动的过程，以及为使保管能有效、低成本的 进行而从事的计划、实施和控制行为”。 随着电子商务的迅猛发展，现代物流配送中保管、存储、j j r i 二l - 、分类、拣 选、输送等各环节己经综合成为一个整体，配送流程司。见图1 - 1 。其中存储的要 求趋向弱化配送成为最重要的环节，直接与用户相连。 配送作业主要包括以下几部 图l - l 物流配送流程 ( 1 ) 集货作业。从生产厂家进货、集结的过程。 ( 2 ) 配货作业。配货即货物的分拣过程，根据各个用户的不同需求，在配送 中心将所需要的货物挑选出来的过程。 浙江大学硕i ：论文 ( 3 ) 车载货物的配装。根据配装作业本身的特点，配装工作所需车辆一般为 汽车，由于配送货物的质量和体积的差异，配装货物时要考虑车辆的载重和容积， 为使车辆的载重和容积充分利用，还要考虑一趟多送几户的问题。 ( 4 ) 配送线路的确定。配送线路合理与否对配送速度、成本、效益影响很大， 特别是多用户配送线路的确定更为复杂。采用科学的、合理的方法来确定配送路 线，足配送活动中非常重要的一项工作。 可见配送的核心部分就是配送车辆的集货、货物配装及送货过程。而在整个 配送环节中，车辆配送路线的合理优化，对于整个物流速度、成本、效益影响至 关重要。所以进行配送系统优化，最主要就是对配送车辆的优化调度，包括集货 线路优化、货物配装及送货线路优化，这不仅可以提高物流经济效益、实现物流 科学化，也是物流集约化发展、建立现代调度指挥系统、发展智能交通运输系统 和开展电子商务的基础。 1 2 国内外物流系统的研究与现状 1 2 1 国外物流的发展和现状” 一般的送货形态在西方国家已有相当长的历史，可以说是随市场而诞生的 种必然市场行为，尤其是伴随资本主义经济的生产过剩，在买方市场情况下，必 然采取各种各样推销手段，送货最初便是作为一种不得已得推销手段出现的。仅 将其作为推销手段而不认识到作为企业发展的战略手段，在有些国家持续了很长 时问。从历史上曾采用的一般送货，发展到以高技术方式支持的、作为企业发展 的配送，也是近一二十年的事情。 在观念发生变化的同时，配送方式和手段也有很大发展，尤其突出反映在以 下几方面： f 1 1 配送共同化的进展 初期送货，是单独企业为主体，为满足用户配送要求，出现了配送企业车辆 利用率低，不同配送企业之间的交错运输，交通紧张，事故频繁等许多方面不合 珲。 2 浙江大学硕l ：论文 ( 2 ) 配送计划化的进展 初期配送，强调即时较多，即完全按顾客要求办事。制定合理计划而不是完 全按顾客要求那样进行配送，是高水平的计划配送的一大进展。 ( 3 ) 配送区域的扩大 近几年，配送已突破了一个城市范围，在更大范围中找到了优势。美国已开 展了洲际配送，同本不少配送是在全国范围或更大区域范围进行的，如h 本a s i c a 配送系统、资生堂配送系统等都是全困性的配送系统 ( 4 ) 直达配送的进展 不经过物流基地中转，在有足够批量且不增加用户库存情况下，配送突破了 原来的概念，对于生产资料而言，直达配送有更广泛的应用。 ( 5 ) 计算机管理配送的进展 配送规模的扩大和计算机的微型化，计算机管理配送取得很大进展，主要在 以下方面： a 信息传递与处理，甚至建立了电子交换数据( e d i ) 系统。 b 计算机辅助决策，如辅助进货决策，辅助配货决策，辅助选址决策等。 e 计算机与其他自动化装置的操作控制，如无人搬运车、配送中心的自动 分拣系统等。 ( 6 ) 配送劳动手段的进展 配送劳动手段作为支撑配送的生产力要素，是进展很大的领域。到2 0 世纪 8 0 年代，发达国家配送已普遍采用了计算机系统、自动搬运系统、大规模分拣、 光电识别、条型码等。 在物流配送算法方面，国外对物流配送车辆调度问题也已经作了大量而深入 的研究。早在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 l d e n 和a s s a d ( 1 9 8 8 ) 编辑的论文集中，以及 a l t i n k e m e r 和g a v i s h ( 1 9 9 1 ) ，l a p o r t e ( 1 9 9 2 ) ，s a l h i ( 1 9 9 3 ) 等的综述文章中都对该领 浙江夫学硕l 论文 域的研究成果进行了详尽的阐述。浚研究领域的代表人物主要有b o d i n ， c h r i s t o f i d e s ，g o l d e n ，a s s a d ，b a l l ，l a p o r t e ，r i n n o o yk a n ，l e n s t r a ，d e s r o s i e r s 和 d e s r o c h e r s 等【。 1 2 2 我国物流配送的实践与发展m 呻3 经过二十年改革开放和经济的持续快速发展，我围目前已初步具备了发展物 流管理和配送技术的经济环境和市场条件： ( 1 ) 市场供求关系已发生熏大变化，市场竞争加剧，为企业加强科学管理， 发展物流配送技术提供了良好的经济环境条件。随着市场化取向改革的深入，中 国经济保持了多年的持续快速增长态势，商品市场的供求关系发生了根本性变 化，打破了长期以来商品供不应求的市场格局，初步形成了供求平衡或供过于求 的买方市场格局。 ( 2 ) 企业改革日益深化，为物流配送技术发展培育了必要的微观基础。推进 企业改革，着力培育市场主体是市场化改革进程中的一个重要方面，其主要的进 展体现在对国有企业放权让利及建立现代化企业制度方面，使国有企业从计划的 执行者逐步转变成为市场主体。与此同时，由于所有制理论的突破和改革开放政 策的引导，特别是近年来大力发展中小企业的政策，使得一大批非国有经济市场 主体迅速成长起来，成为我国经济发展中不容忽视的经济力量。 ( 3 ) 现代信息技术和现代商品物流技术的进步为中国物流配送的快速发展 准备了充分的技术基础。目的已有相当多的物流和配送技术开始进入我国并在企 业中得到越来越广泛的应用。 ( 4 ) 政府对物流和配送的政策支持，为了大力促进流通体制改革和流通现代 化的进程，为了促进连锁经营等组织形式的发展，国家有关部门对商品物流和配 送采取了积极鼓励和支持的政策。 目前，国内物流和配送服务已有较快的发展，物流配送已经成为许多企业降 低成本，提高竞争力的重要手段。 我国入世后服务业有关领域有的已经对外开放，有的即将开放，更多的跨国 4 浙江大学碰t 论文 企业将进入我国与市场竞争；我国物流配送将出现一些新的变化和趋向： f 1 ) 专业化趋向 我国入世后市场竞争进一步加剧，必然促使企业更加关注其核心资源和核心 竞争力的培养，而将企业内部物流交由专业物流公司经营。但目前我圈第三方物 流的市场比重不大，据中国物流与采购联合会和美智管理顾问公司联合进行的一 次调查，被调查企业中使用第三方物流的只占2 2 2 ，而美国这些类型的企业中 使用第三方物流的占5 8 。因此，我困第三方物流潜力很大，有待发展。预计今 后几年，我国第三方物流服务的比重将会逐渐增大。 ( 2 ) 规模化、集团化趋向 发达国家的一些物流公司通过重组、资本扩张、兼并、流程再造等形式，己 经形成了跨国综合物流企业。这些物流公司，拥有雄厚的资金、先进的技术和设 备、先进的管理理念与经验、全球性的服务网络。而我国的物流企业大多规模小、 实力弱，在与国际大型物流公司的市场竞争中处于不利地位。因此，国内的中小 型物流企业，有一部分将利用拥有的国内网络及设施、人力资本成本低等本土优 势，与国内外大型物流企业建立战略合作伙伴关系；部分将可能被大型物流公 司收购、兼并；还有的将进行战略性重组和改造，向综合物流发展，为大型跨圈 物流企业配套，成为供应链的重要组成部分。 ( 3 ) 多元化趋向 随着我国改革开放的深入，以及我国入世后在商品分销、公路运输、铁路运 输、仓储货运代理、邮递服务等领域的逐步开放，市场主体将出现多元化的局面。 是外资物流企业，这些企业主要服务于外资企业，从事跨国公司在我国的生产、 销售和采购等方面的力量。三是国有经济中传统的运输、货代、仓储、批发企业， 现在仍是物流市场的主力军。今后相当长的一段时间内，我国物流市场将呈现一 个国有、集体、个体、中资、外资等各种所有制物流企业相互依存、同台竞争、 相互促进的局面。 ( 4 ) 国际化趋向 由于世界制造业和o e m 中心在向我国转移，以及经济一体化进程的加快， 5 浙江大学硕l 论正 未来我国与世界各国之问的物资、原材料、零部件与制成品的进出口运输，无论 是数量还是质量都会发生较大的变化。为适应这变化，要求我国必须在物流技 术、装备、标准、管理、人才方面与世界对接。因此我国物流配送业在国际化方 面将会发展较快。 f 5 1 传统的运输与仓储企业加快向第三方物流转变 由于国外物流企业纷纷来到中国，尤其是香港、台湾地区的中小物流企业进 入内地物流市场的速度加快，给国内传统的运输与仓储企业造成很大压力。因此， 有更多传统的运输与仓储企业加快向第三方物流转变，利用自己的优势，扩大客 户群，提升市场竞争力，与幽外和境外的物流公司合作或开展竞争。 ( 6 ) 物流配送信息化建设步伐加快 现代物流是以信息技术为支撑的，没有信息化就没有现代物流的发展。在我 国大力发展信息化的新形势下，物流的信息化应该走在其他行业前面。物流派送 作为政府高度重视的热点，为了适应连锁经营等商业发展，物流配送信息技术业 将有新的发展和变化。国外和国内的一些大型物流企业，都在规划建立自己的配 送中心，改善物流配送信息服务技术，以提高企业的物流配送能力。 1 3 本文的主要研究工作 在当今物流业发展迅速的情况下，智能配送物流已经成为各行各业的首选， 笔者在为台州烟草局设计物流配送系统时，主要参与了系统构架的设计，各算法 的设计与实现，对物流系统及用到的算法进行了深入的研究，并提出了一些改进， 论文就系统的背景、理论基础以及研究成果做了详细的归纳与整理。 本论文的结构如下： 第1 章阐述本文的研究背景、意义和研究目的。 第2 章讨论基于g i s 的物流系统的概念，g i s 系统的软、硬件基础，以及实 现。 第3 章介绍系统的整体构架，如何将地理信息转变为数据信息，并在数据信 息基础上计算任意两个客户间的最短距离，以及如何将每天的客户进行配送区域 浙江人学硕l 论立 的划分对相关算法进行了阐述。 第4 章藿点对t s p 问题的解决进行阐述，每个配送区域内路线的选择问题 在本章进行研究。文中提出了配送路线的优化原则，分析了车辆路线问题的定义、 特性及其典型求解策略，介绍了禁忌搜寻法、模拟退火法的原理及组成要素，重 点对本系统所使用的蚁群算法和遗传算法的改迸和实现做了详细论述，具体进行 了建立模型、构造算法求解过程、编写程序代码等工作。 第5 章对本系统的实际应用做了详细介绍，并对系统应用前后数据进行处对 比，最后，论文进行总结并提出下一步研究的方向。 7 浙江大学硕j j 沦立 第二章g i s 在物流配送系统中的应用 2 1 地理信息系统( g i s ) 概述“2 侧 地理信息系统( g i s ) 是计算机科学、地珲学、测量学和地图学等多门学科 的交义，它是以地理空间数据库为基础，采用地理模型分析方法适时提供多种空 问的和动态的地理信息，为地理研究和地理挟策服务的计算机技术系统。从表现 形式来看，g i s 表现为计算机软硬件系统，其核心是管理、计算、分析地理坐标 位置信息及相关位置上属性信息的数据库系统。它表达的是空f i ；i 位置及所有与位 置相关的信息，所以，g i s 又是地球空间实体的再现和综合，其信息的基本表达 形式是各种维或三维电子地图。因此，g i s 也u j 简单定义为“州于采集、模拟、 处理、榆索、分析和表达地理空间数据的计算机信息系统”。 g i s 最早起源丁2 0 世纪6 0 年代“要把地图变成数字形式的地图，便 汁算 机处理分析”这样的目的。1 9 6 3 年，加拿大测量学家r + f t o m l m s o n 首先提出r g i s 这术语，并建成世界上第一个g l s ( 3 n 拿大地理信息系统c m l s ) ，用丁自然 资源的管理和规划。那时的g i s 注重于空间数据的地学处理。 2 0 世纪7 0 年代以后，随着计算机软硬件水平的提高，以及政府部门在自然 资源管理、规划和环境保护等方面对空间信息进行分析、处理的需求，g 1 s 得到 r 巩固和发展。 进入2 0 世纪8 0 年代，g i s 的应用领域迅速扩大，商业化的软件开始进入市 场，其应用从基础信息管理与规划转向空间决策支持分析，地理信息产业的锥形 丌始形成。 2 0 世纪9 0 年代以后，伴随着训算机技术和网络技术的迅猛发展，g i g 的应 用也几趋深化和“泛，在国土资源、农业、气琢、环境、城市规划等领域成为常 蔷的工作系统。尤其是1 9 9 8 年前美国副总统戈尔提出“数字地球”的概念以来， g i s 在全球得到了空前迅速的发展，广泛应用于各个领域，产生了巨大的经济和 社会效益。 我国g i s 的发展自2 0 世纪8 0 年代初丌始，以1 9 8 0 年中国科学院遥感应j j 研究所成立全国第一个g i s 研究室为标志，经历了准备( 1 9 8 0 1 9 8 5 年) 、发展 ( 1 9 8 5 1 9 9 5 年) 、产、业化( 1 9 9 6 年n n ) 3 个阶段。尤其是近年来，国内出现了不 ( 1 9 8 5 1 9 9 5 年) 、产业化( 1 9 9 6 年以后) 3 个阶段。尤其是近年来，国内出现了不 浙江人学硕l 论文 第二章g i s 在物流配送系统中的应用 2 1 地理信息系统( g i s ) 概述“ ”1 地理信息系统( g i s ) 是计算机科学、地理学、测量学和地图学等多门学科 的交叉，它是以地理空间数据库为基础，采用地理模型分析方法适时提供多种空 问的和动态的地理信息，为地理研究和地理决策服务的计算机技术系统。从表现 形式来看，g i s 表现为计算机软硬件系统，其核心是管理、计算、分析地理坐标 位置信息及相关位置上属性信息的数据库系统。它表达的是空间位置及所有与位 置相关的信息，所以，g i s 又是地球空间实体的再现和综合，其信息的基本表达 形式是各种二维或三维电子地图。因此，g i s 也可简单定义为“用于采集、模拟、 处理、检索、分析和表达地理空间数据的计算机信息系统”。 g i s 最早起源于2 0 世纪6 0 年代“要把地图变成数字形式的地图，便于计算 机处理分析”这样的目的。1 9 6 3 年，加拿大测量学家r f t o m l i n s o n 首先提出了 g i s 这术语，并建成世界上第一个g l s ( 自n 拿大地理信息系统c g l s ) ，用于自然 资源的管理和规划。那时的g i s 注重于空间数据的地学处理。 2 0 世纪7 0 年代以后，随着计算机软硬件水平的提高，以及政府部门在自然 资源管理、规划和环境保护等方面对空间信息进行分析、处理的需求，g i s 得到 了巩固和发展。 进入2 0 世纪8 0 年代，g i s 的应用领域迅速扩大，商业化的软件开始进入市 场，其应用从基础信息管理与规划转向空间决策支持分析，地理信息产业的雏形 丌始形成。 2 0 世纪9 0 年代以后，伴随着计算机技术和网络技术的迅猛发展，g i s 的应 用也r 趋深化和广泛，在国土资源、农业、气象、环境、城市规划等领域成为常 备的工作系统。尤其是1 9 9 8 年前美国副总统戈尔提出“数字地球”的概念以来， g i s 在全球得到了空前迅速的发展，广泛应用于各个领域，产生了巨大的经济和 社会效益。 我国g i s 的发展自2 0 世纪8 0 年代初开始，以1 9 8 0 年中国科学院遥感应用 研究所成立全国第一个g i s 研究室为标志，经历了准备( 1 9 8 0 1 9 8 5 年) 、发展 ( 1 9 8 5 1 9 9 5 年、产业化( 1 9 9 6 年以后够个阶段。尤其是近年来，国内出现了不 b 浙江大学硕i 论文 少优秀的国产g i s 软件。 2 2g l s 系统在物流系统中的作用 系统采用北京超图公司的s u p e r m a pi s n e t 5 作为g i s 开发平台，s u p e r m a p i s n e t5 是新一代网络地理信息系统开发平台，它基于m i c r o s o f t n e t 技术和 s u p e r m a po b j e c t s 组件技术开发，设计全新的面向服务的技术体系结构，提供更 灵活的二次丌发方式和更强的并发访问能力。 s u p e r m a pi s n e t5 采用面向i n t e r n e t 的分布式计算技术，支持跨区域、跨 网络的复杂大型网络应用系统集成，提供可伸缩、多种层次的w e b g i s 解决方案， 全面满足网络g i s 应用系统建设的需要。s u p e r m a pi s n e t 5 是政府部门、企事 、止单位、其他组织和个人建立电子地图、w e b g i s 网站的利器，更是开发b s ( 浏 览器服务器) 结构的专业g i s 应用系统的理想平台。 s u p e r m a pi s n e t5 继承了s u p e r m a p2 0 0 0 在多源空间数据无缝集成、海量 数据存储、一体化系统集成等方面的众多优秀特性，增加了3 0 多个a c t i v e x 对 象，新增8 0 0 多个开发接口( 属性、对象、方法) ，提供了更多、更强大的功能， 其特点如下： i ) 灵活的开发方式 s u p e r m a p i s n e t 5 是一种全组件式g i s 丌发开发平台，它以标准的a c t i v e x 组件的方式，可以嵌入v i s u a lb a s i c ，d e l p h i ，v i s u a lc + + ，c + + b u i l d e r ，p o w e r b u i l d e r c # 等流行的可视化高级开发语言进行系统开发。s u p e r m a pi s n e t5 基了二 a c t i v e x 技术标准，可与其他技术实现无缝集成，s u p e r m a pi s n e t5 具有高度 的伸缩性，各g i s 组件可以互相操作组合使用，用于开发不同规模的g l s 系统， 也可以根据需要选择和购买部分组件进行系统开发和系统无缝集成。 2 1 全新的数据模型 s u p e r m a pi s n e t5 同时支持以拓扑关系和面向对象两种方式存储空间数 据，s d b 引擎采用结构化存储技术中的o l e 符合文件，实现多数据集和异构数 据集的一体化存储，在数据组织方面考虑c a d 和g i s 的需求，在提供点、线、 面等分类数据集的同时，针对c a d 提供复合数据集存储管理不同类型的几何对 9 浙江人学坝 一论空 象。此外、s u p e r m a pi s n e t5 支持m r s l d 和e c w 两种摹丁小波变换的影象压 缩技术和矢量数据压缩技术，可轻松管理海量数据。 3 1 多源数据集成 s u p e r m a pi s n e t 53 嘴e 0 0 ，d x f , m 1 f , d g n ，t a b ，s h p ，c o v e r a g e 等数据 格式，同时支持t i f f ，g e o t i f f ，b m p ，j p e g ，i m g ( e r d a s ) ，m r s l d ，e c w 等影象数 据格式，具有强大的数据交换泵a c t i v e x 对象，实现数据转换功能，多源数据无 缝集成( s e 锄l e s si n t e g r a t i o no fm u l t i s o u r c es p a t i a l d a t a ：s i m s ) 技术可直接访问多 种格式的数据。 4 1s d x 空间数据库 s u p e r m a pi s n e t5s d x ( s p a t i a ld a t a b a s ee x t e n s i o n ) 基于o r a c l e ，s o ls e r v e r 等关系数据库系统管理海量的、连续的空问数据。并且实现空间数据和属性数据 的一体化管理，同时实现多用户并发操作和用户权限控制。不仅支持w i n d o w s 2 0 0 0 和w i n d o w sn t 服务器，而且支持u n i x l i n u x 服务器，通过i n t e r n e t 可访 问空间数据库。此外，s d x 空间数据库还支持拓扑关系、参数化几何对象以及 矢量栅格体化存储。 5 ) 灵活的地形编辑 s u p e r m a pi s n e t 5 突破传统g i s 地图编辑的局限，具有灵活的交互式地图 编辑、智能扑捉、自动维护拓扑关系等功能，可以进行多层次地图编辑。 6 1 完整的数据安全机制 s u p e r m a pi s n e t 5 空间数据库技术通过帐号、密码和权限等进行空问数据 库数据、s d b 文件数据的安全保护。同时全面支持g m l ，g x m l 和x m l 等规范。 在本系统中s u p e r m a p 作为整个系统的平台，地图的展示，配送结果的可视 化都是建立在s u p e r m a p 平台上，具体见下章的系统设计图。 2 3 全球卫星定位系统睁”7 2 3 1 全球卫星定位系统的原理 1 1 ) 浙江大学碱l 。论殳 全球卫星定位系统g p s 最早是美国国防部为了军事用途所发展的，现在已 慢慢跨入商业用途的范围。它是利用在离地面约两万多公里高轨道上运行的二卜 四颗人造卫星所发射出来的讯号，以三角测量原理计算出接收者在地球上的位 黄。依据美国i t a ，o f f i c eo f t e l e c o m m u n i c a t i o n s 的资料显示，近年来全球g p s 在各分类产品销售额依序为： 一汽车卫星导航系统 c a r n a v i g a t i o n 消费性产品c o n s u m e r 一位置定位 m a p p i n g 一追踪t r a c k i n g 一原厂委托代工o e m 一航空a v i a t i o n 一航海m a r i n e 一军事 m i l i t a r y 由这个资料可以看出g p s 的应用项目，其中前四人项目与一般大众日常生 活有关，占了8 3 4 ，到2 0 0 3 年更高达8 9 1 。由此可见，g p s 的应用与消费 大众之关系日益密切，全民g p s 时代渐渐来临。 2 3 2g p s 在本系统中的应用 本文将g p s 应用于自动导航系统，自动导航系统使用p o c k e tp c 作为硬件平 台，p o c k e tp c 端操作系统使用m i c r o s o f tw i n d o wc e3 0 ，开发语言使用e m b e d d e d v i s u a lc + + 4 0 s p 4 。，p o c k e tp c 上g i s 系统使用e s u p e r m a p ( e m b e d d e d s u m p e r m a p ) ，通过地图浏览器c a r n a v i 与桌面端g i s 系统相连。地图通过 s u p e r m a p ，e s u p e r m a p 制作，通过经纬度校准数据和用户数据维护，然后以s d b 数据库导入到p o c k e tp c 中。p o c k e tp c 端用c a r n a v i 浏览数据库，实现g p s 定 位和配送线路，用户数据显示，并且实现导航。 图2 - 1 为g p s 导航系统设计图。 1 1 浙江大学硕f j 论义 图2 - 1 导航系统设计图 由于本文研究重点是路径规划问题，在此对g p s 系统只作简单介绍。 浙江夫学碘i j 论立 第三章物流配送系统体系结构 3 1 配送系统综述 物流系统总体设计如图3 - 1 所示，整个系统分别依次包含客户订单处理子系 统、道路网分析子系统、调度处理子系统和g i s 子系统，系统基于s q ls e v e r 2 0 0 0 平台运行，除非特殊情况，各系统间的数据访问都通过数据库来实现。 图3 1 物流配送系统总设计图 核心路径规划系统我们称为t g i s 系统，见图3 2 ，客户订单处理系统负责 每天对有订单的用户进行处理。然后汇总为当同订单表。道路网分析系统处理负 葑对己数字化的地图进行处理，对地图上道路和客户点进行处理，下节将作仔细 介绍，调度子系统对将要配送的客户点进行排序，使车辆所需配送时间尽量少。 第四章将作仔细介绍。调度子系统生成的路径表写入数据库，最后由g i s 子系 统调用生成基于s u p e r m a p 的可视地图路径。具体系统的实施将在第五章做仔细 浙江人学顿f 论文 介绍。 图3 - 2 t g i s 系统设计图 3 2 地图数据的抽象化一拓补图的建立 本课题是在g i s 环境下完成的，主要内容是针对道路路线进行规划。因此 将着重分析城市的路网图层，道路中两个节点问的最短距离的求解就是基于这个 图层的。同时新建一个图层配送网络层，它包含每个连锁门店的信息及配 送中心的信息。配送中的路径规划车辆调度问题的求解就是基于这个图层的。 在城市路网图层中进行最短路径分析，首先必须将现实中的城市道路网络实 体抽象化为网络图论理论中的网络图，然后通过图论中的网络分析理论来实现道 路网络的最短路径分析【1 9 1 。为了能够高效率地进行最短路径分析，必须首先将 其按结点和弧的关系抽象为图的结构f 2 0 i 。这就需要对原始道路图进行预处理， 我们通过长达一个月的采点对试点市区的所有道路进行了详细的测量，并将各项 数据在数据库建表。数据包括道路长度、道路所连接十字路口、道路方向性、道 路等级、道路名称等详细信息。所谓抽象化是建立其相应的网络拓扑关系。建立 拓扑关系就是需要得到任意两个配送点问最短的距离，将配送网抽象为全连通的 浙江大学顾 论文 有向图，然后将这些距离存入道路网距离文件，以备调度处理子系统使用。每一 条边的权值是起点到终点问的最短距离。 3 3 地图中任意两配送点间最短路径算法 3 3 1 最短路径问题叫1 图g = ，e ) 是由有穷而非空的顶点集v 和边集e 所组成，如果边是顶点的 有序对卜，p l 卜。，v ，) e e ；v ，v y ，则此图是有向的。爿，b 是两个非空集合，f ，占 分别是y 到爿，e 到b 的两个映射，则称有序四元组g ：妒，e ，a ，占) 为加权图， 彳，口称为顶点的权和边的权。图g 的一个边序列岛，e ，。，或者说一个顶点 序列v 。，v 。，v ：，叱称为图从v 。到v + 的一条路经；从v 。到v 。的所有路径中，权 ( v 。，v t ) 最小的路径称为从v 。到h 的最短路径，记为( ，v 。) 其长度为： ( v 。，叱) t m i n 慨d 。，咋】，y ；f ；1 , 2 ，j 。 最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量， 如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径问题、最低 费用问题等。无论是计算最短路径还是最佳路径，其算法都是一致的，不同之处 在于有向图中每条弧的权值设置1 2 2 。如果需要计算最短路径，则权值设置为两 个节点的实际距离；而要计算最佳路径，则可以将权值发置为从起点到终点的时 间或费用。因此，无论是距离最短、时间最快还是费用最低，它们的核心算法都 是最短路径算法i 捌。在此我们假设道路的通行质量是相同的，而且是随时间也 没有变化。那么，行车时间和距离之间就存在着简单的正比关系。要计算两点之 间的行车时间，只要知道两点之间的距离就可以了。这样，问题就集中在求两点 之间的距离。两地之间的距离是指两点之间最短路径的长度。两点之间的路径可 以有很多条，在安排行车路线的时候，我们必须保证车辆走最短的路程，这是总 成本最低的保证，同时也是总路径最短的保证。那么求解任意两点之间的最短路 径就成了解决物流路径规划问题的基础。 3 3 2 d i j a s k a 算法2 3 1 2 盯 1 s 浙江大学碗l 硷业 d i j k s t r a 算法是典型最短路算法，用于计算一个节点到其他所有节点的最短 路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为i t 。d i j k s t r a 算法能得出最短路径的最优解，但效率稍低，对于具有1 1 个节点的一个图，计算 一个节点到图中其余节点最短路径的算法时问复杂度为o “2 ) 。具体算法表述如 下： 1 ) 假设用带权的邻接矩阵c o s f 来表示带权有向图，c o s t ，j 表示弧( v i ，v j ) 上 的权值。若( v 。，v f ) 不存在，则置c o s f 【v 。，v ，j 为。s 为己找到从v 出发的最短路 径的终点的集合，它的初始状态为空集。那么，从v 出发到图l 其余各顶点f 终 点) k 可能达到的最短路径长度的初值为：拙七 ；c o s t o r d i n a l o ) ，l 巧y ； 2 ) 选择，使得：d i s t j t 胁铷七批y s j ，就是当前求得的一条从v 出发的最短路径的终点。令s = s 0 ； 3 ) 修改从v 出发到集合v s 上任顶点，k 可达的最短路径长度。如果 d i s t j 】+ c o s t y ，k 】 d i s t k i 贝1 修d i s t k 】为d i s t k 】= d i s t j 】+ c o s t j ，k 】； 4 ) 重复操作( 2 ) ，( 3 ) 共n 一1 次，由此求得从v 到图上其余各项点得各最短路径 使依路径长度递增得序列。 网络中各节点之间相互关联的复杂性的造成每个节点的后继节点集中可能 包含若干节点。算法在访问某个节点之后，有可能会直接反向回到该节点或沿着 某条路径回到该节点，因此必须建立一种机制以避免算法在某几个点之问陷入死 循环的状态。 3 3 3 弗洛伊德( f l o y d ，1 9 6 2 ) 算法 1 9 6 2 年，弗洛伊德提出了一个比较简便的求任意两点间最短路径的算法。 算法的思路是直接在图的带权邻接矩阵中用依次插入节点的方法改变矩阵的元 素值，使最后得到的矩阵成为图的距离矩阵和路径矩阵。算法首先给图的节点编 号( 次序可以是任意的) 并将邻接矩阵a 作为距离矩阵d 的初始值，即： 浙江大学硕i j 论史 d 。a ，d 。! o ) = ( 4 ) 。( 3 1 ) 在矩阵d 。e ，将节点v 。插入任意两点v i 和v i 之间，并按照公式 d ；1 = m i n p ；”，d + d 护) 求出d 1 = ：1 ) 。可见d ：1 是从u 直接经过一条弧到 ”，或者从q 经过中问点h 到v 这两条路径中最短路径的长度。 在矩阵d 1 1 上，将节点v ：插入任意两点v ；和p j 之问，并按照公式 d 笋2m i n 舻；”，d 粤+ d ? 求出d 2 = ) 。则以d ；2 表示从v ，直接到v ，或者 从u 经过v 。或v ：或p 。与v ：而到v ，的所有这些路径中最短的一条路径。 用归纳法，设v ，与_ 之间已插入( k 1 ) 个节点，则插入第k 个节点时得矩阵 d 忙2 ( d ) ，其中d 芦一m i n p ，d 山+ d 等叫) ，则以d 表示从v 。直接到v j ， 或者从t 经过v 。，y ：，中部分或全部节点丽到v j 的梭鱼这些路径中最短的 条路径。 当k = n ，t i d ；( d 扩) 。即为图的距离矩阵。在求距离矩阵的迭代过程中， 也可将路径矩阵p 求出来。 弗洛伊德算法的c 语言实现如下程序所示。 弗洛伊德算法的c 语言实现： i n tf l o y d s ( i n t + m a t r i x ) i n tk ，i j ； f 0 “k = 1 ；k = n ；k + + ) f o r ( i = 1 ；i = n ；i + + ) f o r 0 = l ；j = n ；j + + ) i f ( m a t r i x i j l ( m a t r i x i k + m a t r i x k l j ) ) m a t r i x 【i j 】= m a t r i x 【i 】【k 】+ m a t r i x 【k 】【j 】； ) 1 7 浙江夫学碘i ：论殳 由于弗洛伊德算法相对比较简单目易于实现，在系统中我们使用弗洛伊德算 法求得任意两点间最短路径，然后将这些数据写入文件，以备进行路径调度时使 用。 3 4 配送区域的划分 3 4 1 配送区域的概念 在进行物流配送调度时，每天的配送量都比较大，一般都需要多辆车对客户 进行配送。即先根据车辆装载量等各种约束条件进行配送区域划分，然后在各小 区域内设计最优配送路线。而不同配送的区域的划分方法对最后结果总用时影响 很大，所以确定一种比较合理的划分算法对整个系统是比较关键的。 3 4 2 扫描法简介 扫描法是由g i l l e t t 和m i l l e ：于1 9 7 4 年提出的，浚方法的基本思路是采用逐 次逼近的方法求解物流配送车辆调度问题。该方法对物流中心以及客，、所在位置 用极坐标表示，其中物流中心物为坐标原点。其主要步骤是： s t e p l ：以极坐标角度由小到大顺序对客户进行编号，角度相同的，将距离物 流中心较近的给予较小的序号。如分别设为：1 、2 、l 。 s t e p 2 ：作初始配送区域。其做法是按客户由小到大序号依次将客户1 ，2 ， j ，纳入初始配送区域，其中j 为在满足约束条件下第一辆车所能到达的最后客户。 同样，依此方法将客户j + l ，j + 2 一纳入初始配送区域2 。最后得到k 个初始配 送区域。 s t e p 3 ：配送区域的调整：试着将区域k ( k = i ，2 ，k - 1 ) 上的一个客户与区域 k + i 上的一个或多个客户进行交换，如果交换后能够使总配送距离减少，则保留， 否则，放弃交换。交换客户的原则是：从路线k 上去掉的客户应当是在路线k 上所有客户中距坐标原点( 物流中心) 距离最近的客户。被考虑用来加到线路 k 上的客户应当是：在路线k + i 上所有客户中离最后加到路线k + i 上客，1p 最近 的客户。按照此方法对各条配送线路上的客户逐步替换，使总距离最小。 1 8 浙江大学硕上论史 重复s t e p 3n 次后，得到最小总距离的作为最后的解。 采用扫描法不一定能求得物流配送车辆调度问题的最优解，但是自够有效地 求得问题的满意解。但出于每次交换都要进行大量的计算，所以当客户数增多时， 计算量呈指数增长。研究表明，当的客户数目不大且配送区域不多时，用扫描法 求解是非常有效的。 3 4 2 聚类算法简介和应用 近年来，数据挖掘成为越来越热的一个研究方向，而聚类( c l u s t e r i n g )