管理论文基于Ｍａｐ　Ｉｎｆｏ电子地图的配送车辆线路优化问题研究

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点编号，点类型，经度，纬度在实际处理时，可以根据客

9、户点和道路交叉点将道路分段，每段路都看作直线；而对于弧度特别大的路段，可以通过在路段拐点处添加虚拟点的方法来减小弧度数，从而看作直线处理；然后将分段后的道路信息存储到route.txt文件；由于客户点都会和某段道路的端点相重合，所以把道路交汇点、配送点和虚拟点信息保存在同一个文件point.txt中，这样便于创建邻接矩阵，实现客户点间最短路径的搜索，其中点类型将区分出客户点与其他的点类型。（2）求解客户点间最短路径。由于route.txt实际上保存的是一个相邻点矩阵，可以很轻易的转化成一个不含权重的邻接矩阵；根据邻接矩阵提供的信息，从point.txt文件中获取相邻点的经纬度，从而算出各个相邻

10、点之间的球面距离，作为邻接矩阵的权重，这样就获得了dijkstra算法所需要的邻接矩阵，然后可以根据dijkstra算法求解客户点间最短路径。（3）vrp问题的求解。根据生成的客户点邻接矩阵，并读入各客户点的需求量数据，根据建立的vrp问题数学模型和选择的求解算法，求解出配送车辆线路。（4）线路的显示。运算后生成的配送线路，保存到数据库文件中，利用map info从数据库中读取配送线路，生成新的线路图层，添加到地图上，就可以直观的看到生成的配送线路。对于实际的配送车辆线路优化问题，由于规模过大，可以采用“先聚类后排程”的两阶段算法，只对聚在一起的客户点求解最短路径，这样可以极大降低求解所需要的

11、时间。4结论本文针对map info电子地图的特点，给出了一种从电子地图中提取客户与道路信息应用到解决实际的配送车辆线路优化问题，并将求解后的线路直观地显示到电子地图中的方法。在实际应用中表明，对于一个中等大小城市的日用品配送线路优化问题，vrp问题使用“先聚类后排程”的两阶段算法，整个过程大约耗时1个小时的时间，求解非常高效与直观。参考文献：1 张勇. 物流配送路径优化算法研究d. 北京：北京交通大学，20052 dantzig g. b, ramser j. h the truck dispatching problemj. management science, 1959,6(1):80

12、-91.3 孙丽君，胡祥培，王征. 车辆路径规划问题及其求解方法研究进展j 系统工程，2006,11:31-37.4lenstra, j. k., and rinnooy kan, a. h. g complexity of vehicle routing and scheduling problemsj. networks, 1981,11:221-227.5michel g, gilbert l, potvin j.y. meta-heuristics for the vehicle routing problemc/les cahiers du gerad g-89-04, ecole

13、des hautes etudes commerciales de montreal, 1999.6 李艳，刘志镜. gis中的最短路径算法j. 计算机科学，2006,33(10):325-327.7 胡志杰. 基于gis的配送路径规划方法研究d. 武汉：武汉理工大学，2005其他参考文献baker, sheridan. the practical stylist. 6th ed. new york: harper & row, 1985.flesch, rudolf. the art of plain talk. new york: harper & brothers, 1946.gower

14、s, ernest. the complete plain words. london: penguin books, 1987.snell-hornby, mary. translation studies: an integrated approach. amsterdam: john benjamins, 1987.hu, zhuanglin. 胡壮麟, 语言学教程 m. 北京: 北京大学出版社, 2006.jespersen, otto. the philosophy of grammar. london: routledge, 1951.leech, geoffrey, and ja

15、n svartvik. a communicative grammar of english. london: longman, 1974.li, qingxue, and peng jianwu. 李庆学、彭建武, 英汉翻译理论与技巧 m. 北京: 北京航空航天大学出版社, 2009.lian, shuneng. 连淑能, 英汉对比研究 m. 北京: 高等教育出版社, 1993.ma, huijuan, and miao ju. 马会娟、苗菊, 当代西方翻译理论选读 m. 北京: 外语教学与研究出版社, 2009.newmark, peter. approaches to translation. london: pergmon p, 1981.quirk, randolph, et al. a grammar of contemporary english. london: longman, 1973.wang, li. 王力, 中国语法理论 m. 济南: 山东教育出版社, 1984.xu, jianping. 许建平, 英汉互译