管理论文基于Map Info电子地图的配送车辆线路优化问题研究.doc
《管理论文基于Map Info电子地图的配送车辆线路优化问题研究.doc》由会员分享,可在线阅读,更多相关《管理论文基于Map Info电子地图的配送车辆线路优化问题研究.doc(4页珍藏版)》请在三一文库上搜索。
1、基于电子地图的配送车辆线路优化问题研究 基于电子地图的配送车辆线路优化问题研究是小柯论文网通过网络搜集,并由本站工作人员整理后发布的,基于电子地图的配送车辆线路优化问题研究是篇质量较高的学术论文,供本站访问者学习和学术交流参考之用,不可用于其他商业目的,基于电子地图的配送车辆线路优化问题研究的论文版权归原作者所有,因网络整理,有些文章作者不详,敬请谅解,如需转摘,请注明出处小柯论文网,如果此论文无法满足您的论文要求,您可以申请本站帮您代写论文,以下是正文。 摘要:GIS技术与VRP问题的结合,不仅提供了一种新的查询选择方法,同时还能提供一种直观的解决方案。文章针对Map Info电子地图的特点
2、,给出了一种从电子地图中提取客户与道路信息应用到解决实际的配送车辆线路优化问题,并将求解后的线路直观地显示到电子地图中的方法。在实际应用中表明该方法是高效直观的。关键词:VRP;Dijkstra算法;地理信息系统中图分类号:U116.2文献标识码:A文章编号:1002-3100(2008)12-0023-03Abstract: The combination of GIS and VRP is not only a new method to inquiry, but also offers an intuitive solution. Based on the characteristic
3、of Map Info electro-map, a method to extract customers and routes information from the map to be used by the Vehicle Routing Problem and draw the feasible path on the map is given. Its testified that the method is efficient and intuitive in practice.Key words: Vehicle Routing Problem; Dijkstra algor
4、ithm; GIS0引言配送作为直接与消费者相联系的环节,在整个物流系统中起着举足轻重的作用。相关资料表明,在生产企业原材料物流中运输配送成本占整个物流成本的58%,在生产企业成品物流中达到73%,而在商业企业中该比例为52%1,因此,有效降低配送成本对降低物流系统运行成本具有非常重要的意义。配送车辆线路优化问题(VRP, Vehicle Routing Problem)最早由Danzig和Ramser提出2,就是研究如何制定合理的配送线路,从而以最少的物流成本将货物快速而经济地送达客户手中。近年来,伴随着经济全球化与物流业的迅猛发展,该问题在实践中的应用逐渐受到重视。地理信息系统GIS是用于
5、采集、存储、管理、处理、检索、分析和表达地理空间数据的计算机系统,是一种分析和处理海量地理数据的通用技术。利用GIS技术,可以对空间数据进行直观显示和分析。基于GIS的配送车辆线路优化系统是GIS应用的一个新领域,也是配送车辆线路优化问题向信息化发展的一个趋势。集成后的配送车辆线路优化系统不仅可以为企业提供一种新的查询选择方法,同时还能提供一种直观的解决方案,指导企业选择合理的线路。本文针对Map Info电子地图的特点,给出了一种从电子地图中提取客户与道路信息应用到解决实际的配送车辆线路优化问题,并将求解后的线路直观地显示到电子地图中的方法。1VRP问题数学模型约束(1)表示客户点i在某辆车
6、的服务线路上;约束(2),(3)表示客户点i,j在车辆k的服务线路上,那么将由车辆k服务;约束(4)表示客户点i仅被服务一次;约束(5)表示从配送中心出发的线路有K条;约束(6)保证了不存在未从配送中心出发的子环路;约束(7)保证每条配送线路的送货量不超过车载容量。2VRP问题的求解算法国内外有关VRP问题的求解方法,可以分为精确算法、启发式算法和亚启发式算法三类3。(1)精确算法:主要有分支定界法、割平面法、网络流算法、动态规划法、树法以及拉格朗日松弛算法,但由于VRP问题是公认的计算机难解问题4,随着问题规模的不断扩大,求解难度大大增加,因此,在实际中的应用不大。(2)启发式算法: 求解V
7、RP问题常采用启发式算法,保证以较小的时间与空间代价获得满意的可行解。启发式算法可以分为构造启发式算法和改进启发式算法两类,比较典型的有C-W节约算法、最邻近法、最近插入法、扫描算法、两阶段算法、k-opt算法、-interchange算法等。(3)亚启发式算法:为了避免启发式算法易陷入局部最优解的缺点,亚启发式算法在搜索过程中允许解的劣化甚至是不可行中间状态解的存在。目前,求解VRP问题的亚启发式算法有:模拟退火算法、禁忌搜索算法、遗传算法、蚁群算法与神经网络算法5。3GIS技术与VRP问题的结合理论上的VRP问题通常都是给定节点之间的距离,实际应用中,有时为了简便起见常采用节点间的直线距离
8、,因此,对指导实践还有一定的差距。将GIS技术与VRP问题进行结合后,就可以利用电子地图提供的信息,采用Dijstra算法计算任意两个节点间的最短距离作为实际线路距离,然后用于VRP问题的优化求解,再将模型得到的优化结果返回地理信息系统,直观的呈现出来。具体步骤如下:(1)数据的获取与处理。根据Map Info电子地图提供的道路图层和道路交汇点图层中提取点线信息,保存到文本文件route.txt中,从道路交汇点图层和客户点图层中提取点信息,保存到文本文件point.txt中。文件的格式如下:route.txt起点编号,终点编号point.txt点编号,点类型,经度,纬度在实际处理时,可以根据客
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 管理 论文 基于 Map Info 电子地图 配送 车辆 线路 优化 问题 研究
链接地址:https://www.31doc.com/p-3966515.html