Search

A challenge in same-day delivery operations is that delivery requests are typically not known beforehand, but are instead revealed dynamically during the day. This uncertainty introduces a trade-off between dispatching vehicles to serve requests as soon as they are revealed to ensure timely delivery and delaying the dispatching decision to consolidate routing decisions with future, currently unknown requests. In this paper, we study the dynamic dispatch waves problem, a same-day delivery problem in which vehicles are dispatched at fixed decision moments. At each decision moment, the system operator must decide which of the known requests to dispatch and how to route these dispatched requests. The operator's goal is to minimize the total routing cost while ensuring that all requests are served on time. We propose iterative conditional dispatch (ICD), an iterative solution construction procedure based on a sample scenario approach. ICD iteratively solves sample scenarios to classify requests to be dispatched, postponed, or undecided. The set of undecided requests shrinks in each iteration until a final dispatching decision is made in the last iteration. We develop two variants of ICD: one variant based on thresholds, and another variant based on similarity. A significant strength of ICD is that it is conceptually simple and easy to implement. This simplicity does not harm performance: through rigorous numerical experiments, we show that both variants efficiently navigate the large state and action spaces of the dynamic dispatch waves problem and quickly converge to a high-quality solution. Finally, we demonstrate that the threshold-based ICD variant achieves excellent results on instances from the EURO Meets NeurIPS 2022 Vehicle Routing Competition, nearly matching the performance of the winning machine learning–based strategy. History: This paper has been accepted for the Transportation Science Special Issue on DIMACS Implementation Challenge: Vehicle Routing Problems. Funding: This work was supported by TKI Dinalog, Topsector Logistics, and the Dutch Ministry of Economic Affairs and Climate Policy. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0111. [ABSTRACT FROM AUTHOR]

This paper describes an exact branch-and-cut (B&C) algorithm for the split delivery vehicle routing problem. The underlying model is based on a previously proposed two-index vehicle flow formulation that models a relaxation of the problem. We dynamically separate two well-known classes of valid inequalities, namely capacity and connectivity cuts, and use an in-out algorithm to improve the convergence of the cutting phase. We generate no-good cuts from feasible integer solutions to the relaxation using a recently proposed single-commodity flow formulation in the literature. The exact methodology is complemented by a very effective adaptive large neighborhood search (ALNS) heuristic that provides high-quality upper bounds to initiate the B&C algorithm. Key ingredients in the design of the heuristic include the use of a tailored construction algorithm, which can exploit the situation in which the ratio of the number of customers to the minimum number of vehicles needed is low, and the use of a route-based formulation to improve the solutions found before, during, and after the ALNS procedure. An earlier version of this work was submitted to the DIMACS (Center for Discrete Mathematics and Theoretical Computer Science) implementation challenge, where it placed third. On sets of well-known benchmark instances for limited and unlimited fleet variants of the problem, we demonstrate that the heuristic provides very competitive solutions, with respective average gaps of 0.19% and 0.18% from best-known values. Furthermore, the exact B&C framework is also highly competitive with state-of-the-art methods, providing solutions with an average optimality gap of 1.82%. History: This paper has been accepted for the Transportation Science Special Section on DIMACS Implementation Challenge: Vehicle Routing Problems. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2022.0353. [ABSTRACT FROM AUTHOR]

Production and inventory routing problems consider a single-product supply chain operating under a vendor-managed inventory system. A plant creates a production plan and vehicle routes over a planning horizon to replenish its customers at minimum cost. In this paper, we present two- and three-index formulations, implement a branch-and-cut algorithm based on each formulation, and introduce a local search matheuristic-based algorithm to solve the problem. In order to combine all benefits of each algorithm, we design a parallel framework to integrate all three fronts, called the three-front parallel branch-and-cut algorithm (3FP-B&C). We assess the performance of our method on well-known benchmark instances of the inventory routing problem (IRP) and the production routing problem (PRP). The results show that our 3FP-B&C outperforms by far other approaches from the literature. For the 956 feasible small-size IRP instances, our method proves optimality for 746, being the first exact algorithm to solve all instances with up to two vehicles. 3FP-B&C finds 949 best known solutions (BKS) with 153 new BKS (NBKS). For the large-size set, our method provides two new optimal solutions (OPT), and finds 82% of BKS, being 70% of NBKS for instances with up to five vehicles. This result is more than twice the number of BKS considering all heuristic methods from the literature combined. Finally, our 3FP-B&C finds the best lower bounds (BLB) for 1,169/1,316 instances, outperforming all previous exact algorithms. On the PRP, our method obtained 278 OPT out of the 336 instances of benchmark set of small- and medium-size instances being 19 new ones in addition to 335 BKS (74 NBKS) and 313 BLB (52 new ones). On another set of PRP with medium- and large-size instances, our algorithm finds 1,105 BKS out of 1,440 instances with 584 NBKS. Besides that, our 3FP-B&C is the first exact algorithm to solve the instances with an unlimited fleet, providing the first lower bounds for this subset with an average optimality gap of 0.61%. We also address a very large-size instance set, the second exact algorithm to address this set, outperforming the previous approach by far. Finally, a comparative analysis of each front shows the gains of the integrated approach. History: This paper has been accepted for the Transportation Science Special Issue: DIMACS Implementation Challenge: Vehicle Routing. Funding: C. M. Schenekemberg was supported by the São Paulo Research Foundation (FAPESP) [Grant 2020/07145-8]. A. A. Chaves was supported by FAPESP [Grants 2018/15417-8 and 2016/01860-1] and Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 312747/2021-7 and 405702/2021-3]. L. C. Coelho was supported by the Canadian Natural Sciences and Engineering Research Council [Grant 2019-00094]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0261. [ABSTRACT FROM AUTHOR]

Curb space is one of the busiest areas in urban road networks. Especially in recent years, the rapid increase of ride-hailing trips and commercial deliveries has induced massive pick-ups/drop-offs (PUDOs), which occupy the limited curb space that was designed and built decades ago. These PUDOs could jam curbside utilization and disturb the mainline traffic flow, evidently leading to significant negative societal externalities. However, there is a lack of an analytical framework that rigorously quantifies and mitigates the congestion effect of PUDOs in the system view, particularly with little data support and involvement of confounding effects. To bridge this research gap, this paper develops a rigorous causal inference approach to estimate the congestion effect of PUDOs on general regional networks. A causal graph is set to represent the spatiotemporal relationship between PUDOs and traffic speed, and a double and separated machine learning (DSML) method is proposed to quantify how PUDOs affect traffic congestion. Additionally, a rerouting formulation is developed and solved to encourage passenger walking and traffic flow rerouting to achieve system optimization. Numerical experiments are conducted using real-world data in the Manhattan area. On average, 100 additional units of PUDOs in a region could reduce the traffic speed by 3.70 and 4.54 miles/hour (mph) on weekdays and weekends, respectively. Rerouting trips with PUDOs on curb space could respectively reduce the system-wide total travel time (TTT) by 2.44% and 2.12% in Midtown and Central Park on weekdays. A sensitivity analysis is also conducted to demonstrate the effectiveness and robustness of the proposed framework. Funding: The work described in this paper was supported by the National Natural Science Foundation of China [Grant 52102385], grants from the Research Grants Council of the Hong Kong Special Administrative Region, China [Grants PolyU/25209221 and PolyU/15206322], a grant from the Otto Poon Charitable Foundation Smart Cities Research Institute (SCRI) at the Hong Kong Polytechnic University [Grant P0043552], and a grant from Hong Kong Polytechnic University [Grant P0033933]. S. Qian was supported by a National Science Foundation Grant [Grant CMMI-1931827]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/trsc.2022.0195. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the Special Issue on Machine Learning Methods and Applications in Large-Scale Route Planning Problems, which draws its inspiration from the academic community's positive reception of the 2021 Amazon Last Mile Routing Research Challenge. We provide a structured overview of the papers featured in this special issue, and briefly discuss other noteworthy contributions to the research challenge. Further, we point the reader to a number of peer-reviewed publications outside of this special issue that directly or indirectly emerged from the research challenge. We conclude by highlighting a number of important priorities for future research into applications of machine learning to real-world route planning problems. [ABSTRACT FROM AUTHOR]

In the context of the Amazon Last-Mile Routing Research Challenge, this paper presents a machine-learning framework for optimizing last-mile delivery routes. Contrary to most routing problems where an objective function is clearly defined, in the real-world setting considered in the challenge, an objective is not explicitly specified and must be inferred from data. Leveraging techniques from machine learning and classical traveling salesman problem heuristics, we propose a "pool and select" algorithm to prescribe high-quality last-mile delivery sequences. In the pooling phase, we exploit structural knowledge acquired from data, such as common entry and exit regions observed in training routes. In the selection phase, we predict the scores of candidate sequences with a high-dimensional, pretrained, and regularized regression model. The score prediction model, which includes a large number of predictor variables such as sequence duration, compliance with time windows, earliness, lateness, and structural similarity to training data, displays good prediction accuracy and guides the selection of efficient delivery sequences. Overall, the framework is able to prescribe competitive delivery routes, as measured on out-of-sample routes across several data sets. Given that desired characteristics of high-quality sequences are learned and not assumed, the proposed framework is expected to generalize well to last-mile applications beyond those immediately foreseen in the challenge. Moreover, the method requires less than three seconds to prescribe a sequence given an instance and, thus, is suitable for very large-scale applications. History: This paper has been accepted for the Transportation Science Special Issue on Machine Learning Methods and Applications in Large-Scale Route Planning Problems. Funding: This research was funded by The Dutch Research Council (NWO) Data2Move project under [Grant 628.009.013] and the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie [Grant 754462]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0029. [ABSTRACT FROM AUTHOR]

Eco-labels are a way to benchmark transportation shipments with respect to their environmental impact. In contrast to an eco-labeling of consumer products, emissions in transportation depend on several operational factors like the mode of transportation (e.g., train or truck) or a vehicle's current and potential future capacity utilization when new orders are added for consolidation. Thus, satisfying eco-labels and doing this cost efficiently is a challenging task when dynamically routing orders in an intermodal network. In this paper, we model the problem as a multiobjective sequential decision process and propose a reinforcement learning method: value function approximation (VFA). VFAs frequently simulate trajectories of the problem and store observed values (violated eco-labels and costs) for states aggregated to a set of features. The observations are used for improved decision making in the next trajectory. For our problem, we face two additional challenges when applying a VFA, the multiple objectives and the "delayed" realization of eco-label satisfaction due to future consolidation. For the first, we propose different feature sets dependent on the objective function's focus: costs or eco-labels. For the latter, we propose enhancing the suboptimal decision making and observed pessimistic primal values within the VFA trajectories with optimistic dual decision making when all information of a trajectory is known ex post. This enhancement is a general methodological contribution to the literature of approximate dynamic programming and will likely improve learning for other problems as well. We show the advantages of both components in a comprehensive study for intermodal transport via trains and trucks in Europe. History: This paper has been accepted for the Transportation Science Special Section on 2021 TSL Workshop: Supply and Demand Interplay in Transport and Logistics. Funding: A. Heinold's work is funded by the Deutsche Forschungsgemeinschaft (DFG) [Project 268276815]. M. Ulmer's work is funded by the Emmy Noether Programme of the DFG [Project 444657906]. This support is gratefully acknowledged. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.1164. [ABSTRACT FROM AUTHOR]

The distribution of passenger vehicles is a complex task and a high cost factor for automotive original equipment manufacturers (OEMs). On the way from the production plant to the customer, vehicles travel long distances on different carriers, such as ships, trains, and trucks. To save costs, OEMs and logistics service providers aim to maximize their loading capacities. Modern auto carriers are extremely flexible. Individual platforms can be rotated, extended, or combined to accommodate vehicles of different shapes and weights and to nest them in a way that makes the best use of the available space. In practice, finding feasible combinations is done with the help of simple heuristics or based on personal experience. In research, most papers that deal with auto carrier loading focus on route or cost optimization. Only a rough approximation of the loading subproblem is considered. In this paper, we present two different methodologies to approximate realistic load factors considering the flexibility of modern auto carriers and their height, length, and weight constraints. Based on our industry partner's process, the vehicle distribution follows a first in, first out principle. For the first approach, we formulate the problem as a mixed integer, quadratically constrained assignment problem. The second approach considers the problem as a two-dimensional nesting problem with irregular shapes. We perform computational experiments using real-world data from a large German automaker to validate and compare both models with each other and with an approximate model adapted from the literature. The simulation results for the first approach show that, on average, for 9.37% of all auto carriers, it is possible to load an additional vehicle compared with the current industry solution. This translates to 1.36% less total costs. The performance of the nesting approach is slightly worse, but as it turns out, it is well-suited to check load combinations for feasibility. [ABSTRACT FROM AUTHOR]

This paper studies the problem of determining the strategic location of charging stations and their capacity levels under stochastic electric vehicle flows and charging times taking into account the route choice response of users. The problem is modeled using bilevel optimization, where the network planner or leader minimizes the total infrastructure cost of locating and sizing charging stations while ensuring a probabilistic service requirement on the waiting time to charge. Electric vehicle users or followers, on the other hand, minimize route length and may be cooperative or noncooperative. Their choice of route in turn determines the charging demand and waiting times at the charging stations and hence, the need to account for their decisions by the leader. The bilevel problem reduces to a single-level mixed-integer model using the optimality conditions of the follower's problem when the charging stations operate as M/M/c queues and the followers are cooperative. To solve the bilevel model, a decomposition-based solution methodology is developed that uses a new logic-based Benders algorithm for the location-only problem. Computational experiments are performed on benchmark and real-life highway networks, including a new eastern U.S. network. The impact of route choice response, service requirements, and deviation tolerance on the location and sizing decisions are analyzed. The analysis demonstrates that stringent service requirements increase the capacity levels at open charging stations rather than their number and that solutions allowing higher deviations are less costly. Moreover, the difference between solutions under cooperative and uncooperative route choices is more significant when the deviation tolerance is lower. History: This paper has been accepted for the Transportation Science Special Issue on 2021 TSL Workshop: Supply and Demand Interplay in Transport and Logistics. Funding: This research was supported by the Ontario Graduate Scholarship when Ö. B. Kınay was a PhD candidate at the University of Waterloo, and this support is acknowledged. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2021.0494. [ABSTRACT FROM AUTHOR]

The aim of this erratum is to correct an error in the computer implementation of the algorithm proposed by Dabia, Ropke, and van Woensel [Dabia S, Ropke S, van Woensel T (2013) Branch and price for the time-dependent vehicle routing problem with time windows. Transportation Sci. 47(3):295–454]. Section 6, "Computational Results," from the original paper is rewritten to reflect the corrected implementation, the new computational setup, and the updated results. [ABSTRACT FROM AUTHOR]

In this paper, we study the pickup and delivery problem with time windows and multiple compartments (PDPTWMC). The PDPTWMC generalizes the pickup and delivery problem with time windows to vehicles with multiple compartments. In particular, we consider three compartment-related attributes: (1) compartment capacity flexibility that allows the capacities of the compartments to be fixed or flexible, (2) item-to-compartment flexibility that specifies which items are compatible with which compartments, and (3) item-to-item compatibility that considers that incompatible items cannot be simultaneously in the same compartment. To solve the PDPTWMC, we propose an exact branch-price-and-cut algorithm in which the pricing problem is solved by means of a unified bidirectional labeling algorithm. The labeling algorithm can tackle all possible combinations of the studied compartment-related attributes of the PDPTWMC. Furthermore, we implement several acceleration techniques that allow to, among others, reduce the symmetry in the label extensions with empty compartments, the symmetry in the dominance between compartments with similar attributes, and the complexity of the algorithm with fixed compartment capacity. Finally, we introduce benchmark instances for the PDPTWMC and conduct an extensive computational campaign to test the limits of our algorithm and to derive relevant managerial insights in order to highlight the applicability of considering the studied compartment-related attributes. Funding: This work was supported by Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Grant 439.18.459] and the Natural Sciences and Engineering Research Council of Canada [Grant 2017-06106]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0252. [ABSTRACT FROM AUTHOR]

In this paper, we study a sequential decision-making problem faced by e-commerce carriers related to when to send out a vehicle from the central depot to serve customer requests and in which order to provide the service, under the assumption that the time at which parcels arrive at the depot is stochastic and dynamic. The objective is to maximize the expected number of parcels that can be delivered during service hours. We propose two reinforcement learning (RL) approaches for solving this problem. These approaches rely on a look-ahead strategy in which future release dates are sampled in a Monte Carlo fashion, and a batch approach is used to approximate future routes. Both RL approaches are based on value function approximation: One combines it with a consensus function (VFA-CF) and the other one with a two-stage stochastic integer linear programming model (VFA-2S). VFA-CF and VFA-2S do not need extensive training as they are based on very few hyperparameters and make good use of integer linear programming (ILP) and branch-and-cut–based exact methods to improve the quality of decisions. We also establish sufficient conditions for partial characterization of optimal policy and integrate them into VFA-CF/VFA-2S. In an empirical study, we conduct a competitive analysis using upper bounds with perfect information. We also show that VFA-CF and VFA-2S greatly outperform alternative approaches that (1) do not rely on future information (2) are based on point estimation of future information, (3) use heuristics rather than exact methods, or (4) use exact evaluations of future rewards. Funding: This work was supported by the CY Initiative of Excellence [ANR-16- IDEX-0008]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2022.0366. [ABSTRACT FROM AUTHOR]

This paper investigates the operation of a novel electric vehicles (EVs) charging service mode, that is, crowdsourced mobile charging service for EVs, whereby a crowdsourcing platform is established to arrange suppliers (crowdsourced chargers) to deliver charging service to customers' electric vehicles (parked EVs) at low-battery levels. From the platform operator's perspective, we aim to determine the optimal operation strategies for mobile charging crowdsourcing platforms to achieve specific objectives. A mathematical modeling framework is developed to capture the interactions among supply, demand, and service operations in the crowdsourced mobile charging market. To design an efficient solution method to solve the formulated model, we first analyze the model properties by rigorously proving that a crucial variable set for operating the mobile charging crowdsourcing system includes charging price, commission control, and period-specific aggregate demand control. Besides, we provide both an equivalent condition and a necessary condition for checking the feasibility of these crucial variables. On top of this, we construct a search tree according to the operation periods in a day to solve the optimal operation strategies, wherein a nondominated principle is adopted as an accelerating technique in the searching process. The solution obtained from the proposed solution algorithm is proved to be sufficiently close to the actual global optimal solutions of the formulated model up to the resolution of the discretization scheme adopted. Numerical examples provide evidence verifying the model's validity and the solution method's efficiency. Overall, the research outcome of this work can offer service operators structured and valuable guidelines for operating mobile charging crowdsourcing platforms. Funding: This work was supported by the Singapore Ministry of Education [Grant RG124/21]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2023.0126. [ABSTRACT FROM AUTHOR]

When tackling high-dimensional, continuous simulation-based optimization (SO) problems, it is important to balance exploration and exploitation. Most past SO research focuses on the enhancement of exploitation techniques. The exploration technique of an SO algorithm is often defined as a general-purpose sampling distribution, such as the uniform distribution, which is inefficient at searching high-dimensional spaces. This work is motivated by the formulation of exploration techniques that are suitable for large-scale transportation network problems and high-dimensional optimization problems. We formulate a sampling mechanism that combines inverse cumulative distribution function sampling with problem-specific structural information of the underlying transportation problem. The proposed sampling distribution assigns greater sampling probability to points with better expected performance as defined by an analytical network model. Validation experiments on a toy network illustrate that the proposed sampling distribution has important commonalities with the underlying and typically unknown true sampling distribution of the simulator. We study a high-dimensional traffic signal control case study of Midtown Manhattan in New York City. The results show that the use of the proposed sampling mechanism as part of an SO framework can help to efficiently identify solutions with good performance. Using the analytical information for exploration, regardless of whether it is used for exploitation, outperforms benchmarks that do not use it, including standard Bayesian optimization. Using the analytical information for exploration only yields solutions with similar performance than when the information is used for exploitation only, reducing the total compute times by 65%. This paper sheds light on the importance of developing suitable exploration techniques to enhance both the scalability and the compute efficiency of general-purpose SO algorithms. Funding: T. Tay thanks the Agency for Science, Technology and Research (A*STAR) Singapore for funding his work. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0110. [ABSTRACT FROM AUTHOR]

In last-mile delivery logistics, peer-to-peer logistic platforms play an important role in connecting senders, customers, and independent carriers to fulfill delivery requests. As the carriers are not under the platform's control, the platform has to anticipate their reactions while deciding how to allocate the delivery operations. Indeed, carriers' decisions largely affect the platform's revenue. In this paper, we model this problem using bilevel programming. At the upper level, the platform decides how to assign the orders to the carriers; at the lower level, each carrier solves a profitable tour problem to determine which offered requests to accept, based on her own profit maximization. Possibly, the platform can influence carriers' decisions by determining also the compensation paid for each accepted request. The two considered settings result in two different formulations: the bilevel profitable tour problem with fixed compensation margins and with margin decisions, respectively. For each of them, we propose single-level reformulations and alternative formulations where the lower-level routing variables are projected out. A branch-and-cut algorithm is proposed to solve the bilevel models, with a tailored warm-start heuristic used to speed up the solution process. Extensive computational tests are performed to compare the proposed formulations and analyze solution characteristics. Funding: The research of E. Fernandez was partially funded through the Spanish Ministerio de Ciencia y Tecnología and European Regional Development Funds (ERDF) [Grant MTM2019-105824GB-I00]. The research of C. Archetti, M. Cerulli, and I. Ljubić was partially funded by CY Initiative of Excellence, France [Grant "Investissements d'Avenir ANR-16-IDEX-0008"]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0129. [ABSTRACT FROM AUTHOR]

Simulation-based optimization is an effective solution to complex transportation problems relying on stochastic simulations. However, existing studies generally perform a fixed number of evaluations for each decision vector across the design space, overlooking simulation heteroscedasticity and its effects on solution efficiency and robustness. In this paper, we treat the number of evaluations as an adaptive variable depending upon the simulation heteroscedasticity and the potential optimality of each decision vector. A statistical method, which automatically determines the variable number of evaluations, is presented for a range of derivative-free optimization methods. By fusing Bayesian inference with the probability of correct selection, it permits adaptive allocation of budgeted computational resources to achieve improved solution efficiency and robustness. The method is integrated with the deterministic global optimizer DIviding RECTangles (DIRECT) to yield NoisyDIRECT as a continuous simulation-based robust optimization method (which is open sourced). The key properties of the method are proved and discussed. Numerical experiments on difficult test functions are first conducted to verify the improvement of NoisyDIRECT compared with DIRECT and Bayesian optimization. Given the same computational budget, NoisyDIRECT can better locate the global optimum than the other two alternatives. Applications to representative simulation-based transportation problems, including an M/M/1 queueing problem and a parking pricing problem, are then presented. The results demonstrate the ability of NoisyDIRECT to pinpoint the optimal solution via adaptive computational resources allocation, achieving the desired level of robustness. Funding: This work was supported by the Youth Program [Grant 52102375] and the Key Project [Grant 52131203] of the National Natural Science Foundation of China, the Youth Program [Grant BK20210247] of the Natural Science Foundation of Jiangsu Province, and the High-Level Personnel Project of Jiangsu Province [Grant JSSCBS20220099]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0485. [ABSTRACT FROM AUTHOR]

This paper develops a fast algorithm for computing the equilibrium assignment with the perturbed utility route choice (PURC) model. Without compromise, this allows the significant advantages of the PURC model to be used in large-scale applications. We formulate the PURC equilibrium assignment problem as a convex minimization problem and find a closed-form stochastic network loading expression that allows us to formulate the Lagrangian dual of the assignment problem as an unconstrained optimization problem. To solve this dual problem, we formulate a quasi-Newton accelerated gradient descent algorithm (qN-AGD*). Our numerical evidence shows that qN-AGD* clearly outperforms a conventional primal algorithm and a plain accelerated gradient descent algorithm. qN-AGD* is fast with a runtime that scales about linearly with the problem size, indicating that solving the perturbed utility assignment problem is feasible also with very large networks. Funding: This work has been financed by the European Union—NextGenerationEU. [ABSTRACT FROM AUTHOR]

Urban logistic applications that involve pickup and distribution of goods require making routing and allocation decisions with respect to a set of sites. In cases where the supply quantities and the time in which they become available are unknown in advance, these decisions must be determined in real time based on information that arrives gradually. Furthermore, in many applications that satisfy the described setting, fair allocation is desired in addition to system effectiveness. In this paper, we consider the problem of determining a vehicle route that visits two types of sites in any order: pickup points (PPs), from which the vehicle collects supplies, and demand points (DPs), to which these supplies are delivered. The supply quantities offered by each PP are uncertain, and the information on their value arrives gradually over time. We model this problem as a stochastic dynamic routing and resource allocation problem, with the aim of delivering as many goods as possible while obtaining equitable allocations to DPs. We present a Markov decision process formulation for the problem; however, it suffers from the curse of dimensionality. Therefore, we develop a heuristic framework that presents a novel combination of operations research and machine learning and is applicable for many dynamic stochastic combinatorial optimization problems. Specifically, we use a large neighborhood search (LNS) to explore possible decisions combined with a neural network (NN) model that approximates the future value given any state and action. We present a new reinforcement learning method to train the NN when the decision space is too large to enumerate. A numerical experiment with 38 to 180 site instances, based on data from the Berlin Foodbank and randomly generated data sets, confirms that the heuristic obtains solutions that are on average approximately 28.2%, 41.6%, and 57.9% better than three benchmark solutions. Funding: This research was partially supported by the Israel Science Foundation [Grant 463/15], by the Shlomo Shmeltzer Institute for Smart Transportation at Tel Aviv University, by the Israeli Smart Transportation Research Center (ISTRC), and by the Council for Higher Education in Israel (VATAT). Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0228. [ABSTRACT FROM AUTHOR]

This paper addresses the single crew scheduling and routing problem in the context of road network repair and restoration, which is critical in assisting complex postdisaster decisions in humanitarian logistics settings. We present three novel formulations for this problem, which are the first suitable for column generation and branch-and-price (BP) algorithms. Specifically, our first formulation is based on enumerating crew schedules and routes while explicitly defining the relief paths. The second formulation relies on enumerating the schedules, routes, and relief paths. Finally, the third formulation builds upon the second one by including additional constraints and variables related to relief path decisions. Considering each formulation, we propose BP algorithms that rely on several enhancements, including a new dynamic programming labeling algorithm to efficiently solve the subproblems. Extensive computational results based on 648 benchmark instances reveal that our BP algorithms significantly outperform existing exact approaches, solving 450 instances to optimality, and remarkably 118 instances for the first time. Our framework is also very effective in improving the lower bounds, upper bounds, and optimality gaps that have been reported in the literature. Funding: This work was supported by the Fundação de Amparo à Pesquisa do Estado de São Paulo [Grants 15/26453-7, 16/01860-1, 16/15966-6, and 19/23596-2], the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grant 313220/2020-4], and the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2023.0227. [ABSTRACT FROM AUTHOR]

Despite the rapid growth of the home care industry, research on the scheduling and routing of home care visits in the presence of uncertainty is still limited. This paper investigates a dynamic version of this problem in which the number of referrals and their required number of visits are uncertain. We develop a Markov decision process (MDP) model for the single-nurse problem to minimize the expected weighted sum of the rejection, diversion, overtime, and travel time costs. Because optimally solving the MDP is intractable, we employ an approximate linear program (ALP) to obtain a feasible policy. The typical ALP approach can only solve very small-scale instances of the problem. We derive an intuitively explainable closed-form solution for the optimal ALP parameters in a special case of the problem. Inspired by this form, we provide two heuristic reduction techniques for the ALP model in the general problem to solve large-scale instances in an acceptable time. Numerical results show that the ALP policy outperforms a myopic policy that reflects current practice, and is better than a scenario-based policy in most instances considered. Funding: This work was supported by the Natural Sciences and Engineering Research Council of Canada [Grants RGPIN-2018-05225 and RGPIN-2020-210524] and by the Telfer School of Management SMRG Postdoctoral Research Fellowship Support [Grant 2020]. Supplemental Material: The electronic companion is available at https://doi.org/10.1287/trsc.2023.0120. [ABSTRACT FROM AUTHOR]

With the rise of e-commerce and increasing customer requirements, logistics service providers face a new complexity in their daily planning, mainly due to efficiently handling same-day deliveries. Existing multistage stochastic optimization approaches that allow solving the underlying dynamic vehicle routing problem either are computationally too expensive for an application in online settings or—in the case of reinforcement learning—struggle to perform well on high-dimensional combinatorial problems. To mitigate these drawbacks, we propose a novel machine learning pipeline that incorporates a combinatorial optimization layer. We apply this general pipeline to a dynamic vehicle routing problem with dispatching waves, which was recently promoted in the EURO Meets NeurIPS Vehicle Routing Competition at NeurIPS 2022. Our methodology ranked first in this competition, outperforming all other approaches in solving the proposed dynamic vehicle routing problem. With this work, we provide a comprehensive numerical study that further highlights the efficacy and benefits of the proposed pipeline beyond the results achieved in the competition, for example, by showcasing the robustness of the encoded policy against unseen instances and scenarios. History: This paper has been accepted for the Transportation Science special issue on DIMACS Implementation Challenge: Vehicle Routing Problems. Funding: This work was supported by Deutsche Forschungsgemeinschaft [Grant 449261765]. [ABSTRACT FROM AUTHOR]

There has been a significant body of research on making urban transportation more efficient and sustainable. Planning of urban transportation services is challenging due to the crowded traffic infrastructure, increasing customer expectations, and rules set by municipalities. In recent years, a vast amount of urban transportation data has become available, e.g., travel times and customer demand data. This special issue intends to establish the landscape for the state-of-the-art in urban transportation involving optimization and analytics. [ABSTRACT FROM AUTHOR]

Network optimization or network design with an embedded traffic assignment (TA) to model user equilibrium principle, sometimes expressed as bilevel problems or mathematical programs with equilibrium constraints (MPEC), is at the heart of transportation planning and operations. For applications to large-scale multimodal networks with high dimensional decision variables, the problem is nontrivial, to say the least. General-purpose algorithms and problem-specific bilevel formulations have been proposed in the past to solve small problems for demonstration purposes. Research gap, however, exists in developing efficient solution methods for large-scale problems in both static and dynamic contexts. This paper proposes an efficient gradient estimation method called Iterative Backpropagation (IB) for network optimization problems with an embedded static TA model. IB exploits the iterative structure of the TA solution procedure and simultaneously calculates the gradients while the TA process converges. IB does not require any additional function evaluation and consequently scales very well with higher dimensions. We apply the proposed approach to origin-destination (OD) estimation, an MPEC problem, of the Hong Kong multimodal network with 49,806 decision variables, 8,797 nodes, 18,207 links, 2,684 transit routes, and 165,509 OD pairs. The calibrated model performs well in matching the link counts. Specifically, the IB-gradient based optimization technique reduces the link volume squared error by 98%, mean absolute percentage error (MAPE) from 95.29% to 21.23%, and the average GEH statistics from 24.18 to 6.09 compared with the noncalibrated case. The framework, even though applied to OD estimation in this paper, is applicable to a wide variety of optimization problems with an embedded TA model, opening up an efficient way to solve large-scale MPEC or bilevel problems. Funding: The study is supported by IVADO Postdoctoral Fellowship scheme 2021, HSBC 150th Anniversary Charity Programme HKBF17RG01, National Science Foundation of China (71890970, 71890974), General Research Fund (16212819, 16207920) of the HKSAR Government, and the Hong Kong PhD Fellowship. [ABSTRACT FROM AUTHOR]

Management of humanitarian logistics operations is one of the most critical planning problems to be addressed immediately after a disaster. The response phase covers the first 12 hours after the disaster and is prone to uncertainties because of debris and gridlock traffic influencing the dispatching operations of relief logistics teams in the areas affected. Moreover, the teams have limited time and resources, and they must provide equitable distribution of supplies to affected people. This paper proposes an adjustable robust optimization approach for the associated humanitarian logistics problem. The approach creates routes for relief logistics teams and decides the service times of the visited sites to distribute relief supplies by taking the uncertainty in travel times into account. The associated model allows relief logistics teams to adjust their service decisions according to the revealed information during the process. Hence, our solutions are robust for the worst-case realization of travel times, but still more flexible and less conservative than those of static robust optimization. We propose novel reformulation techniques to model these adjustable decisions. The resulting models are computationally challenging optimization problems to be solved by exact methods, and, hence, we propose heuristic algorithms. The state-of-the-art heuristic, which is based on clustering and a dedicated decision-rule algorithm, yields near-optimal results for medium-sized instances and is scalable even for large-sized instances. We have also shown the effectiveness of our approach in a case study using a data set obtained from an earthquake that hit the Van province of Turkey in 2011. History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.1204. [ABSTRACT FROM AUTHOR]

Unmanned aerial vehicles or drones are increasing in use both for commercial and casual purposes. Although drone traffic management is mostly absent, as drone use increases, aerial conflicts are likely to also increase. This paper studies the problem of planning drone delivery service through an urban air traffic network space. The urban air traffic network is assumed to mostly be the airspace above existing roads and is modeled as a transportation network with multiple flight levels. Drone flights are modeled as individual trip requests with origins, destinations, and time windows. We present a novel integer linear programming formulation for this drone delivery service planning problem. The main contribution of this paper is developing a branch-and-price algorithm to solve the formulation, as the number of decision variables grows quickly with the problem size. We investigate three variations of branch-and-price, including branching on trajectory assignment variables, branching rules related to served requests, and a primal heuristic to quickly find integer feasible solutions. Numerical results show the limits of the integer linear programming formulation and the benefits of the primal heuristic in finding a good feasible solution. History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.1175. [ABSTRACT FROM AUTHOR]

This paper studies the distributionally robust fair transit resource allocation model (DrFRAM) under the Wasserstein ambiguity set to optimize the public transit resource allocation during a pandemic. We show that the proposed DrFRAM is highly nonconvex and nonlinear, and it is NP-hard in general. Fortunately, we show that DrFRAM can be reformulated as a mixed integer linear programming (MILP) by leveraging the equivalent representation of distributionally robust optimization and monotonicity properties, binarizing integer variables, and linearizing nonconvex terms. To improve the proposed MILP formulation, we derive stronger ones and develop valid inequalities by exploiting the model structures. Additionally, we develop scenario decomposition methods using different MILP formulations to solve the scenario subproblems and introduce a simple yet effective no one left-based approximation algorithm with a provable approximation guarantee to solve the model to near optimality. Finally, we numerically demonstrate the effectiveness of the proposed approaches and apply them to real-world data provided by the Blacksburg Transit. History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics. Funding: This work was supported by the Division of Computing and Communication Foundations [Grant 2153607] and the Division of Civil, Mechanical and Manufacturing Innovation [Grant 2046426]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.1159. [ABSTRACT FROM AUTHOR]

In the e-commerce era, efficient order fulfillment processes in distribution centers have become a key success factor. One novel technology to streamline these processes is robot-assisted order picking. In these systems, human order pickers are supported by autonomous mobile robots (AMRs), which carry bins for collecting picking orders, autonomously move through the warehouse, and wait in front of a shelf containing a requested stock keeping unit (SKU). Once a picker has approached a waiting AMR and placed the requested SKU into the respective bin, AMR and picker may separate and move toward other picking positions. In this way, pickers continuously move between different waiting AMRs without having to return to the depot. This paper treats the coordination of multiple AMRs and multiple pickers to minimize the makespan. We present a heuristic method for the deterministic case that can handle the requirements of large e-commerce fulfillment centers and successfully solves instances with more than one thousand picking positions. Based on the obtained solutions, the performance of our picking system is compared with the traditional warehouse setup without AMR support and to another work policy using fixed pairings of picker and AMR per order. We find that largely improved makespans can be expected. In addition, we analyze the effects of stochastic picking times, speed differences between AMRs and pickers, and a zoning strategy. The ripple effect caused by stochastic picking times, in which a single delay may cascade through a tightly synchronized schedule and deteriorate picking performance, can be effectively mitigated by separating the workforce into smaller subgroups. Another important finding is that pickers and AMR should have approximately the same travel speed because slower AMRs deteriorate system performance. Finally, zoning slightly decreases the flexibility of the system and should be used if dictated by organizational reasons. History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.1207. [ABSTRACT FROM AUTHOR]

Childhood vaccines play a vital role in social welfare, but in hard-to-reach regions, poor transportation, and a weak cold chain limit vaccine availability. This opens the door for the use of vaccine delivery by drones (uncrewed aerial vehicles, or UAVs) with their fast transportation and reliance on little or no infrastructure. In this paper, we study the problem of strategic multimodal vaccine distribution, which simultaneously determines the locations of local distribution centers, drone bases, and drone relay stations, while obeying the cold chain time limit and drone range. Two mathematical optimization models with complementary strengths are developed. The first model considers the vaccine travel time at the aggregate level with a compact formulation, but it can be too conservative in meeting the cold chain time limit. The second model is based on the layered network framework to track the vaccine flow and travel time associated with each origin-destination (OD) pair. It allows the number of transshipments and the number of drone stops in a vaccine flow path to be limited, which reflects practical operations and can be computationally advantageous. Both models are applied for vaccine distribution network design with two types of drones in Vanuatu as a case study. Solutions with drones using our parameter settings are shown to generate large savings, with differentiated roles for large and small drones. To generalize the empirical findings and examine the performance of our models, we conduct comprehensive computational experiments to assess the sensitivity of optimal solutions and performance metrics to key problem parameters. History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics. Funding: This work was supported by the Association for Supply Chain Management (ASCM) and the University of Missouri Research Board (UMSL Award 0059109). Supplemental Material: The online supplement is available at https://doi.org/10.1287/trsc.2023.1205. [ABSTRACT FROM AUTHOR]

In unsplittable network flow problems, certain nodes must satisfy a combinatorial requirement that the incoming arc flows cannot be split or merged when routed through outgoing arcs. This so-called no-split no-merge requirement arises in unit train scheduling where train consists should remain intact at stations that lack necessary equipment and manpower to attach/detach them. Solving the unsplittable network flow problems with standard mixed-integer programming formulations is computationally difficult due to the large number of binary variables needed to determine matching pairs between incoming and outgoing arcs of nodes with no-split no-merge constraint. In this paper, we study a stochastic variant of the unit train scheduling problem where the demand is uncertain. We develop a novel decision diagram (DD)-based framework that decomposes the underlying two-stage formulation into a master problem that contains the combinatorial requirements and a subproblem that models a continuous network flow problem. The master problem is modeled by a DD in a transformed space of variables with a smaller dimension, leading to a substantial improvement in solution time. Similar to the Benders decomposition technique, the subproblems output cutting planes that are used to refine the master DD. Computational experiments show a significant improvement in solution time of the DD framework compared with that of standard methods. History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics. Funding: This work was supported by the Iowa Energy Center [Grant 20IEC005]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2022.1194. [ABSTRACT FROM AUTHOR]

Ride-pooling, which accommodates multiple passenger requests in a single trip, has the potential to substantially enhance the throughput of mobility-on-demand (MoD) systems. This paper investigates MoD systems that operate mixed fleets composed of "basic supply" and "augmented supply" vehicles. When the basic supply is insufficient to satisfy demand, augmented supply vehicles can be repositioned to serve rides at a higher operational cost. We formulate the joint vehicle repositioning and ride-pooling assignment problem as a two-stage stochastic integer program, where repositioning augmented supply vehicles precedes the realization of ride requests. Sequential ride-pooling assignments aim to maximize total utility or profit on a shareability graph: a hypergraph representing the matching compatibility between available vehicles and pending requests. Two approximation algorithms for midcapacity and high-capacity vehicles are proposed in this paper; the respective approximation ratios are 1 / p 2 and (e − 1) / (2 e + o (1)) p ln p , where p is the maximum vehicle capacity plus one. Our study evaluates the performance of these approximation algorithms using an MoD simulator, demonstrating that these algorithms can parallelize computations and achieve solutions with small optimality gaps (typically within 1%). These efficient algorithms pave the way for various multimodal and multiclass MoD applications. History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics. Funding: This work was supported by the National Science Foundation [Grants CCF-2006778 and FW-HTF-P 2222806], the Ford Motor Company, and the Division of Civil, Mechanical, and Manufacturing Innovation [Grants CMMI-1854684, CMMI-1904575, and CMMI-1940766]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2021.0349. [ABSTRACT FROM AUTHOR]

In this paper, we study a new variant of the parallel drone scheduling traveling salesman problem that aims to increase the utilization of drones, particularly for heavy item deliveries. The system under consideration adopts a technology that combines multiple drones to form a collective drone (c-drone) capable of transporting heavier items. The innovative concept is expected to add further flexibility in vehicle assignment decisions. An especially difficult challenge to address is the collaboration among drones because it requires temporal synchronization between their delivery tours. To better model the reality, we also consider that drone power consumption is a nonlinear function of both speed and parcel weight. We first develop a two-index mixed integer linear programming (MILP) formulation from which a simple branch and cut is developed to solve small-size instances to optimality. To efficiently handle larger problem instances, we propose a ruin-and-recreate metaheuristic with problem-tailored removal and insertion operators, in which an efficient move evaluation procedure based on the topological sort is designed to deal with the complexity of the synchronization constraints. Computational experiments demonstrate the validity of the developed MILP model and the performance of the proposed metaheuristic. Sensitivity analyses based on the classification and regression tree are performed to investigate the benefits of using c-drones and the important factors affecting the efficiency of the new transportation system. History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics. [ABSTRACT FROM AUTHOR]

An introduction to the journal is presented which discusses various papers published within the issue, including one on a deterministic maritime inventory routing problem, one on an integrated mixed integer linear programming model for linear companies alliances, and another on scheduling disruption scenarios for liner companies.

This paper investigates a variant of the traveling salesman problem (TSP) with speed optimization for a plug-in hybrid electric vehicle (PHEV), simultaneously optimizing the average speed and operation mode for each road segment in the route. Two mixed-integer nonlinear programming models are proposed for the problem: one with continuous speed decision variables and one with discretized variables. Because the models are nonlinear, we propose reformulation schemes and introduce valid inequalities to strengthen them. We also describe a branch-and-cut algorithm to solve these reformulations. Extensive numerical experiments are performed to demonstrate the algorithm's performance in terms of computing time and energy consumption costs. Specifically, the proposed solution method can efficiently solve instances with a realistic number of customers and outperforms the benchmark approaches from the literature. Integrating speed optimization into the TSP of a PHEV can lead to significant energy savings compared with the fixed-speed TSP. In addition, the proposed model is extended to investigate the impact of the presence of charging stations, which makes the problem harder to solve but has the potential to further reduce energy consumption costs. Funding: F. Wu gratefully acknowledges the support of the National Natural Science Foundation of China [Grant 72271161]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0247. [ABSTRACT FROM AUTHOR]

An introduction to articles published within the issue is presented on topics including reducing network delay by controlling traffic signals, a method to calculate the uncertainty in emission predictions of traffic data inputs, and the use of inverse optimization methods to take route-choice behavior.

This paper studies how to integrate rider mode preferences into the design of on-demand multimodal transit systems (ODMTSs). It is motivated by a common worry in transit agencies that an ODMTS may be poorly designed if the latent demand, that is, new riders adopting the system, is not captured. This paper proposes a bilevel optimization model to address this challenge, in which the leader problem determines the ODMTS design, and the follower problems identify the most cost efficient and convenient route for riders under the chosen design. The leader model contains a choice model for every potential rider that determines whether the rider adopts the ODMTS given her proposed route. To solve the bilevel optimization model, the paper proposes an exact decomposition method that includes Benders optimal cuts and no-good cuts to ensure the consistency of the rider choices in the leader and follower problems. Moreover, to improve computational efficiency, the paper proposes upper and lower bounds on trip durations for the follower problems, valid inequalities that strengthen the no-good cuts, and approaches to reduce the problem size with problem-specific preprocessing techniques. The proposed method is validated using an extensive computational study on a real data set from the Ann Arbor Area Transportation Authority, the transit agency for the broader Ann Arbor and Ypsilanti region in Michigan. The study considers the impact of a number of factors, including the price of on-demand shuttles, the number of hubs, and access to transit systems criteria. The designed ODMTSs feature high adoption rates and significantly shorter trip durations compared with the existing transit system and highlight the benefits of ensuring access for low-income riders. Finally, the computational study demonstrates the efficiency of the decomposition method for the case study and the benefits of computational enhancements that improve the baseline method by several orders of magnitude. Funding: This research was partly supported by National Science Foundation [Leap HI Proposal NSF-1854684] and the Department of Energy [Research Award 7F-30154]. [ABSTRACT FROM AUTHOR]

Schedule coordination is the primary form of demand management used at busy airports. At its core, slot allocation involves a highly complex combinatorial problem. In response, optimization models have been developed to minimize the displacement of flight schedules from airline requests, subject to physical and administrative constraints. Existing approaches, however, may not result in the best itineraries for passengers. This paper proposes an original passenger-centric approach to airport slot allocation to maximize available itineraries and minimize connecting times. Because of the uncertainty regarding passenger demand, the proposed approach combines predictive analytics to forecast passenger flows in flight networks from historical data and prescriptive analytics to optimize airport slot assignments in view of flight-centric and passenger-centric considerations. The problem is formulated as a mixed-integer nonconvex optimization model. To solve it, we propose an approximation scheme that alternates between flight-scheduling and passenger-accommodation modules and embed it into a large-scale neighborhood search algorithm. Using real-world data from the Singapore Changi and Lisbon Airports, we show that the proposed model and algorithm return solutions in acceptable computational times. Results suggest that slot-allocation outcomes can be made much more consistent with passenger flows at a relatively small cost in terms of flight displacement. Ultimately, this paper provides a new paradigm that can create more attractive flight schedules by bringing together airport-level considerations, airline-level considerations, and, for the first time, passenger-level considerations. Funding: Financial support from the Civil Aviation Authority of Singapore [Project on Airfield Management and Economics] is gratefully acknowledged. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.1165. [ABSTRACT FROM AUTHOR]

Microscopic traffic flow models enable predictions of traffic operations, which allows traffic engineers to assess the efficiency and safety effects of roadway designs. Modeling vehicle trajectories inside intersections is challenging because there is an infinite number of possible paths in a two-dimensional space, and drivers can simultaneously adapt their speeds as well. To date, human driver models for simultaneous longitudinal and lateral vehicle control based on the infrastructure characteristics and interactions with other drivers inside an intersection are still lacking. The contribution of this paper is threefold. First, it proposes an integrated microscopic traffic flow model to describe human-driven vehicle maneuvers under interactions. Drivers plan their heading and acceleration in the predicted future to minimize costs representing undesirable situations. The model works with a joint optimization for an interaction cost term. The weights associated with the interaction cost reflect how selfish or altruistic drivers are. Second, the proposed model endogenously gives the order of vehicles in case of crossing paths. Third, the paper develops a clustered validation method for microscopic traffic flow models with interacting vehicles, which account for interdriver variations. Results show that the model can accurately describe vehicle passing orders of interacting maneuvers, paths, and speeds against empirical data. The model can be applied to assess various intersection designs. Funding: This work was supported by the National Natural Science Foundation of China [Grants 71971140 and 52122215] and the Natural Science Foundation of Shanghai [Grant 20ZR1439300]. [ABSTRACT FROM AUTHOR]

Performance aspects such as travel time, punctuality, and robustness are conflicting goals of utmost importance for railway transports. To successfully plan railway traffic, it is therefore important to strike a balance between planned travel times and expected delays. In railway operations research, a lot of attention has been given to construct models and methods to generate robust timetables—that is, timetables with the potential to withstand design errors, incorrect data, and minor everyday disturbances. Despite this, the current state of practice in railway planning is to construct timetables manually, possibly with support of microsimulation for robustness evaluation. This paper aims to narrow the gap between the state-of-the-art optimization-based research approaches and the current state of practice to construct timetables by combining simulation and optimization. The paper proposes a combined simulation-optimization approach for double-track lines, which generalizes previous work to allow full flexibility in the order of trains by including a new and more generic model to predict delays. By utilizing delay data from simulation, the approach can make socioeconomically optimal modifications of a given timetable by minimizing predicted disutility—the weighted sum of scheduled travel time and total predicted delay. In a large simulation experiment on the heavily congested Swedish Western Main Line, it is demonstrated that compared with a real-life, manually constructed timetable, large reductions of delays as well as improvements in punctuality could be obtained for a small cost of marginally longer travel times. The cost of scheduled in-vehicle travel time and mean delay was reduced by 5% on average, representing a large improvement for a highly utilized railway line. Furthermore, a separate scaling experiment indicates that the approach can also be suitable for larger problems. Funding: This research was funded by Trafikverket [Grants TRV 2016/5090 and TRV 2020/72690]. [ABSTRACT FROM AUTHOR]

This paper integrates, from a tactical perspective, berth allocation and quay-crane assignment, two important, closely related decisions in container terminal operations in a single model. To obtain optimal solutions, a branch-and-price algorithm is sought in this paper under the framework of Dantzig–Wolfe decomposition. The algorithm decomposes the original problem to a master problem that links all vessels competing for the shared resources of berths and quay cranes and multiple per-vessel pricing subproblems that can be solved efficiently in polynomial time. Specifically, in the stage of generating promising initial feasible columns, three heuristics are adopted; during the column-updating stage, the subgradient-based Lagrangian relaxation is introduced to tackle the possibly encountered degeneracy phenomenon; the branching strategy is implemented in the pricing subproblem rather than in the master problem as reported in the literature with the benefit of avoiding incurring new dual prices, simplifying the branching process; and both breadth- and depth-first searching policies are tested to select the next node to explore. With real-life data, extensive numerical experiments are conducted to select the best choice for each stage with the strengths and drawbacks of each choice provided. And then the superiority of the branch-and-price algorithm configured with the selected combination of strategies is verified by comparing it with both CPLEX, a general-purpose solver, and a set-partitioning model, a dedicated algorithm reported in the literature. In addition, the decomposition by vessels adopted in this paper is also verified numerically by comparing it with the decomposition by berths reported in the literature, and the performance of the algorithm for other problem settings has also been tested. In conclusion, the numerical experiments show that our method outperforms the commercial solver and state-of-the-art solution methods reported in the literature in terms of both solution quality and computational time. [ABSTRACT FROM AUTHOR]

Shipping channels are often a constraint to port capacity because of the significant capital cost and environmental impact of channel dredging. Channels are often narrow in places, which constrains the capability of vessels passing in opposing directions. Capacity impacts of channel operations are significant in tidally restricted ports, where deep draft vessels are able to move through the channel only during narrow windows around high tide to maintain sufficient under-keel clearance. There has been much research to date around berth allocation and sequencing, but in channel-constrained ports, the value of these existing approaches can be limited. This is particularly apparent in a numerical example presented in this paper where the berth allocations are suboptimal when the channel is not considered. In this paper, we present an approach to optimize the scheduling of channel movements and, furthermore, to integrate the channel scheduling and berth allocation/sequencing problems. A mixed integer program formulation is presented for this problem, based on a no-wait bidirectional flow shop with parallel machines. Benchmark problems consistent with the literature for berth allocation/sequencing have been modified to incorporate a range of channel configurations and used as test cases for the proposed model. [ABSTRACT FROM AUTHOR]

This paper studies the two-echelon capacitated vehicle routing problem with time windows. The first echelon consists of transferring freight from depots to intermediate facilities (i.e., satellites), whereas the second echelon consists of transferring freight from these facilities to the final customers, within their time windows. We propose two path-based mathematical formulations for our problem: (1) in one formulation, paths are defined over both first- and second-echelon tours, and (2) in the other one, the first- and second-echelon paths are decomposed. Branch-and-price–based algorithms are developed for both formulations. We compare both formulations and solution methods on a comprehensive set of instances and are able to solve instances up to five satellites and 100 customers to optimality. This paper is the first paper in the literature that solves such large instance sizes. The online appendix is available at https://doi.org/10.1287/trsc.2018.0844. [ABSTRACT FROM AUTHOR]

This paper reviews the literature on vehicle routing problems and location routing problems with intermediate stops. We classify publications into different categories from both an application-based perspective and a methodological perspective. In addition, we analyze the papers with respect to the algorithms and benchmark instances they present. Furthermore, we provide an overview of trends in the literature and identify promising areas for further research. [ABSTRACT FROM AUTHOR]

Since advanced traveler information and traffic management systems have become popular, it is vital to capture the joint impact of various strategies on transportation systems. Developing analytical models to incorporate traffic dynamics and travel behavior is challenging. Based on observation of the heteroscedasticity of the simulation noise in the stochastic simulator, this paper develops the Bayesian stochastic Kriging (BSK) model to adapt for the heteroscedastic noise and metamodel parameter uncertainty in a Bayesian framework, which enhances the existing surrogate-based optimization methods. This paper presents a metamodel for large scale simulation-based freeway traffic management optimization problems. Simulation-based optimization combines the advantages of simulation models and mathematical optimization methods. The parameter estimation of the BSK model is accomplished by the Bayesian inference. The proposed methodology enables the efficient use of large scale high-resolution traffic simulation models for simulation-based optimization, while accounting for travelers' behavioral responses to information provision. We demonstrate the advantages of BSK compared to other existing metamodels using a numerical example of a synthetic network and a mathematical example. In a work zone scenario on a real-world freeway/arterial corridor of I-270 and MD-355 in the State of Maryland, the BSK model is applied to the freeway traffic management via optimizing the high-occupancy/toll rate and deploying dynamic message signs. Field traffic measurements by loop/microwave detections are used to calibrate travel demand and to supply the simulation parameters. The optimization results are promising in reducing the corridor-wide travel delay and enhancing the vehicle throughput. The online appendix is available at https://doi.org/10.1287/trsc.2018.0819. [ABSTRACT FROM AUTHOR]

The BusPlus project aims at improving the off-peak hours public transit service in Canberra, Australia. To address the difficulty of covering a large geographic area, proposes a hub and shuttle model consisting of a combination of a few high-frequency bus routes between key hubs and a large number of shuttles that bring passengers from their origin to the closest hub and take them from their last bus stop to their destination. This paper focuses on the design of the bus network and proposes an efficient solving method to this multimodal network design problem based on the Benders decomposition method. Starting from a mixed-integer programming (MIP) formulation of the problem, the paper presents a Benders decomposition approach using dedicated solution techniques for solving independent subproblems, Pareto-optimal cuts, cut bundling, and core point update. Computational results on real-world data from Canberra's public transit system justify the design choices and show that the approach outperforms the MIP formulation by two orders of magnitude. Moreover, the results show that the hub and shuttle model may decrease transit time by a factor of two, while staying within the costs of the existing transit system. [ABSTRACT FROM AUTHOR]

This paper extends the dynamically formulated hidden Markov models to a high-order hidden Markov model (HO-HMM) formulation. In the HO-HMM, the Markovian assumption that the future states (interpreted as the states of preferences or attitudes) depend only on the current state has been relaxed. Instead, the HO-HMM generalizes that the future states will depend on a number of states occurring beforehand. This paper develops the theoretical formulation of a HO-HMM framework. A recursive algorithm of likelihood computation is derived for model estimation. The algorithm significantly reduces the complexity of estimation and ensures the applicability of high-order hidden Markov modeling. The proposed methodology is further demonstrated on a vehicle ownership choice application using Puget Sound Transportation Panel data coupled with a few supplementary data sources. Long-term life-cycle stage changes in households are used as proxies for the high-order Markov transitions in car ownership hidden states. Results indicate that the HO-HMM has superior explanatory power in fitting longitudinal data. [ABSTRACT FROM AUTHOR]

Because customers must usually arrange their schedules to be present for home services, they desire an accurate estimate of when the service will take place. However, even when firms quote large service time windows, they are often missed, leading to customer dissatisfaction. Wide time windows and frequent failures occur because time windows must be communicated to customers in the face of several uncertainties: future customer requests are unknown, final service plans are not yet determined, and when fulfillment is outsourced to a third party, the firm has limited control over routing procedures and eventual fulfillment times. Even when routing is performed in-house, time windows often do not receive explicit consideration. In this paper, we show how companies can communicate reliable and narrow time windows to customers in the face of arrival time uncertainty when time window decisions are decoupled from routing procedures. Under assumptions on the shape of arrival time distributions, our main result characterizes the optimal policy, identifying structure that reduces a high-dimensional stochastic nonlinear optimization problem to a root-finding problem in one dimension. The result inspires a practice-ready heuristic for the more general case. Relative to the industry standard of communicating uniform time windows to all customers, and to other policies applied in practice, our method of quoting customer-specific time windows yields a substantial increase in customer convenience without sacrificing reliability of service. Our results show that time windows should be tailored to individual customers, time window sizes should be proportional to the service level, larger time windows should be assigned to earlier requests and smaller time windows to later requests, larger time windows should be assigned to customers further from the depot of operation and smaller time windows to closer customers, high quality time windows can be identified even with limited data, and cost savings afforded by routing efficiency should be measured against potential losses to customer convenience. Funding: M. W. Ulmer's work is funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) Emmy Noether Programme, [project 444657906]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/trsc.2023.0004. [ABSTRACT FROM AUTHOR]

Hydrogen can be produced from water, using electricity. The hydrogen can subsequently be kept in inventory in large quantities, unlike the electricity itself. This enables solar and wind energy generation to occur asynchronously from its usage. For this reason, hydrogen is expected to be a key ingredient for reaching a climate-neutral economy. However, the logistics for hydrogen are complex. Inventory policies must be determined for multiple locations in the network, and transportation of hydrogen from the production location to customers must be scheduled. At the same time, production patterns of hydrogen are intermittent, which affects the possibilities to realize the planned transportation and inventory levels. To provide policies for efficient transportation and storage of hydrogen, this paper proposes a parameterized cost function approximation approach to the stochastic cyclic inventory routing problem. Firstly, our approach includes a parameterized mixed integer programming (MIP) model which yields fixed and repetitive schedules for vehicle transportation of hydrogen. Secondly, buying and selling decisions in case of underproduction or overproduction are optimized further via a Markov decision process (MDP) model, taking into account the uncertainties in production and demand quantities. To jointly optimize the parameterized MIP and the MDP model, our approach includes an algorithm that searches the parameter space by iteratively solving the MIP and MDP models. We conduct computational experiments to validate our model in various problem settings and show that it provides near-optimal solutions. Moreover, we test our approach on an expert-reviewed case study at two hydrogen production locations in the Netherlands. We offer insights for the stakeholders in the region and analyze the impact of various problem elements in these case studies. Funding: This project received funding from the Fuel Cells and Hydrogen 2 Joint Undertaking (now Clean Hydrogen Partnership) under [Grant Agreement 875090]. The Joint Undertaking receives support from the European Union's Horizon 2020 research and innovation programme, Hydrogen Europe and Hydrogen Europe Research. A. H. Schrotenboer received support from the Dutch Science Foundation (Nederlandse Organisatie voor Wetenschappelijk Onderzoek; NWO) through [Grant VI.Veni.211E.043]. [ABSTRACT FROM AUTHOR]

In this paper, we present a novel data-driven optimization approach for trajectory-based air traffic flow management (ATFM). A key aspect of the proposed approach is the inclusion of airspace users' trajectory preferences, which are computed from traffic data by combining clustering and classification techniques. Machine learning is also used to extract consistent trajectory options, whereas optimization is applied to resolve demand-capacity imbalances by means of a mathematical programming model that judiciously assigns a feasible four-dimensional trajectory and a possible ground delay to each flight. The methodology has been tested on instances extracted from the Eurocontrol data repository. With more than 32,000 flights considered, we solve the largest instances of the ATFM problem available in the literature in short computational times that are reasonable from the practical point of view. As a by-product, we highlight the trade-off between preferences and delays as well as the potential benefits. Indeed, computing efficient solutions to the problem facilitates a consensus between the network manager and airspace users. In view of the level of accuracy of the solutions and the excellent computational performance, we are optimistic that the proposed approach can make a significant contribution to the development of the next generation of air traffic flow management tools. [ABSTRACT FROM AUTHOR]

This paper considers the scheduling of electric vehicles in a public transit system. Our main innovation is that we take into account that charging stations have limited capacity, while also considering partial charging. To solve the problem, we expand a connection-based network in order to track the state of charge of vehicles and model recharging actions. We then formulate the electric vehicle scheduling problem as a path-based binary program, whose linear relaxation we solve using column generation. We find integer feasible solutions using two heuristics: price-and-branch and a diving heuristic, including acceleration strategies. We test the approach using data from the concession Gooi en Vechtstreek in the Netherlands, containing up to 816 trips. The diving heuristic outperforms the other heuristic and solves the entire concession within seven hours of computation time with an optimality gap of less than 3%. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0253. [ABSTRACT FROM AUTHOR]

In ride-sharing systems, platform providers aim to distribute the drivers in the city to meet current and potential future demand and to avoid service cancellations. Ensuring such distribution is particularly challenging in the case of a crowdsourced fleet, as drivers are not centrally controlled but are free to decide where to reposition when idle. Thus, providers look for alternative ways to ensure a vehicle distribution that benefits users, drivers, and the provider. We propose an intuitive mean to improve idle ride-sharing vehicles' repositioning: repositioning heatmaps. These heatmaps highlight driver-specific earning opportunities approximated based on the expected future demand, current and expected future fleet distribution, and the location of the specific driver. Based on the heatmaps, drivers make decentralized yet better-informed repositioning decisions. As our heatmap policy changes the driver distribution in the future, we propose an adaptive learning algorithm for designing our heatmaps in large-scale ride-sharing systems. We simulate the system and generate heatmaps based on the previously learned policy in every iteration. We then update the policy based on the simulation's outcome and use it in the next iteration. We test our heatmap design in a comprehensive case study on New York ride-sharing data. We show that carefully designed heatmaps reduce service cancellations and therefore, revenue loss for the platform and drivers significantly while leading to a better service level for the users and to a fairer treatment of drivers. History: This paper has been accepted for the Transportation Science Special Issue on Machine Learning Methods and Applications in Large-Scale Route Planning Problems. Funding: This research is funded by the German Research Foundation (Deutsche Forschungsgemeinschaft) [Grant 494812908]. M. W. Ulmer's work is funded by the German Research Foundation Emmy Noether Programme [Grant 444657906]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.1202. [ABSTRACT FROM AUTHOR]