Journées de l'optimisation 2017

HEC Montréal, 8-10 mai 2017

1er Atelier Canadien sur l'optimisation des soins de santé (CHOW)

HEC Montréal, 10-11 mai 2017


HEC Montréal, 8 — 11 mai 2017

Horaire Auteurs Mon horaire
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

TD6 Tournées de véhicules et ordonnancement / Routing & Scheduling

9 mai 2017 15h30 – 17h10

Salle: CPA du Québec

Présidée par Florian Grenouilleau

4 présentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h30 - 15h55

    A GVNS heuristic for the traveling salesman problem with time windows - minimizing completion time

    • Khalid Amghar, Présentateur, Université de Montréal
    • Bernard Gendron, DIRO and CIRRELT, U. de Montréal
    • Jean-François Cordeau, HEC Montréal

    We use a GVNS (General Variable Neighborhood Search) heuristic for the traveling salesman problem with time windows where the objective is to minimize the completion time. We use efficient methods for checking the feasibility and the profitability of a movement, and for exploring the neighborhoods. The results indicate that our method is very competitive with the state-of-the-art.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h55 - 16h20

    A Tabu Search Heuristic for a Multi-Attribute Technician Routing and Scheduling problem

    • Ines Mathlouthi, Présentateur, Université de Montréal
    • Michel Gendreau, Polytechnique Montréal
    • Jean-Yves Potvin, Université de Montréal

    We propose a tabu search heuristic for a technician routing and scheduling problem. Our tabu search includes an adaptive memory that contains the best solutions visited during the search, as measured by their cost and the diversity they bring to the memory. The performance of this tabu search heuristic will be evaluated on instances with different characteristics. A comparison with an exact branch-and-price algorithm will also be reported.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h20 - 16h45

    Integrated Shift Scheduling and Load Assignment Optimization for Attended Home Delivery

    • Maria-Isabel Restrepo-Ruiz , Présentateur, Polytechnique Montréal
    • Frederic Semet, Univ. Lille, CNRS, Centrale Lille, Inria, CRIStAL
    • Thomas Pocreau, Colisweb
    • Frederic Semet, Univ. Lille, CNRS, Centrale Lille, Inria, CRIStAL
    • Thomas Pocreau, Colisweb

    We study an integrated shift scheduling and load assignment optimization problem for attended home delivery. The proposed approach is divided into two phases, each one corresponding to a different planning level: tactical and operational. In the tactical planning, a daily master plan is generated for each courier. This master plan defines the working shifts, the origin-destination pairs to visit, and the number of packages to deliver. In the operational planning, delivery orders are allocated to couriers in real-time. The stochastic and dynamic nature of customer orders is included in the tactical and operational decision levels, respectively. Results demonstrate that our approach provides robust tactical solutions that easily accommodate to fluctuations in customer orders, preventing additional costs related to the underutilization of couriers and to the use of external couriers to satisfy all delivery requests.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h45 - 17h10

    An ALNS for the Home Health Care Routing and Scheduling Problem

    • Florian Grenouilleau, Présentateur, CIRRELT
    • Nadia Lahrichi, Polytechnique Montréal
    • Louis-Martin Rousseau, Polytechnique Montréal

    The Home Health Care Routing and Scheduling Problem consists of scheduling, over a week, a given set of home visits and deciding which health resource will be used to perform each visit in which sequence. This problem can be seen as a mix between an assignment problem, with the visit allocation decision, and a vehicle routing problem with time windows for the scheduling part. In our study, we try to take into account a maximum of practical constraints. These constraints are partly linked to the assignment component of the problem, such as assuring the qualifications and availabilities of each nurse for each visit. We also consider, for the scheduling part, the time-dependent aspect of the travel times and the maximum amount of work hours per nurse over the week and over each workday. To solve this problem, we use a well-known method calls Adaptive Large Neighborhood Search (ALNS) which, starting from an initial solution, iteratively reconstruct some parts of this solution and try to produce a better one. To do so, we have developed problem-specific ALNS' destroy and repair operators coupled with classic ones. To test our method, we have used real data provided by the Alayacare company, a Canadian company which has created software for the home health care management. The results show that our metaheuristic permits to dramatically improve the Alayacare's solutions, by reducing the travel time by 30% and improving the patient-nurse fidelity by more than 6%.