The simple plant location problem (SPLP) is considered and a genetic algorithm is proposed to solve this problem. By using the developed algorithm it is possible to solve SPLP with more than 1000 facility sites and customers. Computational results are presented and compared to dual based algorithms.
We consider a strong NP-hard single-machine scheduling problem with deadlines and minimizing the total weight of late jobs on a single machine (). Processing times are deterministic values or random variables having Erlang distributions. For this problem we study the tolerance to random parameter changes for solutions constructed according to tabu search metaheuristics. We also present a measure (called stability) that allows an evaluation of the algorithm based on its resistance to random parameter...
In this paper we consider the Capacitated Arc Routing Problem, in which a fleet of K vehicles, all of them based on a specific vertex (the depot) and with a known capacity Q, must service a subset of the edges of the graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity.A heuristic algorithm for this problem is proposed consisting of: the selection of K centers, the construction of K connected graphs with associated loads not exceeding the vehicle...
Parallel multi-deme genetic algorithms are especially advantageous because they allow reducing the time of computations and can perform a much broader search than single-population ones. However, their formal analysis does not seem to have been studied exhaustively enough. In this paper we propose a mathematical framework describing a wide class of island-like strategies as a stationary Markov chain. Our approach uses extensively the modeling principles introduced by Vose, Rudolph and their collaborators....
The logistics problems in business environments deal with assignation from a number of sources to a number of destinations. Each source offers amounts of goods, while each destination demands quantities of these goods. The object is to find the cheapest transporting schedule that satisfies the demand without violating supply restraints. In this paper we propose to use Fuzzy Sets to represent the previsional information related to costs, demands and other variables. Moreover, we suggest including...
Periodic Vehicle Routing Problem: classification and heuristic for tactical planning. The Periodic Vehicle Routing Problem (PVRP) consists in assigning customer visits to vehicle routes in some periods of a time horizon so as to satisfy some service level requirements that can take the form of frequency of visit, constraint on time lag between visits, or pre-defined visit patterns. We present different variants of this problem and propose a classification. Then, we consider a model for tactical...
This paper proposes a specialized LP-algorithm for a sub problem arising in simple Profit maximising Lot-sizing. The setting involves a single (and multi) item production system with negligible set-up costs/times and limited production capacity. The producer faces a monopolistic market with given time-varying linear demand curves.
Evolutionary Algorithms, also known as Genetic Algorithms in a former terminology, are probabilistic algorithms for optimization, which mimic operators from natural selection and genetics. The paper analyses the convergence of the heuristic associated to a special type of Genetic Algorithm, namely the Steady State Genetic Algorithm (SSGA), considered as a discrete-time dynamical system non-generational model. Inspired by the Markov chain results in finite Evolutionary Algorithms, conditions are...
In this paper we deal with the preemptive asymmetric stacker crane problem in a heuristic way. We first present some theoretical results which allow us to turn this problem into a specific tree design problem. We next derive from this new representation an integer linear programming model together with simple and efficient greedy and local search heuristics. We conclude by presenting experimental results which aim at both testing the efficiency of our heuristic and evaluating the impact of the...
In this paper we deal with the preemptive asymmetric stacker crane problem in a heuristic way. We first present some theoretical results which allow us to turn this problem into a specific tree design problem. We next derive from this new representation an integer linear programming model together with simple and efficient greedy and local search heuristics. We conclude by presenting experimental results which aim at both testing the efficiency of our heuristic and evaluating the impact of the...
Le problème de planification de techniciens et d'interventions pour les télécommunications (TIST pour Technicians and Interventions Scheduling Problem for Telecommunications) comprend la planification d'interventions et l'affectation d'équipes de techniciens à ces interventions. Chaque intervention est caractérisée, entre autres, par une priorité. L'objectif de ce problème est de séquencer les interventions en tenant compte de leur priorité tout en satisfaisant un ensemble de contraintes comme...
In this paper, a discrete-event simulation model is coupled with a genetic algorithm to treat highly combinatorial scheduling problems encountered in a production campaign of a fine chemistry plant. The main constraints and features of fine chemistry have been taken into account in the development of the model, thus allowing a realistic evaluation of the objective function used in the stochastic optimization procedure. After a presentation of problem combinatorics, the coupling strategy is then...