Autonomous mobility-on-demand systems are a viable alternative to mitigate many transportation-related externalities in cities, such as rising vehicle volumes in urban areas and transportation-related pollution. However, the success of these systems heavily depends on efficient and effective fleet control strategies. In this context, we study online control algorithms for autonomous mobility-on-demand systems and develop a novel hybrid combinatorial optimization-enriched machine learning pipeline which learns online dispatching and rebalancing policies from optimal full-information solutions. We test our hybrid pipeline on large-scale real-world scenarios with different vehicle fleet sizes and various request densities. We show that our pipeline outperforms greedy and model-predictive control approaches with respect to various key performance indicators (KPIs), for example, by up to 17.1% and on average by 6.3% in terms of realized profit, and on average by 4.7% in terms of satisfied customers. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by Deutsche Forschungsgemeinschaft [Grant 449261765]. 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.2024.0637 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0637 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Autonomous Mobility-on-Demand (AMoD) systems, powered by advances in robotics, control, and Machine Learning (ML), offer a promising paradigm for future urban transportation. AMoD offers fast and personalized travel services by leveraging centralized control of autonomous vehicle fleets to optimize operations and enhance service performance. However, the rapid growth of this field has outpaced the development of standardized practices for evaluating and reporting results, leading to significant challenges in reproducibility. As AMoD control algorithms become increasingly complex and data-driven, a lack of transparency in modeling assumptions, experimental setups, and algorithmic implementation hinders scientific progress and undermines confidence in the results. This paper presents a systematic study of reproducibility in AMoD research. We identify key components across the research pipeline, spanning system modeling, control problems, simulation design, algorithm specification, and evaluation, and analyze common sources of irreproducibility. We survey prevalent practices in the literature, highlight gaps, and propose a structured framework to assess and improve reproducibility. While focused on AMoD, the principles and practices we advocate generalize to a broader class of cyber-physical systems that rely on networked autonomy and data-driven control. This work aims to lay the foundation for a more transparent and reproducible research culture in the design and deployment of intelligent mobility systems.

When optimizing transportation systems, anticipating traffic flows is a central element. Yet, computing such traffic equilibria remains computationally expensive. Against this background, we introduce a novel combinatorial optimization augmented neural network pipeline that allows for fast and accurate traffic flow predictions. We propose WardropNet, a neural network that combines classical layers with a subsequent equilibrium layer: the first ones inform the latter by predicting the parameterization of the equilibrium problem's latency functions. Using supervised learning we minimize the difference between the actual traffic flow and the predicted output. We show how to leverage a Bregman divergence fitting the geometry of the equilibria, which allows for end-to-end learning. WardropNet outperforms pure learning-based approaches in predicting traffic equilibria for realistic and stylized traffic scenarios. On realistic scenarios, WardropNet improves on average for time-invariant predictions by up to 72\% and for time-variant predictions by up to 23\% over pure learning-based approaches.

Reinforcement learning (RL) is increasingly applied to real-world problems involving complex and structured decisions, such as routing, scheduling, and assortment planning. These settings challenge standard RL algorithms, which struggle to scale, generalize, and exploit structure in the presence of combinatorial action spaces. We propose Structured Reinforcement Learning (SRL), a novel actor-critic paradigm that embeds combinatorial optimization-layers into the actor neural network. We enable end-to-end learning of the actor via Fenchel-Young losses and provide a geometric interpretation of SRL as a primal-dual algorithm in the dual of the moment polytope. Across six environments with exogenous and endogenous uncertainty, SRL matches or surpasses the performance of unstructured RL and imitation learning on static tasks and improves over these baselines by up to 92\% on dynamic problems, with improved stability and convergence speed.

Current electric vehicle market trends indicate an increasing adoption rate across several countries. To meet the expected growing charging demand, it is necessary to scale up the current charging infrastructure and to mitigate current reliability deficiencies, for example, due to broken connectors or misreported charging station availability status. However, even within a properly dimensioned charging infrastructure, a risk for local bottlenecks remains if several drivers cannot coordinate their charging station visit decisions. Here, navigation service platforms can optimally balance charging demand over available stations to reduce possible station visit conflicts and increase user satisfaction. Although such fleet-optimized charging station visit recommendations may alleviate local bottlenecks, they can also harm the system if self-interested navigation service platforms seek to maximize their own customers’ satisfaction. To study these dynamics, we model fleet-optimized charging station allocation as a resource allocation game in which navigation platforms constitute players and assign potentially free charging stations to drivers. We show that no pure Nash equilibrium guarantee exists for this game, which motivates us to study VCG mechanisms both in offline and online settings, to coordinate players’ strategies toward a better social outcome. Extensive numerical studies for the city of Berlin show that by coordinating players through VCG mechanisms, the social cost decreases on average by 42% in the online setting and by 52% in the offline setting. History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms & Applications. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0269 .

Large discrete action spaces (LDAS) remain a central challenge in reinforcement learning. Existing solution approaches can handle unstructured LDAS with up to a few million actions. However, many real-world applications in logistics, production, and transportation systems have combinatorial action spaces, whose size grows well beyond millions of actions, even on small instances. Fortunately, such action spaces exhibit structure, e.g., equally spaced discrete resource units. With this work, we focus on handling structured LDAS (SLDAS) with sizes that cannot be handled by current benchmarks: we propose Dynamic Neighborhood Construction (DNC), a novel exploitation paradigm for SLDAS. We present a scalable neighborhood exploration heuristic that utilizes this paradigm and efficiently explores the discrete neighborhood around the continuous proxy action in structured action spaces with up to $10^{73}$ actions. We demonstrate the performance of our method by benchmarking it against three state-of-the-art approaches designed for large discrete action spaces across three distinct environments. Our results show that DNC matches or outperforms state-of-the-art approaches while being computationally more efficient. Furthermore, our method scales to action spaces that so far remained computationally intractable for existing methodologies.

We introduce RoutingBlocks, a versatile open-source Python package designed to simplify the development of algorithms for vehicle routing problems with intermediate stops (VRPIS). The package offers a variety of modular algorithmic components and optimized data structures crafted specifically to address key challenges of VRPIS, such as a lack of exact constant-time move evaluations and difficult station visit decisions. By using a unified solution and instance representation that abstracts problem-specific behavior (for example, constraint checking, move evaluation, and cost computation) into well-defined interfaces, RoutingBlocks maintains a clear separation between algorithmic components and specific problem configurations, thus allowing the application of the same algorithm to a variety of problem settings. Leveraging an efficient C++ implementation for performance-critical core elements, RoutingBlocks combines the high performance of C++ with the user-friendliness and adaptability of Python, thereby streamlining the development of effective metaheuristic algorithms. As a result, researchers using RoutingBlocks can focus on their algorithms’ core features, allocating more resources to innovation and advancement in the VRPIS domain. History: Accepted by Ted Ralphs, Area Editor for Software Tools. This paper has been accepted for the INFORMS Journal on Computing Special Issue on Software Tools for Vehicle Routing.

Decision diagrams for classification have some notable advantages over decision trees, as their internal connections can be determined at training time and their width is not bound to grow exponentially with their depth. Accordingly, decision diagrams are usually less prone to data fragmentation in internal nodes. However, the inherent complexity of training these classifiers acted as a long-standing barrier to their widespread adoption. In this context, we study the training of optimal decision diagrams (ODDs) from a mathematical programming perspective. We introduce a novel mixed-integer linear programming model for training and demonstrate its applicability for many datasets of practical importance. Further, we show how this model can be easily extended for fairness, parsimony, and stability notions. We present numerical analyses showing that our model allows training ODDs in short computational times, and that ODDs achieve better accuracy than optimal decision trees, while allowing for improved stability without significant accuracy losses.

Over the past decade, GPS-enabled traffic applications such as Google Maps and Waze have become ubiquitous and have had a significant influence on billions of daily commuters’ travel patterns. A consequence of the online route suggestions of such applications, for example, via greedy routing, has often been an increase in traffic congestion since the induced travel patterns may be far from the system optimum. Spurred by the widespread impact of traffic applications on travel patterns, this work studies online traffic routing in the context of capacity-constrained parallel road networks and analyzes this problem from two perspectives. First, we perform a worst-case analysis to identify the limits of deterministic online routing. Although we find that deterministic online algorithms achieve finite, problem/instance-dependent competitive ratios in special cases, we show that for a general setting the competitive ratio is unbounded. This result motivates us to move beyond worst-case analysis. Here, we consider algorithms that exploit knowledge of past problem instances and show how to design data-driven algorithms whose performance can be quantified and formally generalized to unseen future instances. We then present numerical experiments based on an application case for the San Francisco Bay Area to evaluate the performance of the proposed data-driven algorithms compared with the greedy algorithm and two look-ahead heuristics with access to additional information on the values of time and arrival time parameters of users. Our results show that the developed data-driven algorithms outperform commonly used greedy online-routing algorithms. Furthermore, our work sheds light on the interplay between data availability and achievable solution quality. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete. Funding: This work was supported by National Science Foundation (NSF) Award 1830554 and by the German Research Foundation (DFG) under [Grant 449261765]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2023.1275 .

In this paper, we propose a general algorithmic framework for rotating workforce scheduling. We develop a graph representation that allows to model a schedule as a Eulerian cycle of stints, which we then use to derive a problem formulation that is compact toward the number of employees. We develop a general branch-and-cut framework that solves rotating workforce scheduling in its basic variant, as well as several additional problem variants that are relevant in practice. These variants comprise, among others, objectives for the maximization of free weekends and the minimization of employees. Our computational studies show that the developed framework constitutes a new state of the art for rotating workforce scheduling. For the first time, we solve all 6,000 instances of the status quo benchmark for rotating workforce scheduling to optimality with an average computational time of 0.07 seconds and a maximum computational time of 2.53 seconds. These results reduce average computational times by more than 99% compared with existing methods. Our algorithmic framework shows consistent computational performance, which is robust across all studied problem variants. Summary of Contribution: This paper proposes a novel exact algorithmic framework for the well-known rotating workforce scheduling problem (RWSP). Although the RWSP has been extensively studied in different problem variants and for different exact and heuristic solution approaches, the presented algorithmic framework constitutes a new state-of-the-art for the RWSP that solves all known benchmark sets to optimality and improves on the current state-of-the-art by orders of magnitude with respect to computational times, especially for large-scale instances. The paper is both of methodological value for researchers and of high interest for practitioners. For researchers, the presented framework is amenable for various problem variants and provides a common ground for further studies and research. For practitioners and software developers, low computational times of a few seconds allows the framework to be to embedded into personnel scheduling software.

The use of machine learning algorithms in finance, medicine, and criminal justice can deeply impact human lives. As a consequence, research into interpretable machine learning has rapidly grown in an attempt to better control and fix possible sources of mistakes and biases. Tree ensembles, in particular, offer a good prediction quality in various domains, but the concurrent use of multiple trees reduces the interpretability of the ensemble. Against this background, we study born-again tree ensembles, i.e., the process of constructing a single decision tree of minimum size that reproduces the exact same behavior as a given tree ensemble in its entire feature space. To find such a tree, we develop a dynamic-programming based algorithm that exploits sophisticated pruning and bounding rules to reduce the number of recursive calls. This algorithm generates optimal born-again trees for many datasets of practical interest, leading to classifiers which are typically simpler and more interpretable without any other form of compromise.

In this paper we study models and coordination policies for intermodal Autonomous Mobility-on-Demand (AMoD), wherein a fleet of self-driving vehicles provides on-demand mobility jointly with public transit. Specifically, we first present a network flow model for intermodal AMoD, where we capture the coupling between AMoD and public transit and the goal is to maximize social welfare. Second, leveraging such a model, we design a pricing and tolling scheme that allows the system to recover a social optimum under the assumption of a perfect market with selfish agents. Third, we present real-world case studies for the transportation networks of New York City and Berlin, which allow us to quantify the general benefits of intermodal AMoD, as well as the societal impact of different vehicles. In particular, we show that vehicle size and powertrain type heavily affect intermodal routing decisions and, thus, system efficiency. Our studies reveal that the cooperation between AMoD fleets and public transit can yield significant benefits compared to an AMoD system operating in isolation, whilst our proposed tolling policies appear to be in line with recent discussions for the case of New York City.