模糊需求与时间窗的车辆路径问题及混合遗传算法求解
发布时间：2022-02-13 06:14
针对带模糊需求与模糊时间窗的车辆路径问题,以总行驶距离、车辆使用数最小化,以及平均客户满意度最大化为目标,构建基于可信性测度理论的多目标模糊机会约束模型。为提高种群的多样性,改进了交叉算子,在引入局部优化算法及擂台法则的基础上,设计了适合求解多目标车辆路径问题的混合遗传算法。通过VRPTW标准算例实验,表明算法能够有效地求解带时间窗的车辆路径问题,以及模型的合理性,同时显示了决策者偏好值对决策目标的影响。研究成果可为求解带模糊需求与时间窗的车辆路径问题提供一种思路,也可为实际配送路径规划提供指导。
【文章来源】：系统管理学报. 2020,29(01)北大核心CSSCICSCD
【文章页数】：12 页
【部分图文】：
客户满意度函数图
本文研究的VRPFDFTW属于NP难题,此类问题的求解通常采用启发式算法。遗传算法(Genetic Algorithm,GA)是一种拥有自适应能力的随机化搜索算法。该算法通过模拟生物进化过程搜索最优解,不要求优化函数连续,具有良好的全局寻优能力,但存在过早收敛、后期收敛速度较慢等问题。局部搜索算法是一种简单的贪心搜索算法,该算法每次从当前解的邻域空间中搜索获得一个局部最优解,经过多个邻域变化,扩大搜索空间,有利于找到高质量的满意解。因此,本文结合遗传算法与局部搜索算法的优势,引入擂台法则(Arena’s Principle,AP)构造Pareto非支配集,解决多目标优化问题中各目标间的矛盾,设计混合遗传算法对建立的模型进行求解,如图2所示。擂台法则构造非支配解集的基本思路是,在每一轮比较时,首先,任意从当前种群中选出一个染色体解作为擂主(一般为当前种群中的第1个染色体);然后,将擂主与当前种群中的剩余染色体逐一比较判断,将被支配者(败者)淘汰出局,支配者(胜者)成为新擂主,并继续该轮比较;一轮比较后,最后的擂主个体即为非支配个体。以此类推进行下一轮比较,直到当前种群为空。
2.1 染色体编码与解码本文采用自然数编码方式构造染色体,用0表示配送中心,其他自然数表示客户点,染色体的编码如图3(a)所示,每条染色体表示客户的配送服务顺序。图3(b)所示为对应的解码后的个体,每个个体表示客户的配送服务车辆,表示车辆1从配送中心0开始,依次经过客户1、3、9、5返回配送中心0,车辆2从配送中心0开始,经过客户8、2、4、7、6返回配送中心0。
【参考文献】：
期刊论文
[1]基于模糊时间窗的多中心开放式车辆路径问题[J]. 杨翔,范厚明,张晓楠,李阳. 计算机集成制造系统. 2016(07)
[2]模糊需求车辆路径优化及实时调整[J]. 张晓楠,范厚明. 上海交通大学学报. 2016(01)
[3]求解带时间窗车辆路径问题的有效混合PBIL算法[J]. 孟祥虎,胡蓉,钱斌. 系统工程理论与实践. 2014(10)
[4]基于混合遗传算法的模糊需求车辆路径问题[J]. 吴天羿,许继恒. 解放军理工大学学报(自然科学版). 2014(05)
[5]基于混合NSGA-Ⅱ的有硬时间窗的多目标车辆路径问题[J]. 吴天羿,刘建永,许继恒,翁杰,昝良. 交通运输系统工程与信息. 2014(02)
[6]带硬时间窗的战场物资配送车辆路径优化[J]. 王连锋,宋建社,王正元,曹继平. 系统工程与电子技术. 2013(04)
[7]基于模糊时间窗的车辆调度问题研究[J]. 王旭坪,张凯,胡祥培. 管理工程学报. 2011(03)
[8]模糊环境下多出救点应急救援车辆路径与物资运输优化研究[J]. 汪传旭,邓先明. 系统管理学报. 2011(03)
[9]带模糊预约时间的车辆路径问题的多目标禁忌搜索算法[J]. 王君,李波. 计算机集成制造系统. 2011(04)
[10]高效求解Pareto最优前沿的多目标进化算法[J]. 童晶,赵明旺. 计算机仿真. 2009(06)
本文编号：3622759
【文章来源】：系统管理学报. 2020,29(01)北大核心CSSCICSCD
【文章页数】：12 页
【部分图文】：
客户满意度函数图
本文研究的VRPFDFTW属于NP难题,此类问题的求解通常采用启发式算法。遗传算法(Genetic Algorithm,GA)是一种拥有自适应能力的随机化搜索算法。该算法通过模拟生物进化过程搜索最优解,不要求优化函数连续,具有良好的全局寻优能力,但存在过早收敛、后期收敛速度较慢等问题。局部搜索算法是一种简单的贪心搜索算法,该算法每次从当前解的邻域空间中搜索获得一个局部最优解,经过多个邻域变化,扩大搜索空间,有利于找到高质量的满意解。因此,本文结合遗传算法与局部搜索算法的优势,引入擂台法则(Arena’s Principle,AP)构造Pareto非支配集,解决多目标优化问题中各目标间的矛盾,设计混合遗传算法对建立的模型进行求解,如图2所示。擂台法则构造非支配解集的基本思路是,在每一轮比较时,首先,任意从当前种群中选出一个染色体解作为擂主(一般为当前种群中的第1个染色体);然后,将擂主与当前种群中的剩余染色体逐一比较判断,将被支配者(败者)淘汰出局,支配者(胜者)成为新擂主,并继续该轮比较;一轮比较后,最后的擂主个体即为非支配个体。以此类推进行下一轮比较,直到当前种群为空。
2.1 染色体编码与解码本文采用自然数编码方式构造染色体,用0表示配送中心,其他自然数表示客户点,染色体的编码如图3(a)所示,每条染色体表示客户的配送服务顺序。图3(b)所示为对应的解码后的个体,每个个体表示客户的配送服务车辆,表示车辆1从配送中心0开始,依次经过客户1、3、9、5返回配送中心0,车辆2从配送中心0开始,经过客户8、2、4、7、6返回配送中心0。
【参考文献】：
期刊论文
[1]基于模糊时间窗的多中心开放式车辆路径问题[J]. 杨翔,范厚明,张晓楠,李阳. 计算机集成制造系统. 2016(07)
[2]模糊需求车辆路径优化及实时调整[J]. 张晓楠,范厚明. 上海交通大学学报. 2016(01)
[3]求解带时间窗车辆路径问题的有效混合PBIL算法[J]. 孟祥虎,胡蓉,钱斌. 系统工程理论与实践. 2014(10)
[4]基于混合遗传算法的模糊需求车辆路径问题[J]. 吴天羿,许继恒. 解放军理工大学学报(自然科学版). 2014(05)
[5]基于混合NSGA-Ⅱ的有硬时间窗的多目标车辆路径问题[J]. 吴天羿,刘建永,许继恒,翁杰,昝良. 交通运输系统工程与信息. 2014(02)
[6]带硬时间窗的战场物资配送车辆路径优化[J]. 王连锋,宋建社,王正元,曹继平. 系统工程与电子技术. 2013(04)
[7]基于模糊时间窗的车辆调度问题研究[J]. 王旭坪,张凯,胡祥培. 管理工程学报. 2011(03)
[8]模糊环境下多出救点应急救援车辆路径与物资运输优化研究[J]. 汪传旭,邓先明. 系统管理学报. 2011(03)
[9]带模糊预约时间的车辆路径问题的多目标禁忌搜索算法[J]. 王君,李波. 计算机集成制造系统. 2011(04)
[10]高效求解Pareto最优前沿的多目标进化算法[J]. 童晶,赵明旺. 计算机仿真. 2009(06)
本文编号：3622759
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3622759.html
