开放式车辆调度问题的参数控制蚁群算法的研究

发布时间：2018-04-15 00:40

本文选题：开放式车辆路径问题 + 时间窗　；参考：《合肥工业大学》2017年硕士论文

【摘要】：互联网以及计算机技术的不断快速发展,带动了电子商务的不断发展。物流配送作为电子商务的重要支撑在社会生活中日益显示出极端的重要性。车辆调度问题是物流配送的基础和关键工作,如何安排合理的车辆调度方案使车辆总的行驶距离最短、花费时间最少、企业总的运输成本最低是物流配送的重要环节,具有重要的现实意义和经济意义。本文针对开放式车辆调度问题提出了一种基于参数控制的改进的蚁群算法。考虑到传统的物流配送体系已经无法满足当代社会物流配送的需求,本文在开放式车辆调度问题的基础上进一步扩展,考虑了客户对配送时间的要求以及多配送中心车辆跨区域协同运输的情况,研究了一种带软时间窗的多车场开放式车辆调度问题。蚁群算法作为一种群智能算法经常有学者将其应用到车辆调度问题的求解中。传统蚁群算法中参数通常采用固定的值,而算法的性能在很大程度上会受到其参数的影响,因此传统蚁群算法收敛速度较慢且易陷入局部最优。本文通过分析蚁群算法信息启发因子参数?、期望启发因子?以及信息素挥发系数?对算法性能的影响,进一步研究车辆调度模型中各参数对调度性能的影响,提出了参数动态自适应优化的车辆调度方法。首先在带软时间窗的单车场开放式车辆调度问题中验证了改进蚁群算法的有效性后,再将其应用在更加复杂的多车场车辆调度问题中。本文的创新性及研究成果主要包括以下几个方面:首先,在基本开放式车辆调度问题的基础上进一步研究了带软时间窗的多车场开放式车辆调度问题。针对该问题,通过设置一个虚拟车场,将多车场问题转化为多个单车场问题进行求解。其次,在蚁群算法前期利用细菌觅食算法与k-means算法相结合聚类技术对蚁群结果进行聚类,并根据聚类结果来自适应动态调整蚁群算法参数,使其快速收敛到最优解附近。最后,在算法后期为使算法快速收敛使其跳出局部最优,再利用混沌理论的遍历性来动态调整算法参数。算法最后,又利用2-opt算法对最优解进行优化。本文在车辆调度的模型构建和求解算法上进行有益的探索,对于发展新的车辆调度方法具有重要的理论意义,对于提升物流服务水平,降低物流成本,具有重要的实际意义。
[Abstract]:With the rapid development of internet and computer technology, the development of e-commerce has been promoted.As an important support of electronic commerce, logistics distribution has increasingly shown the extreme importance in social life.The vehicle scheduling problem is the foundation and key work of logistics distribution. How to arrange the reasonable vehicle scheduling scheme to make the vehicle travel distance is the shortest and the time is the least, and the lowest transportation cost of the enterprise is the important link of the logistics distribution.Has the important realistic significance and the economic significance.In this paper, an improved ant colony algorithm based on parameter control is proposed for open vehicle scheduling problem.Considering that the traditional logistics distribution system can no longer meet the needs of modern society, this paper expands on the open vehicle scheduling problem.Considering the customer's requirement of distribution time and the case of multi-distribution center vehicle transportation across different regions, an open vehicle scheduling problem with soft time window is studied in this paper.As a kind of intelligent algorithm, ant colony algorithm (ACA) is often applied to vehicle scheduling problems.In the traditional ant colony algorithm, the parameters are usually fixed, but the performance of the algorithm is greatly affected by its parameters, so the convergence speed of the traditional ant colony algorithm is slow and it is easy to fall into the local optimum.In this paper, by analyzing the ant colony algorithm information heuristic factor parameters, expected heuristic factor?And pheromone volatilization coefficient?The effect of parameters on the performance of vehicle scheduling model is studied, and a vehicle scheduling method based on dynamic adaptive optimization of parameters is proposed.The effectiveness of the improved ant colony algorithm is verified in the open vehicle scheduling problem with soft time windows, and then it is applied to the more complex multi-yard vehicle scheduling problem.The innovation and research results of this paper mainly include the following aspects: firstly, on the basis of the basic open vehicle scheduling problem, the open vehicle scheduling problem with soft time window is further studied.In order to solve the problem, a virtual depot is set up to solve the problem.Secondly, in the early stage of ant colony algorithm, we use the combination of bacterial foraging algorithm and k-means algorithm to cluster the ant colony results. According to the clustering results, we can adjust the parameters of ant colony algorithm dynamically to make it quickly converge to the optimal solution.Finally, in order to make the algorithm converge quickly and jump out of the local optimum, the ergodicity of chaos theory is used to dynamically adjust the parameters of the algorithm.Finally, 2-opt algorithm is used to optimize the optimal solution.This paper makes a beneficial exploration on the modeling and solving algorithm of vehicle scheduling, which has important theoretical significance for developing new vehicle scheduling methods, and is of great practical significance for improving logistics service level and reducing logistics cost.
【学位授予单位】：合肥工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18;U492.22

【相似文献】