4 présentations

• 
  09h00 - 09h25

  Minimizing Emissions in Facility Location

  • John Gunnar Carlsson, prés., University of Minnesota

  We consider a continuous facility location problem in which our objective is to minimize the total emissions that are produced as a result of the placement of the facilities. We consider three sources of emissions: the facilities themselves, transportation between facilities via a backbone network, and transportation from facilities to customers. We first analyze the limiting behavior of this model and derive an expression for the total amount of emissions when facilities are placed in a hexagonal tiling (the well-studied honeycomb heuristic). We then show that the total emissions are reduced by over 27% when facilities are placed along an Archimedean spiral, and that the spiral is in fact an asymptotically optimal conguration as the service region becomes densely populated by customers. Finally, we give a fast constant-factor approximation algorithm for finding the emissions-optimal placement of a set of facilities in any convex
  polygon.

• 
  09h25 - 09h50

  Robust Partitioning for Stochastic Multi-Vehicle Routing

  • Erick Delage, prés., GERAD, HEC Montréal
  • John Gunnar Carlsson, University of Minnesota

  The problem of coordinating a fleet of vehicles so that all demand points on a territory are serviced and that the workload is most evenly distributed among the vehicles is a hard one. For this reason, it is often an effective strategy to first divide the service region and impose that each vehicle is only responsible for its own subregion. This heuristic has also the practical advantage that over time, drivers become more effective at serving their territory and customers. In this paper, we assume that client locations are unknown at the time of partitioning the territory and that each of them will be drawn identically and independently according to a distribution that is actually also unknown. In practice, it might be impossible to identify precisely the distribution if, for instance, information about the demand is limited to historical data. Our approach suggests partitioning the region with respect to the worst-case distribution that satisfies first and second order moments information. As a side product, our analysis constructs for each subregion a closed-form expression for the worst-case density function, thus providing useful insights about what affects the completion time most heavily. The successful implementation of our approach relies on two branch-and-bound algorithms: while the first finds a globally optimal partition of a convex polygon into two subregions, the second finds a local optimum for the harder n-partitioning problem. Finally, simulations of a parcel delivery problem will demonstrate that our data-driven approach makes better use of historical data as it becomes available.

• 
  09h50 - 10h15

  On a Formulation of the Shortest Loop Design Problem

  • Amir Ahmadi-Javid, Amirkabir University of Technology
  • Amir Ardestani-Jaafari, prés., Amirkabir University of Technology

  We correct the constraints of the formulation proposed for the shortest loop design problem by Farahani et al. (2005). We prove the necessity and sufficiency of the corrected constraints in determining all of the appropriate single loops. We also investigate conditions under which the previous constraints work correctly.

• 
  10h15 - 10h40

  Nouvelles inégalités valides pour le problème de partitionnement d’ensemble.

  • Mounira Groiez, prés., GERAD, École Polytechnique de Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Odile Marcotte, Université du Québec à Montréal

  Le problème de partitionnement d'ensemble est l'un des plus importants problèmes d'optimisation combinatoire en raison de ses nombreuses applications. Dans notre présentation, nous proposerons une nouvelle classe d'inégalités valides pour le problème de partitionnement d'ensemble et nous
  décrirons une méthode de séparation. Cette dernière est basée sur la résolution d'un programme linéaire en nombres entiers. Nous présenterons aussi quelques résultats numériques.