基于Memetic算法的动态需求车辆调度问题研究

发布时间：2020-06-14 05:27

【摘要】：随着科学技术的发展,物流的专业水平不断提高,客户对于服务质量和实效性的要求越来越高,越来越多的企业将物流作为提高市场竞争力与核心竞争水平的一个重要手段。随着时间的变化,车辆调度问题中会出现客户需求的变化,新客户的增加,原有客户的减少,原有客户需求的修改等多种动态事件。这就需要制定实时的调度方案,设计合适的算法,从而使系统目标更优。物流配送中的车辆调度问题属于典型的NP-hard问题,一般的精确算法求解动态车辆调度问题时难度较为复杂,当前,智能优化算法越来越受到各界学者的关注与青睐。Memetic算法是进化算法和某些局域搜索算法的灵活结合体。主要结构是由进化模块和局部搜索模块组成,这也是Memetic算法的核心组成部分。Memetic算法提出的是一种灵活的框架,可根据不同的问题模型,选择合适的搜索策略,从而构成不同的Memetic算法。由于它有很好的自适应能力、灵活性、高效性、可移植性等特点,近些年来得到了广泛的关注和发展,成功的应用于各个领域,并取得了很好的效果。鉴于此算法有很大的发展空间,所以论文采用此算法针对动态车辆调度问题的三个不同问题模型,进行了改进,并分别采用改进的算法进行仿真来验证算法的有效性。论文的工作内容主要包括以下几部分:首先,对于带容量约束的动态车辆调度问题(Capacitated Dynamic Vehicle Routing Problem,DVRP),构造了两阶段的数学模型。根据模型特点,设计了一种用于最小化运输总费用的Memetic算法。所采用Memetic算法的全局搜索为改进量子遗传算法,局部搜索为2-opt法和swap法。其次,对于多车型动态车辆调度问题(Heterogenous Fleet Dynamic Vehicle Rounting Problem,HFDVRP),将最小车辆数和最少运输费用作为优化目标,并将问题分为两个阶段来进行求解。针对其模型特点,设计了一种新的Memetic算法。该算法中全局搜索的第一个阶段采用改进分布估计算法,第二个阶段采用改进量子遗传算法。局部搜索采用客户节点重置和2-opt法。通过两个仿真实验来表明所提算法的有效性和优越性。最后,针对有客户需求和时间窗变化的动态需求车辆调度问题,采用了一种基于Memetic算法的干扰管理的扰动恢复策略,所选用Memetic算法在上一部分改进分布估计算法基础上,根据问题模型特点,将车辆的时间窗因素引入采样概率选择函数中,最后通过仿真实验来验证了算法的有效性。 【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：U492.22

【图文】：

昆明理工大学硕士学位论文 18 图 3.1 动态车辆调度问题求解流程图3.1.3 DVRP 数学模型将 DVRP 问题分为两个阶段进行求解，并针对不同的阶段建立相应的数学模型。在客户需求没有发生变化时，客户的需求以及位置均是已知的，这个阶段属于预优化阶段，建立的数学模型如下，首先给出决策变量10=ijkk i jx ，，车辆 从用户 到，其他（3-1）0=1iki ky ，用户 由车辆 配送，其他（3-2）（1）建立预优化阶段模型目标函数：1 0 0minK m mijk ijk i jZ x c （3-3）约束条件：1mi ikiq y Q k ， （3-4）11Kikiy i ， （3-5）

图 3.2 DVRP 求解策略流程图子遗传算法的基本思想的车辆调度问题来说，较为常用的算法是遗传算法应性强、鲁棒性强且易于其他算法混合等优点。但收敛速度慢等不足。所以常将遗传算法和其他一些求解动态车辆调度问题中，量子遗传算法近年来受此同时，由于问题本身的不确定性，为得到更好进。改进的量子遗传算法通过量子旋转角的大小进化方向。设计了一种量子旋转门更新机制，即根定量子旋转角的大小和方向。法

【参考文献】

相关期刊论文 前10条

1 沙林秀;贺昱曜;;一种新的自适应量子遗传算法[J];计算机工程;2013年09期

2 崔丽;王笑丛;;需求驱动下的城市配送车辆动态调度研究[J];计算机工程与应用;2015年02期

3 张景玲;王万良;赵燕伟;;基于沿途补货的多配送中心动态需求VRP建模及优化[J];计算机集成制造系统;2013年04期

4 王圣尧;王凌;方晨;许烨;;分布估计算法研究进展[J];控制与决策;2012年07期

5 王旭;葛显龙;代应;;基于两阶段求解算法的动态车辆调度问题研究[J];控制与决策;2012年02期

6 王万良;黄海鹏;赵燕伟;张景玲;;基于车辆共享的软时间窗动态需求车辆路径问题[J];计算机集成制造系统;2011年05期

7 葛显龙;王旭;代应;;基于混合量子遗传算法的随机需求车辆调度问题[J];系统工程;2011年03期

8 张景玲;赵燕伟;王海燕;介婧;王万良;;多车型动态需求车辆路径问题建模及优化[J];计算机集成制造系统;2010年03期

9 王旭坪;杨德礼;许传磊;;有顾客需求变动的车辆调度干扰管理研究[J];运筹与管理;2009年04期

10 王斌;尚新春;李海峰;;解决车辆路径问题的混合模拟退火算法[J];计算机工程与设计;2009年03期

相关博士学位论文 前2条

1 武燕;分布估计算法研究及在动态优化问题中的应用[D];西安电子科技大学;2009年

2 谢秉磊;随机车辆路径问题研究[D];西南交通大学;2003年

相关硕士学位论文 前7条

1 潘挺雷;基于改进蚁群算法的区域车辆配送路径优化方法研究[D];浙江理工大学;2016年

2 施玮;新型蚁群优化算法在带时间窗口的车辆路径问题中的应用[D];中国科学技术大学;2015年

3 曹高立;基于求解车辆路径问题的混合智能优化算法研究[D];昆明理工大学;2015年

4 李文;物流配送同时取送货低碳车辆调度模型及其QEA研究[D];浙江工业大学;2015年

5 张红豆;基于蚁群算法的物流系统配送车辆路径优化问题研究[D];昆明理工大学;2015年

6 许传磊;物流配送客户时间窗变动干扰管理研究[D];大连理工大学;2009年

7 刘英;应急状态下航班运行的干扰管理研究[D];武汉理工大学;2008年

本文编号：2712352