A particle swarm optimization-based hybrid algorithm for minimum concave cost network flow problems

Traditionally, minimum cost transshipment problems have been simplified as linear cost problems, which are not practical in real applications. Some advanced local search algorithms have been developed to solve concave cost bipartite network problems. These have been found to be more effective than the traditional linear approximation methods and local search methods. Recently, a genetic algorithm and an ant colony system algorithm were employed to develop two global search algorithms for solving concave cost transshipment problems. These two global search algorithms were found to be more effective than the advanced local search algorithms for solving concave cost transshipment problems. Although the particle swarm optimization algorithm has been used to obtain good results in many applications, to the best of our knowledge, it has not yet been applied in minimum concave cost network flow problems. Thus, in this study, we employ an arc-based particle swarm optimization algorithm, coupled with some genetic algorithm and threshold accepting method techniques, as well as concave cost network heuristics, to develop a hybrid global search algorithm for efficiently solving minimum cost network flow problems with concave arc costs. The proposed algorithm is evaluated by solving several randomly generated network flow problems. The results indicate that the proposed algorithm is more effective than several other recently designed methods, such as local search algorithms, genetic algorithms and ant colony system algorithms, for solving minimum cost network flow problems with concave arc costs.     

Meta-heuristic algorithms for wafer sorting scheduling problems

Wafer sorting is usually regarded as the most critical stage in the whole wafer probing process. This paper discusses the wafer sorting scheduling problem (WSSP) with total setup time minimization as the primary criterion and the minimization of the number of machines used as the secondary criterion. Although the need to consider multiple criteria in real-world WSSPs is widely recognized, the present study is the first attempt to investigate this argument with setups consideration. In view of the strongly NP-hard nature of this problem, three meta-heuristic algorithms—an ant colony system algorithm, a Genetic algorithm, and a Tabu search algorithm are proposed. The proposed meta-heuristics are empirically evaluated by 480 simulation instances based on the characteristics of a real wafer testing shop-floor and found to be very effective in terms of finding good quality solutions.     

A Hybrid Meta-Heuristic for the Batching Problem in Just-In-Time Flow Shops

This paper is concerned with a batching problem encountered in the context of production smoothing in just-in-time manufacturing systems. The manufacturing system of interest is a multi-level system with a flow-shop at the final level. We develop a hybrid meta-heuristic method to solve the batching problem, which is known to be NP-hard. We hybridize strategic oscillation (SO) and path re-linking (PR) methods and compare the hybrid method's performance to two benchmark methods: a bounded dynamic programming method developed for the problem earlier and an implementation of robust tabu search (RTS) meta-heuristic. Through a computational study, we show that the proposed hybrid method is effective in solving the problem within several minutes of computer time and yielding near-optimal results.     

A multi-objective multi-population ant colony optimization for economic emission dispatch considering power system security

With increasing concern about global warming and haze, environmental issue has drawn more attention in daily optimization operation of electric power systems. Economic emission dispatch (EED), which aims at reducing the pollution by power generation, has been proposed as a multi-objective, non-convex and non-linear optimization problem. In a practical power system, the problem of EED becomes more complex due to conflict between the objectives of economy and emission, valve-point effect, prohibited operation zones of generating units, and security constraints of transmission networks. To solve this complex problem, an algorithm of a multi-objective multi-population ant colony optimization for continuous domain (MMACO_R) is proposed. MMACO_R reconstructs the pheromone structure of ant colony to extend the original single objective method to multi-objective area. Furthermore, to enhance the searching ability and overcome premature convergence, multi-population ant colony is also proposed, which contains ant populations with different searching scope and speed. In addition, a Gaussian function based niche search method is proposed to enhance distribution and accuracy of solutions on the Pareto optimal front. To verify the performance of MMACO_R in different multi-objective problems, benchmark tests have been conducted. Finally, the proposed algorithm is applied to solve EED based on a six-unit system, a ten-unit system and a standard IEEE 30-bus system. Simulation results demonstrate that MMACO_R is effective in solving economic emission dispatch in practical power systems.     

Path Relinking, Cycle-Based Neighbourhoods and Capacitated Multicommodity Network Design

In this paper, we propose a path relinking procedure for the fixed-charge capacitated multicommodity network design problem. Cycle-based neighbourhoods are used both to move along paths between elite solutions and to generate the elite candidate set by a tabu-like local search procedure. Several variants of the method are implemented and compared. Extensive computational experiments indicate that the path relinking procedure offers excellent results. It systematically outperforms the cycle-based tabu search method in both solution quality and computational effort and offers the best current meta-heuristic for this difficult class of problems.     

Design method using hybrid of line-type and circular-type routes for transit network system optimization

Transit network design is a very important problem. In particular, it has a great influence on passenger satisfaction with the whole transit network system. The present research proposes a simulated annealing (SA) method for optimizing a transit network design. In the algorithm, the strategy to search for neighborhood solutions provides the chance to find the best hybrid of line-type and circular-type routes. The proposed SA method is also compared with other methods. The results show that the proposed SA model is a good alternative for transit network design, particularly as it provides the scope to design hybrids of line-type and circular-type routes.     

Hub location–allocation in intermodal logistic networks

Within the context of intermodal logistics, the design of transportation networks becomes more complex than it is for single mode logistics. In an intermodal network, the respective modes are characterized by the transportation cost structure, modal connectivity, availability of transfer points and service time performance. These characteristics suggest the level of complexity involved in designing intermodal logistics networks. This research develops a mathematical model using the multiple-allocation p-hub median approach. The model encompasses the dynamics of individual modes of transportation through transportation costs, modal connectivity costs, and fixed location costs under service time requirements. A tabu search meta-heuristic is used to solve large size (100 node) problems. The solutions obtained using this meta-heuristic are compared with tight lower bounds developed using a Lagrangian relaxation approach. An experimental study evaluates the performance of the intermodal logistics networks and explores the effects and interactions of several factors on the design of intermodal hub networks subject to service time requirements.     

基于改进蚁群算法的最短路径问题研究及应用

蚁群系统作为一种蚁群算法是解决最短路径问题的一种行之有效的方法.然而,它自身也存在着一些缺陷,主要针对基本蚁群算法易陷入局部最优这一缺陷对其进行改进,集中体现在初始信息素求解和信息素更新这两方面.为了进一步了解改进蚁群算法的优点,进行了实验仿真:将改进的蚁群算法应用子模拟医疗救护GIS中,利用GIS的网络分析功能对城市道路网络的最短路径选择算法进行了深入地探讨研究,并以山西省太原市的交通路线作为实例进行研究.计算机仿真结果表明,改进的蚁群算法在解决最短路径问题时较基本蚁群算法的性能好,它具有一定的理论参考价值和现实意义.     

Meta-heuristic approaches with memory and evolution for a multi-product production/distribution system design problem

We consider a multi-product two-stage production/distribution system design problem (PDSD) where a fixed number of capacitated distribution centers are to be located with respect to capacitated suppliers (plants) and retail locations (customers) while minimizing the total costs in the system. We present a mixed-integer problem formulation that facilitates the development of efficient heuristic procedures. We provide meta-heuristic procedures, including a population-based scatter search with path relinking and trajectory-based local and tabu search, for the solution of the problem. We also develop efficient construction heuristics and transshipment heuristics that are incorporated into the heuristic procedures for the solution of subproblems. We present extensive computational results that show the high performance of the solution approaches. We obtain smaller than 1.0% average optimality gaps with acceptable runtimes, even for relatively large problems. The computational results also demonstrate the effectiveness of the construction and transshipment heuristics that impact the solution quality and overall runtimes.     

A critical-shaking neighborhood search for the yard allocation problem

The yard allocation problem (YAP) is a real-life resource allocation problem faced by the Port of Singapore Authority (PSA). As the problem is NP-hard, we propose an effective meta-heuristic procedure, named critical-shaking neighborhood search. Extensive experiments have shown that the new method can produce higher quality solutions in a much shorter time, as compared with other meta-heuristics in the literature. Further to this, it has also improved or at least achieved the current best solutions to all the benchmark instances of the problem.     

Progressive hedging as a meta-heuristic applied to stochastic lot-sizing

In a great many situations, the data for optimization problems cannot be known with certainty and furthermore the decision process will take place in multiple time stages as the uncertainties are resolved. This gives rise to a need for stochastic programming (SP) methods that create solutions that are hedged against future uncertainty. The progressive hedging algorithm (PHA) of Rockafellar and Wets is a general method for SP. We cast the PHA in a meta-heuristic framework with the sub-problems generated for each scenario solved heuristically. Rather than using an approximate search algorithm for the exact problem as is typically the case in the meta-heuristic literature, we use an algorithm for sub-problems that is exact in its usual context but serves as a heuristic for our meta-heuristic. Computational results reported for stochastic lot-sizing problems demonstrate that the method is effective.     

一种改进的禁忌搜索算法及其在连续全局优化中的应用

禁忌搜索算法是一种元启发式的全局优化算法,是局部搜索算法的一种推广,已被成功地应用于许多组合优化问题中。本文针对有界闭区域上的连续函数全局优化问题,提出了一种改进的禁忌搜索算法,并进行了理论分析和数值实验。数值实验表明,对于连续函数全局优化问题的求解该算法是可行有效的,并且结构简单,迭代次数较少,是一种较好的全局启发式优化算法。     

Focused simulated annealing search: An application to job shop scheduling

This paper presents a simulated annealing search procedure developed to solve job shop scheduling problems simultaneously subject to tardiness and inventory costs. The procedure is shown to significantly increase schedule quality compared to multiple combinations of dispatch rules and release policies, though at the expense of intense computational efforts. A meta-heuristic procedure is developed that aims at increasing the efficiency of simulated annealing by dynamically inflating the costs associated with major inefficiencies in the current solution. Three different variations of this procedure are considered. One of these variations is shown to yield significant reductions in computation time, especially on problems where search is more likely to get trapped in local minima. We analyze why this variation of the meta-heuristic is more effective than the others.     

Discrete particle swarm optimization for the team orienteering problem

Orienteering problem is a well researched routing problem which is a generalization of the traveling salesman problem. Team orienteering problem (TOP) is the extended version of the orienteering problem with more than one member in the team. In this paper the first known discrete particle swarm optimization (DPSO) algorithm has been developed for 2, 3 and 4-member TOP. In the DPSO meta-heuristic novel methods have been introduced for the initial particle generation process. Reduced variable neighborhood search and 2-opt were applied as the local search tools. The efficacy of the algorithm was tested using seven commonly used benchmark problem sets ranging in size from 21 to 102 nodes. The results of the DPSO algorithm were compared against seven other heuristic algorithms that have been developed for TOP. It was concluded that the developed DPSO algorithm for the TOP is competitive and robust across the benchmark problem sets.     

A hybrid scatter search/electromagnetism meta-heuristic for project scheduling

In the last few decades, several effective algorithms for solving the resource-constrained project scheduling problem have been proposed. However, the challenging nature of this problem, summarised in its strongly NP-hard status, restricts the effectiveness of exact optimisation to relatively small instances. In this paper, we present a new meta-heuristic for this problem, able to provide near-optimal heuristic solutions for relatively large instances. The procedure combines elements from scatter search, a generic population-based evolutionary search method, and from a recently introduced heuristic method for the optimisation of unconstrained continuous functions based on an analogy with electromagnetism theory. We present computational experiments on standard benchmark datasets, compare the results with current state-of-the-art heuristics, and show that the procedure is capable of producing consistently good results for challenging instances of the resource-constrained project scheduling problem. We also demonstrate that the algorithm outperforms state-of-the-art existing heuristics.     

Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation

Hub and spoke type networks are often designed to solve problems that require the transfer of large quantities of commodities. This can be an extremely difficult problem to solve for constructive approaches such as ant colony optimisation due to the multiple optimisation components and the fact that the quadratic nature of the objective function makes it difficult to determine the effect of adding a particular solution component. Additionally, the amount of traffic that can be routed through each hub is constrained and the number of hubs is not known a-priori. Four variations of the ant colony optimisation meta-heuristic that explore different construction modelling choices are developed. The effects of solution component assignment order and the form of local search heuristics are also investigated. The results reveal that each of the approaches can return optimal solution costs in a reasonable amount of computational time. This may be largely attributed to the combination of integer linear preprocessing, powerful multiple neighbourhood local search heuristic and the good starting solutions provided by the ant colonies.     

Crane scheduling with non-crossing constraint

In this paper, we examine crane scheduling for ports. This important component of port operations management is studied when the non-crossing spatial constraint, which is common to crane operations, is considered. We assume that ships can be divided into holds and that cranes can move from hold to hold but jobs are not pre-emptive, so that only one crane can work on one hold or job to complete it. Our objective is to minimize the latest completion time for all jobs. We formulate this problem as an integer programming problem. We provide the proof that this problem is NP-complete and design a branch-and-bound algorithm to obtain optimal solutions. A simulated annealing meta-heuristic with effective neighbourhood search is designed to find good solutions in larger size instances. The elaborate experimental results show that the branch-and-bound algorithm runs much faster than CPLEX and the simulated annealing approach can obtain near optimal solutions for instances of various sizes.     

AEGIS—attribute experimentation guiding improvement searches

The development of a quality heuristic is a challenging undertaking. While some work has been done to link solution quality and problem inputs, relatively little has been done to methodically address that linkage. This research, a meta-heuristic framework called AEGIS, is an initial attempt to integrate problem characteristics into the solution process itself. As the name implies, the goal is to provide guidance to the solution process, through a well-defined learning process. By utilizing statistical techniques and concepts, this study will demonstrate how such knowledge may be used to drive the function of the algorithm.     

A meta-heuristic approach for solving the Urban Network Design Problem

This paper proposes an optimisation model and a meta-heuristic algorithm for solving the urban network design problem. The problem consists in optimising the layout of an urban road network by designing directions of existing roads and signal settings at intersections. A non-linear constrained optimisation model for solving this problem is formulated, adopting a bi-level approach in order to reduce the complexity of solution methods and the computation times. A Scatter Search algorithm based on a random descent method is proposed and tested on a real dimension network. Initial results show that the proposed approach allows local optimal solutions to be obtained in reasonable computation times.     

Looking Ahead with the Pilot Method

The pilot method as a meta-heuristic is a tempered greedy method aimed at obtaining better solutions while avoiding the greedy trap by looking ahead for each possible choice. Repeatedly a master solution is modified; each time in a minimal fashion to account for best choices, where choices are judged by means of a separate heuristic result, the pilot solution. The pilot method may be seen as a meta-heuristic enhancing the quality of (any) heuristic in a system for heuristic repetition. Experiments show that the pilot method as well as similar methods can behave quite competitively in comparison with well-known and accepted meta-heuristics. In this paper we review some less known results. As a higher time complexity is usually associated with repetition, we investigate a simple short-cut policy to reduce the running times, while retaining an enhanced solution quality. Furthermore, we report successful experiments that incorporate a distinguishing feature of the pilot method, which is the extension of neighborhoods into “local” search, creating tabu search hybrids.