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

《管理论文基于ｍａｐ　ｉｎｆｏ电子地图的配送车辆线路优化问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于Ｍａｐ　Ｉｎｆｏ电子地图的配送车辆线路优化问题研究 基于Ｍａｐ　Ｉｎｆｏ电子地图的配送车辆线路优化问题研究是小柯论文网通过网络搜集，并由本站工作人员整理后发布的，基于Ｍａｐ　Ｉｎｆｏ电子地图的配送车辆线路优化问题研究是篇质量较高的学术论文，供本站访问者学习和学术交流参考之用，不可用于其他商业目的，基于Ｍａｐ　Ｉｎｆｏ电子地图的配送车辆线路优化问题研究的论文版权归原作者所有，因网络整理，有些文章作者不详，敬请谅解，如需转摘，请注明出处小柯论文网，如果此论文无法满足您的论文要求，您可以

2、申请本站帮您代写论文，以下是正文。 　　摘要：GIS技术与VRP问题的结合，不仅提供了一种新的查询选择方法，同时还能提供一种直观的解决方案。文章针对MapInfo电子地图的特点，给出了一种从电子地图中提取客户与道路信息应用到解决实际的配送车辆线路优化问题，并将求解后的线路直观地显示到电子地图中的方法。在实际应用中表明该方法是高效直观的。 　　关键词：VRP；Dijkstra算法；地理信息系统 　　中图分类号：U116.2文献标识码：A文章编号：1002-3100(2008)12-0023-0

3、3 　　 　　Abstract:ThecombinationofGISandVRPisnotonlyanewmethodtoinquiry,butalsooffersanintuitivesolution.BasedonthecharacteristicofMapInfoelectro-map,amethodtoextractcustomersandroutesinformationfromthemaptobeusedbytheVehicleRoutingProblemanddrawthefeas

4、iblepathonthemapisgiven.It’stestifiedthatthemethodisefficientandintuitiveinpractice. 　　Keywords:VehicleRoutingProblem;Dijkstraalgorithm;GIS 　　 　　0引言 　　 　　配送作为直接与消费者相联系的环节，在整个物流系统中起着举足轻重的作用。相关资料表明，在生产企业原材料物流中运输配送成本占整个物流成本的58%，在生产企业成品物流中达到73%，而在商业企业中该比例

5、为52%[1]，因此，有效降低配送成本对降低物流系统运行成本具有非常重要的意义。配送车辆线路优化问题（VRP,VehicleRoutingProblem）最早由Danzig和Ramser提出[2]，就是研究如何制定合理的配送线路，从而以最少的物流成本将货物快速而经济地送达客户手中。近年来，伴随着经济全球化与物流业的迅猛发展，该问题在实践中的应用逐渐受到重视。 　　地理信息系统GIS是用于采集、存储、管理、处理、检索、分析和表达地理空间数据的计算机系统，是一种分析和处理海量地理数据的通用技术。利用G

6、IS技术，可以对空间数据进行直观显示和分析。基于GIS的配送车辆线路优化系统是GIS应用的一个新领域，也是配送车辆线路优化问题向信息化发展的一个趋势。集成后的配送车辆线路优化系统不仅可以为企业提供一种新的查询选择方法，同时还能提供一种直观的解决方案，指导企业选择合理的线路。本文针对MapInfo电子地图的特点，给出了一种从电子地图中提取客户与道路信息应用到解决实际的配送车辆线路优化问题，并将求解后的线路直观地显示到电子地图中的方法。 　　 　　1VRP问题数学模型 　　 　　约束（1）表示客户点i

7、在某辆车的服务线路上；约束（2），（3）表示客户点i，j在车辆k的服务线路上，那么将由车辆k服务；约束（4）表示客户点i仅被服务一次；约束（5）表示从配送中心出发的线路有K条；约束（6）保证了不存在未从配送中心出发的子环路；约束（7）保证每条配送线路的送货量不超过车载容量。 　　 　　2VRP问题的求解算法 　　 　　国内外有关VRP问题的求解方法，可以分为精确算法、启发式算法和亚启发式算法三类[3]。 　　（1）精确算法：主要有分支定界法、割平面法、网络流算法、动态规划法、Ｋ－树法以及拉格朗日松

8、弛算法，但由于VRP问题是公认的计算机难解问题[4]，随着问题规模的不断扩大，求解难度大大增加，因此，在实际中的应用不大。 　　（2）启发式算法：求解VRP问题常采用启发式算法，保证以较小的时间与空间代价获得满意的可行解。启发式算法可以分为构造启发式算法和改进启发式算法两类，比较典型的有C-W节约算法、最邻近法、最近插入法、扫描算法、两阶段算法、k-opt算法、λ-interchange算法等。 　　（3）亚启发式算法：为了避免启发式算法易陷入局部最优解的缺点，亚启发式算法在搜索过