Aircraft maintenance,routing, and crew scheduling planning for airlines with a single fleet and a single maintenance and crew base

This work proposes an approach for solving the aircraft maintenance routing problem (AMRP) and the crew scheduling problem (CSP) in sequential and integrated fashions for airlines having a single fleet with a single maintenance and crew base, as is the case for most Latin American and many low-cost airlines. The problems were initially solved in the traditional sequential fashion. The AMRP was formulated to maximize revenue while satisfying fleet size. It was solved such that the final flight schedule was also determined. The CSP was solved by including a heuristic to obtain an efficient first feasible solution, and adapting a labeling algorithm to solve the pricing problems that arise in the column-generation technique. Finally, an integrated model was formulated and solved. Both approaches were tested on the real flight schedules of three important Latin American airlines. The solutions were coherent, independent of computational parameters, and obtained in short computational times in a standard PC (e.g. <1 h for up to 522 flights). Continuous relaxations gave very tight bounds (e.g. gaps < 0.8%). The integrated solutions offered small improvements over the sequential solutions (e.g. up to 0.6% or US$45,000 savings/year). However, these savings should increase drastically with fleet size and with the complexity of the flight schedule offered by the airline.     

Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem

This paper presents two solution representations and the corresponding decoding methods for solving the capacitated vehicle routing problem (CVRP) using particle swarm optimization (PSO). The first solution representation (SR-1) is a (n + 2m)-dimensional particle for CVRP with n customers and m vehicles. The decoding method for this representation starts with the transformation of particle into a priority list of customer to enter route and a priority matrix of vehicle to serve each customer. The vehicle routes are then constructed based on the customer priority list and vehicle priority matrix. The second representation (SR-2) is a 3m-dimensional particle. The decoding method for this representation starts with the transformation of particle into the vehicle orientation points and the vehicle coverage radius. The vehicle routes are constructed based on these points and radius. The proposed representations are applied using GLNPSO, a PSO algorithm with multiple social learning structures, and tested using some benchmark problems. The computational result shows that representation SR-2 is better than representation SR-1 and also competitive with other methods for solving CVRP.     

Efficient multicast schemes for 3-D Networks-on-Chip

3-D Networks-on-Chip (NoCs) have been proposed as a potent solution to address both the interconnection and design complexity problems facing future System-on-Chip (SoC) designs. In this paper, two topology-aware multicast routing algorithms, Multicasting XYZ (MXYZ) and Alternative XYZ (AL + XYZ) algorithms in supporting of 3-D NoC are proposed. In essence, MXYZ is a simple dimension order multicast routing algorithm that targets 3-D NoC systems built upon regular topologies. To support multicast routing in irregular regions, AL + XYZ can be applied, where an alternative output channel is sought to forward/replicate the packets whenever the output channel determined by MXYZ is not available. To evaluate the performance of MXYZ and AL + XYZ, extensive experiments have been conducted by comparing MXYZ and AL + XYZ against a path-based multicast routing algorithm and an irregular region oriented multiple unicast routing algorithm, respectively. The experimental results confirm that the proposed MXYZ and AL + XYZ schemes, respectively, have lower latency and power consumption than the other two routing algorithms, meriting the two proposed algorithms to be more suitable for supporting multicasting in 3-D NoC systems. In addition, the hardware implementation cost of AL + XYZ is shown to be quite modest.     

Search space reduction in QoS routing

To provide real-time service or engineer constrained-based paths, networks require the underlying routing algorithm to be able to find low-cost paths that satisfy given quality-of-service constraints. However, the problem of constrained shortest (least-cost) path routing is known to be NP-hard, and some heuristics have been proposed to find a near-optimal solution. However, these heuristics either impose relationships among the link metrics to reduce the complexity of the problem which may limit the general applicability of the heuristic, or are too costly in terms of execution time to be applicable to large networks. In this paper, we focus on solving the delay-constrained minimum-cost path problem, and present a fast algorithm to find a near-optimal solution. This algorithm, called delay-cost-constrained routing (DCCR), is a variant of the k-shortest-path algorithm. DCCR uses a new adaptive path weight function together with an additional constraint imposed on the path cost, to restrict the search space. Thus, DCCR can return a near-optimal solution in a very short time. Furthermore, we use a variant of the Lagrangian relaxation method proposed by Handler and Zang [Networks 10 (1980) 293] to further reduce the search space by using a tighter bound on path cost. This makes our algorithm more accurate and even faster. We call this improved algorithm search space reduction + DCCR (SSR + DCCR). Through extensive simulations, we confirm that SSR + DCCR performs very well compared to the optimal but very expensive solution.     

A high-throughput and high-capacity IPv6 routing lookup system

With the growing number of routing entries, IP routing lookup has become the major performance bottleneck in backbone routers. In this paper, a complete hardware-based routing lookup system is proposed to achieve high-throughput and high-capacity for IPv6. The proposed system is a cache-centric, hash-based architecture that contains a routing lookup application specific integrated circuit (ASIC) and a memory set. A hash function is used to reduce lookup time for the routing table and ternary content addressable memory (TCAM) effectively resolves the collision problem. The gate count of the ASIC, excluding the binary content addressable memory (BCAM), is about 5306 gates, using an in-house 0.18 μm CMOS single-poly six-metal standard cell library. The results of post-layout simulations show that the ASIC operates in 3.6 ns so that the routing lookup system approaches 260 Mega lookups per second (Mlps), which is sufficient for 100 Gbps networks. The memory density is good, with each routing entry requiring only 64 bits. Moreover, the routing table only needs 10.24 KB on-chip BCAM, 20.04 KB off-chip TCAM and 29.29 MB DRAM for 3.6 M routing entries in the proposed system.     

Finding extreme supported solutions of biobjective network flow problems: An enhanced parametric programming approach

We address the problem of determining a complete set of extreme supported efficient solutions of biobjective minimum cost flow (BMCF) problems. A novel method improving the classical parametric method for this biobjective problem is proposed. The algorithm runs in O(Nn(m + nlogn)) time determining all extreme supported non-dominated points in the outcome space and one extreme supported efficient solution associated with each one of them. Here n is the number of nodes, m is the number of arcs and N is the number of extreme supported non-dominated points in outcome space for the BMCF problem. The memory space required by the algorithm is O(n + m) when the extreme supported efficient solutions are not required to be stored in RAM. Otherwise, the algorithm requires O(N + m) space. Extensive computational experiments comparing the performance of the proposed method and a standard parametric network simplex method are presented.     

A comparative study of different local search application strategies in hybrid metaheuristics

This paper presents results of a comparative study with the objective to identify the most effective and efficient way of applying a local search method embedded in a hybrid algorithm. The hybrid metaheuristic employed in this study is called “DE–HS–HJ” because it is comprised of two cooperative metaheusitic algorithms, i.e., differential evolution (DE) and harmony search (HS), and one local search (LS) method, i.e., Hooke and Jeeves (HJ) direct search. Eighteen different ways of using HJ local search were implemented and all of them were evaluated with 19 problems, in terms of six performance indices, covering both accuracy and efficiency. Statistic analyses were conducted accordingly to determine the significance in performance differences. The test results show that overall the best three LS application strategies are applying local search to every generated solution with a specified probability and also to each newly updated solution (NUS + ESP), applying local search to every generated solution with a specified probability (ESP), and applying local search to every generated solution with probability and also to the updated current global best solution (EUGbest + ESP). ESP is found to be the best local search application strategy in terms of success rate. Integrating it with NUS further improve the overall performance. EUGbest + ESP is the most efficient and it is also able to achieve high level of accuracy (the fourth place in terms of success rate with an average above 0.9).     

Vessel routing and scheduling under uncertainty in the liquefied natural gas business

Liquefied natural gas (LNG) is natural gas transformed into liquid state for the purpose of transportation mainly by specially built LNG vessels. This paper considers a real-life LNG ship routing and scheduling problem where a producer is responsible for transportation from production site to customers all over the world. The aim is to create routes and schedules for the vessel fleet that are more robust with respect to uncertainty such as in sailing times due to changing weather conditions. A solution method and several robustness strategies are proposed and tested on instances with time horizons of 3–12 months. The resulting solutions are evaluated using a simulation model with a recourse optimization procedure. The results show that there is a significant improvement potential by adding the proposed robustness approaches.     

Look-ahead controls of heavy duty trucks on open roads — six benchmark solutions

A benchmark problem for fuel efficient control of a truck on a given road profile has been formulated and solved. Six different solution strategies utilizing varying degrees of off-line and on-line computations are described and compared. A vehicle model is used to benchmark the solutions on different driving missions. The vehicle model was presented at the IFAC AAC 2016 symposium and is compiled from model components validated in previous research projects. The driving scenario is provided as a road slope profile and a desired trip time. The problem to solve is a combination of engine-, driveline- and vehicle-control while fulfilling demands on emissions, driving time, legislative speed, and engine protections. The strength of this publication is the collection of all six different solutions in one paper. This paper is intended to provide a starting point for practicing engineers or researchers who work with optimal and/or model based vehicle control.     

A clonal selection algorithm for urban bus vehicle scheduling

The bus vehicle scheduling problem addresses the task of assigning vehicles to cover the trips in a timetable. In this paper, a clonal selection algorithm based vehicle scheduling approach is proposed to quickly generate satisfactory solutions for large-scale bus scheduling problems. Firstly, a set of vehicle blocks (consecutive trips by one bus) is generated based on the maximal wait time between any two adjacent trips. Then a subset of blocks is constructed by the clonal selection algorithm to produce an initial vehicle scheduling solution. Finally, two heuristics adjust the departure times of vehicles to further improve the solution. The proposed approach is evaluated using a real-world vehicle scheduling problem from the bus company of Nanjing, China. Experimental results show that the proposed approach can generate satisfactory scheduling solutions within 1 min.     

A neural network theory for constrained optimization

A variety of real-world problems can be formulated into continuous optimization problems with constraint equalities. The real-world problem here can include, for example, the traveling salesman problem, the Dido’s isoperimetric problem, the Hitchcock’s transportation problem, the network flow problem and the associative memory problem. In spite of the significance, there has not yet been developed any robust solving method that works efficiently across a broad spectrum of optimization problems. The recent Hopfield’s neural network method to solve the traveling salesman problem is a potentially promising candidate because of the efficiency due to its parallel processing. His method, however, has certain drawbacks that must be removed away before it can be qualified for an efficient, robust solving method. That is: (a) locally minimum solutions instead of globally minimum; (b) possible infeasible solutions; (c) heuristic choice of network parameters and an initial state; (d) quadratic objective functions instead of arbitrary nonlinear objective functions with arbitrary nonlinear equality constraints; and (e) unorganized mathematical formulation of the network for extension. This paper develops from the Hopfield method an efficient, robust network solving method of the continuous optimization problem with constraint equalities that resolves all the drawbacks except for (a) that has already been resolved by others. The development is mathematically rigorous and thus constitutes a solid foundation of a neural network theory for constrained optimization.     

A note on two-stage hybrid flowshop scheduling with missing operations

The scheduling problem in a multi-stage hybrid flowshop has been the subject of considerable research. All the studies on this subject assume that each job has to be processed on all the stages, i.e., there are no missing operations for a job at any stage. However, missing operations usually exist in many real-life production systems, such as a system in a stainless steel factory investigated in this note. The studied production system in the factory is composed of two stages in series. The first stage contains only one machine while the second stage consists of two identical machines (namely a 1 × 2 hybrid flowshop). In the system, some jobs have to be processed on both stages, but others need only to be processed on the second stage. Accordingly, the addressed scheduling problem is a 1 × 2 hybrid flowshop with missing operations at the first stage. In this note, we develop a heuristic for the problem to generate a non-permutation schedule (NPS) from a given permutation schedule, with the objective of minimizing the makespan. Computational results demonstrate that the heuristic can efficiently generate better NPS solutions.     

Energy-efficient topology control algorithm for maximizing network lifetime in wireless sensor networks with mobile sink

Uneven energy consumption is an inherent problem in wireless sensor networks characterized by multi-hop routing and many-to-one traffic pattern. Such unbalanced energy dissipation can significantly reduce network lifetime. In this paper, we study the problem of prolonging network lifetime in large-scale wireless sensor networks where a mobile sink gathers data periodically along the predefined path and each sensor node uploads its data to the mobile sink over a multi-hop communication path. By using greedy policy and dynamic programming, we propose a heuristic topology control algorithm with time complexity O(n(m + n log n)), where n and m are the number of nodes and edges in the network, respectively, and further discuss how to refine our algorithm to satisfy practical requirements such as distributed computing and transmission timeliness. Theoretical analysis and experimental results show that our algorithm is superior to several earlier algorithms for extending network lifetime.     

A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem

We address the problem of determining all extreme supported solutions of the biobjective shortest path problem. A novel Dijkstra-like method generalizing Dijkstra׳s algorithm to this biobjective case is proposed. The algorithm runs in O(N(m+n log n)) time to solve one-to-one and one-to-all biobjective shortest path problems determining all extreme supported non-dominated points in the outcome space and one supported efficient path associated with each one of them. Here n is the number of nodes, m is the number of arcs and N is the number of extreme supported points in outcome space for the one-to-all biobjective shortest path problem. The memory space required by the algorithm is O(n+m) for the one-to-one problem and O(N+m) for the one-to-all problem. A computational experiment comparing the performance of the proposed methods and state-of-the-art methods is included.     

A novel adaptive cuckoo search algorithm for intrinsic discriminant analysis based face recognition

This paper presents a novel adaptive cuckoo search (ACS) algorithm for optimization. The step size is made adaptive from the knowledge of its fitness function value and its current position in the search space. The other important feature of the ACS algorithm is its speed, which is faster than the CS algorithm. Here, an attempt is made to make the cuckoo search (CS) algorithm parameter free, without a Levy step. The proposed algorithm is validated using twenty three standard benchmark test functions. The second part of the paper proposes an efficient face recognition algorithm using ACS, principal component analysis (PCA) and intrinsic discriminant analysis (IDA). The proposed algorithms are named as PCA + IDA and ACS–IDA. Interestingly, PCA + IDA offers us a perturbation free algorithm for dimension reduction while ACS + IDA is used to find the optimal feature vectors for classification of the face images based on the IDA. For the performance analysis, we use three standard face databases—YALE, ORL, and FERET. A comparison of the proposed method with the state-of-the-art methods reveals the effectiveness of our algorithm.     

A hybrid column generation approach for an industrial waste collection routing problem

This paper presents a practical roll-on/roll-off routing (ROROR) problem arising in the collection of industrial waste. Skip containers, which are used for the waste collection, need to be distributed between, and collected from, a set of customers. Full containers must be driven to dump sites, while empty containers must be returned to the depot to await further assignments. Unlike, the traditional ROROR problem, where vehicles may transport one skip container at a time regardless of whether it is full or not, we consider cases in which a vehicle can transport up to eight containers, at most two of which can be full. We propose a generalized set partitioning formulation of the problem and describe a hybrid column generation procedure to solve it. A fast Tabu Search heuristic is used to generate new columns. The proposed methodology is tested on nine data sets, four of which are actual, real-world problem instances. Results indicate that the hybrid column generation outperforms a purely heuristic approach in terms of both running time and solution quality. High quality solutions to problems containing up to 100 orders can be solved in approximately 15 min.     

Integrating Factors for Second-order ODEs

A systematic algorithm for building integrating factors of the form μ(x, y), μ(x, y^′) or μ(y, y^′) for second-order ODEs is presented. The algorithm can determine the existence and explicit form of the integrating factors themselves without solving any differential equations, except for a linear ODE in one subcase of the μ (x, y) problem. Examples of ODEs not having point symmetries are shown to be solvable using this algorithm. The scheme was implemented in Maple, in the framework of the ODEtools package and its ODE-solver. A comparison between this implementation and other computer algebra ODE-solvers in tackling non-linear examples from Kamke's book is shown.     

Bin packing problems with rejection penalties and their dual problems

In this paper we consider the following problems: we are given a set of n items {u₁, … , u_n} and a number of unit-capacity bins. Each item u_i has a size w_i ∈ (0, 1] and a penalty p_i ⩾ 0. An item can be either rejected, in which case we pay its penalty, or put into one bin under the constraint that the total size of the items in the bin is no greater than 1. No item can be spread into more than one bin. The objective is to minimize the total number of used bins plus the total penalty paid for the rejected items. We call the problem bin packing with rejection penalties, and denote it as BPR. For the on-line BPR problem, we present an algorithm with an absolute competitive ratio of 2.618 while the lower bound is 2.343, and an algorithm with an asymptotic competitive ratio arbitrarily close to 1.75 while the lower bound is 1.540. For the off-line BPR problem, we present an algorithm with an absolute worst-case ratio of 2 while the lower bound is 1.5, and an algorithm with an asymptotic worst-case ratio of 1.5. We also study a closely related bin covering version of the problem. In this case p_i means some amount of profit. If an item is rejected, we get its profit, or it can be put into a bin in such a way that the total size of the items in the bin is no smaller than 1. The objective is to maximize the number of covered bins plus the total profit of all rejected items. We call this problem bin covering with rejection (BCR). For the on-line BCR problem, we show that no algorithm can have absolute competitive ratio greater than 0, and present an algorithm with asymptotic competitive ratio 1/2, which is the best possible. For the off-line BCR problem, we also present an algorithm with an absolute worst-case ratio of 1/2 which matches the lower bound.     

Realization strategies of dedicated path protection: A bandwidth cost perspective

Communication networks have to provide a high level of availability and instantaneous recovery after failures in order to ensure sufficient survivability for mission-critical services. Currently, dedicated path protection (or 1 + 1) is implemented in backbone networks to provide the necessary resilience and instantaneous recovery against single link failures with remarkable simplicity. However, in order to satisfy strict availability requirements, connections also have to be resilient against Shared Risk Link Group (SRLG) failures. In addition, switching matrix reconfigurations have to be avoided after a failure in order to guarantee instantaneous recovery. For this purpose, there are several possible realization strategies improving the characteristics of traditional 1 + 1 path protection by lowering reserved bandwidth while conserving all its favorable properties. These methods either utilize diversity coding, network coding, or generalize the disjoint-path constraint of 1 + 1.In this paper, we consider the cost aspect of the traditional and the alternative 1 + 1 realization strategies. We evaluate the bandwidth cost of different schemes both analytically and empirically in realistic network topologies. As the more complex realizations lead to NP-complete problems even in the single link failure case, we propose both Integer Linear Programming (ILP) based optimal methods, as well as heuristic and meta-heuristic approaches to solve them. Our findings provide a tool and guidelines for service providers for selecting the path protection method with the lowest bandwidth cost for their network corresponding to a given level of reliability.     

Thinning combined with iteration-by-iteration smoothing for 3D binary images

In this work we present a new thinning scheme for reducing the noise sensitivity of 3D thinning algorithms. It uses iteration-by-iteration smoothing that removes some border points that are considered as extremities. The proposed smoothing algorithm is composed of two parallel topology preserving reduction operators. An efficient implementation of our algorithm is sketched and its topological correctness for (26, 6) pictures is proved.