基于文化基因算法的动态车辆路径问题研究

发布时间：2018-01-04 11:33

本文关键词：基于文化基因算法的动态车辆路径问题研究　出处：《河南大学》2015年硕士论文　论文类型：学位论文

【摘要】：随着现代物流的发展,物流配送问题逐步发展成为制约企业发展的瓶颈,优化物流配送中的车辆路径问题成为了研究的重点。现代物流是以满足客户的需求为目标,把生产、运输、销售等市场情况统一考虑的一种战略措施,其实质是企业策划者通过合理规划使人力、物力、财力在有效的时间内高效的利用。如何实现物流的系统化、现代化、合理化对于社会发展至关重要。车辆路径问题(Vehicle Routing Problem,VRP)在物流配送中扮演很重要的角色,一直是业界人士研究的热点问题,然而现代社会各行各业的发展,物品交换频繁,物类繁多复杂,路面狭窄、道路交通混乱、城市拥挤、车辆抛锚、交通事故等一系列的不可预料的问题,导致车辆行驶的时间过长,物品未能及时的送达客户,客户服务的满意度由此降低。本文将研究不确定环境下动态车辆路径问题,分析动态的车辆路径和静态的车辆路径之间的关系;以车辆行驶的时间最短和最大化客户满意度为目标函数,根据问题影响因素,建立数学模型;在设计的文化基因算法的基础上求解动态车辆路径问题,并介绍算法的主要方法及实现步骤。对不确定环境下动态车辆路径问题进行详细的分析,运用文化基因算法进行求解,文化基因算法是一种全局搜索和局部搜索的启发式搜索相结合的一种算法,本文采用遗传算法和禁忌搜索策略相结合求解此问题。本文运用文化基因算法来求解动态车辆路径优化问题,根据问题设计了文化基因算法的实现步骤,包括染色体编码方式、初始化、设置适应度函数、进化操作、局部搜索的具体步骤、算法终止条件等;进化操作中选择、交叉、变异操作进行全局搜索,运用禁忌搜索算法作为局部搜索策略,对局部搜索的具体步骤进行分析及介绍,遗传算法和禁忌搜索算法相结合求解动态车辆路径问题,得到了问题的最优解,有效处理新订单的增加和老订单的取消或修改等不确定事件,及时有效的改变车辆路调度方案。
[Abstract]:With the development of modern logistics, logistics distribution has gradually become a bottleneck restricting the development of enterprises. The optimization of vehicle routing in logistics distribution has become the focus of the research. Modern logistics is a strategic measure to meet the needs of customers and consider the market conditions such as production, transportation, sales and so on. Its essence is how to realize the systematization and modernization of logistics by the enterprise planner making efficient use of manpower, material resources and financial resources in an effective time through rational planning. Rationalization is very important for social development. Vehicle Routing problem (VRP) plays an important role in logistics distribution. It has always been a hot topic in the industry. However, with the development of various industries in modern society, the exchange of goods is frequent, the kinds of things are complicated, the road surface is narrow, the road traffic is chaotic, the city is crowded, the vehicles break down. A series of unexpected problems, such as traffic accidents, lead to the excessive travel time of vehicles and the failure of goods to reach customers in time. This paper will study the dynamic vehicle routing problem in uncertain environment and analyze the relationship between dynamic vehicle routing and static vehicle routing. Taking the shortest travel time and maximum customer satisfaction as objective function, the mathematical model is established according to the influencing factors of the problem. Based on the design of the cultural genetic algorithm, the dynamic vehicle routing problem is solved, and the main methods and implementation steps of the algorithm are introduced. The dynamic vehicle routing problem in uncertain environment is analyzed in detail. Cultural gene algorithm is used to solve the problem. Cultural gene algorithm is a combination of global search and local search heuristic search algorithm. In this paper, genetic algorithm and Tabu search strategy are used to solve this problem. In this paper, the cultural gene algorithm is used to solve the dynamic vehicle routing optimization problem, and the implementation steps of the cultural gene algorithm are designed according to the problem. Including chromosome coding, initialization, setting fitness function, evolutionary operation, local search specific steps, algorithm termination conditions, and so on; The selection, crossover and mutation operations in evolutionary operations are used for global search. Tabu search algorithm is used as a local search strategy to analyze and introduce the specific steps of local search. Genetic algorithm and Tabu search algorithm are combined to solve the dynamic vehicle routing problem, the optimal solution is obtained, and the uncertain events such as the increase of new orders and the cancellation or modification of old orders are effectively handled. Timely and effective change of vehicle routing plan.
【学位授予单位】：河南大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP18

【相似文献】