论文部分内容阅读
车辆路径问题(Vehicle Routing Problem, VRP)具有大规模、不确定、多目标等复杂因素,对其相关调度算法的研究一直是学术界和工业界的热点课题。根据约束条件不同可将VRP划分成不同的调度问题,其中VRP问题的简单模型是旅行商问题TSP(Traveling Salesman Problem, TSP); VRP问题的普遍应用模型是带容量约束车辆路径问题CVRP (Capacitated Vehicle Routing Problem, CVRP); VRP问题目前研究最多的模型是带时间窗约束车辆路径问题VRPTW (Vehicle Routing Problem with Time Windows, VRPTW).已证明几乎所有VRP问题都具有NP-hard属性,智能算法是求解NP问题的有效方法。其中,遗传算法是一类强调基因层次进化的随机优化算法,通过个体的评价和遗传算子等操作,利用优质解信息指导算法搜索；蚁群算法是一类吸收蚂蚁觅食行为特征的随机优化算法,通过蚁群的反馈和协同机制,构造概率搜索方法,实现对求解目标的优化。量子进化算法是一种新型的群智能算法,通过量子门的量子比特旋转,指导算法实现个体进化。本文分别应用遗传算法求解TSP问题,量子进化算法求解CVRP问题,蚁群算法求解VRPTW问题。(1)针对TSP问题,第二章提出一种混合遗传算法HGA(Hybrid Genetic Algorithm, HGA)进行求解。本算法提出一种多元化选择策略,多样化的择优标准避免基本遗传的早熟现象；又设计一种新型的遗传算子操作方式引导算法进化,用于克服标准遗传算子操作的随机性,降低个体评价次数,从而有效提高算法搜索的效率。(2)针对CVRP问题,第三章提出一种有效混合量子进化算法EHQEA(Effective Hybrid Quantum Evolutionary Algorithm, EHQEA)进行求解。首先,设计了基于2维量子位观测模型和可见度的解生成方式,实现由该模型引导的全局搜索；然后,构造了一种基于客户间距离相近度的交换操作来提高解的质量；最后,提出了基于问题性质的交换(Interchange)和逆转(Inverse)操作来构造两阶段混合变邻域局部搜索,使得算法的全局和局部搜索能力得到平衡。(3)针对VRPTW问题,第四章提出一种有效混合量子蚁群算法(Effective HybridQuantum Ant Colony Algorithm, EHQACA)进行求解。首先,设计一种基于2维量子位观测模型、2维量子蚂蚁概率模型和VRPTW时间窗性质的观测规则,引导量子蚂蚁进行全局搜索；然后,改进了量子位模型的更新机制,根据个体评价值差异实现量子位观测模型的差分更新,提高量子位观测模型的精确性；最后,提出一种基于时间窗性质的最小代价的插入(Insert)和交换(Exchange)规则优化配送车辆数,同时设计了一种HOA方法优化车辆配送总里程,增强算法在多约束条件下的局部搜索能力。本文所提算法均采用国际标准问题进行测试,大量仿真实验和比较验证了所提混合智能优化算法的有效性和鲁棒性。