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/ .

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].

Abstract This paper considers the integrated planning of goods transportation through a multi‐echelon supply chain consisting of a nationwide network and regional distribution system. The previously studied Service Network Design and Routing Problem considered similar planning decisions, albeit with multiple restrictions regarding the transportation of goods that can eliminate the opportunities for transportation savings. It also does not explicitly model the opportunity to increase vehicle utilization by having vehicles serve multiple purposes within the supply chain. We propose a mathematical model of the problem we consider that is inspired by the operations of an industrial partner. We present an adaptation of the Dynamic Discretization Discovery algorithm to solve this problem and illustrate its computational effectiveness on instances derived from the operations of a retail distribution network in France. Finally, we illustrate the potential savings enabled by solving the proposed model.

Based on a partnership between IMT Atlantique and the French company Lumiplan, this work is part of a process of strengthening the Heurès software currently offered by Lumiplan to public transport operators to support their bus and driver scheduling operations. This work addresses the frequency setting problem which aims at defining the frequencies of the bus lines of a network for different time periods of a day. This operation complements a study on line planning with more accurate estimations of the demand, necessary bus types and passengers behaviors. In this paper, the operator’s exploitation costs are minimized while respecting service-levels constraints, based on the predictions of the path choice made by the passengers. The problem is solved by an easily implementable process and a case study based on a real network is presented to show the efficiency of our method.

Abstract In the context of door‐to‐door transportation of people with disabilities, service quality considerations such as maximum ride time and service time consistency are critical requirements. To identify a good trade‐off between these considerations and economic objectives, we define a new variant of the multiperiod dial‐a‐ride problem called the time‐consistent dial‐a‐ride problem. A transportation planning is supposed to be time consistent if for each passenger, the same service time is used all along the planning horizon. However, considering the numerous variations in transportation demands over a week, designing consistent plans for all passengers can be too expensive. It is therefore necessary to find a compromise solution between costs and time‐consistency objectives. The time‐consistent dial‐a‐ride problem is solved using an epsilon‐constraint approach to illustrate the trade‐off between these two objectives. It computes an approximation of the Pareto front, using a matheuristic framework that combines a large neighbourhood search with the solution of set partitioning problems. This approach is benchmarked on time‐consistent vehicle routing problem literature instances. Experiments are also conducted in the context of door‐to‐door transportation for people with disabilities, using real data. These experiments support managerial insights regarding the inter‐relatedness of costs and quality of service.

International audience

This article studies the snow plow routing problem, which is a modified version of the min–max problem with k‐vehicles for arc routing on a mixed graph with hierarchy. Each arc or edge is given a priority and instead of minimizing the overall finishing time, we minimize the latest finishing time for each priority class. We consider turn restrictions, route balancing, and variable vehicle speeds in a real large‐scale network. To solve the problem, we present a graph transformation from a directed rural postman problem with turn penalties to an asymmetric traveling salesman problem. We then make the following modifications to the metaheuristics to better handle the constraints: development of new neighborhood operators, several applications of the same destruction operators before repair of the solution, and a dynamic arc‐grouping procedure when links are removed or inserted. We tested our methodology on three real networks with 1,626 to 2,146 street segments and 613 to 723 intersections. The results show that our approach can improve the solution, and the grouping procedure is helpful. The results also show that some operators perform better than others; the network topology seems to explain these variations. Finally, we validated our methodology by comparing to some routes planned in the past and to some routes obtained from a commercial solver. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(3), 195–215 2017

In this article, we address a problem of the transportation of people with disabilities where customers are served on an almost daily basis and expect some consistency in the service. We introduce an original model for the time-consistency of the service, based on so-called time-classes. We then define a new multiday vehicle routing problem (VRP) that we call the Time-Consistent VRP. We address the solution of this new problem with a large neighborhood search heuristic. Each iteration of the heuristic requires solving a complex VRP with multiple time windows and no waiting time which we tackle with a heuristic branch-and-price method. Computational tests are conducted on benchmark sets and modified real-life instances. Results demonstrate the efficiency of the method and highlight the impact of time-consistency on travel costs. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(3), 211-224 2014