Fabien Lehuédé

We consider the optimization problem of determining schedules for shipments on known paths within a freight transportation network in order to minimize vehicle transportation costs. We refer to this problem as the freight transportation network scheduling problem and present two mixed integer programming formulations of that problem. The first is based on the classical idea of a time-expanded network. The second formulation is based on sets of shipment consolidations. We show both analytically and computationally that the consolidation-based formulation is the superior of the two when all consolidations can be enumerated. However, we also show computationally that its enumerative nature renders it ineffective for instances with large numbers of shipments. Thus, we also present a column generation-based algorithm for solving the consolidation-based formulation that relies on solving relaxations that are integer programs. We demonstrate the superior performance of this algorithm with a computational study wherein we compare it against applications of state-of-the-art approaches from the literature. We also perform a detailed computational analysis of the performance of the algorithm in different settings. History: Accepted by Russel Bent, Area Editor for Network Optimization: Algorithms & Applications. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0435 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0435 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

The code implementing the algorithms presented in this paper is not included in this repository as the project was done for an industrial sponsor who did not give approval to share that code.

Support vector clustering (SVC) has been proposed in the literature as a data-driven approach to build uncertainty sets in robust optimization. Unfortunately, the resulting SVC-based uncertainty sets induces a large number of additional variables and constraints in the robust counterpart of mathematical formulations. We propose a two-phase method to approximate the resulting uncertainty sets and overcome these tractability issues. This method is controlled by a parameter defining a trade-off between the quality of the approximation and the complexity of the robust models formulated. We evaluate the approximation method on three distinct, well-known optimization problems. Experimental results show that the approximated uncertainty set leads to solutions that are comparable to those obtained with the classic SVC-based uncertainty set with a significant reduction of the computation time. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms—Discrete. Funding: This work was supported by the German-French Academy for the Industry of the Future [Data-driven collaboration in Industrial Supply Chains project].

In this paper, we study a paratransit application in which children are transported every day from their homes to their special schools or medical-social establishments. To optimize this transporta...

We consider the optimization problem of determining schedules for shipments on known paths within a terminal network in order to minimize vehicle transportation costs. We refer to this problem as the Service Network Scheduling Problem and present two mixed integer programming formulations of that problem. The first is based on the classical idea of a time-expanded network. The second formulation is new and is based on sets of shipment consolidations. We show both analytically and computationally that the consolidation-based formulation can be the superior of the two, but that its enumerative nature renders it ineffective for instances with large numbers of shipments. Thus, we present a column generation-based algorithm for solving the consolidation-based formulation that relies on solving relaxations that are integer programs. We demonstrate the superior performance of this algorithm with a computational study.