论文部分内容阅读
物流业已成为国际经济体系的重要组成部分,是推动经济全球化的重要服务业。但是物流费用居高不下,特别是运输费用占社会物流费用的比重达到一半以上,是影响物流成本的重要因素。车辆路径问题(Vehicle Routing Problem,VRP)主要研究物流配送环节车辆路线的优化,是物流配送优化中的关键一环。该问题是运筹学和组合优化领域著名的NP问题,随着问题规模的增加会产生指数爆炸,目前的求解方法主要是亚启发式算法。本文主要研究了一种新型的进化算法—量子进化算法(Quantum Evolutionary Algorithm,QEA)在车辆路径问题中的应用,具体求解以下四类问题:有能力约束车辆路径问题(CapacitatedVehicle Routing Problem,CVRP),开发式车辆路径问题(Open Vehicle Routing Problem,OVRP),动态网络车辆路径问题(Dynamic Networks Vehicle Routing Problem),动态需求车辆路径问题(Dynamic Demands Vehicle Routing Problem)。本文的主要成果如下:1.研究了有能力约束车辆路径问题的量子进化算法求解方法。提出0-1矩阵的编码方法,通过量子旋转门实现进化,引入灾变操作保证解的多样性;分析了算法复杂度;选用基准实例进行测试,并与其它算法进行了比较。实验结果表明量子进化算法是求解有能力约束车辆路径问题的有效算法。2.建立了开发式车辆路径问题的数学模型,研究了求解开发式车辆路径问题的量子进化算法。算法采用动态调整旋转角机制,混合了最邻近算法和2-Opt方法增强局部搜索能力;分析了算法复杂度;讨论了算法参数对于优化结果的影响。选用基准实例进行了测试。3.研究了量子进化算法求解动态网络车辆路径问题。建立了动态网络车辆路径问题的数学模型;构造了测试实例并进行了求解,并对量子进化算法的收敛性进行了证明。4.研究了量子进化算法求解动态需求车辆路径问题。建立了动态需求车辆路径问题的两阶段数学模型;第一阶段为预优化阶段,对于已知的需求信息,采用量子进化算法进行预优化;第二阶段为实时优化阶段,对于实时需求信息,采用遗传算法进行实时优化。构造测试实例并进行测试。