求解车辆路径问题的一种遗传算法

车辆路径问题(VRP)是一个典型的NP-hard问题,采用传统方法求解往往找不到满意解。在分析现有求解该问题的遗传算法的基础上,对现有的交叉算子进行了改进,并设计了基于自然数编码的遗传算法,用来求解一般的和有时间窗限制的车辆路径问题。采用文献中的实例进行了数值试验,试验结果表明该算法是有效的。     

车辆路径问题的改进遗传算法

通过引入新颖交叉算子 ,构造了一种改进遗传算法 ,此算法摆脱了对群体多样性的要求 ,不存在传统遗传算法常见的“早熟收敛”问题 .将该算法用于解决车辆路径问题 ,实验结果表明 ,此算法可以有效求得车辆路径问题的优化解 ,是求解车辆路径问题的一个较好方案 .     

具有同时集送货需求的车辆路径问题的粗粒度并行遗传算法

设计了求解VRPSDP的粗粒度并行遗传算法(CGPGA),其中遗传算法以最优划分法计算适应值,邻域搜索法作为变异算子,定义了群体多样性结构.并行算法以单向环作为连接拓扑,各子群体独立进行遗传操作,迁移算子用于群体间的信息交流,采用多样性替换的方法进行个体替换.论文给出了CGPGA算法在集群系统上的重复非阻塞MPI实现.对典型VRPSDP实例进行测试的结果表明:CGPGA算法在大部分实例上超过了已知最好解,未达到已知最好解的实例与已知最好解的相对误差不超过1.5%.在计算速度方面,CGPGA算法具有接近线性甚至超线性的加速比,提高了遗传算法的求解速度.     

求解带软时间窗的车辆路径问题的改进遗传算法

带软时让窗的车辆路径问题(VRPSTW)是在基本的车辆路径问题(VRP)上增加了时间窗约束条件的一种更化形式，是一个典型的NP-难问题。通过引用一种新的编码方法、交叉和变异概率的自适应机制，构造一个改进的遗传算法来求解VRPSTW，并将求解结果与其他遗传算法比较。比较结果显示，该算法具有较好的性能。     

遗传算法在有时间窗车辆路径问题上的应用

本文用遗传算法求解有时间窗车辆路径问题,获得其近优解或最优解．传统的交叉算子如ＰＭＸ,ＥＲ和ＣＸ等对多约束问题的适用性受到限制,本文使用一种直观的编码方法,并提出基于优先关系的交叉算子．实验表明这种遗传算法能够有效地解决复杂的优化问题     

同时送取货的随机旅行时间车辆路径问题方法

建立了同时送取货的随机旅行时间车辆路径问题(STT-VRPSPD)的机会约束规划模型,构建了分散搜索算法求解策略.分散搜索算法中,针对STT-VRPSPD问题的复杂特性,构造了解的改进策略、组合策略,并采用改进的节约算法构造分散搜索算法初始解,从而使文中设计的分散搜索算法更加适应STT-VRPSPD问题特有的负载波动性.仿真实验中,首先对分散搜索算法的参数设置进行分析,确定了最优参数组合;然后基于经典的Dethloff算例数据,构造了STT-VRPSPD的测试算例,并对分散搜索算法和遗传算法进行了对比分析,结果表明,分散搜索算法对于STT-VRPSPD的求解质量优于遗传算法.     

车辆路径问题的遗传算法研究

在分析车辆路径问题的现有启发式算法的基础上,本文构造了车辆路径问题的染色体表达,并对染色体进了可行化影射,建立了此问题的遗传算法．实验结果表明,此算法可以有效求得车辆路径问题的优化解或近似优化解,是求解车辆路径问题的一个较好的方案     

带软时间窗物流配送车辆路径问题的并行遗传算法

针对一般遗传算法在求解有时间窗车辆路径问题时初始种群的单一性,提出一种新的算法.该算法对不同的种群用不同的初始化方法--随机初始化法和构造初始化法,这种算法改变了过去那种种群内部的平衡.并将该算法所得结果与其他算法进行比较,表明该算法的合理性.     

带有时间窗约束的车辆路径问题的一种改进遗传算法

有时间窗的车辆路径问题(VRPTW)是一个典型的NP-难题,传统求解方法往往不能令人满意。在分析现有求解该问题的遗传算法的基础上,设计了一种类似TSP问题染色体编码方式的遗传算法,为此引进了一种新颖的染色体解码算法,用来求解带有时间窗的车辆路径问题。通过使用相关文献中实例的数值试验对比,该结果优于那些文献中的结果。     

装卸一体化车辆路径问题的遗传算法研究

针对装卸混合的车辆路径问题这一类典型的NP难题,采用四位数的遗传编码,并对解的可行性进行验证,降低对交叉算子和变异算子的要求,有效提高解的质量.最后对二十个客户点的装卸混合的问题作了数值试验,结果表明遗传算法作为一种有效的随机型全局搜索算法,体现出群体智能的分布型、鲁棒性和快速性的特点.     

一类集散货物路线问题的禁忌搜索算法设计

针对该类同时集散货物路线问题(VRPSDP)的特点,文章将配送中心车辆的固定费用和可变费用之和作为目标函数.然后,提出了一种SFC-TS算法:先应用分形理论中的空间填充曲线法(SpacefillingCurves,SFC)求解初始解,再用禁忌搜索法(Tabu Search Algorithm,TS)对初始解进行改进优化.最后,应用算例验证了SFC-TS算法的有效性,结果表明SFC-TS算法在求解小规模问题(20个点)时其性能总体优于已有的同类问题的算法.     

不确定车辆数的有时间窗车辆路径问题的遗传算法

给出了不确定车辆数的有时间窗车辆路径问题(VRPTW)的数学模型,提出一种基于客户的编码表示方式,可以表示出不同的车辆数,实现VRPTW的路径长度和车辆数的同时优化,并用计算实例进行了验证,同时对计算中涉及的一些问题进行了讨论.     

客户需求可分的车辆路径问题求解

针对车辆路径问题中客户需求可分的新设想重新进行了问题描述和模型构造,根据该问题的特点,利用蚂蚁算法的基本原理,设计了相应的优化算法.虽然在客户需求不大的情况下,分割客户需求并未产生比较理想的效果,但随着客户点需求与车辆载重的比例逐渐增大.实例计算结果表明,需求可分所带来的车辆需求数量和总行驶里程的下降都比不可分情况下要好很多,从而证明了算法的有效性和分割客户需求策略的现实可行性.     

一体化集货和配送车辆路径问题的混合遗传启发式算法

为满足电子商务客户多样化和个性化的需求,建立多约束条件的一体化集货和配送车辆调度模型.针对模型特点,采用混合遗传启发式算法求解.首先,采用自然数编码,可以使问题变得更简洁;用最佳保留选择法,以保证群体的多样性;用改进的顺序交叉算子避免优良基因片断在顺序交叉时被破坏,保证算法能够收敛到全局最优;其次,对混合遗传算法求得的精英种群进行禁忌搜索求解.通过实例计算表明,该算法好于单独使用遗传算法或是禁忌搜索算法.