基于遗传算法的车辆路径问题研究.doc

基于遗传算法的车辆路径问题研究
中文摘要:近些年,物流作为“第三利润源泉”受到国内各行业的极大重视并得到较大的发展。物流的目标就在于以最少的费用满足消费者的需求。配送作为物流中一种特殊的、综合的活动形式,在当今社会经济发展中发挥着越来越重要的作用。配送的核心为配送车辆的调度、货物配装及送货过程。进行配送系统优化,主要是配送车辆调度的优化。对配送车辆进行优化调度,有利于提高物流经济效益、实现物流科学化。本文主要对单车场非满载无时间窗的车辆路径问题和动态车辆路径问题进行了研究。论文首先对现有车辆优化调度问题归类分析。然后对车辆路径问题的传统求解算法的基本思想、性能、适用性进行了分析,在此基础上提出了采用扫描法和遗传算法相结合的启发式算法来求解物流配送车辆优化调度问题的思想。在对遗传算法中的选择操作、邻域结构操作进行改进的基础上,提出了一种求解车辆路径问题的自适应遗传算法。应用C语言编程进行实例计算,结果表明改进的遗传算法明显增强了群体演化的质量,提高了算法的收敛速度,得到了问题的满意解。与传统遗传算法相比,扫描法和改进遗传算法的结合,其优化能力、运行效率、可靠性均有一定的提高。最后论文在对动态行驶时间车辆路径问题进行建模的基础上,尝试采用扫描法和改进遗传算法相结合的方法对此类问题进行求解,在保证客户服务水平的要求下,取得了比较好的结果。
关键词:物流车辆路径问题; 扫描法; 遗传算法
Abstract:Recent years, logistics, taken as "the third profit resource", has been developing rapidly. The object of logistics is to satisfy the requirements of consumers with least cost. As an especial and integrated activity of logistics, physical distribution plays an important role in modern society. Vehicle Routing Problem (VRP) is the main part of the distribution system optimizing. It is benefits to make economic paper mainly studied a type of vehicle routing problem with single depot, non-full load and without time windows and a dynamic vehicle routing problem. The restrictions and math models of vehicle routing problem is analyzed. This paper pared and analyzed the basic ideas, capabilities and applicability of tradition method heuristics of VRP. Based on this, this paper put forward an improved ic algorithm for vehicle routing problem, through changing its select operation and neighborhood structure operation, an adaptive ic algorithm was presented for solving this problem. Computational results based on C language programming demonstrated that the adaptative algorithm improved the quality of the results and can solve the problem effectively. Exemplifications proved that this algorithm can enhance capability of optimization
, solving efficiency and reliability of running. Finally, a dynamic vehicle routing problem with random time window is modeled. Th