Transportation Science and Logistics Society Best Dissertation Award Competition: Abstracts of 2024 Winners

The 2024 prize winners are as follows:

Winner

Traffic Signal Optimization with Connected Vehicle Trajectories

Xingmin Wang, University of Michigan

Advisor: Henry X. Liu

Honorable Mention

Algorithmic Solutions for Emerging Challenges in Last-Mile Logistics

Patrick Klein, Technical University of Munich

Advisor: Maximilian Schiffer

Traffic Signal Optimization with Connected Vehicle Trajectories

Xingmin Wang

Department of Civil and Environmental Engineering, University of Michigan, Ann Arbor, Michigan 48109

Contact: [email protected], https://orcid.org/0000-0003-0435-2786 (XW)

1. Introduction

Traffic signal retiming is widely regarded by traffic engineers as one of the most cost-effective methods for reducing congestion and energy consumption in urban areas as it does not require any major changes to the existing infrastructure (Wang et al. 2022, Fei et al. 2023). However, the high installation and maintenance costs of vehicle detectors have prevented the widespread implementation of detector-based systems such as vehicle-actuated control and adaptive traffic control systems (ATCSs). As a result, a large proportion of the signalized intersections in the United States do not have detection capability and are still controlled by fixed-time traffic signals. Signal retiming at these intersections still relies on manual data collections and is therefore only executed every three to five years in practice. As traffic demand undergoes natural changes or growth, these timing plans become outdated, which increases congestion and energy costs.

In recent years, vehicle trajectory data have become increasingly available from various connected vehicle services such as en route navigation, roadside assistance, and ride-hailing (Wang et al. 2020, 2023; Jerome et al. 2022). Monitoring traffic through vehicle trajectory data offers many advantages over fixed-location detectors and sensors. It has a much larger coverage area than detector data because it is available at almost every intersection, especially those with higher traffic volumes. Although detector data can only provide traffic counts and estimated speeds at certain locations, vehicle trajectory data span the spatial-temporal space and provide more enriched information such as delay, number of stops, and travel path.

Although vehicle trajectory data have many advantages over traditional detector data, the major challenge for traffic signal retiming is the data sparsity and incompleteness caused by the limited penetration rate (<10%). To overcome this challenge, this dissertation proposes a new stochastic traffic flow model called the probabilistic time-space (PTS) model (Section 2). The PTS model enables us to use different statistical estimation methods to estimate the overall traffic state with low penetration rate vehicle trajectories (Section 3). Based on these methods, we developed an integrated traffic signal retiming system and tested it in the real world, which effectively reduced the vehicle delay and number of stops (Section 4).

2. PTS Model

Stochastic traffic flow models play an important role in reconstructing the overall traffic state with sparse and incomplete observations such as low penetration rate vehicle trajectories. However, existing traffic flow models cannot be directly used because trajectories provide different traffic measurements compared with traditional detectors. To fill this gap, this dissertation proposes a new model framework called the PTS model.

The PTS model is based on a newly proposed Newellian coordinates system. We call it Newellian coordinates because all vehicles are assumed to follow a deterministic Newell’s car-following model. The left of Figure 1 is an illustration of the Newellian coordinates: a distorted mesh grid $(t,n)$ where the horizontal axis $t$ is the free-flow arrival time and the vertical axis $n$ is the number of vehicles. Compared with real-world time-space coordinates, the Newellian coordinates use the free-flow arrival time as the time axis such that the free-flow travel time of trajectories can be ignored. As shown in Figure 1, vehicle trajectories can be projected to a point queue process under the Newellian coordinates, and the dynamical equation is given by

where $X(t)$ denotes the number of stopped vehicles right after time $t$, and $A(t)$ and $B(t)$ denote the vehicle arrival and departure, respectively. With the discrete approximation, both the vehicle arrival and departure are binary at each time: They are either zero or one vehicle.

By applying a stochastic arrival process, the point queue process becomes a stochastic discrete queueing model. The other important part of the PTS model is the PTS diagram, which projects this stochastic point queue process back to the Newellian coordinates to obtain the spatial-temporal distribution of vehicle trajectories. In this way, the PTS model establishes the bidirectional mapping between the point queue process and spatial-temporal vehicle trajectories such that a simple point-queue model can be utilized to describe traffic flow dynamics near intersections. This simplification is made feasible by ignoring the stochastic driving behavior because most of the system uncertainty comes from the stochastic traffic demand, as well as sparse observation at a low penetration rate. The main advantage of the proposed model is that it is a stochastic model with much lower dimensions and can be directly calibrated by taking the vehicle trajectory data as the input. It enables us to apply different statistical estimation algorithms to estimate both stationary traffic parameters (i.e., penetration rate, average arrival rate, etc.) and real-time traffic state (queue length).

3. Traffic State Estimation

Based on the previously introduced PTS model, we develop two different approaches to estimate the unknown traffic state and parameters with the low penetration rate vehicle trajectories.

The first approach is based on the methods of moment estimation. The intuition of this estimator is to match the average delay from the model-estimated value with the measurement from the observed trajectories. Figure 2 is an illustration of estimation results. Figure 2(b) is the aggregated time-space diagram of a real-world corridor, whereas Figure 2(c) shows the calibrated PTS diagram. A darker line in the PTS diagram indicates a higher probability that there is a vehicle traveling on it. As we can see, Figure 2(c) looks very similar to Figure 2(b), demonstrating the effectiveness of the estimation approach as well as the PTS diagram. The calibrated traffic flow model cannot only reconstruct the overall traffic state well, but it can also predict what would happen given different signal timing parameters, which is especially helpful for the further optimization of these parameters.

The second approach is to apply Bayesian estimation method to provide distributional estimation results for those unknown traffic state and parameters (Wang et al. 2024a). Based on the PTS diagram, we can formulate the partially observable system as a hidden Markov chain with unknown parameters. A single recursive algorithm can be used to calculate both the posterior of the traffic state and the marginal likelihood given certain parameters. Figure 3 is an example of the distributional estimation results: We not only provide the estimated value of the unknown parameters (i.e., arrival rate and penetration rate), but we also have the distribution given by equally weighted samples. It is of great significance to quantify the estimation uncertainty caused by limited available data because it can explicitly inform us whether the available data are sufficient to satisfy the desired estimation accuracy.

4. OSaaS System and Field Test

Based on the developed methodology, this dissertation developed an integrated traffic signal retiming system (OSaaS: optimizing traffic signals as a service), and a field implementation was conducted to test its effectiveness. OSaaS is a closed-loop signal optimization system that includes monitoring, modeling, diagnosis, and optimization. In each retiming iteration, delay and stop measurements are first calculated from trajectories. Traffic flow parameters such as the penetration rate and arrival rate are then estimated based on the proposed traffic flow model. With the calibrated model, the diagnosis module finds the optimality gap with respect to different signal timing parameters. Optimization algorithms are finally used to update signal timing parameters for intersections that show potential for improvement. In this way, the OSaaS system can dynamically optimize traffic signal periodically every few weeks.

In April 2022, a citywide field test of OSaaS was conducted in Birmingham, Michigan, with 34 signalized intersections. two corridors, and two isolated intersections implemented with new fixed-time signal timing plans, resulting in decreases in both the delay and number of stops by up to 20% and 30%, respectively. As shown by Figure 4, the coordination of one of the tested corridors was significantly improved after the offset optimization.

5. Summary and Social Impact

This dissertation proposes a holistic approach for traffic signal optimization with low penetration rate vehicle trajectories, which includes a new stochastic traffic flow model and associated traffic state estimation approaches. This leads to the development of OSaaS, the world’s first cloud-based traffic signal optimization system where the only input is vehicle trajectory data with a low penetration rate. As a closed-loop system, OSaaS continuously monitors urban traffic and can generate new signal timing plans whenever sufficient historical data are accumulated. It significantly shortens each retiming iteration, so a more responsive and strategic traffic signal retiming is feasible. By not requiring installation or maintenance of vehicle detectors, OSaaS provides a more scalable, sustainable, resilient, and efficient solution to traffic signal retiming based on vehicle trajectory, which could be applied to every fixed-time traffic signal in the world.

The main work of this dissertation has garnered significant attention for its profound social impact, receiving coverage from numerous news outlets. The core findings have been distilled into a paper entitled “Traffic Light Optimization with Low Penetration Rate Vehicle Trajectory Data,” (Wang et al. 2024b) published in Nature Communications. This paper represents a major milestone, being one of the earliest transportation engineering articles featured in the prestigious Nature series. The research has been reported by University of Michigan News, Associated Press News, and local TV station ClickOnDetroit, with more than 100 hundred media outlets reposting the story. A follow-up project on the online retiming of traffic signals has also been funded by the Strengthening Mobility and Revolutionizing Transportation program under the U.S. Department of Transportation. We will continue to advance this project and anticipate further impactful developments in the future.

Algorithmic Solutions for Emerging Challenges in Last-Mile Logistics

Patrick Sean Klein

Technical University of Munich, 80333 Munich, Germany

Contact: [email protected], https://orcid.org/0000-0002-2851-6047 (PSK)

The logistics sector is experiencing a transformative era characterized by a paradigm shift in customer service expectations, an unprecedented demand increase, and an urgent need for sustainable operations (McKinnon et al. 2015, IEA 2019, ITF 2023, Mordor Intelligence Research & Advisory 2024). These developments present various challenges for logistics service providers (LSPs). They not only need to improve their service quality, offering tighter delivery windows and drastically shortened lead times to meet customer expectations, but also concurrently have to meet an expanded volume of deliveries, all while realizing sustainable operations. In this setting, operators’ reliance on efficient planning to realize cost-competitive last-mile operation becomes increasingly crucial. However, the planning tools available today fail to address the challenges of the modern logistics landscape, requiring the development of more advanced solutions for LSPs.

Traditional day-ahead planning fails to meet customers’ demands for short lead time (on-demand) deliveries as orders are not known in advance, often arriving on the day of delivery, that is, when parts of the fleet have already been dispatched. Dealing with the dynamic nature of this problem setting instead requires real-time reactive planning approaches capable of responding to customer requests in real time.

Many LSPs transition to electric commercial vehicles (ECVs) to realize sustainable operations. These need to be recharged, which is usually done during off-shift hours at a central depot. Here, the high price of chargers and supporting infrastructure limits charging capacity, such that charging operations must be strategically scheduled to ensure that all vehicles are sufficiently charged for next-day operations.

The aim of this thesis is twofold. First, it aims to design algorithms that address the challenges of on-demand delivery and strategic ECV charging. Second, it aims to make these and other algorithmic solutions more accessible to practitioners. We believe that this is pivotal in bridging the gap between theory and practice, as accessible tooling enables operators to rapidly evaluate how well state-of-the-art research amends to their specific operational context.

We achieve our first aim through two separate papers both published in Transportation Science (Klein and Schiffer 2023, Baty et al. 2024). The efficacy and methodological innovations of Baty et al. (2024) specifically have been recognized in the EURO Meets NeurIPS 2022 Vehicle Routing Competition, where it won first prize and was awarded a jury award. We achieve our second aim by open-sourcing our implementations of the developed algorithms and by developing an easy to use software package for designing state-of-the-art algorithms for vehicle routing problems with intermediate stops. This software package and its corresponding paper have been published in the INFORMS Journal on Computing (Klein and Schiffer 2024) and is available on Github.

The following sections outline the contributions of this thesis and the publications that resulted out of it in detail.

Tackling the Challenges of On-Demand Delivery

A particularly challenging aspect of modern logistics is the rise of on-demand (same-day) delivery. Here, orders are not known in advance such that vehicle routes must be planned dynamically. In this setting, retailers’ availability to offer fast and cost-effective deliveries relies heavily on making efficient dispatching and routing decisions, balancing the trade-off between immediate dispatch and awaiting future orders. This constitutes a dynamic vehicle routing and dispatching problem, which we model as follows.

Requests arrive continuously over a finite planning horizon, which is divided into discrete epochs. At the start of each epoch, the operator must decide how many vehicles to dispatch, which requests to postpone, and assemble routes accordingly. These decisions are immutable; that is, vehicles cannot be rerouted to serve additional requests once dispatched. Each request must be fulfilled within its designated time window.

Methodologically, similar dynamic vehicle routing problems have been approached by amending combinatorial optimization (CO) algorithms to dynamic problem settings, that is, by sampling future scenarios (Gendreau et al. 1999, Ritzinger, Puchinger, and Hartl 2016, Steever, Karwan, and Murray 2019, Ojeda Rios et al. 2021), or with machine learning (ML), that is, by predicting future rewards (Nazari et al. 2018, Ulmer, Soeffker, and Mattfeld 2018, Kool, van Hoof, and Welling 2019, Joe and Lau 2020). Applied individually, each approach has its drawbacks: CO algorithms do not fully capitalize on the potential insights from anticipating future demand, whereas ML approaches disregard the combinatorial structure inherent in the underlying routing problem.

Our approach mitigates these individual drawbacks by pioneering the integration of ML and CO methodologies in a single ML-CO pipeline. This innovative pipeline leverages a predictive model to determine the optimal timing for serving a request and embeds a CO layer to effectively assemble served requests into routes. The design of this pipeline is based on two key ideas.

The first idea is to reduce the CO problem to a prize-collecting vehicle routing problem. This transforms the problem of deciding whether to serve a request at a particular time to anticipating the cost of serving an order in the future, moving the dispatching decision into the CO problem. We provide sound and correctness proofs for this reduction in the main body of the thesis.

The second idea is to train the resulting integrated ML-CO pipeline on the decision loss, that is, in an end-to-end learning framework. This, in effect, allows us to train our ML model on the routing rather than the dispatching decision, as is state-of-the-art.

In combination, these two ideas allowed the ML model to effectively leverage the combinatorial structure present in the CO problem. We overcome key challenges of this approach, such as nonsmoothness and degeneracy of the decision loss function, and computational complexity of the CO problem, using a perturbed Fenchel-Young loss function and a custom metaheuristic algorithm designed specifically for being used in such an integrated pipeline. The resulting algorithm is not only the first ML-CO pipeline for dynamic vehicle routing problems but also the first ML-CO pipeline to include a metaheuristic component.

Extensive numerical experiments demonstrate the performance of this approach: it outperforms Monte Carlo and rolling-horizon policies by $1.57\%$ and $7.12\%$ in terms of objective value, whereas only taking $1.67\%$ and $15.00\%$ of the runtime, respectively. The approach further outperformed state-of-the-art reinforcement learning and classic two-stage, that is, nonintegrated, ML approaches in the EURO Meets NeurIPS 2022 Vehicle Routing Competition, where it was awarded first prize.

Large-Scale On-Site ECV Charging

The adoption of electric vehicles in last-mile logistics introduces a complex charge scheduling problem. Expensive charging infrastructure, rising energy prices, and grid capacity constraints require operators to strategically schedule off-shift charging operations to remain cost competitive. This involves balancing vehicle availability, charger utilization, battery degradation, and cost savings from time-of-use energy prices, resulting in an integrated charging and service operation scheduling problem. We model this problem as follows:

A set of vehicles, sited at a central depot, is required to service a set of operations, for example, delivery routes, preassigned to the individual vehicles. Servicing an operation requires the vehicle to leave the depot, to which it returns immediately after providing service. This takes a certain time, consumes a certain amount of energy, and is possible only within a certain time window. The depot is equipped with a set of charging stations that can be used to recharge the vehicles between service operations. Charging incurs time-dependent energy cost and (nonlinear) degradation costs depending on the residual charge of the specific vehicle. We model the charging process as a nonlinear function of time and state of charge. Summarizing, the operator must decide (i) the departure times for vehicles to service operations and (ii) which charger to use for each vehicle and at what times.

This planning problem joins two streams of literature, namely (electric) vehicle scheduling and charge scheduling problems. Thus far, work on electric vehicle scheduling problems remains limited in either the complexity of the battery behavior models considered, assuming instantaneous (Adler and Mirchandani 2017, Yao et al. 2020) or linear (Wen et al. 2016, Alvo, Angulo, and Klapp 2021) charging, discretizes charging (van Kooten Niekerk, van den Akker, and Hoogeveen 2017) or does not consider station capacity constraints (Parmentier, Martinelli, and Vidal 2023). Similarly, existing work on charge scheduling problems either assumes simplified battery behavior models (Sassi and Oulamara 2016, Abdelwahed et al. 2020) or relies on commercial solvers (Pelletier, Jabali, and Laporte 2018), remaining limited in scalability. Moreover, no works integrate charging and service operation scheduling.

Methodologically, this thesis approaches the problem by decomposing it into master and subproblems, solved via branch-and-price. In this setup, the master problem assembles fleet schedules according to infrastructure capacity constraints, drawing from a pool of promising vehicle schedules generated by the individual subproblems. We reduce these schedule-generation subproblems to a resource-constrained shortest path problem over a time-expanded network. The major algorithmic challenge of this shortest path problem lies in taking into account nonlinear tradeoffs involving battery deterioration, charging costs, charger capacity, and the scheduling of service operations while still allowing continuous time recharging. We develop a novel label-setting shortest-path algorithm to overcome this challenge. The key novelty of this algorithm is a function-based label representation, where a label does not correspond to only a single decision, that is, carries a single value for each resource, but instead captures all possible recharging decisions at the previously visited charging station, allowing to delay the charging decision until a finite subset of potentially optimal decisions can be identified. We further contribute a set-based dominance rule, feasibility bounds, and a potential function to maintain the computational efficiency of this approach. We maintain scalability of the branch-and-price algorithm by developing efficient branching and pruning strategies. These strategies encompass a problem-specific branching rule, a primal heuristic, and partial pricing, all of which collectively contribute to effectively managing the algorithm’s scalability.

We show the overall efficiency of the developed algorithm in a comprehensive numerical study conducted on large-scale instances and measure the contribution of each of the developed speedup techniques in an ablation analysis, providing a deeper understanding of the individual and collective impacts of these techniques on the overall effectiveness of the algorithm. We further contribute an analysis of the impact of jointly scheduling charging and service operations, focusing on (i) the benefit of an integrated approach to charge and service operation scheduling, (ii) the impact of infrastructure capacity on operational costs, and (iii) the impact of considering variable energy prices. Specifically, we find that integrating charging and service operation scheduling can lower the amount of charging infrastructure required by up to 57% and reduce operational costs by up to 5%. Here, both the size of the operation time windows, that is, their scheduling flexibility, and the energy price distribution significantly impact operational cost savings.

Algorithmic Accessibility

Although research often addresses many of the planning problems faced by the logistics sector well before they emerge in practice, actual adoption of the developed solutions often occurs years after the problems became relevant. A key reason for this gap between theory and practice is a lack of accessibility: Academic papers often propose innovative algorithms and sophisticated models but rarely provide implementations. This creates a significant barrier for practitioners who aim to evaluate and apply these theoretical contributions to their specific operational context.

We instead maintain implementations of the proposed algorithms in public Github repositories, making them more accessible to interested practitioners. Beyond this general open-source approach, this thesis develops a software package designed to ease the implementation of advanced routing algorithms, called RoutingBlocks. This library serves as a tool to enable researchers and practitioners to leverage advanced routing algorithms in their research or as part of their software infrastructure. The key novelty of RoutingBlocks lies in being adaptable to a variety of unique case-specific problem settings and in supporting numerous algorithmic approaches, including genetic algorithms, neighborhood search, and simulated annealing, all while maintaining computational efficiency. RoutingBlocks achieves this by providing a modular algorithmic framework that allows the composition of tailored solution methods, ranging from optimized, state-of-the-art algorithmic components to efficient data structures. Specifically, the package maintains a clear separation between algorithmic components and problem configurations by employing a unified solution and instance representation that abstracts problem-specific behavior, for example, constraint checking, move evaluation, and cost computation, thus allowing to apply the same algorithm to various problem settings. Each algorithmic component is thoroughly documented and showcased in several tutorials, ensuring the package’s accessibility: a key for its application in educational and practical settings. Examples and numerical benchmarks demonstrate the ease-of-use and competitiveness of this package. Implementing iterated local search, adaptive large neighborhood search, and a state-of-the-art electric vehicle routing algorithm requires only 88, 92, and 290 lines of code, respectively.

Conclusion

The outcome of this thesis include novel solution methodologies complemented by practical contributions in the form of open-source software. This equips LSPs not only with algorithmic solutions for the optimization challenges of today’s logistics networks but also provides practical tools to easily test these novel solutions in practice.

The thesis’ contributions have been twice published in Transportation Science (Klein and Schiffer 2023, Baty et al. 2024) and in the INFORMS Journal on Computing (Klein and Schiffer 2024). The efficacy and methodological innovations of Baty et al. (2024) specifically have been recognized in the EURO Meets NeurIPS 2022 Vehicle Routing Competition, where it won first prize and was further curated with a jury award. Source codes of the developed packages and implementations are available on https://github.com/tumBAIS and well-known package indices (PyPI, Julia Package Registry). The individual publications further contributed to the state-of-the-art in various domains:

• Integrated ML and CO. Our work is the first paper to apply end-to-end learning to a dynamic vehicle routing problem. It demonstrates how to make complex CO problems amenable to integrated ML-CO pipelines through reduction. Additionally, it is the first approach to use a metaheuristic component in an integrated ML-CO pipeline, providing insights on designing such a metaheuristic and generalize the decision loss function accordingly.

• Vehicle and Charge Scheduling. The methodology developed in this work serves as a starting point for future research on integrated charge scheduling problems, providing algorithmic components that tackle some of the fundamental methodological challenges, such as nonlinear tradeoffs, continuous charging, and branch-and-bound tree fan-out, within this integrated problem setting. Moreover, the developed components generalize well to other problem contexts: The primal heuristic is not problem specific and can be applied to various branch-and-bound algorithms. Additionally, the shortest path algorithm is adaptable to any scenario involving nonlinear tradeoffs between resources, enabling its usage across diverse optimization problems.

In summary, this thesis contributed new state-of-the-art methods, algorithms, and software packages that effectively address challenging optimization problems in modern last-mile logistics.