Optimization Days 2017

HEC Montréal, May 8-10, 2017

1st Canadian Healthcare Optimization Workshop (CHOW)

HEC Montréal, May 10-11, 2017



HEC Montréal, 8 — 11 May 2017

Schedule Authors My Schedule

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

May 9, 2017 03:30 PM – 05:10 PM

Location: CPA du Québec

Chaired by Florian Grenouilleau

4 Presentations

  • 03:30 PM - 03:55 PM

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

    • Khalid Amghar, presenter, Université de Montréal
    • Bernard Gendron, Université de Montréal, CIRRELT
    • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT

    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.

  • 03:55 PM - 04:20 PM

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

    • Ines Mathlouthi, presenter, 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.

  • 04:20 PM - 04:45 PM

    Integrated Shift Scheduling and Load Assignment Optimization for Attended Home Delivery

    • Maria-Isabel Restrepo-Ruiz, presenter, 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.

  • 04:45 PM - 05:10 PM

    An ALNS for the Home Health Care Routing and Scheduling Problem

    • Florian Grenouilleau, presenter, 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%.