Including an Industrial Optimization Day

HEC Montréal, May 7 - 9, 2012


HEC Montréal, May 7 — 9, 2012

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

WA9 Problèmes d'aménagement et de partitionnement / Layout and Partitionning Problems

May 9, 2012 09:00 AM – 10:40 AM

Location: Xerox Canada

Chaired by John Carlsson

4 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    09:00 AM - 09:25 AM

    Minimizing Emissions in Facility Location

    • John Gunnar Carlsson, presenter, 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

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    09:25 AM - 09:50 AM

    Robust Partitioning for Stochastic Multi-Vehicle Routing

    • Erick Delage, presenter, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    09:50 AM - 10:15 AM

    On a Formulation of the Shortest Loop Design Problem

    • Amir Ahmadi-Javid, Amirkabir University of Technology
    • Amir Ardestani-Jaafari, presenter, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10:15 AM - 10:40 AM

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

    • Mounira Groiez, presenter, 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.