动态规划启发式算法求解时变车辆调度问题

时变网络中车辆在任意两节点间的行驶时间不仅与节点间的距离有关,还与所处的时段有关.对时变车辆调度问题提出一种满足先入先出准则的跨时段处理方法,直接推导出跨时段对应的车辆行驶时间.在此基础上建立了数学模型,并构造动态规划启发式算法进行求解.该算法能够通过设置参数H平衡求解质量和运行时间.通过对10组随机产生的数据进行测试,结果表明动态规划启发式算法能够在很短时间内改进最近邻算法.当H=2时,求解质量改进11%,平均运算时间为1.34秒;当H=3时,在不到2秒的运算时间内求解质量改进17%.

基于极大代数的阻塞流水车间启发式动态规划调度算法

基于极大代数理论,引入任务排序函数与时间D子集,建立阻塞流水车间排序与调度代数模型,并提出启发式动态规划调度算法,实例计算表明算法十分有效.

基于双重启发式动态规划算法的列车运行调整研究

通过对列车行车组织特点及运行调整策略的研究,采用自适应动态规划体系中的双重启发式动态规划算法,建立了列车运行调整模型。双重启发式动态规划算法适合处理具有实时性、约束性、非线性、随机性等特点的列车运行调整复杂动态系统的优化控制问题,通过仿真验证,该算法求解速度快、精度高,对列车晚点的调整起到了良好的控制作用。为列车运行调整的深入研究提供了一定的参考价值。

舰艇防空反导自适应干扰HDP算法分析与仿真

为干扰来袭的多波次、多方向反舰导弹,提高舰艇防空反导能力,分析了自适应干扰HDP算法模型,并通过实例进行仿真。通过对结果进行分析,验证了启发式动态规划(HDP)算法在自适应电子干扰策略最优组合的生成过程中的时效性、预测精度以及适用性,为该算法的后续研究提供支持。

图博弈下具有未知动态的供应链系统变更设计

为了研究具有未知动态的供应链系统变更一致性问题,将供应链系统建模为多智能体系统,针对多智能体系统图博弈问题,提出一种自适应最优分布式算法,该算法基于数值迭代启发式动态规划,无需系统动力学知识即可求解耦合的Hamilton-Jacobi-Isaacs(HJI)方程。此外,使用神经网络来识别每个子链的未知动态,证明了所提对策的闭环系统稳定性。仿真结果表明,该方法可以保证供应链变更系统的稳定性与一致性。

船厂钢板堆场多时段作业计划优化

针对船舶制造中由于钢板出入库时间段的分散性而引起钢板堆场大量倒垛的问题，建立了以减少计划期内倒垛量为目标的多时段钢板堆场作业计划优化模型。模型考虑钢板入库、倒垛和出库作业过程，以及时间约束和空间约束。根据对钢板入库、倒垛和出库作业流程及堆放原则的研究，提出并实现一种由动态规划启发式算法和变邻域搜索算法组成的两阶段求解方法。最后以某船厂的实际数据为例，分别在不同钢板规模情况下与固定参数的遗传算法及人工决策对比，结果表明，新的方法运算时间短，在较大规模问题时可减少47％～75％的倒垛量。

考虑交通时变特性的城乡快递无人机配送优化研究

针对农村快递网点运营成本高、网点建设滞后导致的电商物流配送成本高的问题,提出了城乡客运班车+无人机的快递配送模式。在考虑了配送过程中路网交通时变特性的情况下,以无人机—车辆配送系统总成本最小为优化目标,建立了时变网络下带时间窗的无人机—车辆路径问题(TDVRPDTW)模型,并提出一个由基于最近邻思想的改进CW算法和动态规划启发式算法构成的两阶段启发式算法来求解TDVRPDTW。最后,通过算例求解验证构建模型的合理性和求解算法的有效性,为制定农村物流配送的城乡客运班车+无人机快递配送方案提供决策支持。

An extended discrete particle swarm optimization algorithm for the dynamic facility layout problem

We extended an improved version of the discrete particle swarm optimization (DPSO) algorithm proposed by Liao et al.(2007) to solve the dynamic facility layout problem (DFLP). A computational study was performed with the existing heuristic algorithms, including the dynamic programming (DP), genetic algorithm (GA), simulated annealing (SA), hybrid ant system (HAS), hybrid simulated annealing (SA-EG), hybrid genetic algorithms (NLGA and CONGA). The proposed DPSO algorithm, SA, HAS, GA, DP, SA-EG, NLGA, and CONGA obtained the best solutions for 33, 24, 20, 10, 12, 20, 5, and 2 of the 48 problems from (Balakrishnan and Cheng, 2000), respectively. These results show that the DPSO is very effective in dealing with the DFLP. The extended DPSO also has very good computational efficiency when the problem size increases.