基于GIS的城物流配送信息系统

1、第 五 章 基 于 G I S 的 城 市 物 流 配 送 信 息 系 统在城市货物需求信息、路面交通状况复杂 , 拥有运输车辆较多的倩况下 ,单纯采用人工 办法在规定时间内连续确定配送车辆整体调度的每日最佳方案是不可能的 , 因此建立 车辆优化调度计算机信息系统成为货运组织提高工作效率 , 增加经济效益的必要手段。 为此,结合实际情况 ,基于前两章所设计的调度算法 ,开发出了基于地理信息系统 (GIS) 的城市物流配送信息系统。5.1gis 系统介绍地理信息系统 (GIS) 是一种以地理空间数据为基础 , 实时提供多种空间、动态的地理信 息及决策服务的计算机技术系统 , 它依据地理对象的空间

2、特征及属性特征 ,建立各种空 间分析模型 , 在这些模型的基础上使用空间查询和空间分析对地理数据进行管理 ,并通 过对地理数据的分析、加工和处理，提取有用的地理信息，为决策服务。利用GIS强大的 空间数据分析能力 ,可以帮助解决路径规划的问题 ,并提供在市场规划、需求预测、空 间信息等方面的决策参考。GIS的主要特点有以下两个方面：(1) 信息可视化将不同区域的各个属性 (如客户名称等 )显示在的图上 ,形象、直观地让人一目了然。(2) 空间关系分析利用GIS可以对不同区域的属性进行比较及同一区域的属性进行叠加等。5.2城市物流配送信息系统的分析与设计5.2.1 系统的功能模块分析与设计基于G

3、IS的物流配送信息系统是针对城市的形式提出来的，其目标是给用户提供一个配 送优化平台,为系统用户提供更好的物流配送方案 ,节省配送成本 ,提高配送效率。 整个 系统由界面控制模块、功能实现模块、系统信息管理模块、系统共通模块、对象组织 管理模块和数据交互模块组成 (图51) 。(1) 系统界面控制模块。用户接口 (UI), 负责与用户的交互 ,响应用户要求和界面控制。(2) 功能实现模块。负责实现系统的具体功能。包含了客户实时地理定位、划分各配送 中心服务区域来确定其配送对象、送货路线设计和电子地图操作等。(3) 系统信息管理模块。负责管理数据存取路径、用户设定等 ; 提供系统运行时所需各 种

4、信息的查询和修改等。(4) 对象组织管理模块。负责组织管理内存中的各种数据对象实例 , 提供遍历、检索等 基本容器功能。(5) 系统共通模块。 提供系统共通的常量定义、 宏定义、数据结构体定义、 共通函数(内 存管理)等。(6) 数据交互模块。提供 Shp,Log,Txt,Bmp 等格式文件数据读写、组织管理等。在整个 系统设计中,功能实现模块和数据交互模块是本系统设计的重点部分 ,分别对应两大部 分设计 ： 一部分是系统具体功能设计和实现 , 另一部分是空闻数据库组织与设计。5.2.2 系统主工作流程系统的主工作流程是 ： 用户通过界面控制模块输入送货点需求信息 , 经过有效性检验合 格之后

5、,选择不同的调度方案模式 ,并把数据通过公共变量的形式传递到功能实现模块 通过算法计算把结果及各项统计指标以文字的形式在窗体上显示 , 然后用户可以选择 以地图的方式在电子地图上显示行进路线 , 看是否满意此调度方案 , 然后用户可以选择 放弃、修改或保存配送方案 , 然后再进行如上步骤 , 或进行别的操作功能。主工作流程如图52所示。5.2.3 空间数据库系统设计 城市物流配送信息系统设计的关键是空间数据库的设计 , 在物流配送系统数据库中包 含空间数据和属性数据设计 ,采取空间数据和属性数据分开管理的方式 ,即“文件系统 + 属性数据库”的方式,空间数据以Arc/lnfo的Shae文件方式

6、存储,主要是街道文件、街 道交叉口(路口)文件,路口文件是路口的点位信息文件：属性数据是利用Access建立小 型属性数据库 , 其中包含客户信息数据库、 配送中心信息数据库以及配送中心和街道交 叉口对照表 , 下面详细介绍空间数据库各表的数据结构。(1) 配送中心信息、客户信息属性表和车辆信息属性表。为了能在电子地图上查询配送 中心信息 , 根据收集的客户信息在地图上进行实时定位 , 以及选择不同的配送车辆进行 实时配送 , 需要建立配送中心信息、客户信息属性表和车辆信息属性表 , 配送中心信息 含有配送中心编号、配送中心的名称、地址、电话等 ： 客户信息包括客户编号、客户名 称、客户地址、

7、客户电话以及客户需求等信息 , 客户通过网上订购、电话订购或者现场 订购的方式 , 留下的相关客户信息 , 输入至客户信息表 ： 车辆信息包括车辆编号、 载重量、 从属的配送中心编号等信息。(2) 街道路段信息表与路口属性表。路段信息表用于表示路段的属性 , 它在建立街道的 网络拓扑时生成 (表51) 。通过拓扑关系进行路径选择分析 , 有关门牌号码的字段 , 是 以后进行客户地理坐标生成的关键字段。 路口属性表用于记录路口结点的属性 , 它在建 立街道的网络拓扑时生成 , 包含路口地理坐标、路口结点标志号、连接路段的标志号 , 其中路口节点标志号与路段信息表的FNode和TNode两个字段对

8、应,连接路段的标志号 对应路段信息表的 ld 字段。(3) 配送中心与路口对照表。这张表是对配送中心配送对象空间的一个划分表。根据后 面豹配送中心配送对象设计，划分了配送空间，将对应空间的路口 Id与配送中心Id对应 起来, 包括两点间的距离和行车时间 , 方便在配送中快速选择合适的配送中心 , 进行送 货服务。5.2.4 系统功能设计 系统核心功能包括地址匹配、配送中心配送对象分析、送货路线设计三大部分。地址 匹配是将不含地理坐标的客户地址在电子地图中定位并显示出来 ; 配送中心配送对象 分析是对各个配送中心配送的空间范围的确定 , 合理的划分配送中心的配送空间 ;送货 路线分析是在前面的基

9、础上 , 对单客户、 多客户等多种情况设计送货的具体路线并产生 送货路线图 , 这是配送系统的最核心功能 , 也是减少运输成本的关键 (图53) 。 5.3核心功能的设计和实现基于GIS的物流配送信息系统,使用对象链接与嵌入(ObjectLinking&EmbeddingAutomation,简记OLEAutomation)技术集成 GIS和开发语言。 利用GIS工具软件实现GIS的基本功能，以4GL语言(如Powerbulider)为开发平台，进行 二者的集成。这样，既保留GIS的地图方面的处理功能，又能利用4GL语言开发出来的应 用程序具有更好的外观效果及用户界面 , 更强大的数据库功能。

10、本系统中 , 利用先进的 桌面地理信息系统 MapInfo Professinal 7.0 与可视化编程工具 Powerbuilder 8.0 集 成来实现系统目标。在多配送中心的物流配送系统设计中 , 其核心问题有以下几种。(1) 根据地址信息 ( 街道名及门牌号 ) 确定客户的地理坐标。在客户属性信息里 , 并没有 客户的确切地理坐标 , 因此要根据客户所在的地址即街道名和门牌号确定其地理坐标(X,Y),主要是利用所建立的具有拓扑关系的街道信息文件来进行分析。利用MapObject中的地理编码对象来定位客户地理位置 , 首先根据街道名查找具有与之同名的路段 , 再 根据门牌号确定所在的具体

11、路段 , 该路段查询与连接的两个路口 , 路口的坐标以及该路 段的起始及终止门牌号进行线性插值 ,进而求出客户所在地址的中心点坐标 (图54) 。 (2) 配送中心配送对象设计。要确定每个配送中心的配送对象 , 首先是根据配送中心的 空间布局 ,结合一些相关的基础地理要素如交通、地形等运用地理信息空间分析中的Voronoi模型对地理空间进行划分,确定各个配送中心的服务区域,这一步运用GIS系统 进行空间分析操作来完成。 然后分析客户位于哪个配送中心的服务区域 , 进而确定其货 物来源, 这样也就确定了配送中心的送货对象。为了提高分析的效率 , 客户匹配到各自 最近的路口坐标，然后根据前面空间分

12、析操作生成的路口和配送中心对照表 ，通过SQL 查询, 可以迅速地查找到单个配送中心的配送对象。(3) 配送中心的送货路线设计。在确定了配送中心送货的客户对象以后 , 剩下的工作就 是如何合理安排配送路线来送货 , 这个问题也是配送中的核心部分 , 可以降低运输成本 提高企业效率。问题描述及车辆调度模型见本文 4.1,4.2, 采用的优化调度算法为车辆 调度分派节约启发式算法 ( 见4.2.4), 解决了单车无时间窗约束、多车有时间窗约束 和多车无时间窗限制问题。5.4应用实例某连锁店有一个配送中心和 10个分布在市内各区的连锁分店 , 称为分场 (分场的数据库 已建好 ) 的需求信息如表 5

13、 2所示。选择费用因子为以路径距离为最小 , 时间窗约束为硬时间窗 , 装车复杂系数为 0.9, 分场之间的距离由地理信息系统功能即可求得 , 分场点的位置是事先确定好的。1. 系统登录界面如图 55所示。在此界面中 , 用户在输入用户名和口令后 , 系统将完成 以下工作 :(1) 检查用户名和口令是否正确 ;(2) 进行系统的初始化工作 ,如界面的初始化、数据库的连接等。2. 需求计划输入 , 如图 56所示。在此窗口中 , 分别录入各分场需求信息 , 从两为进行配送计划制定准备好基础数据。在 进行运算前 , 将验证数据的有效性。3. 配送计划制定。在进行了一些基础因子的选择之后 ,即可进行

14、计算 ,本例的路线安排及路程、 运量如图5 7所示。配送计划制定好之后 , 用户也可以选择以地图的形式显示出来 , 以直观的可选 择的线性和颜色在电子地图上展现 ( 被颜色渲染的街道即为配送行进路线 )。5.5 小结本章主要介绍了基于GISs的城市物流配送信息系统的设计框架。 在此基础上，介绍了系 统数据库的组织结构和构建方法 , 并通过实例论述了系统功能中的客户地址匹配、 配送 中心配送对象设计、配送路径设计的实现过程。结论及展望全文总结城市物流配送系统是一个开放的复杂性系统 ， 也是集多项功能为一体的综合性系统。 本 文从全过程、全局对城市物流配送系统优化的方法展开研究 ， 取得了以下研究

15、成果 :1. 以城市为背景，描述城市物流配送系统的形成机理 ，分别阐述市场需求、政府引导规 划、物流与供应链管理理论、现代技术等因素在配送系统形成过程中所起到的作用 ， 从 系统角度分析城市物流配送系统的本质、构成、功能、优化手段和目标 ， 根据城市交通 道路、设施、客户需求特点 ， 把配送系统分解成配送网络系统、配送运营系统以及配送信息系统分别进行研究 , 使研究更加有针对性和实际操作性 :2. 从成本最小化角度出发 , 考虑集货费用、配送费用、配送中心运营费用三种费用因素 , 建立了具有广泛实际意义的多配送中心城市物流配送网络系统模型 , 并运用启发式算 法一贪婪取走算法对该模型进行优化

16、, 该算法实现了在可行域范围内的较全面搜索 , 反 复判断、实践修正 , 逐次逼近最优解 ,是解决城市物流配送网络系统优化的有效手段 ;3. 从满足客户需求最大化和配送运营成本最小化的角度出发 ,考虑时间窗约束 , 建立城 市物流配送运营系统模型。 在构造配送算法时 , 把该复杂模型分解成配送中心选择以及 车辆调度两个阶段 , 对每个阶段采用启发式算法分别进行优化 , 最后从整体上检查和调 整,得出优化解 ,既能通过分派启发式算法保证最大程度地满足客户的要求,又能利用节约算法保证全局最优 , 实用效果良好 ;4. 根据城市物流配送的特点,利用GIS工具软件实现GIS的基本功能,以Powerbu

17、ilder为 开发平台,两者集成,开发了物流配送信息系统 ,分析了系统的主要功能模块、 设计了系 统的主工作流程和空间数据库系统、实现了各核心功能。上述工作的应用对指导和提 高城市物流配送系统发展将具有良好的社会和经济效益。城市物流配送系统的优化是一项极其复杂的工作 , 它将系统思想、现代管理模式、现代 信息技术、城市配送特征、现代建模技术、现代智能算法和集成技术等融合实现城市 配送系统的优化目标一低配送成本、高服务水平、高配送效率、高配送质量和好的环 保性, 其系统优化的定性与定量分析还不是十分成熟 , 与之相关学科的不断发展和完善 必将有力支持和推动该领域的理论方法、 技术和手段的不断进步

18、 , 这将有力的促进我国 城市配送系统的规划、建设、运营与管理优化 , 提高城市配送水平。本人认为 : 城市物 流配送系统优化的影响因素对模型的量化分析和评价指标标准的评估尺度是今后优化 研究的发展方向 , 由于本人能力有限和时间紧逼 , 论文还有值得完善的地方 , 因此还可 以在以下方面做进一步的研究 :1. 由于配送对象的动态性、时间上的不确定性 , 以及城市交通情况的复杂性 , 配送网络 模型和运营系统模型的建模假设与城市实际情况还有差异 , 如何减少这种差异的建模 方法还有待研究 ;2. 由供应商、配送商、客户三级组成的城市物流配送网络系统可以有包括单配送中心 型、多配送中心型等在内的

19、多种不同的组合方式 , 本文出于篇幅的考虑 , 只对其中的多 配送中心情况进行了一般建模 , 关于该部分还有值得进一步细化研究的地方 ;3. 如何在本文的城市物流配送系统优化体系架构的基础上 , 研究和建立代表城市配送 系统全局、全过程的系统评价指标体系、综合评价计算方法 , 可作为下一阶段的研究方 向。参考文献【1】龙江城市物流系统规划与建设【M 第一舨.中国物资出版社,2004【2】程建权.城市系统工程【M .武汉大学出版社,2002【3】王之泰 . 现代物流管 【M . 北京:中国工人出版社 ,2001【4】白世贞.现代配送管理.第一版【M .第一版中国物资出版社,2005【5】 马士华

20、著供应链管理【 M】 . 华中科技大学出版社 ,2001.【6】薛明德.物流系统规划与设计【Ml .企业管理出版社,2004【7】蔡临宁.物流系统规划一一建模及实例分析【M】.第一版.机械工业出版社,2003【8】贾争现.物流配送中心规划与设计【M】.第一版.机械工业出版社,2004【9】王转.配送中心系统规划【M】.第一版，第一版中国物资出版社,2004【10】牛东来现代物流信息系统【M 第一版清华大学出版社,2004【11】何明柯物流系统论【M .北京：中国审计出版社,2001【12】邓爱民,丛书主编.现代物流系列教材【M ,含（交通港站与枢纽，综合运输学, 物流与供应链管理,物流设备与应

21、用,物流管理信息系 统,电子商务与物流）,人 民交通出版社,2003【13】邓爱民,沈文.国内外物流经典案例【M】.人民交通出版社,2001【14】孙国正.优化设计及应用【M .人民交通出版社,1992【15】孙国正.广义优化理论与方法【M】.人民交通出版社，1997【16】张可明.物流系统分析【Ml .北京：清华大学出版社，北京交通大学出版社,2004【17l鲁晓春.关于配送中心重心法 选址的研究【J】北方交通大学学 报,2000【18】周梅华.论集约化商品配送中心的 选择【J】中国矿业大学学报,2000【19l Aikens C H, Facility Locatino Models fo

22、r Distributen Planning. European Journal ofOperatio nal Research,1985,22（3）:263 279【20l Taniguchi E. Optimal Size and Location Planning of Public Logistics Termi nals. Tran sportatio n Research,1999,35E:207 222【21】Holmberg K. Exact Solution Methods for In capacitated Location Problem with Con vex Tr

23、an sportati on Costs. Europea n Jour nal of Operati onal Research, 1999, 114（2）:127 1402. 参数设定M配送中心备选地的个数K供应地的个数N需求地的个数P-可选的配送中心的最大个数L产品种类k供应地l产品的供应能力j需求地l产品的蹴球总量i配送中心备选地的建设容量备选配送中心i的固定费用产品I的配送中心管理费率（单位：元/吨）产品I的处理费用率（单位：元/吨）l产品从供应地k到配送中心i的运输单价（单位：元/吨?公里）l产品配送中心i到需求地j的运输单价（单位：元/吨?公里）供应地k到配送中心i的距离（单位：

24、公里）配送中心i到需求地j的距离（单位：公里） g固定资产的使用年限3. 模型变量在该模型中，有五个变量：l产品从供应地k到配送中心i的运输量；l产品从配送中心i到需求地j的运输量；配送中心被选中配送中心被淘汰配送中心 与供应地 存在供需关系 配送中心 与供应地 不存在供需关系 配送中心 与需求地 存在供需关系配送中心 与需求地 不存在供需关系4. 问题的数学建模(1) 目标函数在配送中心选址时，我们期望的是使配送费用最小，以达到最佳的经济效益。本模型主要考虑以下三个费用：1) 集货费用，即供应点到配送中心的运输阶段费用。该费用与供货量和供货运输单价 及运输距离也有关，可表示为：(3-1)2)

25、 配送费用，即配送中心到需求地的运输阶段费用。该费用与配送量和配送运输单价 茸及运输距离 有关，可表示为：(3-2)3) 配送中心运营费用，该费用包括配送中心的建造费用和仓库的商品保管费用和处理 费用，同时考虑到建造费用在使用年限内的分摊问题，可表示为：(3-3)由前面对问题的说明可知，模型的目标函数是使配送中心的集货费用、配送费用和运营费用之和最小。即以上3项费用之和最小。可用公式表示如下:(3-4)(2)约束条件1=1,2，L;K=1,2 ,K(35)i=1,2,M(36)i=1,2,M(37)P(39)M 0M为一相当大的正数(310)其中，35为供应约束，即任意一种产品从供应地发运到各

26、配送中心的货物总量 不能超过它的供货能力；36为需求约束，即各配送中心向某需求地配送的任一产品 的货物总量应满足该需求点的需求量；3 7为容量约束，即各供应地供应给任一配送 中心的货物总和不能超过该配送中心的建设容量；38为平衡约束，即通过各配送中心的货物进出量要相等；39为规模约束，即被选中的物流中心备选的个数不能超过 原定的最大限度；310为非负约束，即配送中心的集货数量不能小于零。算法的基本思想：选择配送中心子问题解决的是选择配送中心的问题，即根据不同的客户需求，在所有的配送中心中选出出货的配送中心。本文选定的处理算法结合了 sweep算法和saving算法。首先根据就近分配的原则,通过

27、 计算每个任务点离配送中心最近距离与离配送中心次近距离的比值，按比值从小到大的顺序,将需求分配给最近的车场，考虑路径最短；同时针对边界点的特殊情况，采取特 定的方法进行分派。算法的步骤：首先假设每个配送中心具有足够多的车辆数。1. 设 表示需求点i与配送中心t的距离，表示为需求点i与需求点j间的距离。计算R(i)=其中，一一距离点i最近的配送中心距离点i第二近的配送中心取一适当的(0 1),比较r(i)与 的大小，有以下两种情况：一为R(i) ,这时i点称为边界点。2. 边界点的分派(1) r(i)工1时，边界点的分派借助于Clarke-Wright算法来进行。首先考虑由最近的配送中心发出的车

28、辆服务每个点，构成初始解。线路的初 始费用为：C=(h为边界点数)(4-17)各点对最近配送中心的分派是暂时的，一旦两个或多个点已被分派给一个配送中 心发出的线路，这些点就不再分派给其他配送中心。同原来C W!法一样,只有点i与点j都不为一线路的内点时,才能被连接。计算节 约值如下：=+ -(4-18)其中=点还未给一永久分派否则根据节约值连接点i与点j(在不违反约束前提下)。式中第一种情况下，点i被再分派给离它最近的配送中心，这时总费用节约了 2;在第二种情况下，点j插入车辆l与点i之间。(2) r(i)=1时，边界点按照下面方法分派。若点j和k已分派给一个配送中心t,把点i插入到点j与k之

29、间，产生的附加费用：(i)=+(对车场t)并取的配送中心为点i所分派的配送中心。通过改变 的大小，可以控制边界点的个数。当=0时，所有点均为边界点。当=1时,所有点均分派给最近的配送中心。433车辆调度模型建立选择配送中心子问题解决后，得到的结果为把客户点分配给了配送中心点，即解决了分 配问题。在这个基础上，解决车辆调度子问题，就是决定每个配送中心中的每辆车装载 哪几个客户的货物，何时发车,车辆如何行驶(行车路线安排)等问题。车辆调度子闯题是点对多有时间窗约束的多车配送情况，根据上述总体模型的描述，现车辆调度模型问题可描述为：配送中心k有装载量周为级的k,(k=l,2,? km)辆车，对 应有

30、N个需求点,i需求点的需求量为 (i=l,2,N),需求点i规定在【,】时间段内 到货。这是一个最典型的VSP可题,见图4-2。模型建立如下：=(+)+g,+A+d+e(4-19)一配送中心每辆车的单位运距运输成本；A表示若违反容量约束处理的惩罚值,A表示当一辆车的货运量超过其最大承载量时的惩罚系数。A应趋向于无穷大，考虑到计算机处理的问题,一般取适当大的正数。4.3.4车辆调度分派一节约启发式算法目前,解决城市物流配送系统优化模型的启发式算法还处在探索阶段，对NP隹题的算法研究多是集中在单目标(总成本最低)的问题,而针对多目标问题，特别是以时间限制为 主要目标,追求成本最低、车辆空载率最小的

31、问题的解决方法还没有。作者对旅行商问 题的C-W节约算法进行修正,在连接点对时,考虑时间约束,并结合采用Flisher、 Jaikumar的分派启发式算法，设计了解决具有时间窗的城市物流配送车辆调度问题的 启发式算法，具体步骤如下。1. 确定所需车辆数m2根据各任务的需求量，由以下公式来估计大致使用的车辆数：K=+1(4-20)注:K 一配送中心估计使用的车辆数。其中【】表示不大于括号内数字的最大整数,0 1,是对装成(或卸车)的复杂程 度及约束多少的估计。一般来说,装车越复杂、越多，口越小,其值可通过人机对话调整， 一般取=0.71。由于不同任务的送货特性不同，合在一起运输就有一定的复杂性。

32、 一些任务虽然货 运量可以组合在一起，但对总体组合运输效益并不一定有利。为此,引入“人工变量” G,其中(0 0.5q的顾客作为种子顾客，因为这些顾客中的任何两个都不能在同一条线 路上。(3) 客户的具体要求 (如对时间或装车的要求等 )(4) 选择最远离车场的顾客为第一个种子顾客 , 距离由配送中心和已确定的种子顾客构 成的集合最远的顾客作为下一个种子顾客 , 然后按此规则继续进行 , 直到选出的种子顾 客数达到所需的车辆数。显然 , 两个最远的点属于不同的集合。(5) 计算相邻点间的最大半径距离 , 取定义这个最大半径距离的一个点 , 从配送中心起 作一条穿过该点的射线 ,将此射线按顺时针

33、方向旋转扫描 ,累加所遇到的各点的需求 , 当达到车辆容量的一定百分比时 , 就构成了一个车辆区 , 然后射线继续扫描 , 当所有点 都被包括进某一区域时 ,过程终止。 种子顾客在二等分区域的射线上 ,一般来说,种子顾 客的确定应使根点以内的顾客需求占区域总需求的一定比例。按该方式选择种子顾客时, 种子顾客为虚拟顾客。选出种子顾客后 , 则剩余的任务称为顾客。将种子顾客分别分派给各个进行 配送的车辆,再以种子顾客为依据将其他的任务进行分派。由种子顾客的定义可 知, 种子顾客的数目与配送车辆的数目必须相等。种子顾客的分派步骤如下 : 根据上文中的方式(2)、(3)找出有特殊要求、必须单独装车的任务，,作为种子顾客；在K辆配送车中,将任务4分派到相应的配送车君,中。此时剩 余任务数 nn=N- , 剩余车辆数 kk=K- 。若本次配送中没有需要单独装车的任务 , 则 =0。在剩余的nn项任务中，按上文中的方式(4)搜索任务 ，, 作为种子顾客,直到+ =k,即=kk为止将种子顾客(e=1,2,)分派给相应配送车(h=1,2,kk)中。3. 进行初始分派种子顾客已经分派到相应的配送车上，且种子顾客，,以只能单独装车，因此只需把剩余的(nm)个顾客分派给种子顾客。，具体步骤如下：(1)以种子顾客为供应点，以