求解车辆路径问题的免疫遗传算法

VRP问题是一类典型的NP问题.本文通过引入免疫算子,构造一种新的免疫遗传算法(IGA)求解VRP问题.此算法在保留基本遗传算法(SGA)随机全局搜索能力的基础上,借鉴生物免疫机制中抗体的多样性保持策略,改善了基本遗传算法的群体多样性.实验结果表明,免疫遗传算法可有效改善基本遗传算法的未成熟收敛和局部搜索能力差的缺点,具有很好的全局收敛能力,并能有效解决VRP问题.     

求解车辆路径问题的混合遗传算法

针对物流配送中具有容量限制的车辆路径问题,设计了一种结合2-OPT子路径优化的混合遗传算法.在该算法中,提出了一种新的双层染色体编码方案.该染色体编码方案能确保子路径为满足车辆容量约束的可行路径,并且该编码方案只需根据客户编号生成染色体,无需预先知道有容量限制的车辆路径问题所需的最小车辆数,更适于求解实际中的车辆路径优化问题.采用2-OPT算法作为遗传算法的变异算子以优化子路径,从而提高算法的收敛速度.基于典型基准测试实例的计算结果表明,该算法是求解有容量限制的车辆路径问题的有效方法.     

求解车辆路径问题的周期进化遗传算法

针对标准遗传算法易于“早熟”的问题,提出了用周期进化遗传算法求解车辆路径问题.该算法模拟了自然界演化过程中的“进化一退化”并存且周期性往复的特点,设计了包含插入算子和倒位算子的组合算子以确保算法强大的搜索能力.实例验证结果显示,周期进化遗传算法相比于现有的两类典型遗传算法更易于找到最优解,显示出较佳的全局搜索能力,是一种求解车辆路径问题的有效方法.     

车辆路径问题的智能建模方法研究

针对车辆路径问题的自动建模工作,以人类建模思维规律为依托,提出了基于结构差异的智能建模方法,实现了车辆路径问题的智能建模系统,解决了车辆路径问题动态性导致问题建模不能实现的瓶颈.通过该系统的实际应用,验证了建模方法的可行性与有效性.     

多车型动态需求车辆路径问题建模及优化

针对现代物流配送系统中客户需求动态变化、配送中心车型多样化以及车辆行驶路线开放式的特点,建立了多车型开放式动态需求车辆路径问题的两阶段数学规划模型。制定了相应的预优化路线调度和实时动态调度的两阶段求解策略,提出了混合2-OPT量子进化算法的求解方法,设计了一种将常用的整数编码转换为量子比特的编码方法,每一个染色体都代表一种行车路线方案,对于量子进化算法求得的行车路线方案,引入2-OPT优化方法,对线路内的子路径进行局部调整,进一步提高了算法的收敛速度。最后通过实例测试及与其他算法的比较,验证了该方法的有效性。     

车辆路径问题的双种群遗传算法求解方法

针对标准遗传算法在求解车辆路径问题中出现的早熟、收敛,易陷入局部极值点的问题,提出双种群遗传算法求解车辆路径问题的方法。在求解过程中,初始化两个种群,分别选择不同的交叉、变异概率,在一次迭代完成后,交换种群间的优秀个体所携带的遗传信息,以打破种群内的平衡态,跳出局部最优解。通过实验仿真,将双种群遗传算法与其他各种启发式算法进行比较,双种群遗传算法比标准遗传算法显著提高了全局收敛性能,是解决车辆路径问题的有效方法。     

中厚板考虑母板和板坯规格不确定性的下料问题建模及求解

针对中厚板面向订单的生产是先设计母板及板坯后实施的生产组织模式,研究综合考虑母板、板坯允许的多种断面与长度规格及其转换关系的母板板坯集成优化设计问题,将其归结为一种同时对母板、板坯断面及长度规格不确定性进行决策的下料问题。以最小化无订单余材和热轧切边等加工过程材料损失为目标,将板坯的断面与长度设计柔性转化为模型的约束条件,建立非线性混合整数规划模型;设计结合禁忌搜索与列生成技术的混合优化求解算法:禁忌搜索编码采用一对多的映射方式降低搜索空间维数,以进行板坯断面的优化选择;解码时对母板、板坯长度和下料方法进行设计,子问题为考虑长度柔性和材料加工损耗的母板设计问题,通过设计改进的列生成方法求解;针对问题特征设计了适用的邻域结构、禁忌对象等算法要素。基于某钢铁企业生产数据进行案例计算,结果表明了所提模型及求解方法的可行性和有效性。     

求解车辆路径问题的改进微粒群优化算法

微粒群优化算法是求解连续函数极值的一个有效方法。研究了用该算法求解车辆路径的问题。设计了求解车辆路径问题的一种新的实数编码方案,将车辆路径问题转化成准连续优化问题,并采用罚函数法处理约束条件。应用该微粒群优化算法求解了多个车辆路径问题的算例,并与遗传算法和双种群遗传算法进行了比较。计算结果表明,该算法可以更有效地求得车辆路径问题的优化解,是解决车辆路径问题的有效方法。     

随机动态装卸车辆路径问题的启发式求解策略及仿真研究

以同时最小化顾客期单等待时间和车辆期望等待时间为目标函数,建立了随机动态装卸车辆路径问题的数学模型,提出了求解该问题的两种启发式求解策略--最近邻策略和堆栈策略,推导出两种策略总期望等待时间的上界,并对两种策略在不同需求情形下的表现,以及目标函数与参数之间的关系进行了仿真.仿真结果表明,需求密集和需求稀少时最近邻策略优于堆栈策略,需求中等时堆栈策略优于最近邻策略;两种策略分别存在最优服务强度,且最近邻策略的最优服务强度大于堆栈策略的最优服务强度;堆栈策略存在最优堆栈长度,且最优堆栈长度同时受服务强度和顾客平均到达率的影响.     

基于Witness车辆路径问题的仿真建模与优化

简要介绍了车辆路径问题及仿真的知识,针对实际问题,利用Witness仿真软件,建立车辆路径问题的仿真模型,然后运行仿真模型,得到仿真输出结果,通过对模型结果的输出分析,寻找车辆路径问题的瓶颈因素,通过对瓶颈因素的解决,进行问题的优化,最后得到更优的可行解。     

基于并行模拟退火算法求解时间依赖型车辆路径问题

为提高传统串行模拟退火算法求解时间依赖型车辆路径问题的效率,提出一种并行模拟退火算法。该算法首先使用前向插入启发式算法生成初始解,在主从式并行模拟退火算法框架下使用4种邻域搜索法对初始解进行优化。采用Figliozzi测试数据库(包含56个测试问题,顾客数均设定为100)对算法性能进行测试,结果表明在不同时间依赖型行驶函数情形下,当使用6个线程时,并行模拟退火算法相对于传统串行模拟退火算法可以得到近似于5倍的加速比,且均能在较快时间内得到比Figliozzi算法更优的解。因此,并行模拟退火算法能有效地求解时间依赖型车辆路径问题,并且可以灵活地扩展解决其他车辆路径问题和组合优化问题。     

基于混合模拟退火算法求解电表配送车辆路径问题

为了使电能表集中配送业务中的车辆路径选择最优化,提出一种混合模拟退火算法。针对单相电能表集中检定后的配送需求,综合考虑各车型的固定成本、可变配送成本和配送里程,以总成本最小为目标,建立了具有固定车辆数的多车型车辆路径优化模型。基于多车型路径划分算法生成初始可行解,通过引入基于概率的多算子邻域搜索,采用禁忌搜索中的禁忌表对模拟退火算法进行改进,给出求解算法。以计量中心配送业务为实例,验证了模型的实用性和算法的有效性。     

求解带时间窗车辆路径问题的改进型烟花算法

针对带时间窗车辆路径问题,为寻求组合优化问题最优解,构建总运输成本最小数学模型。由于烟花算法搜索半径不能自适应调整,算法后期易陷入局部最优,故对爆炸算子进行改进,使最优烟花搜索半径自适应调整,增强后期局部搜索能力;同时利用分布式信息共享机制避免算法早熟并引入变异火花增强种群多样性。利用标准测试集进行验证后,结果表明该算法在求解带时间窗车辆路径问题时不仅具有可行性和有效性,并且收敛速度快、搜索质量高。     

求解多车场累积时间车辆路径问题的Memetic算法

在应急救援车辆路径优化问题中,为了及时救援,缩短所有受灾点的总等待时间,提出了多车辆车场累积时间车辆路径问题。它是多个车场通过多个运输车队,使所有受灾点等待时间总和最短的运输问题。针对该NP难问题提出了一种Memetic算法求解。先用改进的最优切割算法MDVRP-Split将受灾点分配至各车场,通过选择、交叉及局部搜索得到最优路径。标准算例的测试结果表明,提出的算法注重了求解质量与求解效率的平衡。     

求解卸装一体化的车辆路径问题的混合粒子群算法

提出了结合粒子群算法(PSO)和变邻域下降搜索(VND)的混合粒子群算法(PSO-VND),用以解决卸装一体化车辆路径问题(VRPSDP)。在此混合算法的前半部分,运用粒子群算法对解空间进行搜索,找到相对较优的一组解。在PSO过程中对于可行化和优化后的粒子添加速度分量,并依据相似度进行变异。在此算法的后半部分,运用变邻域下降搜索对得到的较优解再进行深度搜索,以得到理想的解。在变邻域下降搜索(VND)过程中使用3种不同的邻域结构:插入、交换和交叉,依次对解进行迭代优化。最终采用标准算例进行了仿真试验,验证了混合算法的可行性和有效性。     

求解卸装一体化的车辆路径问题的混合粒子群算法

提出了结合粒子群算法（PSO）和变邻域下降搜索（VND）的混合粒子群算法（PSO-VND）,用以解决卸装一体化车辆路径问题（VRPSDP）。在此混合算法的前半部分,运用粒子群算法对解空间进行搜索,找到相对较优的一组解。在PSO过程中对于可行化和优化后的粒子添加速度分量,并依据相似度进行变异。在此算法的后半部分,运用变邻域下降搜索对得到的较优解再进行深度搜索,以得到理想的解。在变邻域下降搜索（VND）过程中使用3种不同的邻域结构：插入、交换和交叉,依次对解进行迭代优化。最终采用标准算例进行了仿真试验,验证了混合算法的可行性和有效性。     

求解带能力约束车辆路径优化问题的改进模拟退火算法

为高效求解带能力约束的车辆路径优化问题,提出一种带有回火操作的改进模拟退火算法.解析多约束条件下的路径优化特点,构建了结构简单且功能模块相对独立的模拟退火框架,以便相关约束及其算法的耦合嵌套.在此基础上,改变较优解在迭代过程中的接受规则,引入回火操作使全局搜索与局部搜索实现平衡;设计强制的随机邻域变换策略,以提高多约束...     

超启发式遗传算法求解带软时间窗的车辆路径问题

针对车辆路径问题中传统软时间窗惩罚函数过于线性的问题,考虑客户容忍水平,提出一种折线型软时间窗,并构造出相应的惩罚函数。在此基础上,以运输配送总成本最小为目标,构造出一种带折线型软时间窗的车辆路径问题通用数学模型。同时,提出一种具有一定通用性的超启发式遗传算法,该算法以遗传算法作为上层搜索算法,以3种启发式算法——CW节约法、MJ插入法和Kilby插入法作为底层搜索规则,并通过预排序、局部搜索和全局优化来优化算法。最后,通过Solomon标准题库中的R101算例分析并验证了所提算法的可行性和有效性。     

适应性禁忌搜索算法求解带回程的时变速度车辆路径问题

为求解带回程的时变速度车辆路径问题,建立了问题的数学模型并提出适应性禁忌搜索算法求解。适应性禁忌搜索算法为两阶段的启发式方法,改进固定速度下的启发式方法用于生成时变速度下的初始解,然后运用适应性禁忌搜索算法进一步优化,包括邻域生成规则定义,采用Hash表存储搜索过程中的解,检测解的重复状态,定义逃离局部搜索区域规则。对改进的标准问题进行测试,同时与最近邻域搜索算法的结果作比较,结果表明算法是有效的。与固定速度情形相比较,时变速度模型得到的调度方案更加合理。     

求解多隔室车辆路径问题的改进粒子群优化算法

针对同时配送多种不能混装货物的多隔室车辆路径问题,建立了最小化车辆行驶成本的数学模型,并提出一种改进粒子群优化算法进行求解。该算法借鉴传统粒子群优化算法与模拟退火算法的思想,以粒子群算法为主框架,在粒子更新过程中引入模拟退火中的Metropolis准则,以一定概率接受劣解,使粒子在寻优过程中能够概率性地跳出局部最优。通过对经典车辆路径问题算例进行改编实验,并与已有文献、基本粒子群优化算法、基本人工蜂群算法分别进行对比分析表明,所提算法不但求解多隔室车辆路径问题有效,而且在求解质量上具有明显优势。