A linear programming approach to the electricity contract capacity problem

Determination of electricity contract capacity is a problem faced by all industrial customers in Taiwan. In the literature, the problem has been solved using metaheuristics, such as genetic algorithm and particle swarm optimization, which require substantial computation time to solve. In this paper we formulate the problem as a linear program, which requires only polynomial time. Our proposed linear program is better than any metaheuristic approach because a globally optimal solution can be guaranteed while using much less computation time. Two real-world cases, one from a university and the other from a paper mill, are used to demonstrate that the model can minimize the electricity bill for industrial customers.     

Solving the open vehicle routeing problem via a single parameter metaheuristic algorithm

In this paper, we consider the open vehicle routeing problem (OVRP), in which routes are not sequences of locations starting and ending at the depot but open paths. The problem is of particular importance for planning fleets of hired vehicles, a common practice in the distribution and service industry. In such cases, the travelling cost is a function of the vehicle open paths. To solve the problem, we employ a single-parameter metaheuristic method that exploits a list of threshold values to guide intelligently an advanced local search. Computational results on a set of benchmark problems show that the proposed method consistently outperforms previous approaches for the OVRP. A real-world example demonstrates the applicability of the method in practice, demonstrating that the approach can be used to solve actual problems of routing large vehicle fleets.     

Simulated annealing metaheuristics for the vehicle routing problem with time windows

This paper develops simulated annealing metaheuristics for the vehicle routing and scheduling problem with time window constraints. Two different neighborhood structures, the λ-interchange mechanism of Osman and thek-node interchange process of Christofides and Beasley, are implemented. The enhancement of the annealing process with a short-term memory function via a tabu list is examined as a basis for improving the metaheuristic approach. Computational results on test problems from the literature as well as large-scale real-world problem are reported. The metaheuristics achieve solutions that compare favorably with previously reported results.     

Integrated distribution and loading planning via a compact metaheuristic algorithm

The present article examines a vehicle routing problem integrated with two-dimensional loading constraints, called 2L-CVRP. The problem is aimed at generating the optimal route set for satisfying customer demand. In addition, feasible loading arrangements have to be determined for the transported products. To solve 2L-CVRP, we propose a metaheuristic solution approach. The basic advantage of our approach lies at its compact structure, as in total, only two parameters affect the algorithmic performance. To optimize the routing aspects, we propose a local-search method equipped with an effective diversification component based on the regional aspiration criteria. The problem’s loading requirements are tackled by employing a two-dimensional packing heuristic which repetitively attempts to develop feasible loading patterns. These attempts are effectively coordinated via an innovative, simple-structured memory mechanism. The overall solution framework makes use of several memory components for drastically reducing the computational effort required. The performance of our metaheuristic development has been successfully evaluated on benchmark instances considering two distinct versions of the loading constraints. More specifically, the algorithm managed to improve or match the majority of best known solution scores for both problem versions.     

Dynamic reconfiguration in multigroup multicast routing under uncertainty

Motivated by high quality multimedia and remote collaborative environments, we solve the problem of multigroup multicast routing with a number of features important for real-world deployment of the interactive media technologies. Based on the ant colony optimization metaheuristic, our algorithm is the first to work with uncertain knowledge of underlying network capabilities and support on-the-fly media transcoding inside the multicast tree. New contributions of this work are described next. We present two extensions of the algorithm, which improve quality of the solution. We introduce an integrated approach to solution of the problem, which is effective for both original solving from scratch as well as for new dynamic reconfiguration of multicast tree, where minimum perturbation of existing solution is desired. Experiments show that our algorithm is not only successful in maintaining existing communication with low number of unnecessary disruptions, but also capable of keeping the multicast trees efficient.     

Solving the short-term electrical generation scheduling problem by an adaptive evolutionary approach

In this paper, we introduce an adaptive evolutionary approach to solve the short-term electrical generation scheduling problem (STEGS). The STEGS is a hard constraint satisfaction optimization problem. The algorithm includes various strategies proposed in the literature to tackle hard problems with constraints such as: the representation used a non-binary coding scheme that drastically reduces the search space compared with the traditional evolutionary approaches. Specialized operators are especially designed for this problem and for this kind of representation, which also includes a local search procedure. Furthermore, the algorithm is guided by an adaptive parameter control strategy. We used some very well known benchmarks for STEGS to evaluate our approach. The results are very encouraging and we have obtained new better values for all the systems tested. Our aim here is to show that evolutionary approaches can be considered as good techniques to be used to solve real-world highly constrained problems.     

A flexible adaptive memory-based algorithm for real-life transportation operations: Two case studies from dairy and construction sector

Effective routing of vehicles remains a focal goal of all modern enterprises, thriving for excellence in project management with minimal investment and operational costs. This paper proposes a metaheuristic methodology for solving a practical variant of the well-known Vehicle Routing Problem, called Heterogeneous Fixed Fleet VRP (HFFVRP). Using a two-phase construction heuristic, called GEneralized ROute Construction Algorithm (GEROCA), the proposed metaheuristic approach enhances its flexibility to easily adopt various operational constraints. Via this approach, two real-life distribution problems faced by a dairy and a construction company were tackled and formulated as HFFVRP. Computational results on the aforementioned case studies show that the proposed metaheuristic approach (a) consistently outperforms previous published metaheuristic approaches we have developed to solve the HFFVRP, and (b) substantially improves upon the current practice of the company. The key result that impressed both companies’ management was the improvement over the bi-objective character of their problems: the minimization of the total distribution cost as well as the minimization of the number of the given heterogeneous number of vehicles used.     

An effective greedy heuristic for the Social Golfer Problem

The Social Golfer Problem (SGP) is a combinatorial optimization problem that exhibits a lot of symmetry and has recently attracted significant attention. In this paper, we present a new greedy heuristic for the SGP, based on the intuitive concept of freedom among players. We use this heuristic in a complete backtracking search, and match the best current results of constraint solvers for several SGP instances with a much simpler method. We then use the main idea of the heuristic to construct initial configurations for a metaheuristic approach, and show that this significantly improves results obtained by local search alone. In particular, our method is the first metaheuristic technique that can solve the original problem instance optimally. We show that our approach is also highly competitive with other metaheuristic and constraint-based methods on many other benchmark instances from the literature.     

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 Metaheuristic to Solve a Location-Routing Problem with Non-Linear Costs

The paper deals with a location-routing problem with non-linear cost functions. To the best of our knowledge, a mixed integer linear programming formulation for the addressed problem is proposed here for the first time. Since the problem is NP-hard exact algorithms are able to solve only particular cases, thus to solve more general versions heuristics are needed. The algorithm proposed in this paper is a combination of a p-median approach to find an initial feasible solution and a metaheuristic to improve the solution. It is a hybrid metaheuristic merging Variable Neighborhood Search (VNS) and Tabu Search (TS) principles and exploiting the synergies between the two. Computational results and conclusions close the paper.     

A Rollout Metaheuristic for Job Shop Scheduling Problems

In this paper we deal with solution algorithms for a general formulation of the job shop problem, called alternative graph. We study in particular the job shop scheduling problem with blocking and/or no-wait constraints. Most of the key properties developed for solving the job shop problem with infinite capacity buffer do not hold in the more general alternative graph model. In this paper we report on an extensive study on the applicability of a metaheuristic approach, called rollout or pilot method. Its basic idea is a look-ahead strategy, guided by one or more subheuristics, called pilot heuristics. Our results indicate that this method is competitive and very promising for solving complex scheduling problems.     

Fast Fourier optimization

Many interesting and fundamentally practical optimization problems, ranging from optics, to signal processing, to radar and acoustics, involve constraints on the Fourier transform of a function. It is well-known that the fast Fourier transform (fft) is a recursive algorithm that can dramatically improve the efficiency for computing the discrete Fourier transform. However, because it is recursive, it is difficult to embed into a linear optimization problem. In this paper, we explain the main idea behind the fast Fourier transform and show how to adapt it in such a manner as to make it encodable as constraints in an optimization problem. We demonstrate a real-world problem from the field of high-contrast imaging. On this problem, dramatic improvements are translated to an ability to solve problems with a much finer grid of discretized points. As we shall show, in general, the “fast Fourier” version of the optimization constraints produces a larger but sparser constraint matrix and therefore one can think of the fast Fourier transform as a method of sparsifying the constraints in an optimization problem, which is usually a good thing.     

An iterated greedy metaheuristic for the blocking job shop scheduling problem

In this paper we consider a job shop scheduling problem with blocking (BJSS) constraints. Blocking constraints model the absence of buffers (zero buffer), whereas in the traditional job shop scheduling model buffers have infinite capacity. There are two known variants of this problem, namely the blocking job shop scheduling with swap allowed (BWS) and the one with no swap allowed (BNS). This scheduling problem is receiving an increasing interest in the recent literature, and we propose an Iterated Greedy (IG) algorithm to solve both variants of the problem. IG is a metaheuristic based on the repetition of a destruction phase, which removes part of the solution, and a construction phase, in which a new solution is obtained by applying an underlying greedy algorithm starting from the partial solution. A comparison with recent published results shows that the iterated greedy algorithm outperforms other state-of-the-art algorithms on benchmark instances. Moreover it is conceptually easy to implement and has a broad applicability to other constrained scheduling problems.     

Nonlinear goal programming using multi-objective genetic algorithms

Goal programming is a technique often used in engineering design activities primarily to find a compromised solution which will simultaneously satisfy a number of design goals. In solving goal programming problems, classical methods reduce the multiple goal-attainment problem into a single objective of minimizing a weighted sum of deviations from goals. This procedure has a number of known difficulties. First, the obtained solution to the goal programming problem is sensitive to the chosen weight vector. Second, the conversion to a single-objective optimization problem involves additional constraints. Third, since most real-world goal programming problems involve nonlinear criterion functions, the resulting single-objective optimization problem becomes a nonlinear programming problem, which is difficult to solve using classical optimization methods. In tackling nonlinear goal programming problems, although successive linearization techniques have been suggested, they are found to be sensitive to the chosen starting solution. In this paper, we pose the goal programming problem as a multi-objective optimization problem of minimizing deviations from individual goals and then suggest an evolutionary optimization algorithm to find multiple Pareto-optimal solutions of the resulting multi-objective optimization problem. The proposed approach alleviates all the above difficulties. It does not need any weight vector. It eliminates the need of having extra constraints needed with the classical formulations. The proposed approach is also suitable for solving goal programming problems having nonlinear criterion functions and having a non-convex trade-off region. The efficacy of the proposed approach is demonstrated by solving a number of nonlinear goal programming test problems and an engineering design problem. In all problems, multiple solutions (each corresponding to a different weight vector) to the goal programming problem are found in one single simulation run. The results suggest that the proposed approach is an effective and practical tool for solving real-world goal programming problems.     

Metaheuristic methods based on Tabu search for assigning judges to competitions

Two metaheuristic methods based on Tabu search are introduced to assign judges to individual competitions in a tournament. The complexity of the mathematical formulation accounting for the assignment rules, leads us to use such an approach. The first metaheuristic includes two different Tabu searches that are combined with a diversification strategy. The second metaheuristic is applied to a penalized version of the original model formulated as an assignment problem. This metaheuristic is also based on a Tabu search procedure including a diversification strategy driven by the constraints violated. Numerical results are provided to indicate the efficiency of the methods to generate very good solutions.     

Metaheuristics for High School Timetabling

In this paper we present the results of an investigation of the possibilities offered by three well-known metaheuristic algorithms to solve the timetable problem, a multi-constrained, NP-hard, combinatorial optimization problem with real-world applications. First, we present our model of the problem, including the definition of a hierarchical structure for the objective function, and of the neighborhood search operators which we apply to matrices representing timetables. Then we report about the outcomes of the utilization of the implemented systems to the specific case of the generation of a school timetable. We compare the results obtained by simu lated annealing, tabu search and two versions, with and without local search, of the genetic algorithm. Our results show that GA with local search and tabu search based on temporary problem relaxations both outperform simulated annealing and handmade timetables.     

A methodology to solve large-scale cooperative transportation planning problems

In this paper, we suggest a methodology to solve a cooperative transportation planning problem and to assess its performance. The problem is motivated by a real-world scenario found in the German food industry. Several manufacturers with same customers but complementary food products share their vehicle fleets to deliver their customers. After an appropriate decomposition of the entire problem into sub problems, we obtain a set of rich vehicle routing problems (VRPs) with time windows for the delivery of the orders, capacity constraints, maximum operating times for the vehicles, and outsourcing options. Each of the resulting sub problems is solved by a greedy heuristic that takes the distance of the locations of customers and the time window constraints into account. The greedy heuristic is improved by an appropriate Ant Colony System (ACS). The suggested heuristics to solve the problem are assessed within a dynamic and stochastic environment in a rolling horizon setting using discrete event simulation. We describe the used simulation infrastructure. The results of extensive simulation experiments based on randomly generated problem instances and scenarios are provided and discussed. We show that the cooperative setting outperforms the non-cooperative one.     

Universiti Malaysia Pahang examination timetabling problem: scheduling invigilators

This paper presents a real-world examination timetabling problem from Universiti Malaysia Pahang (UMP), Malaysia. The problem involves assigning invigilators to examination rooms. This problem has received less attention than the examination timetabling problem from the research community partly because no data sets are available in the literature. In modelling, and solving, this problem we assume that there is already an examination timetable in place (this was the subject of our previous work) and the task is to assign invigilators to that timetable. The contributions of this paper are to formally define the invigilator scheduling problem and to present a constructive algorithm that is able to produce good quality solutions that are superior to the solutions produced when using the university's current software. We also include additional constraints taking into account the comments made by the invigilators, which the current system fails to capture. The model we present, we believe, accurately reflects the real-world problem, capturing various aspects of the problem that have not been presented before in the scientific literature. Moreover, the proposed approach adheres to all hard constraints, which the university's current system fails to do.     

Optimal Noncollapsing Space-Filling Designs for Irregular Experimental Regions

Space-filling and noncollapsing are two important properties in designing computer experiments. We study how the noncollapsing, space-filling designs for irregular experimental regions can be generated efficiently by the proposed metaheuristic methods. We solve this optimal design problem using variants of the discrete particle swarm optimization (DPSO) approaches. Numerical results, including an application in data center thermal management, are used to illustrate the performances of the proposed algorithms. Based on these numerical results, we assert that the most efficient approach is to reformulate the target optimal design problem as a constrained optimization problem and then use a modified DPSO to solve the constrained optimization problem.     

Direct solution to constrained tropical optimization problems with application to project scheduling

We examine a new optimization problem formulated in the tropical mathematics setting as a further extension of certain known problems. The problem is to minimize a nonlinear objective function, which is defined on vectors over an idempotent semifield by using multiplicative conjugate transposition, subject to inequality constraints. As compared to the known problems, the new one has a more general objective function and additional constraints. We provide a complete solution in an explicit form to the problem by using an approach that introduces an auxiliary variable to represent the values of the objective function, and then reduces the initial problem to a parametrized vector inequality. The minimum of the objective function is evaluated by applying the existence conditions for the solution of this inequality. A complete solution to the problem is given by solving the parametrized inequality, provided the parameter is set to the minimum value. As a consequence, we obtain solutions to new special cases of the general problem. To illustrate the application of the results, we solve a real-world problem drawn from time-constrained project scheduling, and offer a representative numerical example.