论文部分内容阅读
交通运输控制着国民经济发展的动脉,随着社会经济的高速发展,物流管理领域受到企业与学者越来越多的关注,并从早期传统的运输服务逐步发展成为以信息技术和管理技术为核心的综合物流体系。车辆路径问题(Vehicle Routing Problem,VRP )作为运筹学和组合优化领域的热点问题,如企业铁路的智能调度,物流公司的车辆调度,城市公交车的路线制定,铁路及航空日程的安排,校车的路线制定等。这些问题与现实生活息息相关,因此,研究车辆路径问题有很重要的现实意义。目前,车辆路径问题有一定的研究成果,主要集中在:多配送中心问题的研究侧重为寻求整个行车路程最短或费用最少方面;同时取送货问题、带时间窗问题的研究大多是单一性问题方面。而对于最小最大的车辆路径问题研究文献的报导较少见,需要开创性探讨;带时间窗同时取送货车辆路径问题、开放式车辆路径问题等此类VRP的研究也缺乏有效的算法来进行求解,亟待进一步拓展。近年来,蚁群算法(Ant Colony Algorithm, ACA)凭借着其极强的鲁棒性在很多研究领域被广泛应用。本文采用改进的蚁群优化算法实现对各类车辆路径问题进行求解,通过实验仿真并对比相关算法分析,本文提出的算法有较好的优化性能和应用效果。本论文的主要研究工作如下:(1)为求解最小最大车辆路径问题,提出一种动态自适应蚁群优化算法(Dynamic Max Min Ant System-Min Max Vehicle Routing Problem, DMMAS-MMVRP),算法采用动态最大最小蚂蚁系统策略对最优解进行调整,每次迭代更新τmin,将τmin作为当前信息素矩阵最大值的函数,根据当前最优弧来调整选择弧的概率;采用一种灰色模型来预测及控制信息素矩阵的边界,以增强蚁群算法参数的自适应性能;并对信息素浓度相对较高的多个节点及其附近的边,利用信息素关联累积规则进行信息素更新。将DMMAS-MMVRP算法进行3种场景的实例测试,仿真结果表明,该算法与线性规划(Linear Program,LP)算法、其他相关的蚁群算法相比,优化性能和应用效果较好。(2)为求解开放式车辆路径问题,提出一种基于随机配载的混合蚁群优化算法(Hybrid Ant Colony Optimization,HACO)。首先采用一种随机配载车辆的方法生成初始解集,利用蚁群优化算法得到最优解,然后对其进行编码作为粒子群算法的第0个粒子,选择初始适应值将其设置为个体历史最优解,再进行全局最优解的计算,对每个粒子的交换序V给出求解结果,将交换序操作于每个微粒的位置,并利用侧步爬山策略进行局部搜索,以得到个体历史最优解和全局最优解。对基准问题进行仿真,结果表明与其他相关启发式算法相比,本文算法可以快速、有效得到已知最优解或近似解。(3)为求解带时间窗车辆路径问题,针对传统蚂蚁遗传混合算法参数静态设置、冗余迭代以及收敛速度慢等缺点,提出一种动态混合蚁群优化算法(Dynamically Hybrid Ant Colony Optimization,DHACO)。首先借助最大最小蚁群系统(Max-Min Ant System,MMAS)得到初始解,利用蚁群优化算法求解带时间窗车辆路径问题的基本可行解;接着采用遗传算法交叉和变异操作对局部解和全局最优解进行二次优化,从而得到最优解;最后利用蚂蚁遗传混合算法融合策略,动态交叉调用两种算法,根据云关联规则自适应控制蚁群算法参数。该动态混合蚁群优化算法有效减小无效迭代次数,加快了收敛速度。仿真结果分析表明,该算法与其他相关的启发式算法相比,优于某些实例的已知最优解。(4)为求解带时间窗的同时取送货车辆路径问题,针对传统蚂蚁与其他启发式算法混合所得算法的优缺点,提出一种改进混合蚁群优化算法(Improved Hybrid Ant Colony Optimization, IHACO)。首先将蚁群分成数目相同的若干蚂蚁子群,利用粒子群来优化ACO算法的参数,并对每个蚂蚁子群进行信息素交换操作;其次利用一种基于插入的启发式方法来构造带时间窗的同时取送货车辆路径问题的弱可行解,再利用类似的方法将弱可行解转化为强可行解;局部搜索采用变邻域下降搜索、交叉、反转,有助于在当前的邻域中搜索更好的解。该改进混合蚁群优化算法与其他相关的启发式算法相比,大大加快收敛速度。(5)为了验证求解车辆路径问题所提出的蚁群优化算法的可行性与有效性,结合企业铁路运输的实际状况,将算法应用到企业铁路智能调度计划系统中。本文以企业铁路取送货作业为研究对象,将蚁群优化算法应用于解决现实中的车辆调度问题。首先分析了车辆调度问题中车辆作业的特点,建立企业铁路取送车作业优化的数学模型,然后将改进的动态混合蚁群优化算法DHACO应用到马鞍山钢铁股份有限公司铁运公司企业铁路智能调度计划系统中,融合了蚁群算法和遗传算法各自的优势。最后以系统软件的形式反馈出最佳的作业调度,完成了对该类实际问题的解决。