A path-relinking metaheuristic for the resource levelling problem

This paper deals with project scheduling problem with resource levelling objective function where precedence relations among activities are prescribed. We develop a dedicated path-relinking metaheuristic algorithm to tackle this problem. Computational results on randomly generated test sets indicate the developed procedure is efficient and outperforms the best available metaheuristic algorithms in the literature.     

Solving railroad blocking problem using ant colony optimization algorithm

The railroad blocking problem is one of the most important decision in freight railroads. The objective of this problem is to minimize the costs of delivering all commodities by deciding which inter-terminal blocks to build and specifying the assignment of commodities to these blocks, while observing limits on the number and aggregate volume of the blocks assembled at each terminal. This paper presents a metaheuristic algorithm based on ant colony optimization for solving this problem. To evaluate the efficiency of the proposed algorithm and the quality of solutions, experimental analysis is conducted, using several simulated test problems. The results on the test problems are compared with those of solution generated with CPLEX software. The results show high efficiency and effectiveness of the proposed algorithms. The solution method is applied to build car blocking plan in Islamic Republic of Iran Railways. By applying the presented model, Iran Railways can reduce the operational cost considerably and save the time in shipping the freights as well.     

A heuristic method for the minimum toll booth problem

This paper addresses the toll pricing problem in which the objective is to minimize the number of required toll facilities in a traffic network. The problem is shown to be NP-hard. To obtain a solution in a reasonable time, an effective metaheuristic algorithm is developed. The algorithm uses a local search technique in which the neighborhood function employs the dynamic slope scaling procedure to deal with the fixed charge nature of the objective function. Numerical results from 50 randomly generated and three real networks are reported.     

Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands

This article analyzes the performance of metaheuristics on the vehicle routing problem with stochastic demands (VRPSD). The problem is known to have a computationally demanding objective function, which could turn to be infeasible when large instances are considered. Fast approximations of the objective function are therefore appealing because they would allow for an extended exploration of the search space. We explore the hybridization of the metaheuristic by means of two objective functions which are surrogate measures of the exact solution quality. Particularly helpful for some metaheuristics is the objective function derived from the traveling salesman problem (TSP), a closely related problem. In the light of this observation, we analyze possible extensions of the metaheuristics which take the hybridized solution approach VRPSD-TSP even further and report about experimental results on different types of instances. We show that, for the instances tested, two hybridized versions of iterated local search and evolutionary algorithm attain better solutions than state-of-the-art algorithms.     

Dynamic programming based metaheuristics for the dial-a-ride problem

The organization of a specialized transportation system to perform transports for elderly and handicapped people is usually modeled as dial-a-ride problem. Users place transportation requests with specified pickup and delivery locations and times. The requests have to be completed under user inconvenience considerations by a specified fleet of vehicles. In the dial-a-ride problem, the aim is to minimize the total travel times respecting the given time windows, the maximum user ride times, and the vehicle restrictions. This paper introduces a dynamic programming algorithm for the dial-a-ride problem and demonstrates its effective application in (hybrid) metaheuristic approaches. Compared to most of the works presented in literature, this approach does not make use of any (commercial) solver. We present an exact dynamic programming algorithm and a dynamic programming based metaheuristic, which restricts the considered solution space. Then, we propose a hybrid metaheuristic algorithm which integrates the dynamic programming based algorithms into a large neighborhood framework. The algorithms are tested on a given set of benchmark instances from the literature and compared to a state-of-the-art hybrid large neighborhood search approach.     

Pareto set approximation by the method of adjustable weights and successive lexicographic goal programming

A nonlinear multiobjective optimization problem is considered. Two methods are proposed to generate solutions with an approximately uniform distribution in a Pareto set. The first method is supposed to find the solutions as minimizers of weighted sums of objective functions where the weights are properly selected using a branch and bound type algorithm. The second method is based on lexicographic goal programming. The proposed methods are compared with several metaheuristic methods using two and three-criteria tests and applied problems.     

Total tardiness minimization in permutation flowshop with deterioration consideration

In this paper, we consider a permutation flowshop scheduling problem with deteriorating jobs. The objective is to minimize the total tardiness of all jobs. A branch-and-bound algorithm incorporating with a dominance property and a lower bound is developed. Furthermore, two metaheuristic algorithms, the simulated annealing algorithm, and the particle swarm optimization method, are proposed. Finally, computational studies are given.     

A provably convergent heuristic for stochastic bicriteria integer programming

We propose a general-purpose algorithm APS (Adaptive Pareto-Sampling) for determining the set of Pareto-optimal solutions of bicriteria combinatorial optimization (CO) problems under uncertainty, where the objective functions are expectations of random variables depending on a decision from a finite feasible set. APS is iterative and population-based and combines random sampling with the solution of corresponding deterministic bicriteria CO problem instances. Special attention is given to the case where the corresponding deterministic bicriteria CO problem can be formulated as a bicriteria integer linear program (ILP). In this case, well-known solution techniques such as the algorithm by Chalmet et al. can be applied for solving the deterministic subproblem. If the execution of APS is terminated after a given number of iterations, only an approximate solution is obtained in general, such that APS must be considered a metaheuristic. Nevertheless, a strict mathematical result is shown that ensures, under rather mild conditions, convergence of the current solution set to the set of Pareto-optimal solutions. A modification replacing or supporting the bicriteria ILP solver by some metaheuristic for multicriteria CO problems is discussed. As an illustration, we outline the application of the method to stochastic bicriteria knapsack problems by specializing the general framework to this particular case and by providing computational examples.     

Routing a mix of conventional,plug-in hybrid,and electric vehicles

We introduce an electric vehicle routing problem combining conventional, plug-in hybrid, and electric vehicles. Electric vehicles are constrained in their service range by their battery capacity, and may require time-consuming recharging operations at some specific locations. Plug-in hybrid vehicles have two engines, an internal combustion engine and an electric engine using a built-in rechargeable battery. These vehicles can avoid visits to recharging stations by switching to fossil fuel. However, this flexibility comes at the price of a generally higher consumption rate and utility cost.To solve this complex problem variant, we design a sophisticated metaheuristic which combines a genetic algorithm with local and large neighborhood search. All route evaluations, within the approach, are based on a layered optimization algorithm which combines labeling techniques and greedy evaluation policies to insert recharging stations visits in a fixed trip and select the fuel types. The metaheuristic is finally hybridized with an integer programming solver, over a set partitioning formulation, so as to recombine high-quality routes from the search history into better solutions. Extensive experimental analyses are conducted, highlighting the good performance of the algorithm and the contribution of each of its main components. Finally, we investigate the impact of fuel and energy cost on fleet composition decisions. Our experiments show that a careful use of a mixed fleet can significantly reduce operational costs in a large variety of price scenarios, in comparison with the use of a fleet composed of a single vehicle class.     

A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports

In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem. More importantly we highlight the differences in operations between bulk ports and container terminals which highlights the need to devise specific solutions for bulk ports. The objective is to minimize the total service time of vessels berthing at the port. We propose an exact solution algorithm based on a branch and price framework to solve the integrated problem. In the proposed model, the master problem is formulated as a set-partitioning problem, and subproblems to identify columns with negative reduced costs are solved using mixed integer programming. To obtain sub-optimal solutions quickly, a metaheuristic approach based on critical-shaking neighborhood search is presented. The proposed algorithms are tested and validated through numerical experiments based on instances inspired from real bulk port data. The results indicate that the algorithms can be successfully used to solve instances containing up to 40 vessels within reasonable computational time.     

Guided Local Search for Final Placement in VLSI Design

The design of a VLSI circuit consists of two main parts: First, the logical functionality of the circuit is described, and then the physical layout of the modules and connections is settled. In the latter process one wishes to place the modules such that the necessary wiring becomes as small as possible in order to minimize area usage and delays on signal paths. The placement problem is the subproblem of the layout problem which considers the geometric locations of the modules. A new heuristic is presented for the general cell placement problem where the objective is to minimize total bounding box netlength. The heuristic is based on the Guided Local Search (GLS) metaheuristic. GLS modifies the objective function in a constructive way to escape local minima. Previous attempts to use local search on final (or detailed) placement problems have often failed as the neighbourhood quickly becomes too excessive for large circuits. Nevertheless, by combining GLS with Fast Local Search it is possible to focus the search on appropriate sub-neighbourhoods, thus reducing the time complexity considerably. Comprehensive computational experiments with the developed algorithm are reported on a broad range of industrial circuits. The experiments demonstrate that the developed algorithm is able to improve the estimated routing length of large-sized layouts with as much as 20 percent when compared to existing algorithms.     

Ant colony optimization with a specialized pheromone trail for the car-sequencing problem

This paper studies the learning process in an ant colony optimization algorithm designed to solve the problem of ordering cars on an assembly line (car-sequencing problem). This problem has been shown to be NP-hard and evokes a great deal of interest among practitioners. Learning in an ant algorithm is achieved by using an artificial pheromone trail, which is a central element of this metaheuristic. Many versions of the algorithm are found in literature, the main distinction among them being the management of the pheromone trail. Nevertheless, few of them seek to perfect learning by modifying the internal structure of the trail. In this paper, a new pheromone trail structure is proposed that is specifically adapted to the type of constraints in the car-sequencing problem. The quality of the results obtained when solving three sets of benchmark problems is superior to that of the best solutions found in literature and shows the efficiency of the specialized trail.     

A mixed integer formulation and an efficient metaheuristic procedure for the <Emphasis Type="Italic">k</Emphasis>-Travelling Repairmen Problem

In this paper, we study a k-Travelling Repairmen Problem where the objective is to minimize the sum of clients waiting time to receive service. This problem is relevant in applications that involve distribution of humanitarian aid in disaster areas, delivery and collection of perishable products and personnel transportation, where reaching demand points to perform service, fast and fair, is a priority. This paper presents a new mixed integer formulation and a simple and efficient metaheuristic algorithm. The proposed formulation consumes less computational time and allows solving to optimality more than three times larger data instances than the previous formulation published in literature, even outperforming a recently published Branch and Price and Cut algorithm for this problem. The proposed metaheuristic algorithm solved to optimality 386 out of 389 tested instances in a very short computational time. For larger instances, the algorithm was assessed using the best results reported in the literature for the Cumulative Capacitated Vehicle Routing Problem.     

An improved heuristic for the far from most strings problem

The Far From Most Strings Problem (FFMSP) asks for a string that is far from as many as possible of a given set of strings. All the input and the output strings are of the same length, and two strings are far if their Hamming distance is greater than or equal to a given threshold. FFMSP belongs to the class of sequence consensus problems which have applications in molecular biology, amongst others. FFMSP is NP-hard. It does not admit a constant-ratio approximation either, unless P=NP. In the last few years, heuristic and metaheuristic algorithms have been proposed for the problem, which use local search and require a heuristic, also called an evaluation function, to evaluate candidate solutions during local search. The heuristic function used, for this purpose, in these algorithms is the problem’s objective function. However, since many candidate solutions can be of the same objective value, the resulting search landscape includes many points which correspond to local maxima. In this paper, we devise a new heuristic function to evaluate candidate solutions. We then incorporate the proposed heuristic function within a Greedy Randomized Adaptive Search Procedure (GRASP), a metaheuristic originally proposed for the problem by Festa. The resulting algorithm outperforms state-of-the-art with respect to solution quality, in some cases by orders of magnitude, on both random and real data in our experiments. The results indicate that the number of local optima is considerably reduced using the proposed heuristic.     

Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints

Electric bus scheduling problem can be defined as vehicle scheduling problem with route and fueling time constraints (VSPRFTC). Every vehicle’s travel miles (route time) after charging is limited, thus the vehicle must be recharged after taking several trips and the minimal charging time (fueling time) must be satisfied. A multiple ant colony algorithm (ACA) was presented to solve VSPRFTC based on ACA used to solve traveling salesman problem (TSP), a new metaheuristic approach inspired by the foraging behavior of real colonies of ants. The VSPRFTC considered in this paper minimizes a multiple, hierarchical objective function: the first objective is to minimize the number of tours (or vehicles) and the second is to minimize the total deadhead time. New improvement of ACA as well as detailed operating steps was provided on the basis of former algorithm. Then in order to settle contradiction between accelerating convergence and avoiding prematurity or stagnation, improvement on route construction rule and Pheromone updating rule was adopted. A group feasible trip sets (blocks) had been produced after the process of applying ACA. In dealing with the fueling time constraint a bipartite graphic model and its optimization algorithm are developed for trip set connecting in a hub and spoke network system to minimize the number of vehicle required. The maximum matching of the bipartite graph is obtained by calculating the maximum inflow with the Ford–Fulkerson algorithm. At last, an example was analyzed to demonstrate the correctness of the application of this algorithm. It proved to be more efficient and robust in solving this problem.     

Routing and scheduling in a flexible job shop by tabu search

A hierarchical algorithm for the flexible job shop scheduling problem is described, based on the tabu search metaheuristic. Hierarchical strategies have been proposed in the literature for complex scheduling problems, and the tabu search metaheuristic, being able to cope with different memory levels, provides a natural background for the development of a hierarchical algorithm. For the case considered, a two level approach has been devised, based on the decomposition in a routing and a job shop scheduling subproblem, which is obtained by assigning each operation of each job to one among the equivalent machines. Both problems are tackled by tabu search. Coordination issues between the two hierarchical levels are considered. Unlike other hierarchical schemes, which are based on a one-way information flow, the one proposed here is based on a two-way information flow. This characteristic, together with the flexibility of local search strategies like tabu search, allows to adapt the same basic algorithm to different objective functions. Preliminary computational experience is reported.     

A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal

The scheduling problem in a container terminal is characterized by the coordination of different types of equipment. In this paper, we present an integrated model to schedule the equipment. The objective is to minimize the makespan, or the time it takes to serve a given set of ships. The problem is formulated as a Hybrid Flow Shop Scheduling problem with precedence and Blocking constraints (HFSS-B). A tabu search algorithm is proposed to solve this problem. Certain mechanisms are developed and introduced into the algorithm to assure its quality and efficiency. The performance of the tabu search algorithm is analyzed from the computational point of view.     

An evolutionary approach for bandwidth multicoloring problems

In this paper we consider some generalizations of the vertex coloring problem, where distance constraints are imposed between adjacent vertices (bandwidth coloring problem) and each vertex has to be colored with more than one color (bandwidth multicoloring problem). We propose an evolutionary metaheuristic approach for the first problem, combining an effective tabu search algorithm with population management procedures. The approach can be applied to the second problem as well, after a simple transformation. Computational results on instances from the literature show that the overall algorithm is able to produce high quality solutions in a reasonable amount of time, outperforming the most effective algorithms proposed for the bandwidth coloring problem, and improving the best known solution of many instances of the bandwidth multicoloring problem.     

A two-phase hybrid metaheuristic for the vehicle routing problem with time windows

The subject of this paper is a two-phase hybrid metaheuristic for the vehicle routing problem with time windows and a central depot (VRPTW). The objective function of the VRPTW considered here combines the minimization of the number of vehicles (primary criterion) and the total travel distance (secondary criterion). The aim of the first phase is the minimization of the number of vehicles by means of a (μ,λ)-evolution strategy, whereas in the second phase the total distance is minimized using a tabu search algorithm. The two-phase hybrid metaheuristic was subjected to a comparative test on the basis of 356 problems from the literature with sizes varying from 100 to 1000 customers. The derived results show that the proposed two-phase approach is very competitive.