基于多邻域的车辆路径优化迭代局部搜索算法

针对物流配送中的带有容量约束的车辆路径优化问题,提出了一个基于多邻域的迭代局部搜索算法HILS.首先用简单插入法构造可行解,然后从该初始解出发,在多邻域内进行局部优化.当陷入局部最优解后,根据解的接受准则,选择某个解,并对该解进行扰动,然后从扰动后的解出发重新进行局部优化.为提高搜索效率,局部优化过程只在限定邻域内进行.在国际通用的14个benchmark问题上进行仿真实验,结果验证了本文算法HILS的有效性和稳定性,与文献中的其他几种算法的比较结果表明,算法HILS的总体性能更优.     

求解作业车间批量流问题的变邻域搜索算法

对具有等子批和空闲约束的作业车间批量流问题进行了研究,提出一种有效变邻域搜索（VNS）算法以最小化延迟和提前惩罚总和,该算法利用双串表示法描述问题的解.为了适应问题的特点,几个初始解独立进化以改善VNS的探索能力,对批调度采用一个变邻域结构,而对批量流条件则根据一个较小的概率进行调整.将VNS应用于一些实例,计算结果验证了VNS的优异性能.     

一种基于极坐标的快速邻域搜索算法

一般邻域搜索方法面临着邻域定义的难点：定义的邻域较小，搜索就可能很快陷入局部最优，相反，则搜索效率会显著下降．针对这一问题，提出了一种基于极坐标的快速邻域搜索算法．试验证明，该算法能有效地解决邻域定义问题，并能在一定程度上解决常用的优化方法还较难解决的非凸集问题，对于一般复杂度问题，有较小的时间和空间复杂度。     

技术站配流与调机运用综合问题的混合整数线性规划模型

为进一步提高铁路技术站作业计划编制效果,针对采用一台调车机车解体和一台调车机车编组的技术站配流与调机运用的综合问题,作者确定了出发列车的编组内容和解体（编组）调车机车的解体（编组）任务,使得出发列车满足列车编组要求,且车辆在站总停留时间最小。基于单机器调度理论和资源分配理论,在将原问题分解为解体子问题、配流子问题和编组子问题的基础上,首次建立原问题的混合整数线性规划模型。最后,采用既有文献中普遍采用的算例对该模型进行计算分析,并与其他研究方法进行比较。计算结果验证了该模型在问题描述上的正确性以及在消耗更多计算时间前提下计算质量上的优越性。     

技术站间货物列车协同配流方案研究

技术站间货物列车协同作业组织模式,可实现各站获益,整体加强,对提升铁路运输生产效率具有重要意义.本文建立技术站间货物列车协同配流模型.模型以最大化两技术站的正点出发列车数作为目标函数,采用启发式遗传算法进行寻优,得到货物列车解编顺序和配流方案.最后,通过对算例进行实验分析,验证协同配流模型的实用性.结果表明,技术站间协同配流作业明显压缩车辆在站总停留时间,增加了阶段计划内正点出发列车数,进而提高了技术站内线路使用能力.     

基于Greedy方法的动态配流模型与近似算法

为研究寻优能力强、求解效率高且可及时调整的动态配流智能化编制方法,构建了基于Greedy算法的多阶段决策模型.以编组顺序为准依次划分阶段,提出了根据各阶段Δti（将最晚编组时刻和最早解体时刻之差与解体标准作业时间作求余运算所得之值）动态划分解体区间的方法;在解体区间内,以当前阶段待编列车的车流需求为匹配目标,设计了5种依据不同规则与策略的最优解体列车选择算法;将各阶段决策变量依次组成序列,得到最终的解体顺序.选取不同策略或改变参数,进行了8组对比实验,结果表明:简单规则和策略无法保证解的质量,匹配度选择算法的优劣取决于解体区间数量与解体列车选择策略;在基于R_PPCD2（根据当前阶段车流资源与后续阶段所需车流的去向匹配度选择解体列车的策略）的算法中,适当调整解体时间、编组作业时间、出发车作业时间等参数,可以在2 s内寻找到该NP难问题的一个高质量近似解.      

基于大邻域搜索算法的储位分配研究

为了提升无人仓系统订单拣选效率,以同一货架上商品关联度之和最大为目标,构建了混合整数规划模型;设计了针对上述问题的大邻域搜索算法,在大邻域搜索算法中设计了多种破坏与修复算子。利用三种规模的算例对设计算子进行比较,结果证明随机移除—最大后悔插入组合算法相比其他组合算法在时间和性能上更加优越。     

带时间窗的动态车辆路径问题的局部搜索算法

为有效求解带时间窗的动态车辆路径问题, 建立了该问题的数学模型, 通过计划周期分片, 将动态问题转换为一系列的静态子问题, 采用插入法构造初始解, 并将重定位法、节点交换法和2-opt*法3种线路间局部搜索方法, 以及2-opt法和Or-opt法2种线路内局部搜索方法的不同组合应用于初始解的改进, 分析了客户出现时间、地理位置分布与不同客户时间窗范围对线路选择的影响, 比较了标准算例的求解结果。结果表明: 在线路间进行局部搜索时, 重定位法的效果最好, 2-opt*法次之, 节点交换法的最差; 在线路内进行局部搜索时, 2-opt法优于Or-opt法; 当客户请求出现时间越早, 客户比较集中, 客户时间窗较宽的情况下, 使用的车辆数量较少, 整个线路的行驶距离较短, 客户延迟时间也较短。     

铁路网配流优化模型

在分析已有配流模型的基础上,考虑车流改编作业,对已有模型进行了修正,以正确选择车流径路.设置3组0-1变量,建立了适合我国铁路运营实际的铁路网配流模型,目标函数为车流在技术站和线路上的总费用最小.模型考虑了OD流无法完全分配的情形,克服了已有模型未考虑车流改编作业导致车流径路选择不准确的缺陷,从而获得更贴近实际的配流结果及车流改编方案.     

编组站配流相关问题分析

编组站配流是阶段计划中不可缺少的内容。本文以路网性编组站为研究对象,深入分析了编组站站型对车流组织的影响,着重探讨了配流计划与调机运用的关系。根据出发列车车流来源的确定性程度,将出发车流来源划分为A、B、C三类。从编组站配出发车流来源的确定以及到达列车解体顺序的确定,流问题的三个方面入手,即出发列车编组顺序的确定、利用双层规划模型描述了配流问题的优化方法。     

编组站配流的协调优化算法

为了提高编组站动态配流与静态配流协调优化算法的收敛速度,根据编组站解体方案树的构造规则,用解体序号矩阵进行解体方案编码,限制解的生成空间,避免了不必要的搜索.结合遗传算法与蚁群算法(genetic and ant algorithm,GAAA)的优势和配流问题的特点,设计了以GAAA为基础的协调优化算法.用遗传算法求出若干组优化解体方案,并生成初始信息素分布,用静态配流蚁群算法筛选出最优解体方案,在此基础上生成配流方案.实例表明:对阶段到发列车数不超过25列的编组站配流问题,本文算法均能在30 s内收敛到最优解或满意解.     

编组站静态配流的约束传播和启发式回溯算法

为了提高阶段计划的编制效率,针对编组站静态配流字典序多目标累积调度模型,设计了迭代、约束传播和启发式回溯的混合算法.该算法根据多目标的字典序将模型分为3层:第1层为配流成功的出发列车优先级总和最大化,第2层为出发列车车流来源总数最少化,第3层为车辆平均停留时间最短化.每层先通过约束传播算法化简模型、缩小解空间,再通过启发式回溯算法和约束传播技术联合快速求解.上一层的最优解作为下一层的初始解,并动态增加避免上一层目标退化的约束,迭代求解每层的最优解.通过某编组站实际数据验证表明,本算法耗时小于20 s,满足现场对阶段计划编制的实时性要求,且求得的配流方案优于其他算法.      

双向编组站静态配流的优化

定义了配流时间间隔和有效交换配流列车等概念．建立了双向编组站静态配流的双层多目标决策模型,目标函数包括排除与编组去向不符以及接续时间不够的车流形成的总代价、车辆在站总停留时间和交换车数量,用禁忌搜索策略和配流网络相结合的算法求解,算例证明,通过调整到达列车的接人场,可找出有效配流方案,从而实现双向编组站两个解编系统的配流优化,使除摘挂列车外的所有出发列车满轴和正点发车。     

Local Search Algorithm with Hybrid Neighborhood and Its Application to Job Shop Scheduling Problem

A new local search method with hybrid neighborhood for Job shop scheduling problem is developed. The proposed hybrid neighborhood is not only efficient in local search, but also can help overcome entrapments while search procedure get trapped at local optima and carry the search to areas of the feasible set with better prospect. New strategies used for breaking out of entrapments are presented and they are helpful for the procedure to improve local optima. A performance comparison of the proposed method with some best-performing algorithms on all 10-job, 10-machine benchmark problems and the other two problems generated by Fisher and Thompson ( ie. , FT6 and FT20) is made. The experiment results show the better optimal performance of the proposed algorithm.     

大型客运站股道运用均衡性研究

结合客运专线的作业特点和流程、到发线相关作业及运用原则、进路占用原则,分析影响股道均衡分配的主要因素。根据影响股道均衡性分配的因素,建立包含两个目标的股道分配均衡性模型。构建启发式算法并对模型进行求解,证明该算法对求解股道分配均衡性模型的可行性。对某衔接的三个方向双线通过式中间站进行实例计算,并对算例结果进行分析评价,证明该模型的可行性和有效性。     

基于需求转移的货运班列动态舱位控制策略研究

基于收益管理的思想,综合考虑顾客需求转移和批量订舱行为,建立离散时间的铁路货运班列动态舱位控制模型,指出在任意决策阶段,舱位预定请求接受/拒绝阈值点若存在则至少存在一个的特性.然后在任意决策阶段,利用每种舱位的阈值点构造了两组区间序列,针对每组区间序列给出相应的舱位预定请求的接受/拒绝策略.此外还证明了期望收益函数的性质及阈值点关于需求转移率的单调性.最后,通过设计3组仿真实验分别验证了最优舱位控制策略的可行性及相关性质的正确性.     

Dynamic Tabu Search Algorithm for Solving Departure Scheduling Problem

IntroductionWith the rapid development of air traffic, the in-creasing demand of air travel has made the airlinespurchase more aircrafts. Under these circumstances,large amounts of congestion are incurred at major air-ports. According to the related data[…     

简单约束上模函数最小值的局部搜索法

给出了求解一类具有简单约束的上模集函数最小值问题的一种局部搜索法,并讨论了所给算法的性能保证.