The Scheduled Service Network Design Problem (SSNDP) is an optimization problem that prescribes the transportation routes through a network of shipments that are small relative to vehicle capacity. The classical integer programming formulation of the SSNDP captures consolidation opportunities by modeling the routing of shipments on a directed time-expanded network consisting of nodes and arcs. In such a network, activities at a terminal at different points in time are modeled with different nodes. It has been observed that instances of such a formulation present multiple computational difficulties, including huge size due to an a priori enumeration of time points, symmetry, and weak linear programming relaxations.

Recently, a new formulation for the SSNDP has been proposed that differs from the classical time-expanded network formulation in two fundamental ways. The first is that it is not defined on a time-expanded network at all. By avoiding the use of a time-expanded network, both of the first two computational challenges are avoided. The second is that it is based on an a priori enumeration of consolidations, wherein a consolidation is defined as a set of shipments that dispatch on the same physical move at the same time. By modeling explicitly with consolidations, vehicle capacity needs can be encoded in the data of an instance, leading to a much stronger linear programming relaxation

In this presentation we present a Branch-and-Price based approach to solving instances of this formulation that involves generating consolidations dynamically through the solution of a pricing problem. As the pricing problem takes the form of a quadratic knapsack problem, we present a speed-up technique that leverages the observation that a subset of a consolidation is itself a consolidation. With an extensive computational study we compare the effectiveness of the solution approach with a state of the art solution method for the SSNDP.

We propose the electric vehicle routing problem (EVRP) as a general model for electrified routing operations, with applications in trucking for long-haul logistics, robotics, and machine scheduling. The EVRP admits a path-based set-partitioning formulation with infinitely many variables, due to the presence of both discrete routing decisions (as in VRP) and continuous charging decisions (new to EVRP). We develop a two-level label-setting algorithm for the pricing problem arising in column generation, which generates non-dominated subpaths and stitches them together. In so doing, we propose a new paradigm of domination for paths and subpaths, which ensures finite convergence and correctness of column generation even with infinitely many variables. We demonstrate how two-level label-setting can be applied to ng-route relaxations, via additional ng-set resources, and tighten these relaxations iteratively until one obtains elementary paths. We also demonstrate how our two-level label-setting can support cutting planes which strengthen the linear relaxation of EVRP, via additional cut resources. Numerical results show that our approach outperforms state-of-the-art algorithms and scales to realistic problem sizes.

In this presentation, we study an optimization problem that arises in the context of the automobile industry. When a new model of vehicle has just been conceived, it needs to undergo a series of tests before being released on the market. This phase is costly since specific vehicles called prototypes are built exclusively for test purposes. The validation tests carried out in the various facilities are numerous and are repeated on the different mechanical parts of the prototypes (thermal, acoustic, driving, sound insulation, safety or endurance tests, for example). The goal of the company is to minimize the number of tests realized after their due dates, and the number of prototypes to manufacture.

We address the problem by means of a path-flow formulation. In our path-flow model, the sequence of jobs assigned to a machine corresponds with a path in a network, where nodes are related to states representing a partial solution for a machine, and arcs correspond to decisions of assigning a job to a machine in this state. Our contribution is to propose an efficient algorithm to produce columns in the column generation process. In our approach, configurations are thus only considered implicitly, i.e., they are a byproduct of the set of jobs assigned to each machine. To satisfy the compatibility constraints, we have to embed additional information into the states to avoid assigning a set of jobs to a machine for which no possible configuration is possible. These constraints are embedded into a labelling algorithm, which is used to produce feasible assignments of jobs to a machine. From an algorithmic point of view, this calls for a new specific labelling process that we propose in this paper. In our method, new specific resource consumption and dominance checks have to be designed to account for this specificity.

We study arc-flow formulations obtained from transition graphs or transition hypergraphs of dynamic programs. These formulations are known for their generally strong linear relaxations and can be solved directly by a general purpose mixed integer linear programming (MILP) solver. An advantage of the MILP formulation is that one can include additional linear constraints in the form of resource constraints. In the absence of these, arc-flow formulations in graphs -- resp. hypergraphs -- form a totally unimodular -- resp. totally dual integral -- system, meaning the solution of the linear relaxation of the formulation is integer. A drawback of the MILP formulation is its size which can be pseudo-polynomial or exponential. We focus on cutting and packing problems with temporal constraints, i.e., temporal knapsack problem, temporal bin packing problem and their variants. We introduce preprocessing techniques and dominance rules to reduce the size of the transition graphs and hypergraphs: symmetries reduction, equivalent states aggregation using methods from the literature and detection of states that can be replaced by other states where some constraints are relaxed. Numerically, we confirm the strength of the linear relaxation of the arc-flow formulations, we observe that the sizes of the arc-flow formulations are significantly reduced by our techniques and show that these formulations are competitive and can outperform popular compact formulations from the literature.