Conference Agenda

Column generation is an efficient algorithm for solving a variety of large-scale optimization problems. The basic idea is not to consider all variables explicitly, but to add promising variables iteratively. The problem is decomposed into a master problem and one or more subproblems that detect variables with potential for improving the current solution. In routing or scheduling applications, the subproblem is often modeled as a shortest path problem with resource constraints that is solved using a dynamic programming labeling approach. We propose a new pricing heuristic that is based on machine learning predictions. By using information collected in previous executions, labels are evaluated with respect to their probability of leading to a feasible path with negative total cost. The objective is to reduce the search space explored to accelerate the solving process. We test the method on several real-world instances of the railway crew scheduling problem provided by a major European freight railway carrier. We achieve an average reduction in the total runtime of 21% at a marginal average increase in the objective function value of 0.05% when solving the linear programming relaxation.

This study presents an enhancement to the Column Generation (CG) procedure for Dantzig-Wolfe decompositions featuring multiple pricing problems. CG is an efficient technique for solving large linear programs, often embedded within the branch-and-price framework to address a variety of mixed-integer linear programs. In every iteration, CG obtains new columns by solving the pricing problems and adds them to the column pool only if their reduced cost is negative, assuming a minimization problem. Our approach introduces predictions utilizing Graph Neural Networks (GNNs) to estimate the value of the reduced costs at every CG iteration. Based on these predictions, we bypass the pricing problems that we expect to yield a column with a non-negative reduced cost. To maintain the optimality of the algorithm in the case of inaccurate predictions, we solve all pricing problems at the last iteration of the CG procedure. The choice of GNNs is motivated by the graph-based nature of many pricing problems, which are challenging to handle with other architectures. We evaluate our method by integrating it into an existing approach, based on branch-and-price, used to solve an optimization problem stemming from airport operations. Our GNN models are trained on generated data and tested against real-world data. The preliminary results show promising improvements in computational time and solution quality.

We study a contextual multi-stage stochastic control problem for vehicle dispatching in autonomous mobility on demand (AMoD) systems, where a central operator assigns vehicles to customer requests or rejects these with the aim of maximizing its total profit. Recent approaches use multi-agent deep reinforcement learning (MADRL) to realize scalable yet performant algorithms, but train agents based on local rewards. This distorts the reward signal with respect to the system-wide profit, leading to lower performance. We therefore propose a novel global-rewards-based MADRL algorithm for vehicle dispatching in AMoD systems, which resolves so far existing goal conflicts between the trained agents and the operator by assigning rewards to agents leveraging a counterfactual baseline. Using our novel counterfactual baseline, the algorithm combines stable learning with efficient credit assignment. Our algorithm shows statistically significant improvements across various settings on real-world data compared to state-of-the-art MADRL algorithms with local rewards. On average across test dates, our algorithm outperforms state-of-the-art local rewards-based MADRL algorithms by up to 2%, which translates into daily monetary savings of several ten thousand euros from an operator's perspective. On single test dates, it outperforms them by up to 6%. At the same time, it has better scalability properties with regards to the instance size than any other tested global rewards-based algorithm, being as scalable as purely local rewards-based MADRL algorithms. We further provide a structural analysis which shows that the utilization of global rewards can improve implicit vehicle rebalancing and demand forecasting abilities.