共享单车再平衡问题及其容差插入启发式算法

共享单车再平衡问题是一类NP-难问题,已有启发式求解算法随着问题规模扩大求解速度显著变慢。本文先讨论了该问题的线路可行变换性质,推导证明了插入构造可行解时,被插入位置允许插入客户点的容量区间。在此基础上,提出容差概念,设计了容差插入启发式算法,对该算法应用标准算例测试表明,算法速度快,参数设置简单;算法找到11个测试算例的当前最好解,其中1个为新的当前最好解;算法求解大容量问题的质量优于中、小容量问题。

复杂PDPTW问题的插入启发式算法

讨论了多车库、多货物类型且有最大工作时间约束的复杂有时间窗装卸货问题(PDPTW)，给出了解决此类问题的插入启发式算法、对复杂条件的特殊处理方法以及提高解的质量的处理技巧。算例表明此算法能快速有效地处理复杂PDPTW问题。

多车辆有时间窗约束的装卸货问题插入启发式算法

研究了多车辆有时间窗口约束的装卸货问题(m-PDPTw)的路径构造的常用算法--插入启发式算法.分析了插入算法中会影响解质量的因素,提出几个判据指导插入过程.在Solomon的VRPTW插入算法的基础上提出了改进的PDPTW插入算法.算例表明,改进的插入算法克服了简单插入算法的缺点,大大提高了解的质量.

电子侦察卫星动态调度问题的快速启发式算法

卫星电子侦察中针对动态突发事件重新制定侦察计划是侦察任务规划所要解决的基本问题.分析导致动态调度的扰动因素,把不同扰动下的动态调度问题归结为一类复杂约束下的任务插入问题.建立混合整数规划模型,提出快速启发式任务插入算法(含三个基本算法——直接插入任务算法、移位插入任务算法和替换插入任务算法);基于初始调度方案的优良特性,极大降低动态调度复杂性.仿真实验表明:该算法能有效解决电子侦察卫星动态调度问题.

可变线路式公交的两阶段车辆调度模型

针对可变线路式公交设计了一种可同时处理预约需求和实时需求的两阶段车辆调度模型.第1阶段模型以预约需求为服务对象,建立了以乘客出行成本和车辆运营成本最小为目标的路径优化模型,采用模拟退火算法对模型进行求解,获得车辆初始行驶路径方案.第2阶段模型以实时需求为服务目标,在原定行驶路径方案上利用启发式插入算法将4类乘客排入车辆行车计划中.基于实例的仿真试验验证了两阶段车辆调度模型的可行性,结果表明:通过提高乘客预约出行比例的方式可提升系统性能,本例中当乘客需求量达到25人/h、预约出行比例达到70%时,系统整体性能相较于纯动态需求条件下提升近10%.

基于混合果蝇优化算法的现场服务调度问题

员工技能熟练程度对现场服务调度问题(FSSP)的执行效率有极大影响,现有研究中未考虑员工技能因素。针对上述问题,首先以员工的旅行时间、服务时间和等待时间为优化目标,建立考虑员工技能熟练程度的FSSP模型;然后,提出混合果蝇优化算法(HFOA)对该模型进行优化求解,根据问题特征和算法特点,设计了基于矩阵的编码方法;定义了两类矩阵操作,提出了3种搜索算子,重构了果蝇优化算法(FOA)的嗅觉搜索和视觉搜索过程;为了提升算法性能,构造了基于最邻近插入启发式算法的初始化算子;最后,通过典型实例对算法进行了仿真实验,并与遗传算法(GA)、贪婪随机自适应搜索过程(GRASP)算法进行了比较。实验数据显示,与其他两种算法相比,HFOA在均值和最优值方面表现更优秀。结果表明改进初始化方法和搜索策略后,HFOA在优化的精度和稳定性上优于其他算法。