运输调度问题的遗传算法研究

运输调度问题(Vehicle Routing Problem,VRP)是近二十年来运筹学、应用数学、网络分析、图论、计算机应用及交通运输等学科研究的一个热点问题,也是组合优化中的NP完全难题。运输调度问题不但为离散优化领域中其他的各类算法提供了思想方法平台,而且还广泛地应用于运输、生产、国防、生物、计算机应用等领域。 本论文研究运输调度问题的遗传算法。首先是研究顾客需求确定情况下运输调度问题的遗传算法。根据遗传算法的内在特性,初始群体染色体产生的好坏对于其性能影响很大。在第二章研究多种车辆类型运输调度问题的遗传算法,该算法采用花瓣扫描法产生初始群体,采用一种新的交叉算子,实验表明能较快速地取得满意调度方案。第三章研究带时间窗的多种车辆类型的运输调度问题遗传算法,也能取得满意的运输调度方案。 在实际的运输调度过程中,很多情况下客户的需求是随机的。第四章重点对客户需求随机的运输调度问题进行分析,给出车辆类型相同、两种类型车辆和三种类型车辆时的派车定理,建立了相应问题的数学模型,提出了需求随机的运输调度问题的自适应遗传算法。 由于运输调度问题是组合优化中的NP完全难题,计算量大,构造高效的并行求解算法具有重要的意义。本文第五章提出了一种基于粗粒度模型主从式并行遗传算法。 最后,对本论文进行了总结,对下一步要进行的工作提出了自己的设想。