Journal de Physique IV (Proceedings)

Humanitarian logistics operations face increasing difficulties due to rising demands for aid in disaster areas. This paper investigates the dynamic allocation of scarce relief supplies across multiple affected districts over time. It introduces a novel stochastic dynamic postdisaster inventory allocation problem (SDPDIAP) with trucks and unmanned aerial vehicles (UAVs) delivering relief goods under uncertain supply and demand. The relevance of this humanitarian logistics problem lies in the importance of considering the intertemporal social impact of deliveries. We achieve this by considering social costs (transportation and deprivation costs) when allocating scarce supplies. Furthermore, we consider the inherent uncertainties of disaster areas and the potential use of cargo UAVs to enhance operational efficiency. This study proposes two anticipatory solution methods based on approximate dynamic programming, specifically decomposed linear value function approximation (DL-VFA) and neural network value function approximation (NN-VFA) to effectively manage uncertainties in the dynamic allocation process. We compare DL-VFA and NN-VFA with various state-of-the-art methods (e.g., exact reoptimization and proximal policy optimization) and results show a 6%–8% improvement compared with the best benchmarks. NN-VFA provides the best performance and captures nonlinearities in the problem, whereas DL-VFA shows excellent scalability against a minor performance loss. From a practical standpoint, the experiments reveal that consideration of social costs results in improved allocation of scarce supplies both across affected districts and over time. Finally, results show that deploying UAVs can play a crucial role in the allocation of relief goods, especially in the first stages after a disaster. The use of UAVs reduces transportation and deprivation costs together by 16%–20% and reduces maximum deprivation times by 19%–40% while maintaining similar levels of demand coverage, showcasing efficient and effective operations. History: This paper has been accepted for the Transportation Science Special Issue on TSL Conference 2023.

Disruptions in the operational flow of rail traffic can lead to conflicts between train movements, making it impossible to adhere to the scheduled timetable. This is when dispatching comes into play: resolving existing conflicts and providing a revised timetable. In this process, train paths are adjusted in their spatial and temporal dimensions. This adjustment is known as the train dispatching problem (TDP), which involves selecting conflict-free train paths with minimal delay. Starting from a path-oriented formulation of the TDP, a binary linear decision model is introduced. For each possible train path, a binary decision variable indicates whether the path is utilized by a train. Each train path is constructed from a set of predefined path segments within a time–space network. Instead of modeling pairwise conflicts, stronger linear programming formulations are achieved by defining cliques over the complete train paths. The combinatorial nature of the path segments results in a large number of possible paths, necessitating the use of the column-generation method. Within the subproblem, the shadow prices of conflict cliques must be considered. When constructing a new train path, it must be determined whether it belongs to a clique. This issue is addressed using a mixed integer program. The methodology is tested on instances from a dispatching area in Germany. Numerical results show that the presented method achieves acceptable computation times and good solution quality, meeting the requirements for real-time dispatching.

Large-scale traffic flow data are collected by numerous sensors for managing and operating transport systems. However, various measurement errors exist in the sensor data and their distributions or structures are usually not known in the real world, which diminishes the reliability of the collected data and impairs the performance of smart mobility applications. Such irregular error is referred to as the erratic measurement error and has not been well investigated in existing studies. In this research, we propose to estimate the erratic measurement errors in networked traffic flow data. Different from existing studies that mainly focus on measurement errors with known distributions or structures, we allow the distributions and structures of measurement errors to be unknown except that measurement errors occur based on a Poisson process. By exploiting the flow balance law, we first introduce the concept of virtual balance sensors and develop a mixed integer nonlinear programming model to simultaneously estimate sensor error probabilities and recover traffic flow. Under suitable assumptions, the complex integrated problem can be equivalently viewed as an estimate-then-optimize problem: first, estimation using machine learning (ML) methods, and then optimization with mathematical programming. When the assumptions fail in more realistic scenarios, we further develop a smart estimate-then-optimize (SEO) framework that embeds the optimization model into ML training loops to solve the problem. Compared with the two-stage method, the SEO framework ensures that the optimization process can recognize and compensate for inaccurate estimations caused by ML methods, which can produce more reliable results. Finally, we conduct numerical experiments using both synthetic and real-world examples under various scenarios. Results demonstrate the effectiveness of our decomposition approach and the superiority of the SEO framework. History: This paper has been accepted for the Transportation Science Special Issue on Machine Learning Methods for Urban Mobility. Funding: The work described in this paper was supported by the National Natural Science Foundation of China [Grant Project No. 72288101, 72101012, 72301023] and a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China [Grant Project No. PolyU/15206322]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0493 .

Next-day delivery logistics services are redefining the industry by increasingly focusing on customer service. Each logistics service provider’s challenge is jointly optimizing time window assignment and vehicle routing for such next-day delivery services. To do so in a cost-efficient and customer-centric fashion, real-life uncertainty, such as stochastic travel times, needs to be incorporated into the optimization process. This paper focuses on the canonical optimization problem within this context: the time window assignment traveling salesperson problem with stochastic travel times (TWATSP-ST). It belongs to two-stage, stochastic, mixed-integer programming problems with continuous recourse. We introduce two-step Benders decomposition with scenario clustering (TBDS) as an exact solution methodology for solving such stochastic programs. The method utilizes a new two-step decomposition along the binary and continuous first stage decisions and introduces a new scenario-retention strategy that combines and generalizes state-of-the-art Benders approaches and scenario-clustering techniques. Extensive experiments show that TBDS is superior to state-of-the-art approaches in the literature. It solves TWATSP-ST instances with up to 25 customers to optimality. It provides better lower and upper bounds that lead to faster convergence than existing state-of-the-art methods. We use TBDS to analyze the structure of the optimal solutions. By increasing routing costs only slightly, customer service can be improved tremendously driven by smartly alternating between high- and low-variance travel arcs to reduce the impact of delay propagation throughout the executed vehicle route. Funding: A. H. Schrotenboer has received support from the Dutch Science Foundation [Grant VI.Veni.211E.043]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2024.0750 .

Metro systems in densely populated urban areas are often complicated, with some origin-destinations (OD) having multiple routes with similar travel times, leading to complex passenger routing behaviors. To improve modeling and calibration, this paper proposes a novel passenger route choice model with a metro simulator that accounts for passenger flows, queueing, congestion, and transfer delays. A novel, data-driven approach that utilizes a fully differentiable end-to-end simulation-based optimization (SBO) framework is proposed to calibrate the model, with the gradients calculated automatically and analytically using the iterative backpropagation (IB) algorithm. The SBO framework integrates data from multiple sources, including smart card data and train loadings, to calibrate the route choice parameters that best match the observed data. The full differentiability of the proposed framework enables it to calibrate for more than 20,000 passenger route choice ratios, covering every OD pair. To further improve the efficiency of the framework, a matrix-based optimization (MBO) mechanism is proposed, which provides better initial values for the SBO and ensures high efficiency with large datasets. A hybrid optimization algorithm combining MBO and SBO effectively calibrates the model, demonstrating high accuracy with synthetic data from actual passenger OD demands, where hypothesis tests are conducted for accuracies and significances. The accuracies and robustness are validated by experiments with synthetic passenger flow data, offering potential for optimizing passenger flow management in densely populated urban metro systems. Then, the SBO framework is extended for user equilibrium formulations with a crowding-aware route choice model and iterative metro simulations, calibrated by the hybrid optimization algorithm with additional matrix operations. Case studies with actual observed passenger flows are conducted to illustrate the proposed framework with multiple setups, exhibiting the heterogeneity of passenger route choice preferences and providing insights for operation management in the Hong Kong Mass Transit Railway system. History: This paper has been accepted for the Transportation Science Special Issue on Machine Learning Methods for Urban Mobility. Funding: This work was supported by the General Research Fund of the Research Grants Council of Hong Kong [Grant 16219224], the Key Research and Development Program of Hubei Province [Grant 2023BAB076], and the National Natural Science Foundation of China [Grant 72001162]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2024.0557 .

We are pleased to announce the recipients of the Transportation Science Meritorious Service Awards. These awards recognize associate editors, special issue guest editors, and reviewers who have offered exceptional service in the review process. We truly appreciate all the efforts of the many volunteers who provide invaluable service to the journal. The 2024 recipients have distinguished themselves by the number of papers handled, their efficiency in handling papers, and the quality of their reviews.

Robotic sorting systems (RSSs) use mobile robots to sort items by destination. An RSS pairs high accuracy and flexible capacity sorting with the advantages of a flexible layout. This is why several express parcel and e-commerce retail companies, who face heavy demand fluctuations, have implemented these systems. To cope with fluctuating demand, temporal robot congestion, and high sorting speed requirements, workload balancing strategies such as dynamic robot routing and destination reassignment may be of benefit. We investigate the effect of a dynamic robot routing policy using a Markov decision process (MDP) model and dynamic destination assignment using a mixed integer programming (MIP) model. To obtain the MDP model parameters, we first model the system as a semiopen queuing network (SOQN) that accounts for robot movement dynamics and network congestion. Then, we construct the MIP model to find a destination reassignment scheme that minimizes the workload imbalance. With inputs from the SOQN and MIP models, the Markov decision process minimizes parcel waiting and postponement costs and helps to find a good heuristic robot routing policy to reduce congestion. We show that the heuristic dynamic routing policy is near optimal in small-scale systems and outperforms benchmark policies in large-scale realistic scenarios. Dynamic destination reassignment also has positive effects on the throughput capacity in highly loaded systems. Together, in our case company, they improve the throughput capacity by 35%. Simultaneously, the effect of dynamic routing exceeds that of dynamic destination reassignment, suggesting that managers should focus more on dynamic robot routing than dynamic destination reassignment to mitigate temporal congestion. Funding: This work was supported by The Fundamental Research Funds for the Central Universities [Grant WK2040000094] and the National Natural Science Foundation of China [Grants 71921001 and 72091215/72091210]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2023.0458 .

Transit agencies have the opportunity to outsource certain services to established mobility-on-demand (MOD) providers. Such alliances can improve service quality, coverage, and ridership; reduce public sector costs and vehicular emissions; and integrate the passenger experience. To amplify the effectiveness of such alliances, we develop a fare-setting model that jointly optimizes fares and discounts across a multimodal network. We capture commuters’ travel decisions with a discrete choice model, resulting in a large-scale, mixed-integer, nonconvex optimization problem. To solve this challenging problem, we develop a two-stage decomposition with the pricing decisions in the first stage and a mixed-integer linear optimization of fare discounts and passengers’ travel decisions in the second stage. To solve the decomposition, we develop a new solution approach that combines customized coordinate descent, parsimonious second-stage evaluations, and interpolations using special ordered sets. This approach, enhanced by acceleration techniques based on slanted traversal, randomization, and warm-start, significantly outperforms algorithmic benchmarks. Different alliance priorities result in qualitatively different fare designs: flat fares decrease the total vehicle-miles traveled, whereas geographically informed discounts improve passenger happiness. The model responds appropriately to equity-oriented and passenger-centric priorities, improving system utilization and lowering prices for low-income and long-distance commuters. Our profit allocation mechanism improves the outcomes for both types of operators, thus incentivizing profit-oriented MOD operators to adopt transit priorities. Funding: This material is based on work supported by the National Science Foundation [Grants 1122374 and 1750587]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2023.0009 .

The liner shipping industry is undergoing an extensive decarbonization process to reduce its 275 million tons of CO2 emissions as of 2018. In this process, the long-term solution is the introduction of new alternative maritime fuels. The introduction of alternative fuels presents a great set of unknowns. Among these are the strategic concerns regarding sourcing of alternative fuels and, operationally, how the new fuels might affect the network of shipping routes. We propose a problem formulation that integrates fuel supply/demand into the liner shipping network design problem. Here, we present a model to determine the production sites and distribution of new alternative fuels—we consider methanol and ammonia. For the network design problem, we apply an adaptive large neighborhood search combined with a delayed column generation process. In addition, we wish to test the effect of designing a robust network under uncertain demand conditions because of the problem’s strategic nature and importance. Therefore, our proposed solution method will have a deterministic and stochastic setup when we apply it to the second-largest multihub instance, WorldSmall, known from LINER-LIB. In the deterministic setting, our proposed solution method finds a new best solution to three instances from LINER-LIB. For the main considered WorldSmall instance, we even noticed a new best solution in all our tested fuel settings. In addition, we note a profit drop of 7.2% between a bunker-powered and pure alternative fuel–powered network. The selected alternative fuel production sites favor a proximity to European ports and have a heavy reliance on wind turbines. The stochastic results clearly showed that the found networks were much more resilient to the demand changes. Neglecting the perspective of uncertain demand leads to highly fluctuating profits. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0143 .

We discuss the numerical solution of the departure time choice problem. The non–quasi-monotone of the travel cost vector function is first proved to address the study motivation. A two-stage iteration method is then proposed to effectively solve the problem in a single origin-destination (OD) pair network with parallel links, in which departure time and route choices of commuters are involved. We analytically reveal why the iteration method can solve the problem and theoretically prove the convergence, that is, the iteration process finally achieves at a user equilibrium (UE) state. The iteration method is then extended to a single link network with heterogeneous users in the values of travel time and schedule delay and the preferred arrival time. Furthermore, numerical analyses are conducted for the two networks to demonstrate the effectiveness of the iteration method for solving the departure time choice problem. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72288101, 72171007, and 72021001]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2024.0599 .

Restaurant meal delivery has been rapidly growing in the last few years. The main operational challenges are the temporally and spatially dispersed stochastic demand that arrives from customers all over town as well as the customers’ expectation of timely and fresh delivery. To overcome these challenges, a new business concept emerged: ghost kitchens. This concept proposes synchronized food preparation of several restaurants in a central facility. Ghost kitchens can bring several advantages, such as fresher food because of the synchronization of food preparation and delivery and less delay because of the consolidated delivery of orders. Exploiting these advantages requires effective operational strategies for the dynamic scheduling of food preparation and delivery. The goal of this paper is providing these strategies and investigating the value of ghost kitchens. We model the problem as a sequential decision process. For the complex decision space of scheduling order preparations, consolidating orders to trips, and scheduling trip departures, we propose a large neighborhood search (LNS) procedure based on partial decisions and driven by analytical properties. Within the LNS, decisions are evaluated via a value function approximation, enabling anticipatory and real-time decision making. In a comprehensive computational study, we demonstrate the effectiveness of our method compared with benchmark policies and highlight the advantages of ghost kitchens compared with conventional meal delivery. Funding: G. Neria’s research is partially supported by the Israeli Smart Transportation Research Center, the Council for Higher Education in Israel, and the Shlomo Shmeltzer Institute for Smart Transportation at Tel Aviv University. F. D. Hildebrandt’s research is funded by the Deutsche Forschungsgemeinschaft (DFG) German Research Foundation [Grant 413322447]. M. Tzur’s research is partially supported by the Israeli Smart Transportation Research Center. M. W. Ulmer’s work is funded by the DFG Emmy Noether Programme [Grant 444657906]. We gratefully acknowledge their support. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2024.0510 .

In the era of connected and automated mobility, commuters possess strong computation power, enabling them to strategically make sequential travel choices over a planning horizon. This paper investigates the multiday traffic patterns that arise from such decision-making behavior. In doing so, we frame the commute problem as a mean-field Markov game and introduce a novel concept of multiday user equilibrium to capture the steady state of commuters’ interactions. The proposed model is general and can be tailored to various travel choices, such as route or departure time. We explore a range of properties of the multiday user equilibrium under mild conditions. The study reveals the fingerprint of user inertia on network flow patterns, causing between-day variations even at a steady state. Furthermore, our analysis establishes critical connections between the multiday user equilibrium and conventional Wardrop equilibrium. Funding: This work was supported by the National Science Foundation [Grants CMMI-1854684, CMMI-1904575, CMMI-2233057, and CMMI-2240981]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0488 .

Integrated demand management and vehicle routing problems are characterized by a stream of customers arriving dynamically over a booking horizon and requesting logistical services, fulfilled by a given fleet of vehicles during a service horizon. Prominent examples are attended home delivery and same-day delivery problems, where customers commonly have heterogeneous preferences regarding service fulfillment and requests differ in profitability. Thus, demand management methods are applied to steer the booking process to maximize total profit considering the cost of the routing decisions for the resulting orders. To measure the requests’ profitability for any demand management method, it is common to estimate their opportunity cost. In the context of integrated demand management and vehicle routing problems, this estimation differs substantially from the estimation in the well-examined demand management problems of traditional revenue management applications as, for example, found in the airline or car rental industry. This is because of the unique interrelation of demand control decisions and vehicle routing decisions as it inhibits a clear quantification and attribution of cost, and of displaced revenue, to certain customer requests. In this paper, we extend the theoretical foundation of opportunity cost in integrated demand management and vehicle routing problems. By defining and analyzing a generic Markov decision process model, we formally derive a definition of opportunity cost and prove opportunity cost properties on a general level. Hence, our findings are valid for a wide range of specific problems. Further, based on these theoretical findings, we propose approximation approaches that have not yet been applied in the existing literature, and evaluate their potential in a computational study. Thereby, we provide evidence that the theoretical results can be practically exploited in the development of solution algorithms. Funding: This work was supported by the University of the Bundeswehr Munich. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2024.0644 .

In railway systems, a deadlock occurs when trains accidentally occupy positions that prevent each other from moving forward. Although deadlocks are rare events, they do occur from time to time, requiring costly recourse actions and generating significant knock-on delays. In this paper, we present a noncompact 0,1 linear programming formulation and a methodology for discovering (possibly future) deadlocks and the subsequent implementation of optimal recovery measures. The approach is implemented in a tool to dispatch trains in real time developed in cooperation with Union Pacific (UP) and currently in operations on the entire UP network. Funding: This work was partially funded by Europe’s Rail, Flagship Project MOTIONAL [Action Horizon JU Innovation, Project 101101973]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2024.0521 .

We study a system in which a common delivery fleet provides service to both same-day delivery (SDD) and next-day delivery (NDD) orders placed by e-retail customers who are sensitive to delivery prices. We develop a model of the system and optimize with respect to two separate objectives. First, empirical research suggests that fulfilling e-retail orders ahead of promised delivery days increases a firm’s long-run market share. Motivated by this phenomenon, we optimize for customer satisfaction by maximizing the quantity of NDD orders fulfilled one day early given fixed prices. Next, we optimize for total profit; we optimize for a single SDD price, and we then set SDD prices in a two-level scheme with discounts for early-ordering customers. Our analysis relies on continuous approximation techniques to capture the interplay between NDD and SDD orders and particularly the effect one day’s operations have on the next, a novel modeling component not present in SDD-only models; a key technical result is establishing the model’s convergence to a steady state using dynamical systems theory. We derive structural insights and efficient algorithms for both objectives. In particular, we show that, under certain conditions, the total profit is a piecewise-convex function with polynomially many breakpoints that can be efficiently enumerated. In a case study set in metropolitan Denver, Colorado, approximately 10% of NDD orders can be fulfilled one day early at optimality, and profit is increased by 1% to 3% in a two-level pricing scheme versus a one-level scheme. We conduct operational simulations for validation of solutions and analysis of initial conditions. History: This paper has been accepted for the Transportation Science Special Issue on TSL Conference 2023. Funding: This work was supported by the National Science Foundation [Grant DGE-1650044]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0381 .