Dynamic unsplittable flows with path-change penalties: new formulations and solution schemes for large instances

DOI10.1016/J.COR.2023.106154arXiv2303.15558MaRDI QIDQ6164352FDOQ6164352

Authors: François Lamothe, Emmanuel Rachelson, Alain Haït, Cédric Baudoin, Jean-Baptiste Dupé 

Publication date: 4 July 2023

Published in: Computers \& Operations Research (Search for Journal in Brave)

Abstract: In this work, we consider the dynamic unsplittable flow problem. This variation of the unsplittable flow problem has received little attention so far. The unsplittable flow problem is an NP-hard extension of the multi-commodity flow problem where each commodity sends its flow on only one path. In its dynamic version, this problem features several time steps and a penalty is paid when a commodity changes its path from one time step to the next. We present several mixed-integer linear programming formulations for this problem and compare the strength of their linear relaxation. These formulations are embedded in several solvers which are extensively compared on small to large instances. One of these formulations must be solved through a column generation process whose pricing problem is more difficult than those used in classical flow problems. We present limitations of the pricing schemes proposed in earlier works and describe two new schemes with a better worst-case complexity. Overall, this work lays a strong algorithmic baseline for the resolution of the dynamic unsplittable flow problem, proposes original formulations, and discusses the compared advantages of each, thus hopefully contributing a step towards a better understanding of this problem for both OR researchers and practical applications.

Full work available at URL: https://arxiv.org/abs/2303.15558

zbMATH Keywords

heuristicscolumn generationmixed integer linear programmingroutingunsplittable flows

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Cites Work

• Stochastic uncapacitated hub location
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Handbook of Approximation Algorithms and Metaheuristics
• On service consistency in multi-period vehicle routing
• Bandwidth Packing: A Tabu Search Approach
• A hybrid column generation with GRASP and path relinking for the network load balancing problem
• On the minimum cost multiple-source unsplittable flow problem
• An ant colony optimization metaheuristic for single-path multicommodity network flow problems
• A multi-start variable neighborhood search for solving the single path multicommodity flow problem
• The vehicle routing problem with profits and consistency constraints
• Models for the piecewise linear unsplittable multicommodity flow problems
• Multi-period traffic routing in satellite networks

This page was built for publication: Dynamic unsplittable flows with path-change penalties: new formulations and solution schemes for large instances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6164352)