约束满足与邻域搜索结合的混合算法及应用

总结约束满足求解技术和邻域搜索算法,分析约束满足与邻域搜索单一算法的优劣,以及两者结合的优势,提出约束满足与邻域搜索相结合的混合算法的一般框架,并以Job Shop,调度优化问题为例对该算法框架进行实例说明.     

基于实时信息的游客行程动态规划研究

基于实时信息的游客行程动态规划问题可适用于城市景点的游客行程规划、主题公园的游客行程规划、博物馆的游客游览路线规划等服务系统的实际场景。本文采用重规划方法将该问题转化为离散时间段上的静态规划子问题,建立了对应的混合线性整数规划模型,并证明了该问题的NP难性质。提出了一种分支定界算法来求解静态子问题的优化模型,并设计了一种变邻域搜索算法来求解对应的大规模问题。通过数值实验验证了所提的模型和算法,并进行了算法参数标定和算法比较分析。数值实验的结果表明,所提分支定界算法和变邻域搜索算法的计算性能都明显优于已有文献的算法。所提的模型和算法可以嵌入到管理信息系统中,对于提升服务系统的工作效率、降低顾客的等待时间、优化服务系统的资源配置等具有实际意义。     

一种求解双目标flow shop排序问题的进化算法

提出一种求解双目标flow shop排序的递进多目标进化算法.算法采用改进的精英复制策略,在实现精英保留的前提下降低了计算复杂性;通过递进进化模式增加群体多样性,改善了算法收敛性;通过群体进化过程中对非劣解集进行竞争型可变邻域启发式搜索,增强了算法局部搜索性能.采用新算法和参照算法NSGA-II对31个标准双目标flow shop算例进行优化.研究结果表明,新算法在所有算例的求解中均获得了优于NSGA-II的非劣解集,验证了算法的有效性.     

顾客时间窗变化的多车场车辆调度干扰管理模型研究

为解决物流配送过程中某顾客时间窗变化而导致的物流配送难以按照原计划实现的难题,运用干扰管理方法,针对多车场带时间窗的物流配送车辆路径问题,提出包含顾客配送时间总偏离度、配送总成本、新路径方案与初始路径计划偏差量、最长行驶时间违反总量4个因素的扰动程度度量方法;以顾客时间窗变化这类干扰事件发生时的问题状态为基础,以系统整体扰动最小化为目标,建立问题的目标规划数学模型;针对这一复杂模型,提出基于特定邻域结构及其寻优概率的变邻域搜索算法;最后在标准算例上使用变邻域搜索算法与其他文献算法进行比较分析,结果表明该变邻域搜索算法对于干扰事件发生后的车辆路线重排结果在系统整体扰动程度方面明显优于其他文献的算法.     

航空票务公司免费接送服务中的车次调度模型及算法

本文从顾客满意度和成本出发，对航空票务公司免费接送顾客的车次分配和调度问题进行研究，首先分析了票务公司免费接送服务的业务流程；然后给出了基于时间的顾客满意度函数，并建立了在一定顾客满意度下成本最小的车次调度模型；最后利用集划分方法求解该模型。集划分包括以下两步：第一步采用广度优先搜索生成全部车次集；第二步提出了一种启发式算法。通过仿真分析比较，验证了启发式算法的有效性。     

实时/时变路网环境下城市出救点选择与救援车辆路径的集成动态优化

为了提升城市突发公共事件应急资源调配效率,考虑实时/时变路网环境下出救点选择与救援车辆路径的集成优化问题(CERFSVRP),设计了一种实时/时变交通信息的结合策略,并提出了满足先进先出原则的路段行驶时间计算方法.在此基础上,综合考虑出救点选择、供应能力以及车辆路径连续性等约束条件,以应急响应时间最短为目标,基于虚拟出救点概念和滚动时域策略建立了CERFSVRP动态优化模型.针对该模型的特点,设计了一种改进遗传算法和线性规划法相结合的两阶段算法.算例分析结果表明该模型和算法可以有效解决实时/时变路网环境下城市突发公共事件CERFSVRP动态优化问题.     

基于P-中位模型的网络关键设施识别问题的算法设计与实现

在网络服务系统中,存在由于各种人为因素(恐怖行为、黑客袭击等)导致网络设施服务中断的情况.为抵御有预谋的攻击,需要更加重视如何识别网络系统中的关键设施.结合P-中位选址模型,以设施失效对网络系统运行效率影响最大化为目标,给出针对基于P-中位模型的网络关键设施识别问题(即R-中断模型),并针对该模型提出贪婪搜索、邻域搜索和禁忌搜索3种算法.结合Galvo、Europe 150 和USA 263 等大型的测试实例,对上述算法进行比较分析,得出禁忌搜索算法最有效的结论.最后,结合Europe 150 数据的例子比较了P-中位问题与R-中断问题,认为在选址决策中事先考虑到人为攻击导致的中断问题可以增加网络的抗攻击能力,减少损失.     

具有最大总加权满意度的单机调度问题的dynasearch算法

研究了总加权满意程度最大化的单机调度问题.对最优解的性质进行分析和证明,提出该类问题的统治规则.提出该问题新的基于dynasearch 邻域的迭代局域搜索算法(ILS).算法主要特点:1)dynasearch 是基于多摄动的思想,即一次可以做多个相互独立的交换(或插入);2)用动态规划获得最优dynasearch移动;3)ILS采用随机kick 策略对局部最优解进行摄动,然后继续迭代.实现了该问题的两种dynaearch算法;把两种dynasearch算法与统治规则相结合;在进行kick时引入误差限制.实验表明:嵌入统治规则的算法优于没有统治规则的算法;基于dynasearch交换的ILS 优于基于dynasearch插入的ILS;dynaearch算法要优于以交换为邻域的多初始点改进算法.     

第Ⅱ类拆卸线平衡问题建模及优化

环境资源问题日益凸显、人们环保意识的增强以及经济利益的驱动,促使社会进行废旧产品回收再利用,以发展绿色经济。拆卸作为回收再利用过程中的核心环节,采用流水线的方式组织产品精细化拆卸,可实现资源最大化价值。然而,零部件作业任务在流水线上分配排序过程复杂,各工作站上的作业负荷需保持相对均衡,才能保证拆卸线高效运行。为此,本文在拆卸线工作站数量固定的情况下,以最短节拍时间和均衡任务在工作站上的分配为目标,建立第Ⅱ类拆卸线平衡问题优化模型,并提出一种并行动态邻域深度搜索算法进行求解。所提算法采用动态搜索机制实现解在各邻域结构集内的并行深度搜索;通过设置扰动阈值对解实施干扰,以加快跳出局部最优;在节拍时间调整过程中,采用基于二分法的定界策略,以实现向最优节拍时间的快速靠拢。最后,通过不同规模算例验证了模型的有效性以及算法的高效性。     

混合PSO算法求解混装工艺下的加热炉调度问题

针对钢铁生产中为减轻混装的影响在冷热板坯混装处空炉的情况,以提高成品质量、降低能耗为目标,建立了混装工艺下并行加热炉调度的数学模型,并提出了基于粒子群算法和邻域搜索技术的混合算法,仿真实验验证了算法的可行性和有效性.     

同时集散货物的开放式车辆路径问题研究

本文研究了车辆工作时间限制下同时集散货物的多配送中心开放式车辆路径问题,以车辆数和运输里程最小为目标,建立了多目标规划模型,提出了基于拉格朗日松弛技术和禁忌搜索算法的混合求解算法。 该算法首先求出最优解的最大下界,然后采用客户点的分配和调整策略实现解的可行化,其中禁忌搜索引入了4种领域搜索方法,采用了随机变领域搜索方法和重起策略。算例分析表明,该算法能有效地找到满意解,且采用开放式安排路线比闭合式安排路线更加经济合理。     

动态需求下车辆路径问题的周期性优化模型及求解

针对客户点不断更新的动态需求车辆路径问题,依据滚动时域对配送中心工作时间进行划分,提出基于延迟服务的周期性客户点实时重置策略,策略中延迟服务机制能结合车辆启动延迟系数对照当前时域的时间进行检验,满足所有客户点的服务需求,保证车辆满足中心时间窗约束。设计多阶段求解的混合变邻域人工蜂群算法对各时间片内子问题进行连续迭代优化,算法中子路径动态转变的设计能较好平衡原有客户点和新客户点对路径更新和车辆实时信息匹配的要求。算例验证及对比分析表明本文策略和算法在求解动态问题时的有效性和可行性。     

B2C电子商务环境下订单拣选与配送联合调度优化

如何在顾客下单后协调好拣选和配送环节,在最短的时间、以较低的成本将商品从货架上拣出、打包后配送到顾客手中,已成为B2C电子商务物流管理中亟待解决的问题。本文尝试以最小化订单履行时间为目标,构建非线性拣选与配送联合调度模型,以解决订单拣选顺序、拣选作业方式、车辆行驶线路等联合决策。为求解此NP难问题,设计了三阶段启发式算法：首先采用“聚类-路径优化”思想,依据顾客位置进行配送方案确认;然后采用基于相似度聚类的订单分批规则对每条配送线路的订单进行分批合并;最后调整拣选任务与配送线路顺序。通过数据实验对模型进行验证,并与传统拣选与配送分开优化的结果进行对比。结果表明,三阶段算法能够有效缩短订单完成时间、降低配送车辆等待时间、改善配送资源利用率。     

装卸一体化的车辆路径问题及基于插入法的新禁忌算法

在日益激烈的市场竞争中,如何在降低成本的同时,让各个顾客尽快收到货物成了现代交通运输物流中一个越来越重要的考虑因素。基于某快递公司的运输实例,本文提出了装卸一体化的车辆路径问题模型,最终优化目标是最小化车辆运输时间和货物到各个顾客的时间的加权和,并给出了一种基于插入法的新禁忌算法,实验结果表明新禁忌算法在显著提高传统禁忌算法计算时间的同时,还能得到理想的成本,并且对节约快递公司的运输成本方面有显著成效。     

低碳环境下的车辆路径问题及禁忌搜索算法研究

基于节能减排的新视角,本文研究了低碳环境下由第三方提供运输服务的车辆路径问题,在安排车辆路径时,同时考虑了能耗、碳排放和租车费用,而这些费用不仅与距离有关,也与客户点的需求量和车辆速度有关。提出了考虑车辆运量和速度的能耗计算方法,建立了非满载运输方式下的低碳路径模型——LCRP。设计了基于路径划分的禁忌搜索算法RS-TS对问题进行求解,该算法引入了一种新颖的路径编码与解码算法WSS,采用了三种邻域搜索方法。通过基准测试实例验证了算法能有效地找到满意解,并揭示了距离、能耗、行驶时间等参数之间的关系,实验分析表明采用低碳路径安排更加经济环保且选择中低的交通速度更有利于节约能耗和降低碳排放。     

A heuristic algorithm for the period vehicle routing problem

In this paper we consider the period vehicle routing problem, which is the problem of designing routes for delivery vehicles to meet customer service level requirements (not all customers require delivery on every day in the period). A heuristic algorithm, based upon the daily vehicle routing algorithm of Fisher and Jaikumar, is presented and computational results are given for test problems drawn from the literature.     

Vehicle routing using fixed delivery areas

In this paper we consider the problem of vehicle routing using fixed delivery areas. This is the problem of splitting the area serviced by a depot into a number of separate subareas—a single delivery vehicle being assigned to each subarea to supply all the customers within the subarea. A heuristic algorithm is developed for the problem based upon an initial allocation of customers to subareas followed by customer interchanges in an attempt to improve the subareas. Computational results are presented for a number of test problems drawn from the literature.     

突发疫情环境下考虑订单释放时间的零售物流配送路径优化研究

“新冠肺炎”疫情突发严重危及了人们的生活安全，而物流保障在疫情防控、保民生活、稳定社会方面却起到了重要支撑作用。以保证民生的零售物流配送为背景，本文研究考虑订单释放时间的车辆路径优化问题，以配送完工时间与运输成本的加权之和最小为目标，构建了线性规划模型,并设计了改进的迭代局部搜索求解算法。该算法采用基于多种邻域结构和改进的US算法的局部搜索过程以增强算法的寻优能力，通过引入大路径和最优分割过程获得高质量的初始解和打破机制以增强算法的搜索效率。同时，提出一些性质用于拉格朗日松弛算法，为本文研究问题提供高质量的下界。最后，数值实验部分通过求解标杆算例和文中算例验证了模型和算法的有效性，并对订单释放时间和模型参数进行灵敏度分析，结果表明本文模型和算法能够为零售物流配送的效率提升和成本控制提供有效的决策支持。     

无人仓系统储位分配问题的优化模型与算法

考虑到无人仓系统补货阶段货架上只有部分空余储位的特点，研究了补货商品储位分配问题的优化模型与算法。以同一货架上存放的商品之间关联度之和最大化为目标建立了混合整数规划模型；结合贪婪算法和邻域搜索算法设计了求解模型的两阶段方法。第一阶段利用贪婪算法求初始可行解；第二阶段利用邻域搜索算法对初始可行解进行优化。利用一个具体算例验证了邻域搜索算法的优化效果，结果显示，通过邻域搜索算法对初始可行解的优化，可以使目标函数值至少提升27%。进一步利用多个小规模算例分析了两阶段算法的近似比和求解速度，验证了算法的快速有效性。本文的研究结果不仅解决了货架初始状态非空情况下的储位分配问题，同样适合解决货架初始状态为空的情况，因此更加符合实际场景，可以作为无人仓管理信息系统的核心模型和算法。     

有模糊时间窗的车辆调度组合干扰管理研究

研究带有模糊时间窗的车辆调度组合干扰管理模型及其混合遗传算法.采用时间窗模糊化处理方法,定义客户满意度函数,根据干扰管理思想对车辆调度中组合性干扰事件进行分析,从配送路径、配送成本和客户满意度三个方面进行干扰辨识与度量,建立基于模糊时间窗的车辆调度组合干扰管理模型;构造模型求解的混合遗传算法,将最佳客户插入规则与遗传算法结合,同时在算法中嵌入模糊优化程序以处理问题的模糊特征;进行数值实验,实验结果验证了模型与算法的有效性.