基于混合量子算法的动态车辆调度问题研究

发布时间：2018-05-17 13:14

本文选题：动态车辆调度问题 + 自适应量子旋转门　；参考：《昆明理工大学》2017年硕士论文

【摘要】：随着电子商务业的蓬勃发展,物流成为当今社会不可或缺的产业与利益源泉。但是当今社会物流配送系统的配送还没有达到利益最大化、时间最小化的目标。为了解决这一问题,物流配送系统中的车辆调度问题成为学术界的研究热点。虽然学术界对物流配送车辆调度问题的研究各不相同,但是其宗旨都是在更接近现实配送的模型基础上达到最大经济利益、最小成本、最小化时间、最高客户评价口碑。物流配送系统中的车辆调度问题属于NP难问题,常被使用的算法为传统启发式算法。但是启发式算法也存在着一定的局限,如收敛速度慢、易陷入局部最优、全局搜索能力差、精确度低等缺陷。且随着车辆调度数学模型的复杂化,传统的启发式算法更加难以得到理想的优化结果。本文主要针对不同类型的动态车辆调度问题,对混合量子算法进行设计改进,并分别采用所设计的算法进行仿真实验和对比实验来验证算法在解决特定问题时的有效性和优越性,主要工作如下:首先,提出动态车辆调度的数学模型。将量子计算与遗传算法相结合形成量子遗传算法。设计了根据适应度值转换的自适应量子旋转门,并加入了两元素局部搜索来来提高算法的局部搜索能力。有加入了变异操作来提高算法的搜索深度,最后通过仿真实验表明所提出算法与其他算法相比较的优越性,以及所加入的自适应量子旋转门、变异操作和两元素局部搜索的有效性。其次,在动态车辆调度模型的基础上加入了多配送中心。同时将蚁群算法与量子计算相结合形成量子蚁群算法,并用自适应量子旋转门代替常规的量子旋转门。在算法中加入局部搜索操作提高算法的局部搜索能力。最后通过实验表明所提出算法在求解特定问题时与其他算法相比较的优越性,以及所加入的自适应量子旋转门、两元素局部搜索的有效性。最后,在多车场动态车辆调度问题模型中加入多车型因素。同时因车辆调度问题的复杂化,在自适应量子蚁群算法中加入信息素矩阵变异操作来提高算法的搜索深度。最后通过实验表明所提出算法在求解特定问题时与其他算法相比较的优越性,以及所加入的信息素变异操作的有效性。本文通过对混合量子算法和动态车辆调度问题的研究,总结了混合量子算法的特点,为后续车辆调度问题的研究工作建立了基础。
[Abstract]:With the vigorous development of e-commerce, logistics has become an indispensable industry and benefit source. However, the distribution of logistics distribution system has not reached the goal of maximizing benefits and minimizing time. In order to solve this problem, vehicle scheduling problem in logistics distribution system has become a hot research topic in academia. Although the academic research on vehicle scheduling problem of logistics distribution is different, its purpose is to achieve the maximum economic benefit, minimum cost, minimum time and highest customer evaluation word of mouth on the basis of more realistic distribution model. The vehicle scheduling problem in logistics distribution system belongs to NP-hard problem, and the commonly used algorithm is traditional heuristic algorithm. However, heuristic algorithms also have some limitations, such as slow convergence rate, easy to fall into local optimum, poor global search ability, low accuracy and so on. With the complexity of vehicle scheduling mathematical model, the traditional heuristic algorithm is more difficult to obtain ideal optimization results. In this paper, the hybrid quantum algorithm is designed and improved for different types of dynamic vehicle scheduling problems. Simulation experiments and comparative experiments are carried out to verify the effectiveness and superiority of the algorithm in solving specific problems. The main work is as follows: firstly, the mathematical model of dynamic vehicle scheduling is proposed. Quantum genetic algorithm is formed by combining quantum computation with genetic algorithm. An adaptive quantum rotary gate based on fitness conversion is designed and two elements local search is added to improve the local search ability of the algorithm. The mutation operation is added to improve the search depth of the algorithm. Finally, the simulation results show that the proposed algorithm is superior to other algorithms, and the adaptive quantum rotary gate is added. Mutation operation and the effectiveness of local search for two elements. Secondly, multiple distribution centers are added on the basis of dynamic vehicle scheduling model. At the same time, the ant colony algorithm is combined with quantum computation to form a quantum ant colony algorithm, and the adaptive quantum rotary gate is used to replace the conventional quantum rotation gate. The local search operation is added to the algorithm to improve the local search ability of the algorithm. Finally, experiments show that the proposed algorithm is superior to other algorithms in solving specific problems, and that the adaptive quantum rotary gate and the local search of two elements are effective. Finally, multiple vehicle models are added to the dynamic vehicle scheduling problem model. At the same time due to the complexity of vehicle scheduling problem pheromone matrix mutation operation is added to the adaptive quantum ant colony algorithm to improve the search depth of the algorithm. Finally, experiments show that the proposed algorithm is superior to other algorithms in solving specific problems, and that the pheromone mutation operation is effective. Based on the study of hybrid quantum algorithm and dynamic vehicle scheduling problem, the characteristics of hybrid quantum algorithm are summarized in this paper, and the foundation for further research on vehicle scheduling problem is established.
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：U492.22

【参考文献】