运输问题的遗传算法

本文经典的运输问题给出了一种遗传算法，编制了相应的程序，对线性和非线性情况下的大量随机算例进行了求解，得到了较好的结果。     

求解运输问题的GAPSO算法

运输问题是一个应用非常广泛的问题,传统方法对于大规模的运输问题求解比较复杂,而一些基于随机搜索算法的方法对于其约束条件的处理又比较困难.基于运输问题约束条件的特殊性,设计了一种产生可行解的方法,将对约束条件的处理转化到了算法设计之中.在此基础上,又设计了基于遗传算法和粒子群优化算法的求解运输问题的GAPSO算法,为避开对非可行解的处理,该算法对迭代过程也进行了特殊设计,从而简化了运用随机搜索算法解决运输问题的过程.最后给出了三个实例验证,通过对验证结果分析和比较,说明该算法在时间复杂度和收敛性方面都具有其优良性,是行之有效的.     

运输问题的一种计算机算法

本文对运输问题的求解方法进行了分析，改进了传统的计算机算法，运用该方法编写程序，具有开发速度快、容易实现、代码短小的特点。文章不仅给出了算法的理论基础还给出了计算机实现时的一些技巧，对程序开发人员有很强的实用价值。     

基于蚁群算法的邮政运输规划研究

针对国内邮政运输路线规划存在的主要问题,建立解决邮政运输的多目标决策问题的数学模型,使用蚁群算法来求解该模型的近似解.仿真实验证明该方法是有效的、可行的.     

多式联运中运输方式与运输路径集成优化模型研究*

运输方式和运输路径选择问题是影响多式联运时间和费用的关键问题,直接影响承运人和客户的利益。依据运输方式选择和运输路径优化的关系特点,采用主从混合智能启发式方法,构建了运输方式选择和运输路径优化集成模型,给出了粒子群—蚁群双层优化算法求解方案,解决了运输网络多节点、多方式、多路径的集成优化问题。实验结果表明,该方案优于蚁群算法和遗传算法。     

基于遗传算法的动态MC2运输问题求解

动态MC²运输问题是描述多阶段供求波动的运输问题,其模型框架可以应用到很多领域。目前对动态MC²运输模型的求解主要采用传统的单纯形法,针对该问题的特殊性采用具有全局搜索能力的遗传算法进行求解。通过三维数组编码,设计有效的交叉、变异算子和适应度函数,克服了单纯形法求解该问题出现的并行性差、求解整数规划困难的不足。用Matlab7.0编程对算法进行检验,结果表明经过特殊设计的遗传算法能够很好地解决动态MC²运输问题。     

带道路容量动态约束的关联运输调度问题

介绍了混沌遗传算法的基本原理,并对其进行改进,自适应地调整交叉概率和变异概率,引进了模拟退火机制,用聚类分析及改进的算法对多车场的关联运输调度问题进行求解,然后与遗传算法求解此模型的结果相比较。实例证明该算法求解关联运输调度问题是可行的,且优于传统的遗传算法。     

基于遗传算法的动态MC2运输问题求解

动态MC²运输问题是描述多阶段供求波动的运输问题,其模型框架可以应用到很多领域。目前对动态MC²运输模型的求解主要采用传统的单纯形法,针对该问题的特殊性采用具有全局搜索能力的遗传算法进行求解。通过三维数组编码,设计有效的交叉、变异算子和适应度函数,克服了单纯形法求解该问题出现的并行性差、求解整数规划困难的不足。用Matlab7.0编程对算法进行检验,结果表明经过特殊设计的遗传算法能够很好地解决动态MC²运输问题。     

定位2运输路线安排问题的两阶段启发式算法

重点研究了集成化物流中一类特殊的定位一运输路线安排问题(LRP)的解决方法．LRP问题包括设施定位和运输路线优化两方面决策，属于NP-hard难题．由于问题的复杂性，提出基于假设前提的LRP模型及其两阶段启发式求解算法．该方法分两步实现：首先，采用基于最小包络聚类分析的启发式方法确定被选择的潜在设施及由每一个选中的设施所要提供服务的客户群；其次，运用带有控制开关的遗传算法求解每一确定客户类中的优化运输路线．提出利用两阶段启发式算法求解LRP问题，此方法实现容易、运算简单，一定程度上避免了遗传算法中的“局部最优现象”．仿真实验证明了该算法求解单目标LRP的有效性和准确性．     

多式联运运输问题的混合遗传算法

多式联运运输方式的选择关系到货物运输所需费用、时间等。该文对需经过多式联运过程的运输问题进行了研究。首先分析了多式联运运输问题的数学模型;其次通过引入关于运输量及运输方式的混合编码,结合两种混合遗传算子,提出了一种求解多式联运运输问题的混合遗传算法;最后用数值例子对算法的有效性进行了验证。     

一种求解划分问题的新算法

划分问题是ＶＬＳＩ－ＣＡＤ设计中的基本问题,针对近似划分问题、划分问题、背包问题,提出了一种行之有效的快速算法,其核心思想是基于拟物思路构造目标函数。     

解答划分问题的新拟多项式时间算法

利用一种称为平衡技术的新方法解答划分问题。证明若划分问题存在满足条件的子集,则该子集一定是平衡集,仅对平衡集进行枚举即可解答划分问题。若划分问题给定集合中每个元素的长度都被一个常数M所界定,结合动态规划技术且仅考虑平衡集,解答划分问题的时间复杂度为O(nM),此算法在时间效率上对现有算法有较大改进。     

基于混合演化算法的二维下料问题

介绍了将二维下料问题建模成旅行商问题的方法,指出单纯旅行商问题模型的局限性,认为其是一种启发式方法,理论上找不到全局最优解。针对于此,在原有模型的基础上引入旋转变换,提出了两种混合演化算法捆绑式深化算法和元算法。实例仿表明,该算法可以获得比普通经算法好的结果。     

An adaptive large neighborhood search heuristic for the Pickup and Delivery Problem with Time Windows and Scheduled Lines

The Pickup and Delivery Problem with Time Windows and Scheduled Lines (PDPTW-SL) concerns scheduling a set of vehicles to serve freight requests such that a part of the journey can be carried out on a scheduled public transportation line. Due to the complexity of the problem, which is NP-hard, we propose an Adaptive Large Neighborhood Search (ALNS) heuristic algorithm to solve the PDPTW-SL. Complex aspects such as fixed lines׳ schedules, synchronization and time-windows constraints are efficiently considered in the proposed algorithm. Results of extensive computational experiments show that the ALNS is highly effective in finding good-quality solutions on the generated PDPTW-SL instances with up to 100 freight requests that reasonably represent real life situations.     

Improving problem reduction for 0–1 Multidimensional Knapsack Problems with valid inequalities

This paper investigates the problem reduction heuristic for the Multidimensional Knapsack Problem (MKP). The MKP formulation is first strengthened by the Global Lifted Cover Inequalities (GLCI) using the cutting plane approach. The dynamic core problem heuristic is then applied to find good solutions. The GLCI is described in the general lifting framework and several variants are introduced. A Two-level Core problem Heuristic is also proposed to tackle large instances. Computational experiments were carried out on classic benchmark problems to demonstrate the effectiveness of this new method.     

最大团问题的改进遗传算法求解

最大团问题是组合优化中经典的NP完全问题,该问题的枚举算法只适用于求解中小规模的图。提出了基于遗传算法的最大团问题求解算法,引入概率模型指导变异产生新的个体,并结合启发式局部算法搜索最大团。经算例测试,获得了较好的效果。     

基于遗传算法求解TSP问题的一种算法

TSP问题是一个经典的NP难度的组合优化问题，遗传算法是求解TSP问题的有效方法之一。利用交换启发交叉算子实现局部搜索加快算法的收敛速度和利用变换变异算子维持群体的多样性防止算法早熟收敛，给出了一种求解TSP问题的遗传算法。仿真实验结果表明了该算法的有效性和可行性。     

Cooperative surveillance systems and digital-technology enabler for a real-time standard terminal arrival schedule displacement

As the backbone of Communications, Navigation and Surveillance Systems for Air Traffic Management (CNS/ATM), Automatic Dependent Surveillance-Broadcast (ADS-B) is a surveillance technology and digital-technology enabler relying on the Global Navigation Satellite System (GNSS). The onboard ADS-B Out system broadcasts the aircraft’s real-time digital information such as position and ground speed periodically (every 0.5–2 s), which is more frequent than the radar system. Taking this advantage, situational awareness and flight efficiency can be highly improved. In this paper, a novel heuristic search method based on ADS-B is proposed for the Aircraft Landing Problem (ALP) with the objective of reducing flight time while maintaining the time separation standards mandated by the International Civil Aviation Organization (ICAO). The recorded ADS-B data in Shanghai Hongqiao and Pudong international airports are adopted to demonstrate the performance of the proposed method. Results show that there is an obvious decrease in the total flight time. Besides, the heuristic search method can achieve continuous and real-time ALP updates, satisfying the requirements for air traffic control. While highlighting ADS-B-based applications, this study also provides some basic implications for the updated model in air traffic management.     

求解OVRPTW的多开始禁忌搜索算法

在对带时间窗的开放式车辆路径问题描述的基础上提出求解该类问题的一种多开始禁忌搜索算法。使用扫描算法和向前插入法相结合的两阶段方法产生随机的初始解,采用一种混合的启发式算法构建邻域结构,设计全局和局部2个禁忌表加强算法的全局寻优能力。用标准的测试算例对算法进行实验,结果表明该算法得到了较好的寻优效果。     

The inventory-routing problem with transshipment

This paper introduces the Inventory-Routing Problem with Transshipment (IRPT). This problem arises when vehicle routing and inventory decisions must be made simultaneously, which is typically the case in vendor-managed inventory systems. Heuristics and exact algorithms have already been proposed for the Inventory-Routing Problem (IRP), but these algorithms ignore the possibility of performing transshipments between customers so as to further reduce the overall cost. We present a formulation that allows transshipments, either from the supplier to customers or between customers. We also propose an adaptive large neighborhood search heuristic to solve the problem. This heuristic manipulates vehicle routes while the remaining problem of determining delivery quantities and transshipment moves is solved through a network flow algorithm. Our approach can solve four different variants of the problem: the IRP and the IRPT, under maximum level and order-up-to level policies. We perform an extensive assessment of the performance of our heuristic.