An integrated scenario-based approach for robust aircraft routing,crew pairing and re-timing

For reasons of tractability, the airline scheduling problem has traditionally been sequentially decomposed into various stages (e.g. schedule generation, fleet assignment, aircraft routing, and crew pairing), with the decisions from one stage imposed upon the decision-making process in subsequent stages. Whilst this approach greatly simplifies the solution process, it unfortunately fails to capture many dependencies between the various stages, most notably between those of aircraft routing and crew pairing, and how these dependencies affect the propagation of delays through the flight network. In Dunbar et al. (2012) [9] we introduced a new algorithm to accurately calculate and minimize the cost of propagated delay, in a framework that integrates aircraft routing and crew pairing. In this paper we extend the approach of Dunbar et al. (2012) [9] by proposing two new algorithms that achieve further improvements in delay propagation reduction via the incorporation of stochastic delay information. We additionally propose a heuristic, used in conjunction with these two approaches, capable of re-timing an incumbent aircraft and crew schedule to further minimize the cost of delay propagation. These algorithms provide promising results when applied to a real-world airline network and motivate our final integrated aircraft routing, crew pairing and re-timing approach which provides a substantially significant reduction in delay propagation.     

A heuristic algorithm for cube packing with time schedule

Packing problem has been proved to be an NP-hard problem. Many algorithms such as simulation annealing algorithm, genetic algorithm and other heuristic algorithms have been proposed to solve twodimensional and three-dimensional packing problem. To solve the cube packing problem with time schedule, this paper first introduces some concepts such as packing level, space distance and average neighbor birth order and then proposes a greedy algorithm. The algorithm tries every feasible corner greedily to calculat...     

A new heuristic algorithm for rectangle packing

The rectangle packing problem often appears in encasement and cutting as well as very large-scale integration design. To solve this problem, many algorithms such as genetic algorithm, simulated annealing and other heuristic algorithms have been proposed. In this paper, a new heuristic algorithm is recommended based on two important concepts, namely, the corner-occupying action and caving degree. Twenty-one rectangle-packing instances are tested by the algorithm developed, 16 of which having achieved optimum solutions within reasonable runtime. Experimental results demonstrate that the algorithm developed is fairly efficient for solving the rectangle packing problem.     

An efficient heuristic algorithm for rectangle-packing problem

Rectangle-packing problem involves many industrial applications, such as shipping, timber cutting, very large scale integration (VLSI) floor planning, and so on. This problem has shown to be NP hard, and many algorithms such as genetic algorithm, simulated annealing and other heuristic algorithms are presented to solve it. Based on the wisdom and experience of human being, an efficient heuristic algorithm is proposed in this paper. Two group benchmarks are used to test the performance of the produced algorithm, 19 instances of first group and 3 instances of second group having achieved optimal solutions. The experimental results demonstrate that the presented algorithm is rather efficient for solving the rectangle-packing problem.     

A disruption recovery plan in a three-stage production-inventory system

This paper proposes a recovery plan for managing disruptions in a three-stage production-inventory system under a mixed production environment. First, a mathematical model is developed to deal with a disruption at any stage while maximizing total profit during the recovery-time window. The model is solved after the occurrence of a disruption event, with changed data used to generate a revised plan. We also propose a new and efficient heuristic for solving the developed mathematical model. Second, multiple disruptions are considered, where a new disruption may or may not affect the recovery plans of earlier disruptions. The heuristic, developed for a single disruption, is extended to deal with a series of disruptions so that it can be implemented for disruption recovery on a real-time basis. We compare the heuristic solutions with those obtained by a standard search algorithm for a set of randomly generated disruption test problems, and that show the consistent performance of our developed heuristic with lower computational times. Finally, some numerical examples and a real-world case study are presented to demonstrate the benefits and usefulness of our proposed approach.     

A new heuristic approach for non-convex optimization problems

In this work a new optimization method, called the heuristic Kalman algorithm (HKA), is presented. This new algorithm is proposed as an alternative approach for solving continuous, non-convex optimization problems. The principle of HKA is to explicitly consider the optimization problem as a measurement process designed to give an estimate of the optimum. A specific procedure, based on the Kalman estimator, was developed to improve the quality of the estimate obtained through the measurement process. The main advantage of HKA, compared to other metaheuristics, lies in the small number of parameters that need to be set by the user. Further, it is shown that HKA converges almost surely to a near-optimal solution. The efficiency of HKA was evaluated in detail using several non-convex test problems, both in the unconstrained and constrained cases. The results were then compared to those obtained via other metaheuristics. The numerical experiments show that HKA is a promising approach for solving non-convex optimization problems, particularly in terms of computation time and success ratio.     

A heuristic block-loading algorithm based on multi-layer search for the container loading problem

This paper presents an efficient heuristic block-loading algorithm based on multi-layer search for the three-dimensional container loading problem. First, a basic heuristic block-loading algorithm is introduced. This algorithm loads one block, determined by a block selecting algorithm, in one packing phase, according to a fixed strategy, until no blocks are available. Second, the concept of composite block is introduced, the difference between traditional block and composite block being that composite block can contain multiple types of boxes in one block under some restrictions. Third, based on the depth-first search algorithm, a multi-layer search algorithm is developed for determining the selected block in each packing phase, and making this result closer to the optimal solution. Computational results on a classic data set show that the proposed algorithm outperforms the best known algorithm in almost all the test data.     

Exact algorithm and heuristic for the Closest String Problem

The Closest String Problem (CSP) is an NP-hard problem, which arises in computational molecular biology and coding theory. This class of problems is to find a string that minimizes the maximum Hamming distance to a given set of strings. In this paper, we present an exact algorithm called Distance First Algorithm (DFA) for three strings of CSP with alphabet size two. For the general CSP, we design a polynomial heuristic which is a combination of our proposed approximation algorithm LDDA ([10] Liu Xiaolan, Fu Keqiang, Shao Renxiang. Largest distance decreasing algorithm for the Closest String Problem. Journal of Information & Computational Science 2004; 1(2): 287–92) and local search strategies. Numerical results show that the proposed heuristic may obtain a nearly optimal value in a reasonable time for small and large-scale instances of the CSP.     

Single-Source Capacitated Multi-Facility Weber Problem—An iterative two phase heuristic algorithm

Multi-Facility Weber Problem (MFWP), also known as continuous location-allocation problem, entails determining the locations of a predefined number of facilities in a planar space and their related customer allocations. In this paper, we focus on a new variant of the problem known as Single-Source Capacitated MFWP (SSCMFWP). To tackle the problem efficiently and effectively, an iterative two-phase heuristic algorithm is put forward. At the phase I, we aim to determine proper locations for facilities, and during the phase II, assignment of customers to these facilities is pursued. As an alternative solution method, a simulated annealing (SA) algorithm is also proposed for carrying out the phase I. The proposed algorithms are validated on a comprehensive set of test instances taken from the literature. The proposed iterative two-phase algorithm produces superior results when assessed against the proposed SA algorithm as well as a general MINLP Solver known as BARON. The latter is applied to produce optimal solutions for small sized instances and generate upper bound for medium ones.     

一种求解车间作业调度问题的免疫算法

人工免疫系统是基于生物免疫系统特性而发展的新兴智能系统。基于免疫系统的克隆选择机制,提出一种求解车间作业调度问题的免疫算法。利用免疫算法较强的搜索能力可以实现全局寻优。通过使用克隆、高频变异和抗体抑制等免疫操作,提高了算法的收敛速度和种群的多样性,可以有效地克服遗传算法种群早熟化和收敛速度慢的问题。仿真结果表明,与改进后的遗传算法比较,提出的免疫算法在全局最优解和收敛速度上都有较为明显的优势。     

A genetic algorithm with the heuristic procedure to solve the multi-line layout problem

The paper presents a genetic algorithm-based meta-heuristic to solve the facility layout problem (FLP) in a manufacturing system, where the material flow pattern of the multi-line layout is considered with the multi-products. The matrix encoding technique has been used for the chromosomes under the objective of minimizing the total material handling cost. The proposed algorithm produces a table with the descending order of the data corresponding to the input values of the flow and cost data. The generated table is used to create a schematic representation of the facilities, which in turn is utilized to heuristically generate the initial population of the chromosomes and to handle the heuristic crossover and mutation operators. The efficiency of the proposed algorithm has been proved through solving the two examples with the total cost less than the other genetic algorithms, CRAFT algorithm, and entropy-based algorithm.     

A new heuristic algorithm for cuboids packing with no orientation constraints

The three-dimensional cuboids packing is NP-hard and finds many applications in the transportation industry. The problem is to pack a subset of cuboid boxes into a big cuboid container such that the total volume of the packed boxes is maximized. The boxes have no orientation constraints, i.e. they can be rotated by 90^°${90}^{°}$ in any direction. A new heuristic algorithm is presented that defines a conception of caving degree to judge how close a packing box is to those boxes already packed into the container, and always chooses a packing with the largest caving degree to do. The performance is evaluated on all the 47 related benchmarks from the OR-Library. Experiments on a personal computer show a high average volume utilization of 94.6% with an average computation time of 23 min for the strengthened A1 algorithm, which improves current best records by 3.6%. In addition, the top-10 A2 algorithm achieved an average volume utilization of 91.9% with an average computation time of 55 s, which also got higher utilization than current best records reported in the literature.     

On the variable-depth-search heuristic for the linear-cost generalized assignment problem

The classical assignment problem seeks to determine a mapping between a set of assignees and a set of assignments. The linear cost assignment problem (LCGAP), as a generalized model, incorporates the relative workloads between assignees and assignments. Although LCGAP is computationally intractable, it has been extensively studied because of its practical implications in many real world situations. Variable-depth-search heuristic (VDSH) method is one of the solution methods that have been developed to produce quality near-optimal solutions to LCGAP. The main structure of VDSH consists of two basic operations: reassign and swap. In this paper, we make further observations on this effective heuristic method through a series of computational experiments. The numerical results statistically evince that different combina-tions of these two operations will result in solutions of different quality levels. These findings are expected to have similar implications to search heuristics for other optimization problems.     

A new heuristic recursive algorithm for the strip rectangular packing problem

A fast and new heuristic recursive algorithm to find a minimum height for two-dimensional strip rectangular packing problem is presented. This algorithm is mainly based on heuristic strategies and a recursive structure, and its average running time is T(n)=θ(n³)$T(n)=\theta (n^3)$. The computational results on a class of benchmark problems have shown that this algorithm not only finds shorter height than the known meta-heuristic ones, but also runs in shorter time. Especially for large test problems, it performs better.     

A two-phase hybrid heuristic algorithm for the capacitated location-routing problem

In this paper, we propose a two-phase hybrid heuristic algorithm to solve the capacitated location-routing problem (CLRP). The CLRP combines depot location and routing decisions. We are given on input a set of identical vehicles (each having a capacity and a fixed cost), a set of depots with restricted capacities and opening costs, and a set of customers with deterministic demands. The problem consists of determining the depots to be opened, the customers and the vehicles to be assigned to each open depot, and the routes to be performed to fulfill the demand of the customers. The objective is to minimize the sum of the costs of the open depots, of the fixed cost associated with the used vehicles, and of the variable traveling costs related to the performed routes. In the proposed hybrid heuristic algorithm, after a Construction phase (first phase), a modified granular tabu search, with different diversification strategies, is applied during the Improvement phase (second phase). In addition, a random perturbation procedure is considered to avoid that the algorithm remains in a local optimum for a given number of iterations. Computational experiments on benchmark instances from the literature show that the proposed algorithm is able to produce, within short computing time, several solutions obtained by the previously published methods and new best known solutions.     

A fault-tolerant parallel heuristic for assignment problems

This paper presents a new approach for parallel heuristic algorithms based on adaptive parallelism. Adaptive parallelism was used to dynamically adjust the parallelism degree of the application with respect to the system load. This approach demonstrates that high-performance computing using a hundred of heterogeneous workstations combined with massively parallel machines is feasible to solve large optimization problems with respect to the personal character of workstations. The fault-tolerant algorithm allows a minimal loss of computation in case of failures. The proposed algorithm exploits the properties of this class of applications in order to reduce the complexity of the algorithm in terms of the checkpoint files size and the control messages exchanged. The parallel heuristic algorithm combines different search strategies: simulated annealing and tabu search. Encouraging results have been obtained in solving the quadratic assignment problem. We have improved the best known solutions for some large real-world problems.     

蚁群算法求解非等同并行机调度问题的研究

针对非等同并行机服务调度问题,以机场除冰调度服务为背景并以最小化旅客延误数为目标,提出了一种改进的蚁群算法。该算法根据调度模型的特点,充分考虑模型的约束条件并运用了一种改进的信息素更新策略求解并行机调度问题。仿真结果表明,改进的蚁群算法收敛速度快且结果较优,明显优于FIFO算法,适合求解非等同并行机调度问题。     

A heuristic rule for relocating blocks

One of the most important objectives of the storage and pickup operations in block stacking systems is to minimize the number of relocations during the pickup operation. This study suggests two methods for determining the locations of relocated blocks. First, a branch-and-bound (B&B) algorithm is suggested. Next, a decision rule is proposed by using an estimator for an expected number of additional relocations for a stack. The performance of the decision rule was compared with that of the B&B algorithm.     

A least wasted first heuristic algorithm for the rectangular packing problem

The rectangular packing problem is to pack a number of rectangles into a single large rectangular sheet so as to maximize the total area covered by the rectangles packed. The paper first presents a least wasted first strategy which evaluates the positions used by the rectangles. Then a random local search is introduced to improve the results and a least wasted first heuristic algorithm (LWF) is further developed to find a desirable solution. Twenty-one rectangular-packing instances are tested by the algorithm developed, the experimental results show that the presented algorithm can achieve an optimal solution within reasonable time and is fairly efficient for dealing the rectangular packing problem. LWF still performs well when it is extended to solve zero-waste and non-zero-waste strip packing instances.