A Graph Reduction Heuristic For Supply Chain Transportation Plan Optimization

Simon Belieres 1 Nicolas Jozefowiez 2 Frédéric Semet 3, 4
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
3 INOCS - Integrated Optimization with Complex Structure
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : We address to a problem of freight transportation in supply chains. To model flows over time in the system, we use time-expanded graphs. However, the time-expanded graphs' size increases exponentially with the number of actors and the time dimension, which makes the industrial solvers inefficient to overcome real instances. To face this difficulty, we conceived an heuristic based from Boland's and Hewitt's Dynamic Discretization Discovery. We manipulates a partially time-expanded graph, componed of a small subset of nodes and arcs, and enriches it incrementally. We produce a sparse graph with the essential elements and solve the associated problem, with much less constraints and variables.
Document type :
Conference papers
Complete list of metadatas

Cited literature [3 references]  Display  Hide  Download

https://hal.laas.fr/hal-01876531
Contributor : Simon Belieres <>
Submitted on : Wednesday, September 26, 2018 - 1:30:46 PM
Last modification on : Friday, June 14, 2019 - 6:31:20 PM
Long-term archiving on : Thursday, December 27, 2018 - 1:31:16 PM

File

Odysseus18.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01876531, version 1

Citation

Simon Belieres, Nicolas Jozefowiez, Frédéric Semet. A Graph Reduction Heuristic For Supply Chain Transportation Plan Optimization. ODYSSEUS 2018 - Seventh International Workshop on Freight Transportation and Logistics, Jun 2018, Cagliari, Italy. pp.4. ⟨hal-01876531⟩

Share

Metrics

Record views

124

Files downloads

65