Multiobjective service restoration in electric distribution networks using a local search based heuristic

Contingency situations may cause emergency states in distribution systems; these states are defined as the interruption of power supply. Such situations should be avoided whenever possible in order to maintain certain quality limits related to frequency and duration of interruptions. The main objective of service restoration is to minimize the number of consumers affected by the fault, by transferring them to energized support feeders. Electrical and operational conditions, such as radial network configuration, equipment and voltage drop limits, must be respected. This paper presents a new multiobjective local search based heuristic for the restoration of service which considers the minimization of two conflicting criteria: the load not supplied and the number of switching operations involved. Computational experiments with three network systems have shown the flexibility and effectiveness of the proposed method.     

Weighted search games

In this paper we shall deal with search games in which the strategic situation is developed on a lattice. The main characteristic of these games is that the points in each column of the lattice have a specific associated weight which directly affects the payoff function. Thus, the points in different columns represent points of different strategic value. We solve three different types of games. The first involves search, ambush and mixed situations, the second is a search and inspection game and the last is related to the accumulative games.     

Weighted proximity search

Journal of Heuristics - Proximity search is an iterative method to solve complex mathematical programming problems. At each iteration, the objective function of the problem at hand is replaced by...     

Optimizing heuristic search in forest planning

Heuristic search methods are being used more and more in forest planning since the current formulations of exact methods such as linear programming are not suitable to all today's planning problems. A practical problem with most heuristics is that their performance greatly depends on the parameters that guide their search process. The effect of parameters is hard to know without extensive tests, but these tests cannot be conducted in forest planning practice, because of lacking time and experience. This study presented a method that uses Hooke and Jeeves direct search to optimize the parameters of a heuristic, taking into account the allowed computing time. The method was used to optimize three local-improvement heuristics in a non-spatial and a spatial forest planning problem, and with a short and long computing time. The heuristics were simulated annealing, threshold accepting, and tabu search, all of which are used in forestry. The results were logical and showed that while the optimal values of some parameters were rather constant the others were sensitive to problem type, allowed computing time, or problem size. The objective function value of the forest planning problem was not sensitive to small changes in the parameters of the heuristics. However, because computing time was very sensitive to many parameters, there was not much freedom to set the parameters if both the quality of the solution and speed of the algorithm had to be maintained.     

A unifying approach to heuristic search

We present the General Search Procedure (GSP) that provides a unifying way of describing search algorithms. The GSP captures both constructive and iterative search algorithms. We demonstrate as an exercise that various well-known heuristic search procedures can be obtained as instances of the GSP. The introduced formalism provides a solid ground to prove theoretical properties of search methods. Furthermore, by the formal approach we obtain a framework that can serve as the basis of implementing a search based problem solver.     

A pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search

We propose a new heuristic for the single-searcher path-constrained discrete-time Markovian-target search. The algorithm minimizes an approximate, instead of exact, nondetection probability computed from the conditional probability that reflects the search history over the time windows of a fixed length, l. Having a pseudo-polynomial complexity, it can solve, in reasonable time, the instances an order of magnitude larger than those solved in the previous studies. By an asymptotic analysis relying on the fast-mixing Markov chain, we show that the relative error of the approximation exponentially diminishes as l increases and the experimental results confirm the analysis. The experiment also reveals a correlation very close to 1 between the approximate and exact nondetection probability of a search path. This means that the heuristic produces near-optimal search paths.     

A neighborhood search heuristic for pre-marshalling export containers

In a yard where export containers are piled up, only those on the top are directly accessible to the stacking equipment. As a result, extra rehandles may occur when lifting them up for loading onto ships. One way to improve operational efficiency is to pre-marshal the containers in such an order that it fits the loading sequence. This paper proposes a model to develop a movement plan to improve the layout of containers in a bay. The proposed heuristic consists of a neighborhood search process, an integer programming model, and three minor subroutines. Each of the components plays a different role in the heuristic. Several sets of testing results demonstrate the performance of the heuristic as well as the contributions of the components.     

Depth-first heuristic search for the job shop scheduling problem

We evaluate two variants of depth-first search algorithms and consider the classic job shop scheduling problem as a test bed. The first one is the well-known branch-and-bound algorithm proposed by P. Brucker et al. which uses a single chronological backtracking strategy. The second is a variant that uses partially informed depth-first search strategy instead. Both algorithms use the same heuristic estimation; in the first case, it is only used for pruning states that cannot improve the incumbent solution, whereas in the second it is also used to sort the successors of an expanded state. We also propose and analyze a new heuristic estimation which is more informed and more time consuming than that used by Brucker’s algorithm. We conducted an experimental study over well-known instances showing that the proposed partially informed depth-first search algorithm outperforms the original Brucker’s algorithm.     

A variable neighborhood search heuristic for periodic routing problems

The aim of this paper is to propose a new heuristic for the Periodic Vehicle Routing Problem (PVRP) without time windows. The PVRP extends the classical Vehicle Routing Problem (VRP) to a planning horizon of several days. Each customer requires a certain number of visits within this time horizon while there is some flexibility on the exact days of the visits. Hence, one has to choose the visit days for each customer and to solve a VRP for each day. Our method is based on Variable Neighborhood Search (VNS). Computational results are presented, that show that our approach is competitive and even outperforms existing solution procedures proposed in the literature. Also considered is the special case of a single vehicle, i.e. the Periodic Traveling Salesman Problem (PTSP). It is shown that slight changes of the proposed VNS procedure is also competitive for the PTSP.     

A tabu search heuristic for ship routing and scheduling

The purpose of this paper is to solve a planning problem faced by many shipping companies dealing with the transport of bulk products. These shipping companies are committed to carrying some contract cargoes and will try to derive additional revenue from optional spot cargoes. An efficient tabu search algorithm has been developed to ensure quick decision support for the planners. The solutions generated by the tabu search heuristic are compared with those produced by a previously published multi-start local search heuristic. Computational results show that the tabu search heuristic yields optimal or near-optimal solutions to real-life instances within reasonable time. For large and tigthly constrained cases, the tabu search heuristic provides much better solutions than the multi-start local search heuristic. A version of the tabu search heuristic will be integrated as an improved solver in a prototype decision support system used by several shipping companies.     

Lagrangean heuristic for primary routes assignment in survivable connection-oriented networks

Our discussion in this article centers on the application of a Lagrangean relaxation and a subgradient optimization technique to the problem of primary route assignment (PRA) in survivable connection-oriented networks. The PRA problem consists in a static optimization of primary routes minimizing the Lost Flow in Node (LFN) function. The major contribution of this work is a combination of the Lagrangean relaxation with other heuristic algorithms. We evaluate the performance of the proposed Lagrangean-based heuristic by making a comparison with their counterparts including evolutionary algorithm and GRASP using various network topologies and demand patterns. The results of simulation tests show that the new algorithm provides sub-optimal results, which are better than other heuristics.     

A heuristic search based on diversity for solving combinatorial problems

Journal of Heuristics - In this paper we propose a novel heuristic search for solving combinatorial optimization problems which we call Diverse Search (DS). Like beam search, this constructive...     

The analysis of a fringe heuristic for binary search trees

A detailed analysis is presented for the behaviour of binary search trees built by using a heuristic that performs only local reorganizations at the bottom of the tree.     

An adaptive large neighborhood search heuristic for the Pollution-Routing Problem

The Pollution-Routing Problem (PRP) is a recently introduced extension of the classical Vehicle Routing Problem with Time Windows which consists of routing a number of vehicles to serve a set of customers, and determining their speed on each route segment so as to minimize a function comprising fuel, emission and driver costs. This paper presents an adaptive large neighborhood search for the PRP. Results of extensive computational experimentation confirm the efficiency of the algorithm.     

A heuristic approach for capacity expansion of packet networks

We address the problem of expanding transmission capacity of an existing packet network over a multiperiod planning horizon, the objective being low total cost of expansion. Discrete capacity choices, interaction with routing decisions, and economy of scale in the cost of capacity make it extremely difficult to decide when, where and how much capacity to add. A fast heuristic solution method is developed based on the well established Flow Deviation routing algorithm. The heuristic begins by making myopic expansion decisions, which are then subsequently adjusted to account for economies of scale in the cost of capacity. Heuristic solutions are compared to a benchmark which approximates the real cost function by its linear lower envelope. Since the number of possible expansion plans is an exponential function of the number of edges, capacity choices, and periods in the planning horizon, a fast heuristic allows one to look beyond small problems at more realistically sized ones.     

A self-tuning heuristic for the design of communication networks

This paper addresses the design of communication networks that has a large application area. The problem is to design a minimum cost network subject to a given reliability level. Complexity of the problem is twofold: (1) finding a minimum-cost network topology that every pair of nodes can communicate with each other and (2) computing overall reliability to provide the reliability constraint. Over the last two decades, metaheuristic algorithms have been widely applied to solve this problem due to its NP-hardness. In this study, a self-tuning heuristic (STH), which is a new approach free from parameter tuning, is applied to the design of communication networks. Extensive computational results confirm that STH generates superior solutions to the problem in comparison to some well-known local search metaheuristics, and also more sophisticated metaheuristics proposed in the literature. The practical advantage of STH lies in both its effectiveness and simplicity in application to the design problem.     

A large neighborhood search heuristic for the longest common subsequence problem

Given a set S={S ¹,…,S ^k } of finite strings, the k-Longest Common Subsequence Problem (k-LCSP) seeks a string L ^* of maximum length such that L ^* is a subsequence of each S ⁱ for i=1,…,k. This paper presents a large neighborhood search technique that provides quality solutions to large k-LCSP instances. This heuristic runs in linear time in both the length of the sequences and the number of sequences. Some computational results are provided.     

A local search heuristic for the Multi-Commodity k-splittable Maximum Flow Problem

The Multi-Commodity $k$ -splittable Maximum Flow Problem consists of maximizing the amount of flow routed through a network such that each commodity uses at most $k$ paths and such that edge capacities are satisfied. The problem is $\mathcal NP $ -hard and has application in a.o. telecommunications. In this paper, a local search heuristic for solving the problem is proposed. The heuristic is an iterative shortest path procedure on a reduced graph combined with a local search procedure to modify certain path flows and prioritize the different commodities. The heuristic is tested on benchmark instances from the literature and solves 83 % of the instances to optimality. For the remaining instances, the heuristic finds good solution values which on average are 1.04 % from the optimal. The heuristic solves all instances in less than a second. Compared to other heuristics, the proposed heuristic again shows superior performance with respect to solution quality.     

A tabu search heuristic procedure for the capacitated facility location problem

A tabu search heuristic procedure is developed, implemented and computationally tested for the capacitated facility location problem. The procedure uses different memory structures. Visited solutions are stored in a primogenitary linked quad tree. For each facility, the recent move at which the facility changed its status and the frequency it has been open are also stored. These memory structures are used to guide the main search process as well as the diversification and intensification processes. Lower bounds on the decreases of total cost are used to measure the attractiveness of the moves and to select moves in the search process. A specialized network algorithm is developed to exploit the problem structure in solving transportation problems. Criterion altering, solution reconciling and path relinking are used to perform intensification functions. The performance of the procedure is tested through computational experiments using test problems from the literature and new test problems randomly generated. It found optimal solutions for almost all test problems from the literature. As compared to the heuristic method of Lagrangean relaxation with improved subgradient scheme, the tabu search heuristic procedure found much better solutions using much less CPU time.