A project and lift approach for a 2-commodity flow relocation model in a time expanded network

• Published in: Discrete Applied Mathematics 2024-10, Vol.356, p.350-368
• Main Authors: Figueroa González, José Luis, Baiou, Mourad, Quilliot, Alain, Toussaint, Hélène, Wagler, Annegret
• Format: Article
• Language: English
• Subjects: Branch-and-Cut; Computer Science; Mathematics; Network flows; Relocation Problem; Time expanded networks
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2024.06.033

We deal here with a general 2-commodity flow model over a time expanded network designed for the management of a shared mobility systems. The model involves an integral flow vector that represents carriers together with an integral flow vector that represents the items transported by those carriers. It simultaneously copes with temporal and resource issues, and is difficult to handle in the practice. So we propose here a Project and Lift approach to handle it. We start by projecting the time expanded network model on the original transit network to obtain a simpler two-commodity flow projected model. In order to make this projected model consistent with the original problem, we introduce some complex constraints, prove that these constraints can be separated in polynomial time and discuss the experimental behavior of the related Branch-and-Cut algorithm. Next, we introduce the Lift issue about the way one may turn an optimal solution of our projected model into a solution of the original problem. Finally, we thoroughly study a somewhat restrictive Strong Lift setting of this Lift issue, design and test an exact mixed integer programming Strong Lift model, and discuss some flexible alternative approaches.