基于Memetic算法的多车型CARP问题优化研究
发布时间：2019-05-23 15:01
【摘要】：限量弧路由问题(Capacitated Arc Routing Problem,CARP)在现实生活中有着广泛的应用,对缓解能源危机,提高生产效率,创建节约型社会有着重大的意义。然而,许多实际问题是无法用基本CARP模型解决的,因此结合实际情况,增加约束条件形成的扩展CARP模型越来越受到人们的重视。目前有许多的扩展CARP模型被提出,如多中心CARP模型,多车型CARP模型(Heterogeneous Vehicle Capacitated Arc Routing Problem,HVCARP),多周期CARP模型,不确定CARP模型等等。基本限量弧路由问题模型的研究已经日渐成熟,但是扩展CARP模型相关的研究成果并不是很多。本论文就常见扩展CARP模型中的多车型CARP模型做了深入的研究。针对多车型CARP模型(HVCARP)提出了一种有效的Memetic算法MAEVSGR(Memetic Algorithm Exchanging Vehicles among Same Group Routes)。首先将多车型CARP模型(HVCARP)的路径费用分为可变费用和固定费用,通过车辆惩罚系数紧密联系车型和路径之间的关系,形成了特有的多车型CARP费用计算公式。针对多车型CARP的特点,本论文提出了一种针对车型的同档路径交换车辆算子,该算子根据路径负载以及车队情况,调整服务车型,以实现服务费用的最优化;然后以其为局部搜索算子,设计了用于求解多车型CARP的Memetic算法;然后,以CARP标准测试集的修改算例进行实验验证,大量的实验结果表明了本文所提基于同档路径交换车辆算子Memetic算法的有效性。针对不确定CARP模型,本论文先描述了基本不确定CARP模型的定义方法。然后介绍了几种常见的不确定评价标准。最后结合多车型CARP模型提出了不确定多车型CARP模型。
[Abstract]:The limited-arc routing problem (CARP) has a wide application in real life. It is of great significance to alleviate the energy crisis, improve the production efficiency and create an economical society. However, many practical problems can not be solved by the basic CARP model, so the extended CARP model, which is formed by adding the constraint conditions, is more and more important to people. There are many extended CARP models, such as the multi-center CARP model, the multi-model CARP model, the multi-cycle CARP model, the CARP model and so on. The research on the basic limit arc routing problem model is becoming more and more mature, but the research results related to the extension of the CARP model are not much. This paper makes an in-depth study of the multi-model CARP model in the common extended CARP model. A valid Memetic algorithm MAEVSGR is proposed for the multi-model CARP model (HVCARP). First, the route cost of the multi-model CARP model (HVCARP) is divided into the variable cost and the fixed cost, and the relationship between the vehicle model and the route is closely connected through the vehicle penalty coefficient, and the specific multi-model CARP cost calculation formula is formed. In view of the characteristics of the multi-model CARP, this paper presents a vehicle operator with the same gear path for the model, which is based on the path load and the vehicle fleet, and the service model is adjusted so as to realize the optimization of the service cost; and then it is a local search operator. In this paper, a Memetic algorithm for solving the multi-model CARP is designed, and the experimental verification is carried out with the modified example of the CARP standard test set. In order not to determine the CARP model, the definition method of the CARP model is described in this paper. Several common uncertain evaluation criteria are then presented. Finally, a multi-model CARP model is proposed in combination with the multi-model CARP model.
【学位授予单位】：安庆师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：U491
本文编号：2484002
[Abstract]:The limited-arc routing problem (CARP) has a wide application in real life. It is of great significance to alleviate the energy crisis, improve the production efficiency and create an economical society. However, many practical problems can not be solved by the basic CARP model, so the extended CARP model, which is formed by adding the constraint conditions, is more and more important to people. There are many extended CARP models, such as the multi-center CARP model, the multi-model CARP model, the multi-cycle CARP model, the CARP model and so on. The research on the basic limit arc routing problem model is becoming more and more mature, but the research results related to the extension of the CARP model are not much. This paper makes an in-depth study of the multi-model CARP model in the common extended CARP model. A valid Memetic algorithm MAEVSGR is proposed for the multi-model CARP model (HVCARP). First, the route cost of the multi-model CARP model (HVCARP) is divided into the variable cost and the fixed cost, and the relationship between the vehicle model and the route is closely connected through the vehicle penalty coefficient, and the specific multi-model CARP cost calculation formula is formed. In view of the characteristics of the multi-model CARP, this paper presents a vehicle operator with the same gear path for the model, which is based on the path load and the vehicle fleet, and the service model is adjusted so as to realize the optimization of the service cost; and then it is a local search operator. In this paper, a Memetic algorithm for solving the multi-model CARP is designed, and the experimental verification is carried out with the modified example of the CARP standard test set. In order not to determine the CARP model, the definition method of the CARP model is described in this paper. Several common uncertain evaluation criteria are then presented. Finally, a multi-model CARP model is proposed in combination with the multi-model CARP model.
【学位授予单位】：安庆师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：U491
【参考文献】
相关期刊论文 前10条
1 刘天堂;江志斌;耿娜;刘冉;刘树军;;带有异质固定车队的能力约束弧路径问题[J];上海交通大学学报;2012年11期
2 金倩倩;林丹;;求解UCARPP问题的变邻域搜索算法[J];计算机工程;2012年21期
3 段渊;向毅;;不同遗传算子组合求解TSP问题的比较研究[J];科技通报;2012年05期
4 胡珊;林丹;;求解CARP-RP-ML问题的改进算法[J];计算机工程;2012年07期
5 徐凯;朱征宇;;改进遗传算法对带服务时间约束的弧路径问题的求解[J];微处理机;2010年05期
6 金毅;;对“中国邮递员问题”的数理分析[J];科技经济市场;2009年03期
7 朱征宇;杨永;邓欣;谢志华;夏梦霜;李小花;;一种求解多车型CARP问题的高效进化算法[J];计算机工程与应用;2008年08期
8 孙海雷;刘琼荪;胡上尉;;TSP问题的顺序插入交叉算子[J];计算机工程与应用;2007年08期
9 李念祖;;关于中国邮递员问题的最优完全子图算法[J];上海师范大学学报(自然科学版);2006年04期
10 魏平,李利杰,熊伟清;求解TSP问题的一种混合遗传算法[J];计算机工程与应用;2005年12期
相关博士学位论文 前1条
1 梅一;基于元启发式方法对限量弧路由问题的求解[D];中国科学技术大学;2010年
，本文编号：2484002
本文链接：https://www.wllwen.com/kejilunwen/daoluqiaoliang/2484002.html
