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
JOPT2017
HEC Montréal, 8 — 11 mai 2017
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
-
15h30 - 15h55
A GVNS heuristic for the traveling salesman problem with time windows - minimizing completion time
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.
-
15h55 - 16h20
A Tabu Search Heuristic for a Multi-Attribute Technician Routing and Scheduling problem
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.
-
16h20 - 16h45
Integrated Shift Scheduling and Load Assignment Optimization for Attended Home Delivery
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.
-
16h45 - 17h10
An ALNS for the Home Health Care Routing and Scheduling Problem
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%.