Publications HAL de Ladier

Article dans une revue

ref_biblio
Faycal Touzout, Anne-Laure Ladier, Khaled Hadj-Hamou. An assign-and-route matheuristic for the time-dependent Inventory Routing Problem. European Journal of Operational Research, 2022, 300 (3), pp.1081-1097. ⟨10.1016/j.ejor.2021.09.025⟩. ⟨hal-03354383⟩
resume
In this paper, we consider a variant of the Inventory Routing Problem (IRP), the Time-Dependent IRP (TD-IRP). The TD-IRP extends the routing component of the IRP by making the travelling time between two locations no longer constant but depending on the departure time. In order to investigate the relevance of considering time-dependent travelling time functions, a set of new benchmark instances based on real-data is assumed. Numerical experiments show that optimising with time-dependent travelling times is cost-efficient, but computationally challenging. Thus, we propose a matheuristic that decomposes the problem, based on the observation of the structure of optimal TD-IRP solutions. The proposed matheuristic defines the set of clients to visit and the quantity to deliver for each period first and solves the routing problem second. Numerical experiments prove it to be very efficient and yield solutions with small gaps to the best lower bounds found. Because it separates the routing problem, the proposed matheuristic opens the possibility to solve the TD-IRP very efficiently by taking advantage of the rich literature on time-dependent routing problems.
Accès au texte intégral et bibtex
https://hal.science/hal-03354383/file/S0377221721008006.pdf BibTex
ref_biblio
Faycal Touzout, Anne-Laure Ladier, Khaled Hadj-Hamou. Modelling and comparison of stability metrics for a re-optimisation approach of the Inventory Routing Problem under demand uncertainty. EURO Journal on Transportation and Logistics, 2021, 10, pp.100050. ⟨10.1016/j.ejtl.2021.100050⟩. ⟨hal-03354380⟩
resume
The inventory routing problem (IRP) is an optimisation problem that integrates transportation and inventory management decisions. When subjected to unexpected events such as demand changes, the a posteriori approach consists in re-optimising including the data related to this event; the challenge is to ensure that the obtained solution does not deviate too much from the original one, lest that creates important organisational issues. Therefore, a stability metric is needed when re-optimising IRP models. This article proposes a panel of stability metrics adapted from the scheduling, routing and inventory management literature to fit the requirements of the IRP and proposes mathematical formulations for the most relevant ones. A framework of comparison is proposed to validate and compare these metrics over a benchmark of 3000 instances generated from the literature. A strong correlation between the metrics is observed. Moreover, the results show that ensuring the stability of the re-optimised solutions has little impact on the initial objective, the total cost.
Accès au texte intégral et bibtex
https://hal.science/hal-03354380/file/S2192437621000212.pdf BibTex

Communication dans un congrès

ref_biblio
Maximilian Zimmermann, Fayçal A. Touzout, Anne-Laure Ladier, Khaled Hadj-Hamou. Deterministic construction heuristics for the time-dependent travelling salesman problem. 23ème Congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2022), INSA Lyon, Feb 2022, Villeurbanne - Lyon, France. ⟨hal-03595274⟩
resume
The time-dependent travelling salesman problem (TD-TSP) extends the TSP by considering the travel time between two locations as time-dependent. As the TD-TSP is NP-hard, it is difficult to find an optimal solution for large-sized instances. In this case, construction heuristics provide fast and easy to implement solutions. Such solutions can be used in real-world situations where optimality is not necessary. Furthermore, they can be used for improvement heuristics as initial solutions. Although construction heuristics are commonly used for the TSP, only few of them are adapted to the TD-TSP. This thesis adapts and evaluates five of the most prominent construction algorithms of the TSP to the TD-TSP: Cheapest Insertion, Christofides, First Fit, Nearest Neighbour and Savings. In order to compare the performances of the considered heuristics, numerical experiments are performed on one artificial and two real-life based time-dependent benchmarks. The results of the comparison are validated on TSP instances from the literature. The outcomes show that the modified Savings algorithm outperforms all other approaches significantly.
Accès au texte intégral et bibtex
https://hal.science/hal-03595274/file/Abstract_Conference.pdf BibTex
ref_biblio
Fayçal Touzout, Anne-Laure Ladier, Khaled Hadj-Hamou. An assignment-and-routing decomposition matheuristic for the time-dependent Inventory Routing Problem. 23ème Congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2022), INSA Lyon, Feb 2022, Villeurbanne - Lyon, France. ⟨hal-03595238⟩
resume
The inventory routing problem (IRP) integrates two operational problems of the supply chain: inventory management and routing. The objective of the decision-maker is to decide, for each period of the time horizon, whether a client should be replenished, with which quantity and following which route, optimising both the inventory and transportation costs.When evolving in an urban logistics context, one problem that can be faced is the volatility of the travelling times between locations. This volatility is represented in this paper by considering the travelling times as time dependent. As time-dependent problems tend to be harder to solve than their basic counterpart \cite{Gendreau2015}, it is necessary to propose new efficient algorithms. In this paper, a matheuristic that decomposes the problem into first assigning the clients to visit at each period and then solving a time-dependent travelling salesman problem (TD-TSP) is proposed.
Accès au texte intégral et bibtex
https://hal.science/hal-03595238/file/Papier.pdf BibTex
ref_biblio
Faycal Touzout, Anne-Laure Ladier, Khaled Hadj-Hamou. Time-dependent travel-time constrained Inventory Routing Problem. International Conference of Computational Logistics, Sep 2020, Enschede (virtual conference), Netherlands. pp 151-166, ⟨10.1007/978-3-030-59747-4_10⟩. ⟨hal-02955305⟩
resume
The Inventory Routing Problem (IRP) is an integration of two operational problems: inventory management and routing. The Time-Dependent Travel-Time Constrained (TD-TC-IRP) is a new proposed variant of the IRP where the travelling time between two locations depend on the time of departure throughout the day and the length of a trip is time-constrained. The real-world discontinuous time-dependent data that we use will be modelled by a piece-wise linear continuous function. A mathematical formulation for the TD-TC-IRP is proposed, to emulate such transformation. Numerical experiments are conducted, to validate the mathematical formulation, on a new benchmark combining benchmarks from the IRP and time-dependent routing problems literature .
Accès au texte intégral et bibtex
https://hal.science/hal-02955305/file/Paper.pdf BibTex
ref_biblio
Faycal Touzout, Anne-Laure Ladier, Khaled Hadj-Hamou. Inventory Routing Problem : ré-optimisation sous incertitudes. 21ème Congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2020), Feb 2020, Montpellier, France. ⟨hal-02900785⟩
Accès au texte intégral et bibtex
https://hal.science/hal-02900785/file/ROADEF2020.pdf BibTex