pith. sign in

arxiv: 2604.05153 · v1 · submitted 2026-04-06 · 🧮 math.OC · cs.DM

A column-generation approach for an electricity technician routing and scheduling problem with a lexicographic objective

Elise Bangerter , David Schindl , Meritxell Pacheco Paneque , Nour Elhouda Tellache , Rodolphe Griset This is my paper

Pith reviewed 2026-05-10 18:48 UTC · model grok-4.3

classification 🧮 math.OC cs.DM
keywords technician routingschedulingcolumn generationlexicographic optimizationmulti-objectiveset packingdynamic programmingelectric utility
0
0 comments X

The pith

A column-generation algorithm solves the lexicographic technician routing problem more effectively than compact mixed-integer formulations on real utility data.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Electric utilities must decide daily which technician interventions to complete when not all can finish in one day. The primary goal is to maximize total completed intervention time; the secondary goal is to minimize travel and overtime costs. The paper formulates the problem as a set-packing model and solves it with column generation whose pricing subproblems use dynamic programming labels. Two reformulations keep the primary objective strictly ahead of the secondary one. Tests on instances from a French electric utility show the sequential column-generation variant proves optimality on more small cases and returns solutions with smaller gaps to the best observed value on larger cases, all within practical daily time limits.

Core claim

The authors present both a compact mixed-integer linear program and an extended set-packing formulation for the multi-day technician routing and scheduling problem with lexicographic objectives. They solve the extended model with an exact column-generation procedure whose pricing problems are solved by a dynamic-programming labeling algorithm. Weighted-sum and sequential reformulations are used to enforce the lexicographic order inside a single-objective solver. Computational tests on real instances demonstrate that the sequential column-generation variant finds the best-known solutions on more instances and achieves lower mean gaps relative to the best solution found in each instance size.

What carries the argument

Column-generation algorithm with dynamic-programming labeling for the pricing subproblems, applied to sequential or weighted-sum reformulations of the lexicographic objective inside a set-packing formulation.

If this is right

  • The sequential reformulation maintains the strict priority of maximizing total completed intervention duration over cost minimization.
  • The column-generation method proves optimality on a larger fraction of small real instances than the compact formulation.
  • On larger instances the column-generation approach consistently yields smaller optimality gaps within a five-minute limit.
  • Daily schedules generated this way remain feasible for operational use at electric utilities.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar column-generation schemes could handle other routing problems where one objective must dominate another exactly.
  • The labeling algorithm for pricing may extend to technician problems that add time windows or skill constraints.
  • Embedding the method in a rolling daily planner could improve week-long intervention coverage without increasing overtime.

Load-bearing premise

The weighted-sum and sequential reformulations preserve the exact lexicographic priority between maximizing completed intervention time and minimizing cost without numerical instability or optimality loss for the first objective.

What would settle it

A new collection of instances on which the sequential column-generation variant produces solutions with equal or larger gaps to the best-known values than the compact formulation, or fails to prove optimality on a comparable share of small cases, would falsify the performance advantage.

Figures

Figures reproduced from arXiv: 2604.05153 by David Schindl, Elise Bangerter, Meritxell Pacheco Paneque, Nour Elhouda Tellache, Rodolphe Griset.

Figure 1
Figure 1. Figure 1: Vehicle-to-intervention ratio of the raw and test (standardized) instances [PITH_FULL_IMAGE:figures/full_fig_p018_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Objective values f 1 obtained on the five largest EDF instances (5- minute time limit). formulations, and their respective values remain close across instances. This behavior can be compared to the results observed for the L instances in [PITH_FULL_IMAGE:figures/full_fig_p022_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Objective values f 1 obtained on the five largest EDF instances (8-hour time limit). The y-axis has been truncated to improve visibility of differences. 22 [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗
read the original abstract

Electric utility companies perform numerous technical interventions every day. Since it is generally not possible to complete all planned interventions within a single day, companies face two objectives: maximizing the total duration of completed interventions (primary objective) and minimizing the associated operational cost (secondary objective). In this paper, we introduce a multi-objective variant of the technician routing and scheduling problem in which both objectives are optimized in lexicographic order. We propose a compact mixed-integer linear formulation and an extended set-packing-based formulation. To handle the objectives within a single-objective framework, we consider weighted-sum reformulations that preserve lexicographic priorities as well as sequential reformulations that individually optimize each objective while maintaining the optimal value of higher-priority ones. For the extended formulation, we develop an exact column-generation-based algorithm, in which the pricing subproblems are solved via a labeling algorithm based on dynamic programming. As technician schedules are typically generated on a daily basis, the algorithm is designed to deliver high-quality solutions within short computation times (e.g., 5 minutes). Computational experiments on real-life instances provided by the French electric utility company show that the CG-based algorithm proves optimality on a larger number of small instances than the compact formulation and consistently outperforms it on larger instances. In particular, the sequential CG-based variant finds the best-known solutions on more instances and achieves lower mean gaps relative to the best solution found in each instance category.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces a multi-objective technician routing and scheduling problem with lexicographic objectives: primary maximization of total completed intervention duration and secondary minimization of operational cost. It presents a compact MILP formulation and an extended set-packing formulation, handles the lexicographic order via both weighted-sum and sequential single-objective reformulations, and develops an exact column-generation algorithm whose pricing problems are solved by dynamic-programming labeling. Computational experiments on real instances from a French electric utility demonstrate that the CG approach (especially its sequential variant) proves optimality on more small instances than the compact model, consistently outperforms it on larger instances, and yields the best-known solutions on more instances with lower mean gaps.

Significance. If the reported performance holds, the work supplies a practical exact method for a recurring real-world utility scheduling task under a 5-minute time limit, directly addressing the daily planning needs of electric companies. The combination of set-packing formulation, DP pricing, and careful lexicographic handling via sequential optimization is a solid, standard-strength contribution that could be adopted or extended in other multi-objective routing settings.

major comments (2)
  1. [§4] §4 (reformulations): the claim that the weighted-sum reformulation preserves exact lexicographic priorities is load-bearing for all subsequent claims; the manuscript must explicitly state the weight-selection rule (e.g., M larger than any possible secondary-objective range) and verify that the chosen M does not induce numerical instability on the real instances.
  2. [Table 2 / §5.2] Table 2 / §5.2 (computational results): the statement that the sequential CG variant 'finds the best-known solutions on more instances' is central to the performance claim, yet the table reports only aggregate counts and mean gaps; per-instance best-known values and the identity of the competing methods must be shown so that the superiority can be verified.
minor comments (2)
  1. [§2.1] §2.1: the notation for the two objectives (duration vs. cost) should be introduced with a single consistent symbol pair rather than switching between descriptive phrases and symbols.
  2. [Abstract and §5] Abstract and §5: 'best-known solution' is used without definition; it should be clarified that this refers to the best feasible solution found by any of the tested methods within the time limit.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and the recommendation for minor revision. We address each of the major comments below.

read point-by-point responses

  1. Referee: [§4] §4 (reformulations): the claim that the weighted-sum reformulation preserves exact lexicographic priorities is load-bearing for all subsequent claims; the manuscript must explicitly state the weight-selection rule (e.g., M larger than any possible secondary-objective range) and verify that the chosen M does not induce numerical instability on the real instances.

    Authors: We agree that an explicit statement of the weight-selection rule is necessary to substantiate the claim that the weighted-sum reformulation preserves the lexicographic order. In the revised manuscript, we will include in Section 4 the precise rule used: the weight M for the primary objective is set to a value strictly larger than the maximum attainable value of the secondary objective on any feasible solution. We will also report that numerical experiments on the real instances confirmed no instability issues with the chosen M in the CPLEX solver. revision: yes

  2. Referee: [Table 2 / §5.2] Table 2 / §5.2 (computational results): the statement that the sequential CG variant 'finds the best-known solutions on more instances' is central to the performance claim, yet the table reports only aggregate counts and mean gaps; per-instance best-known values and the identity of the competing methods must be shown so that the superiority can be verified.

    Authors: We recognize that aggregate results alone do not allow full verification of the per-instance superiority claims. To address this, we will add to the revised manuscript (likely as an online appendix or supplementary table) the detailed per-instance results, including the best-known objective value for each instance, the values achieved by the compact MILP, the weighted-sum CG, and the sequential CG variants, and an indication of which method(s) attained the best-known solution. This will substantiate the statement that the sequential CG variant finds the best-known solutions on more instances. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper develops a standard MILP formulation, set-packing extension, weighted-sum/sequential lex-objective reformulations, and exact CG algorithm with DP pricing. All load-bearing steps are explicit algorithmic constructions whose correctness is verified by standard theory (lex-order preservation via reformulations) and whose performance claims rest on empirical results over external real-life instances from the utility company. No self-definitional reductions, fitted inputs renamed as predictions, or load-bearing self-citations appear in the derivation chain. The central claims remain independent of the paper's own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the work relies on standard mixed-integer linear programming assumptions and column-generation techniques without introducing new entities or fitted parameters.

axioms (1)
  • domain assumption Mixed-integer linear programming can accurately represent the routing, scheduling, and intervention constraints of the problem.
    Both the compact and extended formulations are presented as MILPs.

pith-pipeline@v0.9.0 · 5570 in / 1162 out tokens · 65255 ms · 2026-05-10T18:48:22.026197+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

  1. [1]

    Arturo Castillo-Salazar, Dario Landa-Silva, and Rong Qu

    J. Arturo Castillo-Salazar, Dario Landa-Silva, and Rong Qu. Workforce scheduling and routing problems: literature survey and computational study.Annals of Operations Research, 239:39–67, 2016

    work page 2016

  2. [2]

    Fast local search and guided local search and their application to british telecom’s workforce scheduling problem.Operations Research Letters, 20(3):119–127, 1997

    Edward Tsang and Chris Voudouris. Fast local search and guided local search and their application to british telecom’s workforce scheduling problem.Operations Research Letters, 20(3):119–127, 1997

    work page 1997

  3. [3]

    Adaptive large neighborhood search for service technician routing and scheduling problems.Journal of scheduling, 15:579–600, 2012

    Attila A Kovacs, Sophie N Parragh, Karl F Doerner, and Richard F Hartl. Adaptive large neighborhood search for service technician routing and scheduling problems.Journal of scheduling, 15:579–600, 2012

    work page 2012

  4. [4]

    A parallel matheuristic for the technician routing and scheduling problem.Optimization Letters, 7(7):1525–1535, 2013

    Victor Pillac, Christelle Gueret, and Andrés L Medaglia. A parallel matheuristic for the technician routing and scheduling problem.Optimization Letters, 7(7):1525–1535, 2013

    work page 2013

  5. [5]

    Mixed integer linear programming for a multi-attribute technician routing and scheduling problem.INFOR: Information Systems and Operational Research, 56(1):33–49, 2018

    Ines Mathlouthi, Michel Gendreau, and Jean-Yves Potvin. Mixed integer linear programming for a multi-attribute technician routing and scheduling problem.INFOR: Information Systems and Operational Research, 56(1):33–49, 2018

    work page 2018

  6. [6]

    Branch-and-price for a multi- attribute technician routing and scheduling problem

    Ines Mathlouthi, Michel Gendreau, and Jean-Yves Potvin. Branch-and-price for a multi- attribute technician routing and scheduling problem. InOperations Research Forum, volume 2, page 1. Springer, 2021

    work page 2021

  7. [7]

    Dominique Feillet, Pierre Dejax, Michel Gendreau, and Cyrille Gueguen. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems.Networks: An International Journal, 44(3):216–229, 2004

    work page 2004

  8. [8]

    Ecole des hautes études commerciales, Groupe d’études et de recherche en analyse des décisions, 1988

    Martin Desrochers.An algorithm for the shortest path problem with resource constraints. Ecole des hautes études commerciales, Groupe d’études et de recherche en analyse des décisions, 1988. 26

    work page 1988

  9. [9]

    Exact and hybrid methods for the multiperiod field service routing problem.Central European Journal of Operations Research, 21:359–377, 2013

    Fabien Tricoire, Nathalie Bostel, Pierre Dejax, and Pierre Guez. Exact and hybrid methods for the multiperiod field service routing problem.Central European Journal of Operations Research, 21:359–377, 2013

    work page 2013

  10. [10]

    A new optimization algorithm for the vehicle routing problem with time windows.Operations research, 40(2):342–354, 1992

    Martin Desrochers, Jacques Desrosiers, and Marius Solomon. A new optimization algorithm for the vehicle routing problem with time windows.Operations research, 40(2):342–354, 1992

    work page 1992

  11. [11]

    Branch-and-price approaches for the multiperiod technician routing and scheduling problem.European Journal of Operational Research, 257 (1):55–68, 2017

    Emilio Zamorano and Raik Stolletz. Branch-and-price approaches for the multiperiod technician routing and scheduling problem.European Journal of Operational Research, 257 (1):55–68, 2017

    work page 2017

  12. [12]

    Branch-and-price and constraint programming for solving a real-life technician dispatching problem.European Journal of Operational Research, 238(1):300–312, 2014

    Cristián E Cortés, Michel Gendreau, Louis Martin Rousseau, Sebastián Souyris, and Andrés Weintraub. Branch-and-price and constraint programming for solving a real-life technician dispatching problem.European Journal of Operational Research, 238(1):300–312, 2014

    work page 2014

  13. [13]

    Optimization of the technician routing and scheduling problem for a telecommunication industry.Annals of Operations Research, 315 (1):371–395, 2022

    Ehsan Pourjavad and Eman Almehdawe. Optimization of the technician routing and scheduling problem for a telecommunication industry.Annals of Operations Research, 315 (1):371–395, 2022

    work page 2022

  14. [14]

    Enhanced iterated local search for the technician routing and scheduling problem.Computers & Operations Research, 160: 106385, 2023

    Ala-Eddine Yahiaoui, Sohaib Afifi, and Hamid Allaoui. Enhanced iterated local search for the technician routing and scheduling problem.Computers & Operations Research, 160: 106385, 2023

    work page 2023

  15. [15]

    Tactical planning for dynamic technician routing and scheduling problems.Transportation Research Part E: Logistics and Transportation Review, 177:103225, 2023

    Clara Chini Nielsen and David Pisinger. Tactical planning for dynamic technician routing and scheduling problems.Transportation Research Part E: Logistics and Transportation Review, 177:103225, 2023

    work page 2023

  16. [16]

    Gamache, F

    M. Gamache, F. Soumis, D. Villeneuve, J. Desrosiers, and É. Gélinas. The preferential bidding system at Air Canada.Transportation Science, 32(3):246–255, 1998

    work page 1998

  17. [17]

    Achour, M

    A. Achour, M. Gamache, F. Soumis, and G. Desaulniers. An exact solution approach for the preferential bidding system problem in the airline industry.Transportation Science, 41 (3):354–365, 2007

    work page 2007

  18. [18]

    Heßler, S

    K. Heßler, S. Irnich, T. Kreiter, and U. Pferschy. Bin packing with lexicographic objectives for loading weight-and volume-constrained trucks in a direct-shipping system.OR Spectrum, 44:1–43, 2022

    work page 2022

  19. [19]

    On a variant of the minimum path cover problem in acyclic digraphs: Computational complexity results and exact method.Networks, 86(3):325–357, 2025

    Nour ElHouda Tellache and Roberto Baldacci. On a variant of the minimum path cover problem in acyclic digraphs: Computational complexity results and exact method.Networks, 86(3):325–357, 2025

    work page 2025

  20. [20]

    Linear lexicographic optimization and preferential bidding system.Transportation Science, 58(3):597–613, 2024

    Nour ElHouda Tellache, Frédéric Meunier, and Axel Parmentier. Linear lexicographic optimization and preferential bidding system.Transportation Science, 58(3):597–613, 2024

    work page 2024

  21. [21]

    The weighted sum method for multi-objective optimization: new insights.Structural and multidisciplinary optimization, 41(6):853–862, 2010

    R Timothy Marler and Jasbir S Arora. The weighted sum method for multi-objective optimization: new insights.Structural and multidisciplinary optimization, 41(6):853–862, 2010

    work page 2010

  22. [22]

    On a bicriterion formulation of the problems of integrated system identifica- tion and system optimization.IEEE transactions on systems, man, and cybernetics, (3): 296–297, 1971

    Yacov Haimes. On a bicriterion formulation of the problems of integrated system identifica- tion and system optimization.IEEE transactions on systems, man, and cybernetics, (3): 296–297, 1971

    work page 1971

  23. [23]

    The big-M method with the numerical infi- nite M.Optim Lett, 15(7):2455–2468, 2021

    Marco Cococcioni and Lorenzo Fiaschi. The big-M method with the numerical infi- nite M.Optim Lett, 15(7):2455–2468, 2021. ISSN 1862-4472, 1862-4480. doi: 10.1007/ s11590-020-01644-6. URLhttps://link.springer.com/10.1007/s11590-020-01644-6. Publisher: Springer Science and Business Media LLC

    work page doi:10.1007/s11590-020-01644-6 2021

  24. [24]

    An exact algorithm for the pickup and delivery problem with time windows.Operations research, 59(2):414–426, 2011

    Roberto Baldacci, Enrico Bartolini, and Aristide Mingozzi. An exact algorithm for the pickup and delivery problem with time windows.Operations research, 59(2):414–426, 2011. 27

    work page 2011

  25. [25]

    Nemhauser and Laurence A

    George L. Nemhauser and Laurence A. Wolsey.Integer and Combinatorial Optimization. Wiley, 1988. ISBN 978-0-471-35943-2

    work page 1988

  26. [26]

    Johnson, and Manfred Padberg

    Harlan Crowder, Ellis L. Johnson, and Manfred Padberg. Solving large-scale zero-one linear programming problems.Operations Research, 31(5):803–834, 1983. doi: 10.1287/opre.31.5

    work page doi:10.1287/opre.31.5 1983

  27. [27]

    URLhttps://doi.org/10.1287/opre.31.5.803

    work page doi:10.1287/opre.31.5.803

  28. [28]

    Solution of a large-scale traveling- salesman problem.Journal of the operations research society of America, 2(4):393–410, 1954

    George Dantzig, Ray Fulkerson, and Selmer Johnson. Solution of a large-scale traveling- salesman problem.Journal of the operations research society of America, 2(4):393–410, 1954. E. Bangerter, Decision Support & Operations Research Group, Department of Informatics, University of Fribourg, Fribourg, Switzerland Email address:elise.bangerter@unifr.ch D. Sc...

    work page 1954