An algorithm is presented that is capable of producing Pareto-optimal solutions for multi-objective infrastructure routing problems: the Multi-Objective Ant Colony Optimization (MOACO). This algorithm offers a constructive search technique to develop solutions to different types of infrastructure routing problems on an open grid framework. The algorithm proposes unique functions such as graph pruning and path straightening to enhance both speed and performance. It also possesses features to solve issues unique to infrastructure routing not found in existing MOACO algorithms, such as problems with multiple end points or multiple possible start points. A literature review covering existing MOACO algorithms and the Ant Colony algorithms they are derived from is presented. Two case studies are developed to demonstrate the performance of the algorithm under different infrastructure routing scenarios. In the first case study the algorithm is implemented into the Ice Road Planning module within the North Slope Decision Support System (NSDSS). Using this ice road planning module a case study is developed of the White Hills Ice road to test the performance of the algorithm versus an as-built road. In the second case study, the algorithm is applied to a raw water transmission routing problem in the Region C planning zone of Texas. For both case studies the algorithm produces a set of results which are similar to the preliminary designs. By successfully applying the algorithm to two separate case studies the suitability of the algorithm to different types of infrastructure routing problems is demonstrated.

This thesis presents a novel algorithm called ant colony optimization with dual pheromone tables (ACODPT) for improving the quality of ant colony optimization (ACO). The proposed algorithm works by adding a so-called ¡§negative¡¨ pheromone table to ACO to avoid the problem of ACO easily falling into local optima. By using the ¡§negative¡¨ pheromone table to eliminate the most impossible path to search for the new solution, the probability of selecting the remaining paths is increased, and so is the quality. To evaluate the performance of the proposed algorithm, ACODPT is compared with several state-of-the-art algorithms in solving the clustering problem. The experimental results show that the proposed algorithm can eventually prevent ACO from falling into local optima in the early iterations, thus providing a better result than the other algorithms in many cases.

No description available.

This study provides heuristic approaches, including an ant colony optimization (ACO) inspired heuristic, to solve a crane scheduling problem that exists in most shipyards, where cranes are a primary means of processing and handling materials. Cranes move on a network of tracks, thus, blocking of crane movements is an issue. The crane scheduling problem consists of two major sub-problems: scheduling problem that determines the best overall order in which jobs are to be performed; the assignment problem that assigns cranes to jobs. The proposed heuristic consists of an Earliest Due Date sorting procedure in combination with an ACO assignment procedure that aims to satisfy the objectives of minimizing makespan while maximizing crane utilization. Test data sets of various sizes are generated and the results of the proposed approach are compared to other developed heuristics. The proposed approach outperforms others in both objective measures and obtains solutions in a timely manner.

The aim of this work is to investigate Ant Colony Algorithm for the traveling salesman problem (TSP). Ants of the artificial colony are able to generate successively shorter feasible tours by using information accumulated in the form of a pheromone trail deposited on the edges of the TSP graph. This paper is based on the ideas of ant colony algorithm and analysis the main parameters of the ant colony algorithm. Experimental results for solving TSP problems with ant colony algorithm show great effectiveness.

The traditional mobile radio channel has always suffered from the detrimental effects of multipath fading. The use of multiple antennae at both ends of the wireless channel has proven to be very effective in combatting fading and enhancing the channel's spectral efficiency. To exploit the benefits offered by Multi-Input Multi-Output (MIMO) systems, both the transmitter and the receiver have to be optimally designed. In this thesis, we are concerned with the problem of receiver design for MIMO systems in a spatial multiplexing scheme. The MIMO detection problem is an NP-hard combinatorial optimization problem. Solving this problem to optimality requires an exponential search over the space of all possible transmitted symbols in order to find the closest point in a Euclidean sense to the received symbols; a procedure that is infeasible for large systems. We introduce a new heuristic algorithm for the detection of a MIMO wireless system based on the Ant Colony Optimization (ACO) metaheuristic. The new algorithm, AntMIMO, has a simple architecture and achieves near maximum likelihood performance in polynomial time.

The traffic signal optimization problem is to find a traffic signal setting in a traffic network such that vehicles could arrive at their destination with minimum waiting time. The design of traffic signal setting to decrease waiting time for vehicles moving on the roads in urban city is important but difficult. In this thesis, we use a graph model to represent a traffic network. We propose two signal setting algorithms, a fast heuristic approach and an evolutionary algorithm based on the ant colony optimization (ACO) method, to give a good traffic signal setting. The results show that we could find better solutions by ACO algorithms, and the heuristic algorithm is faster but gets more total waiting time for vehicles. Furthermore, we transform the traffic network data of Kaohsiung city in Taiwan into our traffic graph model and test our algorithm on this traffic graph.

In this thesis, the Hybrid Genetic Algorithm-Ant Colony Optimization (GACO) approach is presented to solve the unit commitment problem (UC), and comparison with the results obtained using literature methods. Then this thesis applied the ability of the Genetic Algorithm (GA) operated after Ant Colony Optimization (ACO) can promote the ACO efficiency. The objective of GA is to improve the searching quality of ants by optimizing themselves to generate a better result, because the ants produced randomly by pheromone process are not necessary better. This method can not only enhance the neighborhood search, but can also search the optimum solution quickly to advance convergence. The other objective of this thesis is to investigate an influence of emission constraints on generation scheduling. The motivation for this objective comes from the efforts to reduce negative trends in a climate change. In this market structure, the independent power producers have to deal with several complex issues arising from uncertainties in spot market prices, and technical constraints which need to be considered while scheduling generation and trading for the next day. In addition to finding dispatch and unit commitment decisions while maximizing its profit, their scheduling models should include trading decisions like spot-market buy and sell. The model proposed in this thesis build on the combined carbon finance and spot market formulation, and help generators in deciding on when these commitments could be beneficial.

Ant Colony Optimization is a relatively new meta-heuristic that has proven its quality and versatility on various combinatorial optimization problems such as the traveling salesman problem, the vehicle routing problem and the job shop scheduling problem. The paper introduces an Ant Colony Optimization approach to solve the problem of determining a job-sequence that minimizes the overall tardiness for a given set of jobs to be processed on a single, continuously available machine, the Single Machine Total Tardiness Problem. We experiment with various heuristic information as well as with variants for local search. Experiments with 250 benchmark problems with 50 and 100 jobs illustrate that Ant Colony Optimization is an adequate method to tackle the SMTTP. (author's abstract) / Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

Combinatorial optimization problems are of high academical as well as practical importance. Many instances of relevant combinatorial optimization problems are, due to their dimensions, intractable for complete methods such as branch and bound. Therefore, approximate algorithms such as metaheuristics received much attention in the past 20 years. Examples of metaheuristics are simulated annealing, tabu search, and evolutionary computation. One of the most recent metaheuristics is ant colony optimization (ACO), which was developed by Prof. M. Dorigo (who is the supervisor of this thesis) and colleagues. This thesis deals with theoretical as well as practical aspects of ant colony optimization. * A survey of metaheuristics. Chapter 1 gives an extensive overview on the nowadays most important metaheuristics. This overview points out the importance of two important concepts in metaheuristics: intensification and diversification. * The hyper-cube framework. Chapter 2 introduces a new framework for implementing ACO algorithms. This framework brings two main benefits to ACO researchers. First, from the point of view of the theoretician: we prove that Ant System (the first ACO algorithm to be proposed in the literature) in the hyper-cube framework generates solutions whose expected quality monotonically increases with the number of algorithm iterations when applied to unconstrained problems. Second, from the point of view of the experimental researcher, we show through examples that the implementation of ACO algorithms in the hyper-cube framework increases their robustness and makes the handling of the pheromone values easier. * Deception. In the first part of Chapter 3 we formally define the notions of first and second order deception in ant colony optimization. Hereby, first order deception corresponds to deception as defined in the field of evolutionary computation and is therefore a bias introduced by the problem (instance) to be solved. Second order deception is an ACO-specific phenomenon. It describes the observation that the quality of the solutions generated by ACO algorithms may decrease over time in certain settings. In the second part of Chapter 3 we propose different ways of avoiding second order deception. * ACO for the KCT problem. In Chapter 4 we outline an ACO algorithm for the edge-weighted k-cardinality tree (KCT) problem. This algorithm is implemented in the hyper-cube framework and uses a pheromone model that was determined to be well-working in Chapter 3. Together with the evolutionary computation and the tabu search approaches that we develop in Chapter 4, this ACO algorithm belongs to the current state-of-the-art algorithms for the KCT problem. * ACO for the GSS problem. Chapter 5 describes a new ACO algorithm for the group shop scheduling (GSS) problem, which is a general shop scheduling problem that includes among others the well-known job shop scheduling (JSS) and the open shop scheduling (OSS) problems. This ACO algorithm, which is implemented in the hyper-cube framework and which uses a new pheromone model that was experimentally tested in Chapter 3, is currently the best ACO algorithm for the JSS as well as the OSS problem. In particular when applied to OSS problem instances, this algorithm obtains excellent results, improving the best known solution for several OSS benchmark instances. A final contribution of this thesis is the development of a general method for the solution of combinatorial optimization problems which we refer to as Beam-ACO. This method is a hybrid between ACO and a tree search technique known as beam search. We show that Beam-ACO is currently a state-of-the-art method for the application to the existing open shop scheduling (OSS) problem instances.