Journées de l'optimisation 2007 Optimizations days

The Dynamic Fixed Charge Capacitated Location Problem (DFCCLP) is a NP-Hard location problem where are given a number of scenarios in a pre-defined time horizon, in each scenario exists a defined static situation of demand, offer and capacities related to the customers and the facilities. Between these scenarios, the customers may appear and/or disappear, increase or decrease demand, and also the facilities, and the transportation costs may vary. A function of regret for misallocation is considered in which the problem's objective searches to minimize the maximum regret of allocating the same set of facilities during all the time horizon. In this work we show the formulation of the problem and a new approach based on a GRASP based meta-heuristic, that combines the effort of best allocating at each scenario and the maintenance of the same set for the other scenarios (taking the maximum regret), and then minimizing the regrets obtained. A set of OR-Library test problem were used to evaluate the solutions and also a random set of euclidean instances were generated to show the performance and accuracy of the proposed polynomial procedure. Keywords: Capacitated Location Problem, Dynamic Location Problems.

The Multi-commodity Pickup-and-Delivery Single Vehicle Routing Problem is a variant of the TSP where cities corresponds to customers providing or requiring known amounts of $m$ different commodities, and the vehicle has a given upper-limit capacity. Each object may have one or more sources/destinations, and the vehicle must visit each customer exactly once. We discuss mathematical models for the "one-to-one" and the "many-to-many" versions, and present computational results based on a branch-and-cut procedure.

The Constrained Clustering Problem in Graphs (CCPG) is stated as follows: given a symmetric connected weighted graph in the nodes and links, where in each node its weight means demand, and at each link the weight means cost to connect two adjacent nodes, the problem searches for a number of connected components of the graph that does not exceed a pre-defined capacity constraint of the demanded nodes. Its objective function minimizes the variable cost related to the links used in each connected component and the fixed cost associated in opening a component. The CCGP is NP-HARD and it is closely related to the Multi-Cut Problem, previously reported by the literature. It can be applied in VLSI design, Garbage Collection, Aggregation of Similar Regions for the Bureau Census, Distribution of Disease Urban Sanitary Agents, Districting, and many others. Here we propose a composite exact method using multi-start metaheuristic, and a Branch & Bound oracle, which use cuts on the branching tree by an embedded previous sieves procedure. The sieves explore common and high level sense ideas about the technics of exploring the CCGP solutions, as the actual structure and relationships of groups formed to achieve the exact solution. The strategy reduces the whole branching tree characterized by other B&B approaches based on nodes. We show the parallelization of the method and the speedup related to the number of machines used versus the size of the instances. Keywords: Branch&Bound, Sieves, Bad Structured Problems