Retour

Séance TB8 - Tournées de véhicules III / Vehicle Routing Problem III

Jour mardi, le 8 mai 2007
Salle TAL Gestion globale d'actifs inc.
Président Gilbert Laporte

Présentations

13h30-
13h55
An Approach to the Dynamic Fixed Charge Capacitated Location Problem
  Marcos José Negreiros Gomes, State University of Ceará, Mestrado Profissional em Computação Aplicada - MPCOMP-UECE/CEFET-CE, Av Paranjana, 1700 - Campus do Itaperi, Fortaleza, Ceará, Brazil, 60740-000
Augusto Wagner de Castro Palhano, State University of Ceará, Mestrado Profissional em Computação Aplicada - MPCOMP-UECE/CEFET-CE, Av Paranjana, 1700 - Campus do Itaperi, Fortaleza, CE, Brazil, 60740-000
Ingrid Guedes Teles, Federal University of Ceará, Mestrado em Ciência da Computação, Campus do Pici, Fortaleza, Ceará, Brazil

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.


13h55-
14h20
Modeling and Solving a Multi-Commodity Pickup-and-Delivery Single Vehicle Routing Problem
  Juan-José Salazar González, Universidad de La Laguna, DEIOC, Canary Islands, La Laguna, Tenerife, Spain, E-38271
Hipólito Dr. Hernández Pérez, University of La Laguna, DEIOC, La Laguna, Tenerife, Spain, E-38271

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.


14h20-
14h45
A Branch & Bound and Sieves Approach to the Capacitated Clustering Problem in Graphs
  Marcos José Negreiros Gomes, State University of Ceará, Mestrado Profissional em Computação Aplicada - MPCOMP-UECE/CEFET-CE, Av Paranjana, 1700 - Campus do Itaperi, Fortaleza, Ceará, Brazil, 60740-000
José Alexandre Dantas Filho, State University of Ceará, Mestrado Profissional em Computação Aplicada - MPCOMP-UECE/CEFET-CE, Av Paranjana, 1700 - Campus do Itaperi, Fortaleza, Ceará, Brazil, 60740-000

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


Retour