Rolling horizon scheduling algorithm for dynamic vehicle scheduling system

Dynamic exclusive pickup and delivery problem with time windows (DE-PDPTW), aspecial dynamic vehicle scheduling problem, is proposed. Its mathematical description is given andits static properties are analyzed, and then the problem is simplified asthe asymmetrical travelingsalesman problem with time windows. The rolling horizon scheduling algorithm (RHSA) to solve thisdynamic problem is proposed. By the rolling of time horizon, the RHSA can adapt to the problem'sdynamic change and reduce the computation time by dealing with only part of the customers in eachrolling time horizon. Then, its three factors, the current customer window, the scheduling of thecurrent customer window and the rolling strategy, are analyzed. The test results demonstrate theeffectiveness of the RHSA to solve the dynamic vehicle scheduling problem.

基于离散混合蛙跳算法的地震应急物资调度

建立震后应急物资调度数学模型。该模型根据各灾区的受灾情况评估其救援紧急程度,并设计一种需求拆分供应的运输机制,提高车辆的利用效率。为求解该模型,提出一种多源信息学习的离散混合蛙跳算法。所提算法引入多种信息源以扩展算法的搜索方向,降低种群的同化速度。同时,让子组最差个体学习种群中的有效信息,提高算法的收敛精度。实验结果表明,所提算法能够搜索到精度更优的调度方案,对问题规模具有良好的可扩展性。

一种针对无人机配送网络的能量自维持调度方案

近年来,快递行业需求快速增长,物流配送行业压力剧增。无人机(UAV, unmanned aerial vehicle)配送凭借其人力成本低、灵活方便等特性成为车辆配送的有益补充。然而,无人机配送受续航能力和负载能力等因素的制约,需要低成本且能量自维持的配送和充电调度方案来支持多无人机的协同配送。提出了两阶段的能量自维持的多无人机协同配送及充电调度方案。第一阶段在满足无人机能量和载重容量约束的前提下,最小化能完成区域内所有配送任务所需的无人机数量,并给出对应配送路线。提出了无人机配送调度算法(UDSA, UAV delivery scheduling algorithm),并从理论上证明了UDSA的近似度。第二阶段对具有不同到达时间的无人机进行充电调度,最小化所有无人机的最大充电完成时间。提出了一种具有近似度的无人机充电调度算法(UCSA, UAV charging scheduling algorithm)来求解该问题。仿真实验结果表明,与基准算法相比,UDSA最多可以减少44.17%的无人机数量;UCSA最多可以缩短18.87%的最大充电完成时间。

分支定价算法求解携带医疗资源的家庭医护人员调度问题

针对携带医疗资源的家庭医护人员调度优化问题,综合考虑医疗资源、弹性服务时间窗、医患技能等级匹配等特征,以最小化运营成本和弹性时间窗惩罚成本为目标构建数学模型。并根据Dantzig-Wolfe分解原理将模型重构为基于访问路径的主问题和若干带资源约束的最短路子问题模型。根据问题特征设计了分支定价算法来求解该问题。小规模算例结果表明医疗资源特性对医护人员路径调度有重要影响,而弹性时间窗可以有效降低总成本;多种算例的运算结果证明了分支定价算法求解的高效性。

基于文献计量和知识图谱的电动车辆路径问题研究综述

为揭示电动车辆路径问题领域的研究与发展现状,对CNKI和Web of Science数据库中电动车辆路径问题1994-2022年间的期刊文献进行知识挖掘与分析。基于文献计量学的量化分析与知识图谱的可视化,通过分析文献外部特征和共被引情况,梳理研究热点及热点演进趋势,归纳研究主题,总结出电动车辆路径问题的知识域包括研究主题和应用场景,其中,研究主题由变体研究、充电调度、求解方法三部分构成;对电动车辆路径问题在复杂实际问题、高效求解算法方面的未来发展进行展望,这将为电动车辆路径问题研究的深入化与国际化提供一定的推动作用。

一种具有模糊费用系数的VSP的修正C-W节约算法

将传统的确定性车辆调度问题扩展为具有模糊特征的模糊车辆调度问题.在对具有模糊费用系数的车辆调度问题进行简单描述的基础上,构建了模糊车辆调度的数学模型;通过Gaufmann Gupta模糊数排序方法与传统车辆调度问题的C W节约算法的有效结合,提出了解决该问题的一种改进C W节约算法.最后,给出了一个算例.

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

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

改进混合粒子群算法求解带时间窗的无人机与车辆协同路径调度问题

为提高物流配送效率,考虑时间窗、无人机换电以及无人机多点连续配送等因素,提出了一种带时间窗的车辆与无人机协同配送问题,并设计一种带局部搜索的混合粒子群算法进行求解。该算法以混合粒子群算法为核心,通过构建高效的编解码策略实现了问题解空间到算法搜索空间的转换。进一步,该算法融合单点插入策略、车辆更换策略、无人机更换策略组成局部搜索策略,以此提高算法寻优能力。实验结果表明:所提模型比纯车辆配送的模型效率更高,节省了31.51%的成本;所提算法优于四种对比算法,优化率最高达到82.08%。

求解VSPSTW问题的混合差分演化算法

在描述带软时间窗车辆调度问题数学模型基础上,提出将模拟退火算法与差分演化算法相结合的混合优化算法求解该问题。该算法利用了模拟退火算法具有的较强局部搜索能力和差分演化算法的强全局搜索能力,克服了差分演化算法的"早期收敛"问题。实验结果表明,该算法比单一的差分演化算法计算效率高,收敛速度快,计算结果也比较稳定,是解决车辆调度问题的有效方法。

考虑AGV运输和机器转速的作业车间绿色调度研究

在车间实际生产中,机器在加工状态和空载状态下都需要消耗能量,且机器在不同转速下的能耗也不同。此外,随着自动导引车(AGV)在车间的广泛应用,其能耗也不可忽略,因此对考虑AGV和机器转速的作业车间绿色调度问题进行研究具有重要意义。完工时间不仅被认为是表示车间生产效率的指标,而且在一定程度上意味着机器空载能耗的减少、机器利用率的提高。为此,对考虑AGV运输和机器转速的作业车间完工时间和能耗优化问题进行了研究。首先,对作业车间机器的能耗、AGV能耗进行了分析,探讨了AGV、工件和机器之间的工艺约束,建立了考虑AGV运输和机器转速的作业车间绿色调度模型;然后,采用两阶段优化的方式分别对完工时间和车间总能耗进行了优化,在第一阶段,机器以最高转速进行了加工,采用改进麻雀搜索算法对其最大完工时间进行了优化;在第二阶段,在保证第一阶段优化得到的完工时间最小值不变的前提下,提出了一种间隙档位调整策略,通过降低部分工序的机器转速来降低车间能源消耗,实现对车间总能耗的优化;最后,采用标准用例对算法进行了仿真实验。研究结果表明:在第一阶段采用改进麻雀搜索算法,提高了种群质量,加快了算法的收敛速度,算法具有较强的跳出局部最优能力;第二阶段在保证完工时间的基础上,采取间隙档位调整策略来降低能耗,通过10个用例测试表明能耗可减少1.13%~5.18%。该结果验证了考虑AGV和机器转速绿色调度模型的正确性以及改进麻雀算法的有效性。

考虑道路限制的建设场地内车辆调度问题研究

针对大型设备运输车辆进入建设场地后,在场内道路上的车辆调度和路径规划问题进行了研究。受场内道路宽度限制,车辆难以在同一道路上相向行驶;同时,由于不同车辆所运输的货物及运输任务的紧急程度不同,车辆的通行具有不同优先级。针对上述特性,利用时空网络技术构建整数规划模型,在考虑道路限制和不同车辆优先级情况下,对建设场地内的车辆进行调度和会车规避。模型的目标为最小化所有车辆在场内的总时间,包括行驶时间和会车等待时间;模型包含两类约束,即车辆流平衡约束和车辆会车避让约束。为快速有效地求解模型,设计基于时空网络的启发式算法得到各车辆的时空路径,为车辆的路径规划和会车避让提供指导。结合一个实际的大型风电场路网,构建多个算例,对模型和算法的有效性进行验证。结果表明,提出的算法能迅速对不同规模的问题进行求解;另外,算法可以在消除车辆时空冲突的同时,保证车辆在会车时不等待过长时间,最终的方案具有较高的车辆运输效率。

一种多车场多车型VSP问题的求解算法

论文考虑了一种具有模糊指派功能、车辆具有车型利用水平约束和容量约束、顾客有Hard时间窗的多车场车辆调度问题。同时设计出两阶段的求解算法,第一阶段考虑将各个客户需求点模糊指派给各个车场;第二阶段安排优化子路线时,增加了多车型、车型利用水平、硬时间窗的约束。最后,给出一个算例。

面向矩阵式制造车间AGV调度的改进模拟退火算法

随着客制化和大规模生产需求的不断增长,矩阵制造车间的重要性日益凸显。同时,多台自动导引车(AGV)的有效调度可提高矩阵制造车间的运行效率。以矩阵制造车间内的AGV运输过程为研究对象,提出一种改进的模拟退火(ISA)算法,旨在找到降低运输成本的最佳调度方案。ISA算法通过Metropolis准则来提高算法跳出局部最优解的能力;利用顺序交叉算子和前置交叉算子更新种群,以提高ISA算法寻找全局最优解的收敛速度和精度;提出一种种群重生机制,避免ISA算法陷入局部最优解。为了评估ISA算法的有效性,在某工厂100个真实实例的数据集上进行了仿真测试,并与FCFS算法、HFOA、IHS算法进行对比实验。实验结果表明,ISA算法更适合解决矩阵制造车间的AGV调度问题。

供应链系统下的成品卷烟物流调度研究规划

为降低成品卷烟物流调度成本,顺应全面贯彻新发展理念做好碳达峰碳中和工作改革对物流工作提出的更高要求,综合考虑实际运输调度中如时间窗、点位费、异构车辆配载等真实情况下的性能约束以及行驶速度、道路状况、实际载重等对配送车辆碳排放的影响,在确保服务和成本优势的前提下建立面向低碳的多起讫点物流调度模型。以物流调度总成本以及物流运输活动中碳排放量的最小值为目标构造目标函数,并将多目标函数问题转化为单目标函数问题建立了相应的物流调度规划数学模型。最后,基于某烟草企业的成品物流业务历史数据,通过食肉植物智能优化算法进行仿真实验求解,得到的车辆路径规划方案可以有效地减少企业物流成本以及物流活动中的碳排放量,推动烟草物流产业绿色化,塑造企业竞争新优势。

考虑病人时间窗偏好的周期性家庭医护人员调度优化问题

针对周期性家庭医护人员调度问题,研究了病人接受医疗服务的频次固定,但对不同接受服务的时间窗有不同偏好的情形。以最小化运营成本、最大化病人偏好满意度为目标建立了混合整数规划线性模型,设计了混合禁忌搜索算法进行求解。数值实验表明:医护人员的最大降级数越大,路径成本和目标函数值越小;病人对时间窗偏好的权重和医患匹配偏好权重越大,路径成本越大但目标函数值越小;混合禁忌搜索算法能有效求解各种规模的算例。

免疫算法在车辆调度问题中的应用

免疫算法是模仿生物体高度进化、复杂的免疫系统仿生的一种智能化启发式算法。本文根据车辆调度问题的具体情况,应用免疫算法解决车辆调度中路线安排问题,并提出了一种基于分组匹配的亲和力的计算方法。实验结果表明,免疫算法能有效地应用于车辆调度中路线安排问题。

基于遗传算法的不同约束条件车辆调度问题研究

研究了不同约束条件下,车辆调度问题的最短行车距离。分别针对带有里程约束限制、带有时间窗口限制、带有满载和非满载约束限制的约束条件,建立了不同的车辆调度模型。针对车辆调度模型设计了自然数编码的遗传算法,并改进了遗传算法中的交叉算法,尽可能地保留了最优基因的遗传性,加速了算法的收敛性。最后进行算例分析,结果表明了模型和算法的有效性。

基于改进遗传算法的有时间窗车辆调度问题研究

在分析带有时间窗车辆调度问题的基础上,建立了车辆调度问题的数学模型,并构造了不同时间窗的惩罚函数。设计了针对车辆调度问题基于自然数编码的遗传算法,并改进了传统的交叉运算,避免优秀基因在交叉操作中被破坏,提高了遗传算法的寻优能力。最后,结合算例进行了仿真计算,分析了载重体积约束和时间窗约束对车辆调度的影响,验证了算法的有效性。

基于免疫算法的带软时间窗车辆调度问题

在对带软时间窗车辆调度问题(VSPSTW)简要叙述的基础上建立了VSPSTW数学模型。针对VSPSTW问题,构造一种免疫算法来求解VSPSTW,并提出了一种新的抗体编码、改进的亲和力计算方法,将求解结果与遗传算法比较。结果表明:该算法对于求解VSPSTW问题具有较好的性能和更好的鲁棒性。

多需求点车辆调度模型及其群体智能混合求解

建立货运关系明细的多需求点车辆调度模型,模型求解过程是先由粒子群算法的粒子位置向量得到单车运送的货物,再由蚁群算法优化单车路径,根据优化目标筛选粒子,直到终止条件,实现所有货物对所有车辆的分配.实例求解结果表明混合求解得到的车辆总路径小于蚁群算法得到的结果.