EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3849. A Column Generation Approach for the Routing of Electricity Technicians

Invited abstract in session MC-58: Column Generation for Vehicle Routing, stream VeRoLog - Vehicle Routing and Logistics.

Monday, 12:30-14:00
Room: S07 (building: 101)

Authors (first author is the speaker)

1. Elise Bangerter
DS&OR group, University of Fribourg
2. David Schindl
Economie d'entreprise, HEG Genève, HES-SO University of Applied Sciences and Arts Western Switzerland
3. Meritxell Pacheco Paneque
DS&OR, Univeristy of Fribourg

Abstract

The maintenance of an electricity distribution network involves numerous daily technical interventions. In this problem, we are given a set of interventions each with associated time windows, location, necessary skills and duration, as well as a set of teams of technicians with associated set of skills. We need to find feasible routes on the interventions for each team, considering the time windows and skills, and ensure that each team returns to its departure depot before the end of the day. The primary objective is to maximize the total duration of completed interventions and as a secondary objective, we aim to minimize the overall routing cost. This problem can be formulated as a capacitated vehicle routing problem with time windows. Due to the large number of teams and interventions, this results in a large-scale optimization problem, and its operational nature limits the time available for exact solving. Here, we propose a column generation approach where one subproblem per vehicle has to be solved and each potential route of a vehicle is considered as a new column in the master problem. To generate these routes, we rely on dynamic programming. Real-world instances from EDF (Electricité de France) of historical technicians' interventions will be used to evaluate the effectiveness of the proposed methods.

Keywords

Status: accepted

Back to the list of papers