带有异质固定车队的能力约束弧路径问题

研究了带有异质固定车队的能力约束弧路径问题(CARP).为了在可接受时间里求得较理想的解,提出了基于Route-First,Cluster-Second思想的两阶段启发式算法,并使用局域搜索(LS)和加强的局域搜索(ELS)进行改善.基于标准CARP算例生成了HFFCARP测试数据,算法结果表明了LS和ELS的有效性,且ELS具有更好的效果.

加强的混合遗传算法求解能力约束弧路径问题

为了在可接受的时间里求解具有NP-hard性质的能力约束弧路径问题(CARP),提出了加强的混合遗传算法(EHGA).该算法是在遗传算法框架里嵌入加强的局域搜索算子来强化搜索,充分发挥了遗传算法的全局搜索能力和加强的局域搜索算子的局域搜索能力.同时,在进行种群替代时,二元锦标赛替代被提出,并使用了种群管理来保持种群的多样性.测试了标准CARP算例,并给出了算法效果比较.结果表明,加强的混合遗传算法胜出一般的Memetic算法,是有效的求解CARP的方法.

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

为高效求解带能力约束的车辆路径优化问题,提出一种带有回火操作的改进模拟退火算法。解析多约束条件下的路径优化特点,构建了结构简单且功能模块相对独立的模拟退火框架,以便相关约束及其算法的耦合嵌套。在此基础上,改变较优解在迭代过程中的接受规则,引入回火操作使全局搜索与局部搜索实现平衡;设计强制的随机邻域变换策略,以提高多约束条件下的新解生成质量。结合初始解生成方法,构建了整体算法。通过不同类型算例的对比实验表明,所提算法具有优越的求解性能,相应的求解框架与优化方法研究,能够为相关的多约束耦合求解提供参考。

利用带感知能力的粒子群算法求解约束优化问题

提出一种求解约束优化问题的改进粒子群优化算法。它利用可行性判断规则处理约束条件,更新个体最优解和全局最优解。通过为粒子赋予自适应感知能力,算法能较好地平衡全局和局部搜索,且有能力跳出局部极值,防止早熟。边界附近粒子的感知结果被用来修正其飞行速度以加强算法对约束边界的搜索。实验结果表明,新算法收敛速度快,寻优能力强,能很好地求解约束优化问题。

有能力约束回收车辆路径问题的食物链算法

介绍了有能力约束逆向物流回收车辆路径问题,设计了求解有能力约束逆向物流回收车辆路径问题的食物链算法;选取文献典型算例进行了仿真求解及比较分析,结果表明设计的食物链算法性能优于遗传算法、粒子群算法和量子进化算法。

时变路网无能力约束车辆路径优化

讨论了一类时变路网下的无能力约束车辆配送路径优化问题,建立了基于时变路网的以配送总耗时最短为优化目标的无能力约束车辆配送路径优化模型。提出了基于实时Dijkstra算法的模型求解方法。数值算例表明考虑路网时变特性得到的优化配送方案将更加符合配送实际。

多起始点进化算法在容量约束弧路径问题上的应用

容量约束弧路径问题(CARP)是一类NP难的组合优化问题,通常采用启发式算法求解,计算时间较长.本文在竞争模因算法基础上采用多点同时搜索,构造了多点进化算法(MSEA).算法由多个初始解开始,同时进行局部搜索与遗传进化,再将结果合并,得到最终的解.在29个基准数据集上的数值试验表明,该算法可行有效,并可以节省大量计算时间.

同时配送和回收需求的带容量约束弧路径问题

提出了一种同时配送和回收需求的带容量约束的弧路径问题(CARPSPD),建立了该问题的基于直观描述的数学模型,设计了求解该问题的构造启发式算法与变邻域搜索算法。前者利用基于路径扫描的构造方法产生弱可行解,再转换成强可行解;后者采用5种邻域结构混合进行局部搜索,并采用了一种分层的局部搜索策略,扩大了算法的搜索空间。两种算法在23个基准数据集上的求解结果表明,变邻域搜索算法在稳定性与解的质量等方面都优于构造启发式算法,能更有效地求解CARPSPD。

带有随机运输时间和成本的4PL路径优化问题

针对复杂多变环境带来的第四方物流(4PL)运输时间和成本的随机性,研究带有随机运输时间和成本的4PL路径优化问题.在总运输成本约束下,以总运输时间最小为目标,建立期望值模型(EVM)以及机会约束规划模型(CCPM).进而,为提高模型求解效率以及鲁棒性,将CCPM转化为等价确定性模型(EDM).根据4PL选择路径过程中需要同时选择第三方物流供应商的特点,设计蚁群算法和带有替换策略的改进蚁群算法对模型进行求解.算例分析验证改进算法的有效性,并表明EDM在保证解的鲁棒性的同时保证了较高的求解效率.

粒子群算法求解无能力约束生产批量计划问题

经典的粒子群优化算法是一个在连续的定义域内搜索数值函数极值的有效方法.目前,粒子群算法(particle swarm optimization,PSO)已经成为优化领域中的一个重要的优化工具,其应用在很多优化问题中都可以见到.虽然粒子群算法的应用范围已经十分广泛,但是关于应用其求解多级生产批量计划问题(multilevel lot-sizing problem,MLLS)的文章并不多见.文章提出结合遗传算法(genetic algorithm,GA)变异算子的混合粒子群优化算法(hybrid panicle swarmoptimization,HPSO)求解无能力约束装配结构 MLLS 问题.通过实验验证了算法的可行性和有效性.

基于路径模型的区域危险废物管理选址—路径问题优化

为了从宏观角度最优化配置规划期内系统的废物设施,并确定废物设施间危险废物和残渣的运输方案,以满足所有相关的运营和能力约束,借鉴网络流问题的路径模型,以运输和选址决策中的总费用和总风险最小为目标,引入路段风险承载能力约束,构建基于路径的大规模双目标混合整数线性规划模型。利用所构建模型的优势,开发增广ε-约束算法,获得近似的非支配前沿。对1个大规模切实算例的计算测试显示,与既有的路段模型相比,所提出的路径模型可在更短的时间内返回相同数量的非支配解,所开发的增广ε-约束算法在解的质量上明显优于既有的线性加权求和算法。

考虑个体客户满意度的多车程生鲜品配送路径优化

随着生鲜电商的兴起,生鲜品的道路运输量越来越大,其配送任务越来越复杂,提升客户满意度是生鲜品配送的重要目标组成。文章以一个具有配送自主权的生鲜品供应商为研究对象,以整个计划周期内生鲜品配送的车辆运输成本最小及客户满意度最大为双目标,且客户满意度从顾客的个体视角考虑,构建双目标多车程带时间窗及考虑订单打包时间的车辆路径优化模型。基于ε-约束方法,设计了两阶段变邻域搜索(VNS)和模拟退火(SA)相结合的元启发式算法,基于车辆构造初始路线,并针对性地提出了3点改进措施,包括通过数学性质推导下界、减少求解过程中不必要的搜索空间以及规避求解过程中被支配解的后优化处理。最后,以Solomon标准算例为基础构造算例对所设计的算法进行了计算实验,其求解结果表明:其设计的算法具有有效性,并通过敏感性分析得出相关管理启示。

随机的库存—路径问题的机会约束规划模型与算法

随机需求下的库存—路径问题是一类复杂的组合优化问题。本文讨论了VMI背景下的库存—路径联合优化问题,构建了问题的机会约束规划模型,并将随机模拟、人工神经网络和遗传算法结合在一起,设计了求解问题的混合智能算法。实验表明算法性能良好。

基于遗传算法的数值优化约束问题的研究

针对数值优化约束中出现的大规模、多峰多态函数,含离散变量等情况下的全局优化问题,采用常规的优化方法,收敛速度较慢,求得全局极值的概率较低.提出用遗传算法的数值优化约束问题解决,通过数值仿真实验结果表明,该算法性能优于现有其它算法,它不仅可以处理线性等式约束,而且还可以处理非线性等式约束,同时提高了收敛速度和解的精度,是高效稳健的智能算法,具有很高的全局寻优能力和很快的收敛速度,对求解复杂多峰多态函数的优化约束问题具有可行性和有效性.

求解约束优化问题的改进微粒群算法

微粒群算法在处理约束条件时最常采用的方法是约束保持法,但该方法易使粒子在搜索中停滞不前,为了改进传统约束保持法的缺点,将微粒群算法与信赖域算法相结合,从而保持了粒子的多样性并使最优解在可行域内。另外,采用与信赖域搜索技术相结合的随机惯性权重,改善了算法的全局寻优能力,提高了算法的收敛速度和计算精度。实验结果表明:与标准微粒群算法和一些其他优化算法相比,改进算法具有较强的寻优能力和寻优效率。

道路养护中的带随机时间变量的弧路径规划问题

研究高速路网日常维护中的养护车辆路径优化问题,考虑车辆养护服务时间和移动时间的不确定性,通过科学的规划手段和精确有效的决策方法,可以减少以前依赖人工决策导致的资源浪费。将问题定义为一个带随机时间变量的限容量弧路径规划问题,分别使用机会约束规划模型和带修正的随机规划模型进行描述。针对问题的随机性,提出自适应大规模邻域搜索算法,在优化过程中根据各个删除策略和插入策略对解的表现对其进行评分,根据轮盘赌原则自适应地选择删除策略和插入策略。与分支切割算法进行比较,解的差距只有1.45%~3.15%,但计算时间有显著提升,证明了自适应大规模邻域搜索算法的有效性,能够适用于中大规模问题。通过真实路网算例,显示了带修正的随机规划模型在特定情况下相对于机会约束规划模型的优越性。还对置信水平α和变异系数CV这2个重要变量进行了敏感性分析,显示了其对解的影响程度。

求解带容量约束车辆路径问题的多模态差分进化算法

针对带容量约束车辆路径问题(CVRP)中交通拥堵、资源供给、客户需求等不确定性因素的影响容易导致单一最优解不可行或非最优的问题,提出一种多模态差分进化(MDE)算法,以同时求解得到目标值相近的多个备选车辆路径方案。首先结合CVRP的特点,构建高效的解个体编解码策略,并基于修复机制提升解个体的质量;然后在差分进化(DE)算法框架下,基于多模态优化视角引入动态半径小生境生成方法,并采用杰卡德系数来度量解个体之间相似性,进而实现对于解个体之间距离的计算;最后,改进邻域搜索策略,采用精英存档和更新策略来得到多模态最优解集。基于典型数据集的仿真实验与分析结果表明,所提MDE算法寻优得到的平均最优解个数达到1.7434个,平均最优解与已知最优解的平均偏差为0.03%,而差分进化(DE)算法二者分别为0.8486和0.63%。可见,所提算法在求解CVRP上表现出较高的有效性和稳定性,能同时得到CVRP的多个近似最优解。

基于免疫拉马克的道路洒水车路径问题优化

高效节能地完成道路洒水作业对改善城市环境、节约资源有着非常重要的意义.将道路洒水车路径问题转化为带容量约束的弧路径优化问题,并建立相应的数学模型.根据问题的NP难特性,提出了一种拉马克免疫算法进行求解.算法有效利用了免疫算法全局优化和拉马克学习局部搜索的优势;设计了适合问题求解的锦标赛选择法、顺序交叉法、自适应变异等免疫算子,并设计了拉马克局部搜索策略,避免算法陷入局部最优.实验结果表明,所提算法能得到代价最小的洒水路径.

带双重量和软时间窗约束的路径优化混合遗传算法研究

针对有集送货双重需求、有软时间窗约束的集送货一体化的车辆路径优化问题,建立了统一量纲的数学模型。研究了求解客户行车费用最小的多约束、多目标问题的混合遗传算法Hybrid-Gen。通过采用节约算法的运行结果改进了初始种群的构建方式,控制了行驶路径数并满足客户的双重量需求;改进了选择算子,实现了对优秀个体和全局最优个体的保留;改进了交叉算子,实现了对完整子串的保留。案例验证了算法的可行性和有效性。在此基础上,进一步讨论了迭代次数对运算结果的影响,展示了增加优中选优大循环loop对算法稳定收敛的影响。研究表明所提出的混合遗传算法可以获得较好的优化结果。

堆垛约束下基于偏序的路径优化时间窗松弛方法

在求解车辆路径优化问题时,通常使用时间窗对任务之间的偏序关系进行建模,设计带时间窗约束的路径优化模型与算法,然而时间窗约束与偏序约束是不等价的.在集装箱码头堆垛作业背景下,针对时间窗约束的路径优化模型,提出将时间窗约束转化为偏序约束的松弛方法,并据此设计偏序约束的路径优化模型.在分支定界算法框架下,研究时间窗约束与偏序约束之间的关系,对两种模型的特征进行分析.采用Solomon数据集进行数值分析,验证两个模型在寻优能力与性能之间的差异.结果表明,偏序模型具有更好的优化性能,但是时间窗模型具有更好的计算时间性能,通过时间窗紧缩的特征分析发现基于时间窗分解设计偏序模型求解算法是新的研究方向.