【作者】 陈梅；

【导师】 伏玉琛；

【作者基本信息】 苏州大学 ， 计算机应用技术， 2008， 硕士

【摘要】 随着市场经济的发展,物流对经济活动的影响日益明显。配送流程是物流活动中直接与消费者相连的环节,而车辆路径规划问题(VRP)又是物流配送中关键的一环。因此,对车辆路径规划问题进行研究,建立满足客户需求的车辆优化系统,是提升企业服务水平及资源利用率的重要课题。物流配送所涉及到的信息80%以上与空间地理信息有着直接的关系,对地理空间有很大的依赖性。而地理信息系统(GIS)技术作为获取、存储、分析和处理空间地理数据的工具,具有强大的空间数据管理和空间分析能力。于是本文将GIS技术应用到物流配送中来辅助解决路径规划问题。本文主要研究内容为:(1)研究了物流配送系统和GIS的发展过程及现状特征,指出两者相结合的可行性和必要性。(2)对现有国内外VRP解决方法进行研究和比较,得出了两阶段法虽在VRP求解上具有优越性、但其初始解却很少从空间角度考虑的结论。(3)利用空间聚类对需求点进行分簇以得到初始解,使得VRP问题变为K个旅行商问题(TSP);并根据VRP的特点,对所采用的K-means算法进行改进,同时通过实验验证了正确性。(4)在各分簇内引入蚁群算法来解决TSP问题,并通过仿真实验,研究分析了蚁群算法在求解TSP问题上各参数对结果的影响及其最佳设置。(5)通过对标准VRP问题进行实验与结果分析,验证了“加权K-means+蚁群”算法求解VRP问题的有效性、准确性及优越性。最后,在实验结果的基础上,提出切合实际系统集成方案,完成了一个原型系统,实现空间和属性数据库的统一存储管理、电子地图基本操作、最优路径查找功能。更多还原

【Abstract】 With the development of market economy, logistics influences to the economic activity obviously day by day. Distribution is the tach in the logistics activity with consumer connected link directly, logistics distribution for vehicle routing problem, is a pivotal tach of the logistics distribution optimization. Therefore, carrying on the vehicle routing problem and establishment a system that can meet the customer’s needs immediately, is an important topic to promote the service and the resources use rate.80 percent of logistics distribution information which depends on the geography space is related with the geography space information directly. While GIS , which support us to get, manage, operate, analyze and display the geographic space data, has the powerful capability of managing and analyzing geography data. So we apply GIS to the logistics system to optimize VRP. This paper’s main research works include:(1)To research the development and current character of logistics distribution system and GIS, and to point out the necessity and feasibility of the integration of logistics distribution system and GIS.(2)To study and compare the VRP current research work, and get the conclusion of 2-Phase Algorithm’s advantage , but the initial value is not considered by the spatial point.(3) The problem of customers classifying is solved by clustering algorithm, then the Vehicle Routing Problem is abstracted as TSP. Aiming at the trait of VRP, to accomplish improvement and implement to the K-means, and prove the veracity by experiment.(4)Then Ant Colony Algorithm was used to offer solution to TSP. By making stimulation experiment, this experiment also devoted to investigations of how to set parameters which affects the capability and results, when Ant Colony Algorithm is employed in dealing with TSP. And analyzing the experiment result proves the validity and correctness of the combination algorithm of improved K-means and Ant Colony Algorithm.(5)According to experiment, to prove the validity、veracity and superiority of the algorithm proposed by this paper to solve VRP.Finally, on the basis results of above experiment, this paper have proposed practical system integration solutions and then accomplished a prototype model. This research have realized the storage and management of spatial and attribute database, the basic operation function of electronic map and the shortest route searching function component module.更多还原