Christine Solnon
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Christine Solnon has a total of 22 co-authors. Here are the top co-authors by number of shared publications:
- Arthur Gontier
Univ Rennes, CNRS, IRISA
1 shared publication David Gérault
University of Surrey
1 shared publication- François Delobel
Université Clermont-Auvergne, CNRS, Mines de Saint-Étienne, LIMOS
1 shared publication François Schwarzentruber
ENS Lyon, UCB Lyon 1, CNRS, LIP, Universit de Lyon, Lyon, France
1 shared publication- Heiko Hamann
Department of Computer and Information Science, University of Konstanz, Konstanz, Germany
1 shared publication Loïc Rouquette
CITI, INRIA, INSA Lyon
1 shared publication
Latest Publications
- 25 December 2025
- Published by Elsevier in Artificial Intelligence
- Vol. 352
LAD2025, A constraint-based solver for the subgraph isomorphism problem
- 25 December 2025
- Published by Elsevier in Artificial Intelligence
- Vol. 352
LAD2025, A constraint-based solver for the subgraph isomorphism problem
- Open Access
- 7 April 2025
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 82, 2167-2188
On the Phase Transition of the Euclidean Travelling Salesman Problem with Time Windows
Algorithms are often evaluated on randomly generated instances to study scale-up properties with respect to features such as the size, for example. Also, machine learning based approaches often train models on randomly generated instances as they need large sets of training instances. In this paper, we consider the Euclidean Travelling Salesman Problem with Time Windows (TSPTW), and we study the impact of parameters used to randomly generate TSPTW instances on hardness and feasibility. We first consider the decision version of the problem, where feasibility depends on start and end times of time windows. We introduce two parameters, α and β, for controlling the tightness of the time horizon and the time windows. We show that instance hardness is related to a phase transition phenomenon: as we increase α and β, we pass from an unfeasible region (where almost all generated instances have no solution) to a feasible region (where almost all generated instances have solutions), and the hardest instances are located within the transition zone. We formally relate this transition zone with respect to α and β, thus allowing us to control hardness and feasibility when randomly generating instances. Then, we study the optimization problem, the goal of which is to find the smallest tour that satisfies all time windows. We show that the empirical hardness is still related to the phase transition: hardness increases when moving from the infeasible region to the transition zone, as in the decision problem. However, unlike the decision problem, some hard instances are also located in the feasible region where instances are very loosely constrained.
- 7 April 2025
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 82, 2167-2188
Open AccessOn the Phase Transition of the Euclidean Travelling Salesman Problem with Time Windows
Algorithms are often evaluated on randomly generated instances to study scale-up properties with respect to features such as the size, for example. Also, machine learning based approaches often train models on randomly generated instances as they need large sets of training instances. In this paper, we consider the Euclidean Travelling Salesman Problem with Time Windows (TSPTW), and we study the impact of parameters used to randomly generate TSPTW instances on hardness and feasibility. We first consider the decision version of the problem, where feasibility depends on start and end times of time windows. We introduce two parameters, α and β, for controlling the tightness of the time horizon and the time windows. We show that instance hardness is related to a phase transition phenomenon: as we increase α and β, we pass from an unfeasible region (where almost all generated instances have no solution) to a feasible region (where almost all generated instances have solutions), and the hardest instances are located within the transition zone. We formally relate this transition zone with respect to α and β, thus allowing us to control hardness and feasibility when randomly generating instances. Then, we study the optimization problem, the goal of which is to find the smallest tour that satisfies all time windows. We show that the empirical hardness is still related to the phase transition: hardness increases when moving from the infeasible region to the transition zone, as in the decision problem. However, unlike the decision problem, some hard instances are also located in the feasible region where instances are very loosely constrained.
- 6 January 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Robotics and Automation Letters
- Vol. 10 (2) , 1888-1895
Spanning-Tree Based Coverage for a Tethered Robot
Tethered robots find widespread application in underwater and disaster recovery missions. This study focuses on the coverage path planning (CPP) problem for a tethered robot, considering cable constraints and the presence of forbidden areas in the environment. We propose adapting the spanning tree- based coverage algorithm to address CPP. Theoretical complexity analysis reveals NP-completeness in cases involving forbidden areas. We show how to solve CPP by searching for a tree in a configuration graph, and how to reduce the size of this graph to compute approximate solutions faster. We introduce Integer Linear Programming (ILP) models corresponding to these approximations and experimentally compare them on various instances.
- 6 January 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Robotics and Automation Letters
- Vol. 10 (2) , 1888-1895
Spanning-Tree Based Coverage for a Tethered Robot
Tethered robots find widespread application in underwater and disaster recovery missions. This study focuses on the coverage path planning (CPP) problem for a tethered robot, considering cable constraints and the presence of forbidden areas in the environment. We propose adapting the spanning tree- based coverage algorithm to address CPP. Theoretical complexity analysis reveals NP-completeness in cases involving forbidden areas. We show how to solve CPP by searching for a tree in a configuration graph, and how to reduce the size of this graph to compute approximate solutions faster. We introduce Integer Linear Programming (ILP) models corresponding to these approximations and experimentally compare them on various instances.
- 29 March 2024
- Published by Springer Nature
- p. 247-268
A CP-Based Automatic Tool for Instantiating Truncated Differential Characteristics
- 29 March 2024
- Published by Springer Nature
- p. 247-268
A CP-Based Automatic Tool for Instantiating Truncated Differential Characteristics
- 2 September 2020
- Published by Springer Nature
- p. 566-584
abstractXOR: A global constraint dedicated to differential cryptanalysis
- 2 September 2020
- Published by Springer Nature
- p. 566-584
abstractXOR: A global constraint dedicated to differential cryptanalysis
- 16 May 2019
- Published by Springer Nature
- p. 1-13
Experimental Evaluation of Subgraph Isomorphism Solvers
- 16 May 2019
- Published by Springer Nature
- p. 1-13
Experimental Evaluation of Subgraph Isomorphism Solvers
- Open Access
The Static and Stochastic VRPTW with both random Customers and Reveal Times: algorithms and recourse strategies
Unlike its deterministic counterpart, static and stochastic vehicle routing problems (SS-VRP) aim at modeling and solving real-life operational problems by considering uncertainty on data. We consider the SS-VRPTW-CR introduced in Saint-Guillain et al. (2017). Like the SS-VRP introduced by Bertsimas (1992), we search for optimal first stage routes for a fleet of vehicles to handle a set of stochastic customer demands, i.e., demands are uncertain and we only know their probabilities. In addition to capacity constraints, customer demands are also constrained by time windows. Unlike all SS-VRP variants, the SS-VRPTW-CR does not make any assumption on the time at which a stochastic demand is revealed, i.e., the reveal time is stochastic as well. To handle this new problem, we introduce waiting locations: Each vehicle is assigned a sequence of waiting locations from which it may serve some associated demands, and the objective is to minimize the expected number of demands that cannot be satisfied in time. In this paper, we propose two new recourse strategies for the SS-VRPTW-CR, together with their closed-form expressions for efficiently computing their expectations: The first one allows us to take vehicle capacities into account; The second one allows us to optimize routes by avoiding some useless trips. We propose two algorithms for searching for routes with optimal expected costs: The first one is an extended branch-and-cut algorithm, based on a stochastic integer formulation, and the second one is a local search based heuristic method. We also introduce a new public benchmark for the SS-VRPTW-CR, based on real-world data coming from the city of Lyon. We evaluate our two algorithms on this benchmark and empirically demonstrate the expected superiority of the SS-VRPTW-CR anticipative actions over a basic "wait-and-serve" policy.
Open AccessThe Static and Stochastic VRPTW with both random Customers and Reveal Times: algorithms and recourse strategies
Unlike its deterministic counterpart, static and stochastic vehicle routing problems (SS-VRP) aim at modeling and solving real-life operational problems by considering uncertainty on data. We consider the SS-VRPTW-CR introduced in Saint-Guillain et al. (2017). Like the SS-VRP introduced by Bertsimas (1992), we search for optimal first stage routes for a fleet of vehicles to handle a set of stochastic customer demands, i.e., demands are uncertain and we only know their probabilities. In addition to capacity constraints, customer demands are also constrained by time windows. Unlike all SS-VRP variants, the SS-VRPTW-CR does not make any assumption on the time at which a stochastic demand is revealed, i.e., the reveal time is stochastic as well. To handle this new problem, we introduce waiting locations: Each vehicle is assigned a sequence of waiting locations from which it may serve some associated demands, and the objective is to minimize the expected number of demands that cannot be satisfied in time. In this paper, we propose two new recourse strategies for the SS-VRPTW-CR, together with their closed-form expressions for efficiently computing their expectations: The first one allows us to take vehicle capacities into account; The second one allows us to optimize routes by avoiding some useless trips. We propose two algorithms for searching for routes with optimal expected costs: The first one is an extended branch-and-cut algorithm, based on a stochastic integer formulation, and the second one is a local search based heuristic method. We also introduce a new public benchmark for the SS-VRPTW-CR, based on real-world data coming from the city of Lyon. We evaluate our two algorithms on this benchmark and empirically demonstrate the expected superiority of the SS-VRPTW-CR anticipative actions over a basic "wait-and-serve" policy.
- 23 June 2015
- Published by Springer Nature in Swarm Intelligence
- Vol. 9 (2-3) , 71-73
ANTS 2014 special issue: Editorial
- 23 June 2015
- Published by Springer Nature in Swarm Intelligence
- Vol. 9 (2-3) , 71-73
ANTS 2014 special issue: Editorial
- 16 April 2015
- Published by Springer Nature
- p. 1-17
A Time-Dependent No-Overlap Constraint: Application to Urban Delivery Problems
- 16 April 2015
- Published by Springer Nature
- p. 1-17
A Time-Dependent No-Overlap Constraint: Application to Urban Delivery Problems