改进文化基因算法求解带午休时间的多级别家庭护理路径和调度问题

针对护理员的技能等级以及午休时间等约束,以总运营成本最小为目标建立模型,设计混合初始化策略以及自适应邻域搜索结构改进文化基因算法,并采用田口方法调整算法参数。算例测试结果验证了算法的有效性;对比随机的邻域搜索方式,结果证明自适应邻域搜索提升了算法的收敛性;Friedman及后续检验结果则表明该算法优于遗传算法和禁忌搜索算法。针对午休时长和多级别护理员结构的灵敏度分析则分别证明合适的午休时长对降低成本的作用以及多级别护理员的引入对问题的重要性。

考虑众包场景的电动车动态需求车辆路径问题

针对企业自有车辆和社会车辆共同取送货的场景,以及国家节能环保的政策背景,考虑分时电价、部分充电、软时间窗、以及动态需求等因素,以最小化配送总成本为目标,建立考虑众包场景的电动车动态需求车辆路径问题(EDDVRP-CD)的两阶段整数规划模型。考虑动态需求的时效性,设计了启发式算法——改进的禁忌自适应大规模邻域搜索算法(IALNS-TS),增加了新的删除算子和修复算子,同时提出了加速策略。分别与两种算法——自适应大规模邻域搜索算法(ALNS)以及禁忌搜索算法(TS)进行对比,通过大量算例验证了IALNS-TS算法能够快速响应动态需求,并有效降低总配送费用。

站点可变型需求响应式公交车辆调度优化研究

站点可变型需求响应式公交是一种既有固定服务站点又允许乘客在可变站点预约的公交运营模式.传统研究聚焦于单个车次的行程规划,而忽视车辆在整个运营周期执行多个车次的接续性.本研究从系统视角建立单个运营周期内车辆发车时刻表编制和车辆调度协同优化模型,以总成本最小化为目标,构建时空网络图,清晰表达站点可变型需求响应式公交的服务逻辑和复杂的时空约束.同时根据问题特征,整合8类邻域算子和改进的最大网络流算法,设计可快速求解现实大规模复杂问题的自适应变邻域搜索算法.以中国广州市黄埔区部分路网为例进行数值实验,结果表明,相比传统两阶段车辆调度模型,本模型车辆使用率提高8.7%以上,总成本下降20%~70%;相比传统算法,在绝大多数订单规模下自适应变邻域搜索算法求解质量更优,在预约订单规模为60时,可节省总成本30%以上.

考虑充换电的模块化需求响应公交路径优化

模块车能通过中途分离与合并来调整车队容量、实现无缝换乘,兼具规模化与“门到门”灵活性优势,但其轻量化的电池设计也在一定程度上限制了车辆续航能力。为了探索模块车在需求响应公交中的应用,并解决车辆中途充电问题,本文建立了模块化需求响应公交路径规划模型,优化车辆路径计划、车队编组策略、车内换乘策略以及换电和机会充电计划。针对模型特征设计了改进的自适应大邻域搜索算法,根据各车辆路径之间需要进行编组和协同交互的特点,定制化设计了车队类修复算子和能源类修复算子等。使用安徽宣城的出行数据进行实验,结果显示:与传统公交相比,模块化需求响应公交系统使乘客总出行用时降低48.81%;与车辆单独运行的方案相比,车队编组方案能够使系统总成本平均降低13.24%;相比仅充电策略,充换电结合策略能在少量增加备用电池固定成本的情况下,使能源成本减少21.09%;此外,企业可以通过调整等待时间惩罚系数来平衡企业经营成本与乘客时间成本,达到动态最优。

基于混合启发式算法的快递末端选址路径优化研究

传统快递末端配送模式存在快递网点建设冗余、派送路径重叠等问题,而共同配送模式可有效解决此类问题,因此对共同配送模式下同时收派件且收件需求为不确定情形的快递末端网点选址路径问题进行研究。首先,建立了两阶段数学优化模型,引入随机机会约束来处理收件量不确定的问题。其次,设计基于遗传算法和自适应大邻域搜索算法的混合启发式算法。最后,通过数值实验表明:所设计的混合算法比传统遗传算法具有较快的收敛速度和较好的求解质量;决策者对随机需求下的优化方案风险接受程度过高或过低都会导致成本上升;随客户收派量之比的增加,快递末端配送成本呈先降低后增高的趋势;采用最近网点返回策略可有效降低企业配送成本。

基于改进灰狼优化算法的柔性作业车间分批调度问题研究

针对以最小化最大完工时间为目标的柔性作业车间分批调度问题(Flexible Job shop Batch Scheduling Problem,FJBSP),提出了一种改进灰狼优化(Improved Grey Wolf Optimization,IGWO)算法,优化对象为工件的分批方案。首次将流体模型应用于FJBSP的求解,提出了一种基于流体模型的解码方法,用于获得更好的子批调度方案;然后改进了狼群的等级制度,避免了算法过早收敛;其次设计了一种全新的适应可变长编码的交叉方法,深入交流2个个体之间的分批信息,增强了算法的搜索能力和稳定性;再次,提出了能够动态更新个体游走率的自适应灰狼游走策略,兼顾了算法的搜索质量和收敛速度;此外,对领头狼使用自适应邻域搜索动态调整每种工件选择各邻域的概率,提高算法的局部搜索能力;最后,设计了9个算例和3组实验,验证了所提出的IGWO算法的有效性和优越性。

考虑优先级和需求可拆分的灾后应急血液多车舱调度

为保障非常规突发事件发生后安全救援顺利进行,提高应急血液调度效率,针对受灾点的灾情严重程度不同以及多类型血液制品的生理特性与应急保障特性,考虑受灾点优先级,构建多血库、多受灾点的二级路网,并采用多车舱的运输方式进行多类型血液制品调度。建立以应急血液调度的时效性和受灾点公平性为目标的多车舱应急血液调度模型,运用改进的自适应大邻域搜索算法进行求解,设计不同规模算例进行数据仿真实验,证明算法的有效性。最后,基于汶川地震构建实际案例,通过对比分析和敏感性分析验证所提出模型和算法的有效性,并提炼出相关管理启示。

基于GA-ALNS算法的带可容忍时间窗的VRP求解

针对带可容忍时间窗的车辆路径规划问题,建立最小化配送总成本的规划模型,结合遗传算法构造改进自适应大邻域搜索算法对该问题求解.利用遗传算法构建高质量解开始自适应大邻域搜索寻优,减小算法计算时间成本;加入3种破坏算子和3种修复算子,以增加种群多样性;嵌入模拟退火接受准则以一定概率接受较差解,自适应更新破坏和修复算子权重,避免算法陷入局部最优.选取Solomon标准测试集进行3组实验,与已知最优解比较距离成本验证算法可行性;在单边容忍度时间窗模型下,与基础ALNS算法对比验证算法改进效果;在双边可容忍时间窗模型下,与相关文献的最优结果对比.实验结果表明,提出的GA-ALNS算法改进效果较为显著,求得的最优解同其他算法相比优化率较好,计算得到的最优方案能实现更低的车辆配送总成本,具有一定的可行性和有效性.

考虑碳排放和时效性的多能源车辆冷链配送问题研究

随着冷链物流的快速发展,燃油冷藏车碳排放日益加剧,但电动冷藏车由于续航里程限制,导致冷链配送时效性差从而影响企业发展。为了在节能减排的同时降低冷链物流企业配送成本,通过构建基于多能源车辆及充电、换电模式选择的冷链路径优化模型,研究多能源车的冷链配送问题和电动冷藏车的充电、换电优化问题,并提出一种改进的自适应大邻域搜索(modified adaptive large neighborhood search, MALNS)算法,设计相关破坏、修复算子来进行有效求解。实验结果表明:该模型不仅可以减少碳排放,还可节约配送成本,实现企业可持续发展;MALNS算法可以更高效率地搜索最优成本。研究成果对冷链物流企业配送具有重要指导意义。

考虑众包物流的大型生鲜商超配送策略研究

针对冷链运输导致大型生鲜商超配送成本高的问题,本文提出了一种采用众包车和自备物流协同配送的模式。考虑企业调用社会车辆并结合自有冷链运输实施众包协同配送,将商品分为冷冻、冷藏、常温三类,构建了带容量和软时间窗限制的多车型车辆路径问题(HFCVRPSTW)模型。该模型涉及冷藏车行驶成本、固定成本、众包车补偿成本、冷藏商品包装成本和损失成本以及时间成本等多个参数。通过设计初始解、采用自循环的衰减破坏策略以及引入新算子的改进自适应大规模邻域搜索(ALNS)算法对模型求解。采用Solomon数据集的拓展算例验证了模型的合理性和算法的优越性。研究得到以下结论:(1)通过对不同类商品的数量比例以及众包车数量进行灵敏度分析发现,众包协同配送的总成本对物流货物中各类商品的配比不敏感,但众包车数量的增加会更有效地降低总成本;(2)对比不同客户分布的算例研究得出,客户点的分布对众包协同配送降低总成本的效果具有显著影响,当客户处于随机分布与混合分布状态时,企业应优先选择众包协同配送,当客户呈聚集分布且众包车数量较少时,企业应优先选择自营配送。

灾后应急救援背景下卡车-无人机协同配送路径规划

无人机因其具有不受道路条件和交通拥堵影响的特点而被应用于物流配送,因此针对灾后道路损毁严重,卡车无法及时配送救援物资的问题,提出利用“卡车-无人机”协同配送的模式进行救援物资的配送。文章对多辆卡车多架无人机灾后协同配送物资的路径规划问题进行了研究,考虑到受灾群众对救援物资的需求紧迫性,受灾群众满意度会随着救援物资送达时间的延长而降低,因此以最大化受灾群众满意度为目标建立了卡车-无人机协同物资配送模型,并使用了自适应大邻域搜索算法对模型进行求解。最后,通过卡车-无人机协同配送和卡车单独配送两种情况下的对比实验验证了无人机在灾后救援物资配送中的有效性。

考虑动态需求的多中心沿途补货冷链物流配送路径优化

为提升冷链物流配送效率、降低物流成本,本文在综合考虑多配送中心、客户动态需求、沿途补货策略的前提下,建立以总配送成本和客户满意度最优为目标的冷链物流配送模型.模型采用主目标法处理客户满意度和成本之间的背反关系,将动态问题按照时间轴依次分解为一系列的静态调度子问题并考虑了5种配送成本.本文提出自适应大邻域搜索算法求解该模型,设计了三种破坏算子和三种修复算子,对小中大三种不同规模的算例进行测算.结果表明该算法在速度、精度和稳定性上表现良好,对求解此类问题有较好的适应性和准确性.与不考虑沿途补货策略的动态配送方案相比,沿途补货策略可使成本降低23.06%、客户满意度提升8.69%.结果表明提出的配送方案可很好地节约企业的配送资源、减少配送成本、增强竞争力.

基于ALNS-TS算法的半灵活型需求响应公交调度问题

半灵活型需求响应公交模式往往拥有1个基准线路方向与1批确定访问的固定站点,服务车辆可以根据预约请求灵活响应候选的可变站点为其提供服务,当可变站点无请求时则不服务.基于低客流区域内需求响应公交服务所面临载客率低、运营成本高等问题,完善该模式的发车条件,设计差异化票价策略和未预约乘客服务判断的半灵活型需求响应公交服务系统,并建立车辆路径优化模型.为提高算法的搜索空间范围和局部搜索强度,设计了混合自适应大邻域禁忌搜索算法进行模型求解.以中国广州市黄埔区公交站点网络作为案例分析,结果表明,在新策略模式下,去除和未去除未预约乘客的半灵活型需求响应公交的票价收入较传统模式分别提高3.0%和15.5%,响应未预约乘客服务模式的服务人数可以提高7.5%;混合自适应大邻域搜索算法在求解速度和求解质量上均有较好表现,与混合模拟退火算法和遗传算法相比,计算时间分别节约76.9%和97.0%.

多策略改进的麻雀搜索算法

针对麻雀搜索算法在迭代收敛时易陷入局部最优的问题,提出多策略改进的麻雀搜索算法(NLSSA)。利用邻域重心反向学习策略优化麻雀算法的初始种群,提高初始个体质量。通过Levy飞行策略的长短距离跳跃更新麻雀生产者位置,从而提升麻雀算法的局部极值逃逸能力。在跟随者位置更新机制中引入自适应权重,从而平衡麻雀算法的局部挖掘和全局寻优能力。为了验证所提NLSSA算法的性能,利用8个基准测试函数进行测验,测试结果与Wilcoxon符号秩检验结果表明,与麻雀搜索算法、粒子群优化算法、灰狼优化算法和其他改进的麻雀搜索算法相比,NLSSA算法在寻优精度、稳定性能和收敛速度方面的效果更佳。

基于改进自适应大邻域算法的公交线网规划方法

面向城市中大规模线网规划问题,本文提出一种基于改进自适应大邻域算法的公交线网规划方法。该方法首先缩减问题规模,将大量乘客出行OD(Origin-Destination)合并获得城市公交备选站点;综合考虑线网服务客流量、公交站点覆盖率和线路服务效率等优化目标,线网长度、非直线系数、线路换乘等限制条件,分别建立以服务需求/延展换乘为主要功能的主线/支线公交线网规划模型;在OD合并结果基础上设计改进自适应大邻域算法进行问题求解,该方法含改进的8种邻域算子和自适应规则等。案例分析结果表明:本文两阶段算法整体优化效果明显,改进自适应大邻域算法领先现有其他元启发算法;邢台市实际案例计算结果表现良好,该方法能有效解决较大规模线网规划问题。

考虑员工满意度的多目标外卖订单配送路径优化研究

针对外卖订单配送问题,首先对员工满意度影响因素进行量化分析,并构建了以配送总成本、客户满意度、员工满意度为目标的外卖订单配送路径优化模型;其次提出适用于外卖订单配送的两阶段初始解构造法、基于“HV贡献值”的邻域解评价策略以及新的拆分和修复算子,对自适应大邻域搜索算法进行改进;最后以饿了么外卖平台的实际数据设计仿真实验,与原始自适应大邻域搜索算法求解结果进行对比,验证了模型在提升员工满意度上的实用性和改进算法对外卖订单配送的有效性。

轨道交通封站条件下应急疏散车辆路径优化

针对轨道交通封站条件下站外滞留乘客需要应急疏散的现实需求,设计了一种疏散服务模式,在保证滞留旅客有效疏散的前提下,允许线路沿途旅客搭乘以提高车辆的利用效率。以车辆运营成本和乘客时间成本之和最小为优化目标,建立应急疏散车辆路径优化模型,根据问题特点改进自适应大邻域搜索算法进行模型求解。最后,结合北京市城市交通数据,对应急疏散车辆进行路线设计并进行灵敏度分析,用算例验证了模型与算法的有效性。结果表明,相较于最短路径疏散方案,模型的优化结果节省了15.02%的乘客乘车时间,能够在保证乘客出行体验的前提下实现对站点滞留乘客的快速疏散,提升封站事件下轨道交通应急管理的精细化水平。

“卡车+无人机”模式下带时间窗的取送货车辆路径问题

无人机由于成本低、速度快、直线飞行等优势被越来越多地用于物流配送。考虑到无人机的载货量小、续航能力有限等因素,针对“卡车+无人机”模式下的带时间窗的取送货车辆路径问题进行优化,建立了以最小化运输成本为目标的混合整数规划模型。设计了自适应大邻域搜索算法对其求解。在该算法中,通过设计基于模型特点的多种高效的破坏算子和修复算子、引入模拟退火接受准则避免陷入局部最优解来提高算法性能。通过算例求解验证了模型和算法的有效性,分析了卡车与无人机联合配送模式对路径成本的影响,为“卡车+无人机”模式的路径规划提供决策依据。

基于ALNS-TS的大规模维修任务调度优化快速求解算法

大规模维修任务的调度优化在实际生产过程中具有广泛的应用,例如煤层气井维修任务调度优化、修井作业调度和压裂作业调度等。该问题规模庞大且求解困难,是实时调度优化的难点和挑战。合理的大规模维修任务调度对于保障油气田平稳生产和降低成本具有重要意义。为了有效解决这一难题,提出了基于ALNS-TS的优化求解算法,并通过不同规模的案例验证了算法的有效性。实验结果显示,对于代表性的10、50和100个维修任务的案例,求解时间分别为0.03、8.33和74.32 s,都能在分钟级时间内给出合理的调度方案。随着问题规模增加,基于ALNS-TS的算法比传统算法更高效,并能找到目标函数值更低的更优解。

考虑服务定价的选择性众包配送优化

提出众包服务定价与选择性众包配送方案联合优化方法.根据众包服务价格与众包供给量关系,构建众包供给-价格函数,进而构建出优化众包服务价格、客户分配方案以及配送路径的混合整数非线性规划模型,并采用大M法将其处理成混合整数线性规划模型.依据问题领域知识设计局部搜索规则,并结合节约算法、禁忌搜索算法和模拟退火算法设计出求解大规模案例的自适应大邻域搜索算法.自适应大邻域搜索算法的性能优于GUROBI、最早配送规则以及节约算法;选择性众包配送服务模式在降低配送成本上优于无众包配送服务模式和全众包配送模式;众包配送服务模式适用于众包供给价格敏感度高、客户服务时间窗紧的场景;适当增加中转点或者拓宽客户服务时间窗可以降低配送成本.