改进遗传算法在多目标带时间窗车辆路径问题中的研究与应用
发布时间：2018-08-10 20:25
【摘要】：随着现在电子商务的飞速发展,物流运输行业逐渐成为当今社会的热门行业,如何快速、高效、安全和便捷地运送货物已经成为现阶段各大企业关注的焦点。车辆路径问题是物流运输行业中十分重要的问题,自从被提出以来,就在运筹学与组合优化等多个领域受到了研究者的关注。本文研究的内容是多目标带时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW)。先对VRPTW问题采用多目标模型,同时最小化车辆数目和行驶距离这两个目标,通过改进的遗传算法求解该问题模型。该改进遗传算法首先采用随机法和前相插入法产生初始解,然后运用最佳个体选择和轮盘赌法对群体中的优良个体进行选择操作,改进交叉操作使个体的性能达到更优,改进变异操作促进种群的多样性。接着,再进行局部搜索操作,在邻域内搜寻到更好的解,结合改进非支配排序遗传算法(Non-dominated Sorting Genetic Algorithm,NSGA-II),将新的种群与上一代种群组合进行非支配排序,寻找Pareto最优解集。最后,本文改进的遗传算法通过VC++6.0进行编程,在Solomon Benchmark测试集上进行了实验,并将其中一部分测试集的结果与其他文献的结果进行了比较,实验结果表明了改进遗传算法具有较好的性能。
[Abstract]:With the rapid development of electronic commerce, logistics transportation industry has gradually become a hot industry. How to transport goods quickly, efficiently, safely and conveniently has become the focus of attention of large enterprises at this stage. Vehicle routing problem (VRP) is an important problem in logistics and transportation industry. Since it was proposed, it has attracted the attention of researchers in many fields, such as operational research and combinatorial optimization. This paper focuses on the vehicle routing problem with time windows (Vehicle Routing Problem with Time Windows Windows VRPTW). First, the multi-objective model is adopted to solve the VRPTW problem, and the two objectives of minimizing the number of vehicles and the driving distance are minimized, and the improved genetic algorithm is used to solve the model. The improved genetic algorithm first uses random method and antecedent insertion method to produce initial solution, then uses the best individual selection and roulette method to select the superior individual in the population, and improves the crossover operation to make the individual's performance better. Improved mutation operation promotes population diversity. Then, a local search operation is carried out, and a better solution is found in the neighborhood. Combined with the improved Non-dominated Sorting Genetic algorithm (NSGA-II), the new population is combined with the previous generation population to search for the optimal solution set of Pareto. Finally, the improved genetic algorithm is programmed by VC 6.0, and the experiment is carried out on the Solomon Benchmark test set, and the results of some of the test sets are compared with the results of other documents. Experimental results show that the improved genetic algorithm has better performance.
【学位授予单位】：广东财经大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：U116
本文编号：2176101
[Abstract]:With the rapid development of electronic commerce, logistics transportation industry has gradually become a hot industry. How to transport goods quickly, efficiently, safely and conveniently has become the focus of attention of large enterprises at this stage. Vehicle routing problem (VRP) is an important problem in logistics and transportation industry. Since it was proposed, it has attracted the attention of researchers in many fields, such as operational research and combinatorial optimization. This paper focuses on the vehicle routing problem with time windows (Vehicle Routing Problem with Time Windows Windows VRPTW). First, the multi-objective model is adopted to solve the VRPTW problem, and the two objectives of minimizing the number of vehicles and the driving distance are minimized, and the improved genetic algorithm is used to solve the model. The improved genetic algorithm first uses random method and antecedent insertion method to produce initial solution, then uses the best individual selection and roulette method to select the superior individual in the population, and improves the crossover operation to make the individual's performance better. Improved mutation operation promotes population diversity. Then, a local search operation is carried out, and a better solution is found in the neighborhood. Combined with the improved Non-dominated Sorting Genetic algorithm (NSGA-II), the new population is combined with the previous generation population to search for the optimal solution set of Pareto. Finally, the improved genetic algorithm is programmed by VC 6.0, and the experiment is carried out on the Solomon Benchmark test set, and the results of some of the test sets are compared with the results of other documents. Experimental results show that the improved genetic algorithm has better performance.
【学位授予单位】：广东财经大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：U116
【参考文献】
相关期刊论文 前5条
1 章琦;庞小红;吴智铭;;约束法蚁群算法在多目标VRP中的研究[J];计算机仿真;2007年03期
2 吴雷;魏臻;葛方振;;基于Memetic算法的带时间窗车辆路径问题研究[J];计算机应用研究;2012年01期
3 王君;;带时间窗车辆路径问题的多目标文化基因算法[J];计算机工程与科学;2013年01期
4 曹二保;赖明勇;聂凯;;带时间窗的车辆路径问题的改进差分进化算法研究[J];系统仿真学报;2009年08期
5 王征;张俊;王旭坪;;多车场带时间窗车辆路径问题的变邻域搜索算法[J];中国管理科学;2011年02期
，本文编号：2176101
本文链接：https://www.wllwen.com/guanlilunwen/wuliuguanlilunwen/2176101.html
