Skip to main content

Über dieses Buch

Meta-heuristics have developed dramatically since their inception in the early 1980s. They have had widespread success in attacking a variety of practical and difficult combinatorial optimization problems. These families of approaches include, but are not limited to greedy random adaptive search procedures, genetic algorithms, problem-space search, neural networks, simulated annealing, tabu search, threshold algorithms, and their hybrids. They incorporate concepts based on biological evolution, intelligent problem solving, mathematical and physical sciences, nervous systems, and statistical mechanics. Since the 1980s, a great deal of effort has been invested in the field of combinatorial optimization theory in which heuristic algorithms have become an important area of research and applications.
This volume is drawn from the first conference on Meta-Heuristics and contains 41 papers on the state-of-the-art in heuristic theory and applications. The book treats the following meta-heuristics and applications: Genetic Algorithms, Simulated Annealing, Tabu Search, Networks & Graphs, Scheduling and Control, TSP, and Vehicle Routing Problems. It represents research from the fields of Operations Research, Management Science, Artificial Intelligence and Computer Science.



1. Meta-Heuristics: An Overview

Meta-heuristics are the most recent development in approximate search methods for solving complex optimization problems, that arise in business, commerce, engineering, industry, and many other areas. A meta-heuristic guides a subordinate heuristic using concepts derived from artificial intelligence, biological, mathematical, natural and physical sciences to improve their performance. We shall present brief overviews for the most successful meta-heuristics. The paper concludes with future directions in this growing area of research.

Ibrahim H. Osman, James P. Kelly

2. A Parallel Genetic Algorithm for the Set Partitioning Problem

This paper describes a parallel genetic algorithm developed for the solution of the set partitioning problem—a difficult combinatorial optimization problem used by many airlines as a mathematical model for flight crew scheduling. Tests on forty real-world set partitioning problems were carried out on an IBM SP parallel computer. We found that performance, as measured by the quality of the solution found and the iteration on which it was found, improved as additional subpopulations were added to the computation. With larger numbers of subpopulations the genetic algorithm was regularly able to find the optimal solution to problems having up to a few thousand integer variables. A notable limitation was the difficulty solving problems with many constraints.

David Levine

3. Evolutionary Computation and Heuristics

Evolutionary computation techniques constitute an important category of heuristic search. Any evolutionary algorithm applied to a particular problem must address the issue of genetic representation of solutions to the problem and genetic operators that would alter the genetic composition of offspring during the reproduction process. However, additional heuristics should be incorporated in the algorithm as well; these heuristic rules provide guidelines for evaluating unfeasible and feasible individuals. This paper surveys such heuristics for discrete and continuous domains and discusses their merits and drawbacks.

Zbigniew Michalewicz

4. Gene Pool Recombination in Genetic Algorithms

A new recombination operator, called Gene Pool Recombination (GPR) is introduced. In GPR, the genes are randomly picked from the gene pool defined by the selected parents. The mathematical analysis of GPR is easier than for two-parent recombination (TPR) normally used in genetic algorithms. There are n difference equations for the marginal gene frequencies that describe the evolution of a population for a fitness function of size n. For simple fitness functions TPR and GPR perform similarly, with a slight advantage for GPR. Furthermore the mathematical analysis shows that a genetic algorithm with only selection and recombination is not a global optimization method, in contrast to popular belief.

Heinz Mühlenbein, Hans-Michael Voigt

5. Genetic and Local Search Algorithms as Robust and Simple Optimization Tools

One of the attractive features of recent metaheuristics is in its robustness and simplicity. To investigate this direction, the single machine scheduling problem is solved by various genetic algorithms (GA) and random multi-start local search algorithms (MLS), using rather simple definitions of neighbors, mutations and crossovers. The results indicate that: (1) the performance of GA is not sensitive about crossovers if implemented with mutations, (2) simple implementation of MLS is usually competitive with (or even better than) GA, (3) GRASP type modification of MLS improves its performance to some extent, and (4) G A combined with local search is quite effective if longer computational time is allowed.

Mutsunori Yagiura, Toshihide Ibaraki

6. Comparison of Heuristic Algorithms for the Degree Constrained Minimum Spanning Tree

The degree constrained minimum spanning tree on a graph is the problem of generating a minimum spanning tree with constraints on the number of arcs that can be incident to vertices of the graph. In this paper we develop several heuristics, including simulated annealing, neural networks, greedy and greedy random algorithms for constructing such trees. We compare the computational performance of all of these approaches against the performance of an exact solution approach, using standard problems taken from the literature.

Geoff Craig, Mohan Krishnamoorthy, M. Palaniswami

7. An Aggressive Search Procedure for the Bipartite Drawing Problem

Graphs are used to represent reality in several areas of knowledge. This has generated considerable interest in graph drawing algorithms. Arc crossing minimization is a fundamental aesthetic criterion to obtain a readable map of a graph. The problem of minimizing the number of arc crossings in a bipartite graph (BDP) is NP-complete. In this paper we present an aggressive search scheme for the BDP based on the Intensification, Diversification and Strategic Oscillation elements of Tabu Search. Several algorithms can be obtained with this scheme by implementing different evaluators in the move definitions. In this paper we propose two variants. Computational results are reported on a set of 300 randomly generated test problems. The two algorithms have been compared with the best heuristics published in the literature and, for limited-size instances, with the optimal solutions.

Rafael Martí

8. Guided Search for the Shortest Path on Transportation Networks

This paper addresses the well-known problem of locating a shortest path between a start and a terminal vertex on a network with non-negative arc costs. We present a new approach which guides the search of the shortest path algorithms under investigation. The ordering of vertices in the vertex list is performed by dividing the network into a set of disjoint regions, each represented by a queue. Each queue holds a set of vertices which fall within a range given by a heuristic measure of their current proximity to the end vertex. Computational results show that the guided algorithm outperforms the original algorithms for transportation networks with Euclidean arc costs. The results are analyzed against the queue size and the accuracy of the heuristic function used.

Yazid M. Sharaiha, Richard Thaiss

9. A Metaheuristic for the Timetabling Problem.

A metaheuristic algorithm based on Simulated Annealing and Tabu Search techniques is adapted to timetabling problems. The technique is designed with a certain flexibility to allow different schools and faculties at the University of Wesminster to be able to develop their own timetables.

H. Abada, E. El-Darzi

10. Complex Sequencing Problems and Local Search Heuristics

Many problems can be formulated as complex sequencing problems. We will present problems in flexible manufacturing that have such a formulation and apply local search methods like iterative improvement, simulated annealing and tabu search to solve these problems. Computational results are reported.

Peter Brucker, Johann Hurink

11. Heuristic Algorithms for Single Processor Scheduling with Earliness and Flow Time Penalties

We consider the problem of scheduling a set of n tasks on a single processor. Each task has a processing time, a deadline, a flow time penalty and an earliness penalty. The objective is to minimize the total cost incurred by the penalties. The problem is NP-hard in the strong sense. Exact enumerative algorithms from the literature can solve random instances with n ≤ 50. We study a tabu search approach to the approximate solution of the problem and show, through computational experiments, that instance with n = 300 are effectively solved with short computing times.

Mauro Dell’Amico, Silvano Martello, Daniele Vigo

12. Heuristics for the Optimal Control of Thermal Energy Storage

A dynamic programming based search algorithm was developed to determine the control strategy that minimizes the total operating cost of a thermal energy storage system. A mixed integer programming model was used to validate the findings of the DP-based heuristic. To expedite the search procedure, a second heuristic was developed that determines the approximate value of the two search parameters. The DP algorithm then searches within a smaller domain marked by a search radius around the MIP approximations. Significant savings in run time were realized at the cost of only marginal deviations in the minimum objective function value compared to the full DP-based search.

Gregor P. Henze, Manuel Laguna, Moncef Krarti

13. Exploiting Block Structure to Improve Resource-Constrained Project Schedules

We identify a block structure, typically found in resource-constrained project schedules, that yields a natural decomposition of the original problem into a series of smaller subproblems. Reducing the makespan of any subproblem has the effect of reducing the total makespan by an equivalent amount. Since these subproblems can be independently reoptimized, this block structure provides a way of improving schedules generated by heuristic methods. We report computational results of applying this technique to problems containing up to five resources and on the order of 200 activities, and speculate as to its applicability to more powerful local search based heuristics.

Helmut E. Mausser, Stephen R. Lawrence

14. Combining the Large-Step Optimization with Tabu-Search: Application to The Job-Shop Scheduling Problem

We apply the combined technique of tabu-search and large-step optimization to the job-shop scheduling problem. The job-shop scheduling problem can be defined as follows: given a set of machines and a set of jobs, the objective is to construct a schedule which minimizes the time necessary to complete all the jobs. We also present some diversification strategies for the tabu-search methods and relate them with the large-step optimization method. Relevant computational results and respective conclusions are also presented.

Helena Ramalhinho Lourenço, Michiel Zwijnenburg

15. Job-Shop Scheduling by Simulated Annealing Combined with Deterministic Local Search

The Job-Shop Scheduling Problem (JSSP) is one of the most difficult NP-hard combinatorial optimization problems. This paper proposes a new method for solving JSSPs based on simulated annealing (SA), a stochastic local search, enhanced by shifting bottleneck (SB), a problem specific deterministic local search. In our method new schedules are generated by a variant of Giffler and Thompson’s active scheduler with operation permutations on the critical path. SA selects a new schedule and probabilistically accepts or rejects it. The modified SB is applied to repair the rejected schedule; the new schedule is accepted if an improvement is made. Experimental results showed the proposed method found near optimal schedules for the difficult benchmark problems and outperformed other existing local search algorithms.

Takeshi Yamada, Ryohei Nakano

16. Cybernetic Optimization by Simulated Annealing: An Implementation of Parallel Processing Using Probabilistic Feedback Control

The convergence of the simulated annealing (SA) algorithm is accelerated by a probabilistic feedback control (PFC) scheme. This scheme uses two or more parallel processors to solve the same or related combinatorial optimization problems and are coupled by a Probabilistic Measure of Quality (PMQ). The PMQ is used to generate an error signal for use in feedback control. Control over the search process is achieved by using the error signal to modulate the temperature parameter. Other aspects of control theory, such as the system gain and its effects on system performance, are described. Theoretical and experimental results which demonstrate the merits of a PFC system are also presented.

Mark A. Fleischer, Sheldon H. Jacobson

17. A simulated annealing algorithm for the computation of marginal costs of telecommunication links

The aim of this study is the calculation of marginal costs in a transmission network. A classical network model enables the marginal costs of links to be defined for any given topology. The limits of a computation linked to a particular optimal network configuration led us to consider statistical mechanics methods originally used in combinatorial optimization. Probabilistic properties such as thermostatistical persistency ensure the convergence of a Metropolis based algorithm adapted from network design and dimensioning to the computation of marginal costs.

J. L. Lutton, E. Philippart

18. Learning to Recognize (Un)Promising Simulated Annealing Runs: Efficient Search Procedures for Job Shop Scheduling and Vehicle Routing

Simulated Annealing (SA) procedures can potentially yield near-optimal solutions to many difficult combinatorial optimization problems, though often at the expense of intensive computational efforts. The single most significant source of inefficiency in SA search is the inherent stochasticity of the procedure, typically requiring that the procedure be rerun a large number of times before a near-optimal solution is found. This paper describes a mechanism that attempts to learn the structure of the search space over multiple SA runs on a given problem. Specifically, probability distributions are dynamically updated over multiple runs to estimate at different checkpoints how promising a SA run appears to be. Based on this mechanism, two types of criteria are developed that aim at increasing search efficiency: (1) a cutoff criterion used to determine when to abandon unpromising runs and (2) restart criteria used to determine whether to start a fresh SA run or restart search in the middle of an earlier run. Experimental results obtained on a class of complex job shop scheduling problems show (1) that SA can produce high quality solutions for this class of problems, if run a large number of times, and (2) that our learning mechanism can significantly reduce the computation time required to find high quality solutions to these problems. The results also indicate that, the closer one wants to be to the optimum, the larger the speedups. Similar results obtained on a smaller set of benchmark Vehicle Routing Problems with Time Windows (VRPTW) suggest that our learning mechanisms could help improve the efficiency of SA in a number of different domains.

Norman M. Sadeh, Yoichiro Nakakuki, Sam R. Thangiah

19. A Preliminary Investigation into the Performance of Heuristic Search Methods Applied to Compound Combinatorial Problems

Many real combinatorial problems involve several objectives. A common procedure for such problems is to combine these separate objectives into a single overall objective, by means of weightings. Such a problem is therefore compound in nature, since its objective is a single entity made up of several individual elements, as with chemical compounds.However, it is reasonable to suppose that compound problems may exhibit different features from truly single-objective problems, because the natures of their solution spaces (and, in particular, the ‘shapes’ of their local optima) are likely to be rather different. It is hypothesized that this fact may significantly affect the relative effectiveness of heuristic search techniques used to solve these problems.This paper presents the results of a preliminary investigation into three sets of compound problems (31 problems in total), using three well-known heuristic search techniques. A measure of local optimum shape is proposed and used. The results show that the above hypothesis appears to be true to at least some extent.

Mike B. Wright, Richard C. Marett

20. Tabu Search, Combination and Integration

This work studies the shortest path problem as represented by finding the route with least processing time in data communication networks. This is accomplished by a more effective procedure, known here as the SARA algorithm, that combines tabu search with other established search techniques such as backtracking, label-setting, and label-correcting.The main objective of this work is the adaptive optimization of data network resources within specified constraints, and a demonstration of the benefits in applications to network management. In performing the optimization, consideration is given to both the total (processing) time for a message to travel from source node to destination node and the computational (processing) time to achieve this travel time.Three major search techniques are combined with tabu search, namely backtracking, label setting (Dijkstra), and label correcting (Bellman-Ford). These techniques were chosen because of their common use to find shortest paths in data communication networks. Computations of the approach presented demonstrate that combining tabu search with the above search methods results in a procedure that enhances tabu search. Results and comparisons of the four methods are provided.

Ahmed S. Al-Mahmeed

21. Vector Quantization with the Reactive Tabu Search

A novel application of the Reactive Tabu Search to Vector Quantization (RTS-VQ) is presented. The results obtained on benchmark tasks demonstrate that a performance similar to that of traditional techniques can be obtained even if the code vectors are represented with small integers. The result is of interest for application-specific VLSI circuits.

Roberto Battiti, Giampietro Tecchiolli, Paolo Tonella

22. Tabu Thresholding for the Frequency Assignment Problem

The frequency assignment problem is to allocate frequencies to communication links such that the total interference is minimised. In this paper we investigate a tabu thresholding procedure to solve the frequency assignment problem. Several variants of the method are implemented using large computer-generated but realistic data sets. We report on these investigations, the selection of suitable parameters and compare the method with a tabu search for the same problem. We conclude that, in the same amount of time, tabu thresholding provides better quality solutions than tabu search.

Diane Castelino, Nelson Stephens

23. A New Tabu Search Approach to the 0–1 Equicut Problem

Given an undirected graph, the 0–1 equicut problem consists of finding a partition of the vertex set into two subsets of equal size, such that the number of edges going from one subset to the other is minimized. A classical heuristics for this problem was presented 25 years ago, whereas simulated annealing, genetic algorithms, tabu search and a greedy randomized procedure have been developed in the last 5 years. In this paper we present a new tabu search algorithm and show, thorough extensive computational experiments, that in most cases it beats the other methods.

Mauro Dell’Amico, Francesco Maffioli

24. Simple Tabu Thresholding and the Pallet Loading Problem.

Rectangle packing problems are particularly challenging for local search methods as they frequently give rise to spiky solution landscapes. This paper is concerned with the development of a simple tabu thresholding algorithm for the pallet loading problem, with the ultimate objective of comparing it with a non-monotonic version of simulated annealing. Although the focus of the discussion is problem specific, some of the conclusions are relevant to the implementation of simple tabu thresholding in any problem domain.

Kathryn A. Dowsland

25. Critical Event Tabu Search for Multidimensional Knapsack Problems

We report a new approach to creating a tabu search method whose underlying memory mechanisms are organized around “critical events.” A balance between intensification and diversification is accomplished by a strategic oscillation process that navigates both sides of the feasibility boundary, and serves to define the critical events. Surrogate constraint analysis is applied to derive choice rules for the method. Computational tests show the approach performs more effectively than previous heuristics for multidimensional knapsack problems, obtaining optimal solutions for all problems in a standard testbed.

Fred Glover, Gary A. Kochenberger

26. Solving Dynamic Stochastic Control Problems in Finance Using Tabu Search with Variable Scaling

Numerous multistage planning problems in finance involve nonlinear and nonconvex decision controls. One of the simplest is the fixed-mix investment strategy. At each stage during the planning horizon, an investor rebalances her/his portfolio in order to achieve a target mix of asset proportions. The decision variables represent the target percentages for the asset categories. We show that a combination of Tabu Search and Variable Scaling generates global optimal solutions for real world test cases, despite the presence of nonconvexities. Computational results demonstrate that the approach can be applied in a practical fashion to investment problems with over 20 stages (20 years), 100 scenarios, and 8 asset categories. The method readily extends to more complex investment strategies with varying forms of nonconvexities.

Fred Glover, John M. Mulvey, Kjetil Hoyland

27. Comparison of Heuristics for the 0–1 Multidimensional Knapsack Problem

The multidimensional 0–1 knapsack problem (0–1MKP) is a generalization of the well-known 0–1 knapsack problem. As for any hard optimization problem also for 0–1MKP, a reasonable effort to cope with the problem is trying to derive heuristics which solve it suboptimally and which, possibly, yield a good trade-off between the solution quality and the time and the memory requirements. In this paper, we describe several heuristics for 0–1MKP. The first one is a simple multistage algorithm (SMA) which always maintains feasibility requirements. We also propose variants of the tabu search dealing with infeasibility, called also tunneling effect. We implement these heuristics as C code and compare their performances.

S. Hanafi, A. Freville, A. El Abdellaoui

28. Probabilistic Move Selection in Tabu Search for Zero-One Mixed Integer Programming Problems

We extend our previous work applying first-level Tabu Search mechanisms to 0/1 MIP problems, introducing probabilistic measures for move selection. These are especially applicable when the move evaluation function is contaminated by noise or contains elements not directly related to the objective function value. We also look at the possibility of replacing tabu memory completely by associated probabilistic guidance. Our approach is designed with the ability to solve general 0/1 MCP problems, and thus contains no problem domain specific knowledge. The outcome improves significantly on the solutions obtained by the first-level Tabu Search mechanisms previously employed. The probabilistic measures are extremely simple to implement, and can be readily incorporated in standard Tabu Search designs.

Arne Løkketangen, Fred Glover

29. A Star-Shaped Diversification Approach in Tabu Search

Diversification is among the most versatile strategic components of tabu search. In this paper we propose and investigate a star-shaped approach providing multiple disjoint search trajectories scattering over the solution space. The approach is based on a dynamic strategy that explicitly incorporates logical interdependencies between multiple lists representing these trajectories. Numerical results are presented for some benchmark instances derived from the problem of balancing hydraulic turbine runners, which may be formulated as a quadratic assignment problem.

Lutz Sondergeld, Stefan Voß

30. Communication Issues in Designing Cooperative Multi-Thread Parallel Searches

Roughly speaking, parallel local search techniques can be divided into three categories: low-level parallelization strategies (e.g., master-slave schemes), solution-space partitioning methods and multi-thread procedures in which several processes explore concurrently the same search space. The multi-thread technique can be further subdivided into independent and cooperative search thread algorithms. In this paper, we focus on cooperative multi-thread heuristics applied to methods such as tabu search, and attempt to identify the key questions to be addressed in the design of any algorithm in this class. In particular, we show that questions related to inter-agent communications are a central element of the algorithmic design of these methods.

Michel Toulouse, Teodor G. Crainic, Michel Gendreau

31. A Study on Algorithms for Selecting r Best Elements from An Array

The issue of identifying r best (smallest or largest) elements from a data set is relevant in a variety of combinatorial search settings, for example, some strategies of tabu search (Glover 1989, 1992, 1994, Lokketangen and Glover 1995), semi-greedy heuristics (Hart and Shogan 1987), and GRASP (Laguna, Feo, and Elrod 1994, Feo and Resende 1995). This is particularly true of aggressive search strategies such as probabilistic tabu search, which strongly bias the choice among elements to favor those with preferred evaluations. The identification of r best elements is also relevant for applying candidate list selection strategies within combinatorial search (e.g. Glover 1992, 1994). This occurs notably where compound moves are screened by decomposing them into components, as where exchange moves are broken into “add moves” and “drop moves,” and r best options for each type of component are identified (and then combined) to restrict the number of compound moves examined. Additional applications to candidate list strategies occurs where distribution of the r best elements is monitored as a supplementary guideline for determining the suitability of the candidate list composition. In these instances, the most appropriate value for r is often relatively small, e.g. typically less than 20.Because the need to identify r best elements occurs repetitively within such contexts, it is important to isolate these elements efficiently. The computer science literature proposes many algorithms for sorting data files, and a few have become widely adopted due to their convenience and efficiency. Yet, by comparison, little attention has been given to selecting r best elements from a list, and the issue of selecting such elements for relatively small values of r has received even less consideration. Conceivably, The worst case emphasis that pervades the computer science literature has served to draw the focus away from such issues, in spite of their potential practical interest.In this paper, we have adapted a few of the more prominent sorting algorithms to the function of selecting r best elements and compare their performance. Experimental results show that a hardwired threshold algorithm (based on simple binary sorting) performs surprisingly well in selecting a relatively small number of the best elements from a larger collection.

Fan T. Tseng

32. A Modified Tabu Thresholding Approach for the Generalised Restricted Vertex Colouring Problem

We present a modification of the Tabu Thresholding (TT) approach and apply it to the solution of the generalised restricted vertex colouring problem. Both the bounded and unbounded cases are treated. In our algorithms, the basic TT elements are supplemented with an evaluation function that depends on the best solution obtained so far, together with a mechanism which reinforces the aggressive search in the improving phase, and new diversification strategies which depend on the state of the search. The procedure is illustrated through the solution of the problem of minimising the number of workers in a heterogeneous workforce.

Vicente Valls, M. Ángeles Pérez, M. Sacramento Quintanilla

33. Chunking Applied to Reactive Tabu Search

In an earlier paper (Woodruff 1994) we describe the use of, and search for, groupings of solution vector elements that we refer to as chunks. The use of chunks has the potential to enhance heuristic search methods such as tabu search and genetic algorithms. In this paper we have two goals: 1) we describe the details of a fully generalized application of chunking to reactive tabu search (Bat-titi and Tecchiolli 1994) and give some computational results on a particular problem and 2) we use the chunks to explore the nature of the relationship between the search and cups (i.e., domains of attraction or chaotic attractors). We find that chunking allows us to characterize the shape and location of cups in a useful way. We are able to compute the distance from a group of solutions believed to be from one cup to a given solution and test that solution for membership in the cup.

David L. Woodruff

34. Tabu Search on the Geometric Traveling Salesman Problem

This paper presents a new tabu search approach for the geometric Traveling Salesman Problem. The use of complex TSP transitions in a tabu search context is investigated; among these transitions are the classical Lin-Kernighan transition and a new transition, called the Flower transition. The neighbourhood of the complex transitions is reduced strategically by using computational geometry forming a so-called variable candidate set of neighbouring solutions, the average quality of which controlled by a parameter. A new diversification method based on a notion of solution-distance is used. The experimental results are comparable to the best published results in the literature.

Martin Zachariasen, Martin Dam

35. Mixing Different Components of Metaheuristics

This paper studies the effects of mixing different components of metaheuristics applied to the TSP, namely simulated annealing and a new combinatorial optimization one, called the noising method. The results deal with the comparison of these methods with a given number of evaluations of the function to optimize. Many combinations have been tested: they show that the classical patterns are not always the best.

Irène Charon, Olivier Hudry

36. A Probabilistic Analysis of Local Search

We present a theoretical average-case analysis of a 2-opt algorithm for the traveling salesman problem. First, we give a model which allows us to compute the required number of steps and the distribution of final solutions found by a best improvement algorithm. This model is empirically validated for a restricted version of the 2-opt neighborhood. Secondly, we present a semi-empirical analysis of the average-case performance of an iterated 2-opt and Lin-Kernighan algorithm based on empirically obtained parameters.

H. M. M. ten Eikelder, M. G. A. Verhoeven, T. W. M. Vossen, E. H. L. Aarts

37. The Clustered Traveling Salesman Problem: A Genetic Approach

The Clustered Traveling Salesman Problem is an extension of the classical Traveling Salesman Problem, where the set vertices is partitioned into clusters. The goal is to find the shortest tour in such a way that all vertices of each cluster are visited contiguously. In this paper, a genetic algorithm is proposed to solve this problem. Computational results are reported on a set of Euclidean problems, and comparisons are provided with another recent heuristic.

Jean-Yves Potvin, François Guertin

38. A Tabu Search based Heuristic for Arc Routing with a Capacity Constraint and Time Deadline

The problem considered is to find the minimum cost set of routes which enable vehicles to service a set of required arcs in a network subject to the service capacity of the vehicles and a time constraint by which each arc must be serviced. The problem is NP-Hard so heuristic methods are required to give good solutions within an acceptable computing time. A new tabu search based heuristic called LOCSAR is introduced and compared with other approaches.

Richard W. Eglese, Leon Y. O. Li

39. Supervision in the Self-Organizing Feature Map: Application to the Vehicle Routing Problem

In this paper, we describe a neural heuristic to find an approximate optimal solution to the vehicle routing problem (VRP) with capacity and time limits constraints. This heuristic is based upon the hierarchical deformable nets (HDN) with stochastic competition introduced by Ghaziri [1991] to solve the VRP with capacity constraints only. For the time limits constraint we have added a constructive procedure to the HDN algorithm. Partial trial solutions are generated one of them is selected using a stochastic competition. In order to improve the results of this approach we have introduced a supervision process to the primary unsupervised algorithm. The performance of this hybrid approach is compared with the unsupervised algorithm and the methods based on other heuristics. We have tested the performance in terms of quality and CPU time consumption. We found that the solutions of the traditional heuristics are still better than the neural heuristics but their CPU time consumption is higher.

Hassan Ghaziri

40. A Parallel Tabu Search Algorithm Using Ejection Chains for the Vehicle Routing Problem

In this paper we describe a Parallel Tabu Search algorithm for the vehicle routing problem under capacity and distance restrictions. In the neighborhood search, the algorithm uses compound moves generated by an ejection chain process. Parallel processing is used to explore the solution space more extensively and different parallel techniques are used to accelerate the search process. Tests were carried out on a network of SUNSparc workstations and computational results for a set of benchmark problems prove the efficiency of the algorithm proposed.

César Rego, Catherine Roucairol

41. Fast Local Search Algorithms for the Handicapped Persons Transportation Problem

We examine the problem of determining an optimal schedule for a fleet of vehicles used to cover the trips required to transport handicapped persons in an urban area. The problem is a generalization of the well-known Pickup and Delivery Problem with Time Windows since, due to the high level of service required by this kind of transport, many additional operational constraints must be considered. We describe fast and effective local search refining procedures, based on trip movements and exchanges, which can be used to improve within acceptable computing time the solutions of large-size instances obtained by using a parallel insertion heuristic algorithm. The procedures have been successfully applied to a set of large real-life problems for the town of Bologna, involving about 300 trips each, showing the effectiveness of the proposed approach.

Paolo Toth, Daniele Vigo
Weitere Informationen