Journées de l'optimisation 2014

                             Incluant une Journée industrielle de l'optimisation

                                              HEC Montréal, 5 - 7 mai 2014


HEC Montréal, 5 — 7 mai 2014

Horaire Auteurs Mon horaire

WA3 Problèmes du voyageur de commerce / Traveling Salesman Problems

7 mai 2014 09h00 – 10h40

Salle: Gérard-Parizeau

Présidée par Jamal Ouenniche

3 présentations

  • 09h00 - 09h25

    The Selective Traveling Salesman Problem with Incompatibility Constraints

    • M. Angélica Salazar-Aguilar, prés., Universidad Autónoma de Nuevo León
    • Pamela Jocelyn Palomo-Martínez, Universidad Autónoma de Nuevo León

    The problem addressed in this work consists of finding a path whose duration does not exceed a given time limit, includes all mandatory vertices, and a subset of optional vertices such that the total collected profit is maximized. Additionally, some incompatibility constraints between vertices is taken into account.

  • 09h25 - 09h50

    Comparative Analysis of Construction Methods for Probabilistic TSPs

    • Jamal Ouenniche, University of Edinburgh
    • Pascal Wissink, prés., University of Edinburgh

    The first attempts to address the stochastic versions of the well-known and challenging traveling salesman problem (TSP) have led to a variety of heuristics – both construction methods and improvement methods. In this research, we classify the construction heuristics proposed so far for the probabilistic TSP and provide a conceptual comparative analysis along with an empirical one with the aim of shedding light on the similarities and differences in design and their implications on empirical performance.

  • 09h50 - 10h15

    The Traveling Salesman Problem with Time-Dependent Service Times

    • Duygu Tas, prés., HEC Montréal
    • Michel Gendreau, Polytechnique Montréal
    • Ola Jabali, HEC Montréal
    • Gilbert Laporte, HEC Montréal

    The Traveling Salesman Problem (TSP) with time-dependent service times is a generalization of the classical TSP where the duration required to serve any customer is defined as a function of the moment to begin service at that location. We describe analytical insights derived from properties of service time, and present experimental results.