In order to overcome the demerits of traditional city air terminals (CAT), a brand-new service mode based on urban mobile stations (UMS) is introduced in this article for providing the luggage check-in service in urban area. Different from CAT, for each service time period, the UMSs are located based on the real-time passenger distributions. The objectives are to improve the service quality and enhance the competitiveness of air transportation. First, the system components and operation mode of UMS are described. Second, a mathematical model is set up for locating UMSs and assigning passengers to service stations. Three aspects, including the average path length from passengers to UMSs, the maximum acceptable path length for passengers, and the maximum service capacity of a station are considered. Third, to meet the strict time requirement of the UMS system, an effective evolutionary algorithm for optimizing UMS locations in real time is further developed. In the method, the ripple-spreading algorithm is applied for solving the many-to-many path optimization problem and a two-stage adaptive genetic algorithm is utilised for efficiently locating UMSs. Finally, a test case is set up based on the city centre of Tianjin, China, and passenger source locations are obtained by surveying passengers at Tianjin Airport. The reported method is then applied to dynamically locate UMSs in Tianjin urban area and it is compared to some other existing methods to show its effectiveness and efficiency. The service quality of UMS is compared to CAT in both cases with realistic data and randomly generated data to show its advantages.

City air terminals are small-scale terminals located in city center for airport transport service. To optimize the locations of city air terminals, first, a mathematic model of the problem is introduced. Three aspects including the average distance from passengers to city air terminals, the maximum tolerable path length, and the maximum terminal volume are considered. Then, a novel hybrid algorithm is proposed. In the method, the ripple-spreading algorithm is applied for solving the many-to-many path optimization problem and a genetic algorithm is used for locating city air terminals. In order to improve the performance and increase the convergence speed, a self-adaptive genetic algorithm is further developed, varying the genetic operations and the number of generations according to the current convergence status. A test case is set up based on the city center of Tianjin, China. The proposed method is tested and compared to some other existing methods to show its effectiveness and efficiency.

Inspired by the multi-agent co-evolving nature reflected in many methods of evolutionary computation, this paper proposes a challenging routing problem - co-evolutionary path optimization (CEPO). Static path optimization (SPO) is a foundation of computational intelligence, but in reality, the routing environment is usually time-varying (e.g., moving obstacles, spreading disasters and uncertainties), and therefore dynamic path optimization (DPO) has to be addressed. To resolve DPO, a common practice is as following: at each time t, environmental parameters are measured/predicted first, and then the best path is re-calculated by resolving SPO based on the newly measured/predicted environmental parameters. In other words, during the path optimization process of time t, the routing environment is actually fixed and static. Usually, DPO cannot lead to optimal actual travelling trajectory, and it demands high online computation capacity. Distinguishing from DPO, in CEPO, future environmental parameters keep changing during the optimization process of time t. In other words, the routing environment co-evolves within the path optimization process of time t. No existing method can address CEPO without losing optimality or efficiency. This paper then reports a ripple-spreading algorithm (RSA), which can resolve CEPO with both optimality and efficiency. Surprisingly, in just a single offline run of RSA for the CEPO, the optimal actual travelling trajectory can be achieved in a given dynamical routing environment. Simulation results clearly demonstrate that: (i) the solutions to CEPO are far better than those to DPO, and (ii) the reported RSA is an effective and efficient method for addressing CEPO.

The k shortest paths problem (k-SPP) has a wide application background. Inspired by the natural ripple-spreading phenomenon that occurs on a water surface, we have recently proposed an original ripple-spreading algorithm (RSA) for the k-SPP. However, the computational efficiency of the reported algorithm is poor. This paper is concerned with how to improve the scalability of RSA for the k-SPP. To this end, two methods are proposed in this study. One is to impose an upper bound of k as the maximal number of ripples a node may generate. The other is to start ripple relay race from both the source and the destination simultaneously. Some theoretical analyses on the optimality and time complexity of improved RSA for the k-SPP are given. Surprisingly, the improved RSA can be extended from one-to-one k-SPP to one-to-all k-SPP, with no increase in computational complexity. The experimental results demonstrate the effectiveness and efficiency of the proposed methods.

It is a challenging task to find the k shortest paths in a time-window network, where a node may have some specific time windows only within which is the node accessible. Existing research assumes that a traveller can pass through an accessible node immediately or wait to pass at start times of future time windows at the node. This paper targets at a more general case where a traveller, once arriving at a node, may choose to pass through the node at any discrete time in the time windows of the node. In such a generalized time-window network, the degree of complexity increases significantly, as the size of solution space soars up exponentially. By mimicking the natural ripple-spreading phenomenon on a liquid surface, we propose an effective ripple-spreading algorithm (RSA) for the k shortest paths problem in a generalized time-window network (k-SPPGTW). Besides one-to-one k-SPPGTW, the RSA is also extended to one-to-all k-SPPGTW, where all the k shortest paths from a given source to every other node in the network need to be found. The new method has a theoretical guarantee of optimality. The computational complexity of the reported RSA is just 0(k×NATU×NL), where Nlis the number of links in the network, and Natu is the average simulated time units for a ripple to travel through a link. The effectiveness and efficiency of the reported RSA for the k-SPPGTW are demonstrated by some preliminary experimental results.

Inspirations from nature have contributed fundamentally to the development of evolutionary computation. Learning from the natural ripple-spreading phenomenon, this article proposes a novel ripple-spreading algorithm (RSA) for the path optimization problem (POP). In nature, a ripple spreads at a constant speed in all directions, and the node closest to the source is the first to be reached. This very simple principle forms the foundation of the proposed RSA. In contrast to most deterministic top-down centralized path optimization methods, such as Dijkstra's algorithm, the RSA is a bottom-up decentralized agent-based simulation model. Moreover, it is distinguished from other agent-based algorithms, such as genetic algorithms and ant colony optimization, by being a deterministic method that can always guarantee the global optimal solution with very good scalability. Here, the RSA is specifically applied to four different POPs. The comparative simulation results illustrate the advantages of the RSA in terms of effectiveness and efficiency. Thanks to the agent-based and deterministic features, the RSA opens new opportunities to attack some problems, such as calculating the exact complete Pareto front in multiobjective optimization and determining the kth shortest project time in project management, which are very difficult, if not impossible, for existing methods to resolve. The ripple-spreading optimization principle and the new distinguishing features and capacities of the RSA enrich the theoretical foundations of evolutionary computation.

Inspired by the temporal receding horizon control in control engineering, this paper reports a novel spatial receding horizon control (SRHC) strategy to partition the facility location optimization problem (FLOP), in order to reduce the complexity caused by the problem scale. Traditional problem partitioning methods can be viewed as a special case of the proposed SRHC, i.e., one-step-wide SRHC, whilst the method in this paper is a generalized N-step-wide SRHC, which can make a better use of global information of the route network where a given number of facilities need to be set up. With SRHC to partition the FLOP, genetic algorithm (GA) is integrated as optimizer to resolve the partitioned problem within each spatial receding horizon. On one hand, SRHC helps to improve the scalability of GA. On the other, the population feature of GA helps to reduce the shortsighted performance of SRHC. The effectiveness and efficiency of the reported SRHC and GA for the FLOP are demonstrated by comparative simulation results.

Existing methods for multi-objective optimization usually provide only an approximation of a Pareto front, and there is little theoretical guarantee of finding the real Pareto front. This paper is concerned with the possibility of fully determining the true Pareto front for those continuous multi-objective optimization problems for which there are a finite number of local optima in terms of each single objective function and there is an effective method to find all such local optima. To this end, some generalized theoretical conditions are firstly given to guarantee a complete cover of the actual Pareto front for both discrete and continuous problems. Then based on such conditions, an effective search procedure inspired by the rising sea level phenomenon is proposed particularly for continuous problems of the concerned class. Even for general continuous problems to which not all local optima are available, the new method may still work well to approximate the true Pareto front. The good practicability of the proposed method is especially underpinned by multi-optima evolutionary algorithms. The advantages of the proposed method in terms of both solution quality and computational efficiency are illustrated by the simulation results.

Searching the Pareto front for multiobjective optimization problems usually involves the use of a population-based search algorithm or of a deterministic method with a set of different single aggregate objective functions. The results are, in fact, only approximations of the real Pareto front. In this paper, we propose a new deterministic approach capable of fully determining the real Pareto front for those discrete problems for which it is possible to construct optimization algorithms to find the k best solutions to each of the single-objective problems. To this end, two theoretical conditions are given to guarantee the finding of the actual Pareto front rather than its approximation. Then, a general methodology for designing a deterministic search procedure is proposed. A case study is conducted, where by following the general methodology, a ripple-spreading algorithm is designed to calculate the complete exact Pareto front for multiobjective route optimization. When compared with traditional Pareto front search methods, the obvious advantage of the proposed approach is its unique capability of finding the complete Pareto front. This is illustrated by the simulation results in terms of both solution quality and computational efficiency.

When genetic algorithms (GAs) are applied to combinatorial problems, permutation representations are usually adopted. As a result, such GAs are often confronted with feasibility and memory-efficiency problems. With the aircraft sequencing problem (ASP) as a study case, this paper reports on a novel binary-representation-based GA scheme for combinatorial problems. Unlike existing GAs for the ASP, which typically use permutation representations based on aircraft landing order, the new GA introduces a novel ripple-spreading model which transforms the original landing-order-based ASP solutions into value-based ones. In the new scheme, arriving aircraft are projected as points into an artificial space. A deterministic method inspired by the natural phenomenon of ripple-spreading on liquid surfaces is developed, which uses a few parameters as input to connect points on this space to form a landing sequence. A traditional GA, free of feasibility and memory-efficiency problems, can then be used to evolve the ripple-spreading related parameters in order to find an optimal sequence. Since the ripple-spreading model is the centerpiece of the new algorithm, it is called the ripple-spreading GA (RSGA). The advantages of the proposed RSGA are illustrated by extensive comparative studies for the case of the ASP.

The network coding problem (NCP) is an NP-hard combinatorial problem, and genetic algorithms (GAs) have recently been applied to address this problem. This paper reports a novel ripple-spreading GA (RSGA) for the NCP. In contrast to existing GAs where a chromosome directly represents a solution, the proposed RSGA separates chromosomes and solutions by introducing a purpose-designed pre-problem for the NCP. In the pre-problem, the nodes in the NCP are projected into an artificial space, in which some ripple epicenters are randomly generated. Then a specially parameterized ripple-spreading process is employed such that as ripples (starting from the epicenters) spread out in the artificial space, the incoming signals and outgoing signals of all nodes will be individually determined, according to the amplitudes of the ripples which have reached the node. Changing the values of the ripple-spreading parameters will result in different information flows in the networks. Therefore, a simple binary-string based GA, unlike existing GAs which employ permutation representations for the NCP, can be used to optimize the values of the ripple-spreading parameters, in order to find a good solution to the NCP. A potential advantage of the RSGA is its scalability in complex networks, where permutation representation based GAs may face serious memory-efficiency problems. The effectiveness of the proposed RSGA is illustrated in the context of some experiments.

The optimization of network coding is a relatively new area for evolutionary algorithms, as very few efforts have so far been reported. This paper is concerned with the design of an effective genetic algorithm (GA) for tackling the network coding problem (NCP). Differing from previous relevant works, the proposed GA is designed based on a permutation representation, which not only allows each chromosome to record a specific network protocol and coding scheme, but also makes it easy to integrate useful problem-specific heuristic rules into the algorithm. In the new GA, a more general fitness function is proposed, which, besides considering the minimization of network coding resources, also takes into account the maximization of the rate actually achieved. This new fitness function makes the proposed GA more suitable for the case of dynamic network coding, where any link could be cut off at any time, and consequently, the target rate might become unachievable even if all nodes allow coding. Based on the new representation and fitness function, other GA related techniques are modified and employed accordingly and carefully. Comparative experiments show that the proposed GA clearly outperforms previous methods.

Since the Gate Assignment Problem (GAP) at airport terminals is a combinatorial optimization problem, permutation representations based on aircraft dwelling orders are typically used in the implementation of Genetic Algorithms (GAs), The design of such GAs is often confronted with feasibility and memory-efficiency problems. This paper proposes a hybrid GA, which transforms the original order based GAP solutions into value based ones, so that the basic a binary representation and all classic evolutionary operations can be applied free of the above problems. In the hybrid GA scheme, aircraft queues to gates are projected as points into a parameterized space. A deterministic model inspired by the phenomenon of natural ripple-spreading on liquid surfaces is developed which uses relative spatial parameters as input to connect all aircraft points to construct aircraft queues to gates, and then a traditional binary GA compatible to all classic evolutionary operators is used to evolve these spatial parameters in order to find an optimal or near-optimal solution. The effectiveness of the new hybrid GA based on the ripple-spreading model for the GAP problem are illustrated by experiments.

Recently complex network theory has been broadly applied in various domains. How to effectively and efficiently optimize the topology of complex networks remains largely an unsolved fundamental question. When applied to the network topology optimization, Genetic Algorithms (GAs) are often confronted with permutation representation, memory-inefficiency and stochastic modeling problems, as well as difficulties in the design of problem-specific evolutionary operators. This paper, inspired by the natural ripple spreading phenomenon, reports a deterministic model of random complex networks. Unlike existing stochastic models, the topology of a random network can be thoroughly determined by some ripple-spreading related parameters in the new model. Therefore, the network topology can be improved by optimize these ripple-spreading related parameters. As a result, no purpose-designed GA is required, but a very basic binary GA, compatible to all classic evolutionary operators, can be applied in a straightforward way. Preliminary simulation results demonstrate the potential of the proposed ripple-spreading model and GA for the topology optimization of random complex networks.

Arrival sequencing and scheduling (ASS) at airports is an NP-hard problem. Much effort has been made to use permutation-representation-based genetic algorithms (GAs) to tackle this problem, whereas this paper attempts to design an efficient GA based on a binary representation of arriving queues. Rather than using the order and/or arriving time of each aircraft in the queue to construct chromosomes for GAs, this paper uses the neighboring relationship between each pair of aircraft, and the resulted chromosome is a 0-1-valued matrix. A big advantage of this binary representation is a highly efficient uniform crossover operator, which is normally not applicable to those permutation representations. The strategy of receding horizon control (RHC) is also integrated into the new GA to attack the dynamic ASS problem. An extensive comparative simulation study shows that the binary-representation-based GA outperforms the permutation-representation-based GA.

Genetic Algorithms (GAs) have a good potential of solving the Gate Assignment Problem (GAP) at airport terminals, and the design of feasible and efficient evolutionary operators, particularly, the crossover operator, is crucial to successful implementations. This paper reports an application of GAs to the multi-objective GAP. The relative positions between aircraft rather than their absolute positions in the queues to gates is used to construct chromosomes in a novel encoding scheme, and a new uniform crossover operator, free of feasibility problems, is then proposed, which is effective and efficient to identify, inherit and protect useful common sub-queues to gates during evolution. Extensive simulation studies illustrate the advantages of the proposed GA scheme with uniform crossover operator.

The inability of airport capacity to meet the growing air traffic demand is a major cause of congestion and costly delays. Airport capacity management (ACM) in a dynamic environment is crucial for the optimal operation of an airport. This paper reports on a novel method to attack this dynamic problem by integrating the concept of receding horizon control (RHC) into a genetic algorithm (GA). A mathematical model is set up for the dynamic ACM problem in a multiairport system where flights can be redirected between airports. A GA is then designed from an RHC point of view. Special attention is paid on how to choose those parameters related to the receding horizon and terminal penalty. A simulation study shows that the new RHC-based GA proposed in this paper is effective and efficient to solve the ACM problem in a dynamic multiairport environment

Airports, especially busy hub airports, proved to be the bottleneck resources in the air traffic control system. How to carry out arrival scheduling and sequencing effectively and efficiently is one of main concerns to improve the safety, capacity, and efficiency of the airports. This paper introduces the concept of receding horizon control (RHC) to the problem of arrival scheduling and sequencing in a dynamic environment. The potential benefits RHC could bring in terms of airborne delay and computational burden are investigated by means of Monte Carlo simulations. It is pointed out that while achieving similar performance as existing schemes, the new arrival scheduling and sequencing scheme significantly reduces the computational burden and provides potential for developing new optimization algorithms for further reducing airborne delay.