Research

My work contributes to optimization theory and logistics practice. Here you'll find a summary of my approach and its impact along with papers and software.

Decision tree drawn on a chalkboard

Overview

How to make choices across time and in the face of uncertainty is the crux of many real-world challenges. These sequential decision problems arise in many domains, including business, engineering, the sciences, and health care. Often, both researchers and practitioners struggle to identify good policies, much less optimal decisions. My research aims to fill this gap. It addresses challenging dynamic and stochastic optimization problems. It expands theory and makes an impact on practice.

The value function and a decision tree

Sequential Decision Problems

Algorithms guaranteed to identify optimal policies for sequential decision problems suffer from the “curse of dimensionality.” The effort required to execute these procedures grows exponentially with problem size. For many problems of practical interest, the methods are intractable.

When provable optimal policies are beyond reach, how can we know whether a policy is good? My research approaches the issue from two directions. First, it establishes performance guarantees. These guarantees ensure the quality of a policy's decisions are at or above some benchmark level. Second, it constructs dual bounds on the value of an optimal policy. Dual bounds serve as an absolute limit on policy quality. My work aims to shrink the gap between a policy's performance and a dual bound, sandwiching the (unknown) optimal policy value between the two. When the gap is small enough, we can say with confidence the policy is good.

This approach to solving sequential decision problems draws on concepts in the fields of dynamic programming, optimal control, Markov decision processes, and reinforcement learning. For examples, see my papers titled "Bounded Backward Induction for Max-Min Dynamic Programs" and "A Rollout Algorithm Framework for Heuristic Solutions to Finite-Horizon Stochastic Dynamic Programs."

An illustration of the gap between the optimal policy value and a dual bound

Transportation and Logistics

Transportation and logistics problems provide context for much of my research. Practically, these problems are key drivers of the global supply chain. Theoretically, they are very challenging. Two things make them difficult. First, the size of the decision space is combinatorial. For example, the number of ways to route a fleet of vehicles across a supply network is considerable. Second, uncertainty is often multidimensional and unfolds across time. For instance, the number of possible demand realizations across SKUs and over an operating horizon can be substantial.

How to obtain good policies for dynamic and stochastic logistics problems is often an open question. My research approaches the issue by bringing together a deterministic legacy and recent theoretical advances. Modern transportation research leans on decades of deterministic analyses where demand, travel conditions, customer behavior, and various other factors are assumed to be known. When uncertainty enters the mix, deterministic methods generally break down. However, deterministic procedures can often be adapted to stochastic environments, leading to feasible policies, to dual bounds on the value of an optimal policy, and to insights that improve decision making.

This approach has led to problem-specific advances and to general methodological innovations. For example, see my paper titled "Electric Vehicle Routing with Public Charging Stations." For an example that also leverages developments in deep neural networks, see my paper titled "Dynamic Ridehailing with Electric Vehicles."

A word cloud listing various optimization terms

Impact

My research in dynamic and stochastic optimization has provided methodological underpinnings for academics and practitioners to address a wide range of issues, including problems in:

  • Food Distribution
  • Sustainable Transportation
  • Vaccine Allocation
  • Air Traffic Flow
  • Inventory Management
  • Carbon Sequestration
  • Political Campaign Management
  • Hazard Detection
  • Covert Information Collection
  • Crowdsourced Delivery
  • Media Buying
A graph showing optimal vaccine allocation in Missouri during the pandemic
Read more about collaboration with public health experts in my paper titled "Spatial Optimization to Improve COVID-19 Vaccine Allocation."

Submitted and Working Papers

Blocks with arrows forming a decision tree

Bounded Backward Induction for Max-Min Dynamic Programs

with Luca Bertazzi. July 2024.

How to hedge against worst-case outcomes when making decisions in sequence. The solution methodology, which includes general dual bounds and policy performance guarantees, solves problems orders of magnitude larger than what is tractable with conventional backward induction.

Read the Paper
Atari joystick and two game cartridges

Gamifying the Vehicle Routing Problem with Stochastic Requests

with Nicholas D. Kullman, Nikita Dudorov, Martin Cousineau, & Jorge E. Mendoza. July 2024.

Do you remember your first video game console? We remember ours. Decades ago, they provided hours of entertainment. Now, we have repurposed them to solve dynamic and stochastic optimization problems.

Read the Paper

Published Papers

Road sign displaying: what are you waiting for?

Optimal Service Time Windows

with Marlin W. Ulmer & Barrett W. Thomas. Transportation Science, 2024:58(2), 279-556.

Time is valuable. Stop waiting around for the cable guy! The paper provides an optimal policy to minimize time window size for a given service level. It shows firms how to improve customer convenience without compromising on reliability.

Read the Paper
Vials of COVID-19 vaccines

Spatial Optimization to Improve COVID-19 Vaccine Allocation

with Steve Scroggins, Enbal Shacham, & Tasnova Afroze. Vaccines, 2023:11(1).

How to allocate a limited supply of vaccines during a pandemic: Use terabytes of cell phone data, predict disease spread with regression, then distribute across time and space with off-the-shelf optimization software. Help us cut through the red tape by sharing this with policy makers wherever you live.

Read the Paper
Fleet of self-driving vehicles

Dynamic Ridehailing with Electric Vehicles

with Nicholas D. Kullman, Martin Cousineau, & Jorge E. Mendoza. Transportation Science, 2022:56(3), 567-798.

Transportation Science Paper of the Year

Autonomous ridesharing is the future of public transit. The paper develops AI methods to match riders with vehicles and position the fleet in anticipation of future use and charging needs.

Read the Paper
Electric vehicle charger

frvcpy: An Open-Source Solver for the Fixed Route Vehicle Charging Problem

with Nicholas D. Kullman, Aurelien Froger, & Jorge E. Mendoza. INFORMS Journal on Computing, 2021:33(4), 1259-1684.

The most fundamental tasks in electric vehicle routing are when and where to charge. These tasks underlie many operational problems in sustainable transportation. The paper describes software to manage the tasks along a given route.

Read the Paper
Electric van charging

Electric Vehicle Routing with Public Charging Stations

with Nicholas D. Kullman & Jorge E. Mendoza. Transportation Science, 2021:55(3), 637-659.

INFORMS Transportation Science & Logistics Society Best Paper Honorable Mention

Don't let uncertainty in the availability of public chargers stop a transition to EVs. The paper establishes a suite of optimization tools to design delivery routes that anticipate station queue dynamics.

Read the Paper
Illustration of a map app

On Modeling Stochastic Dynamic Vehicle Routing Problems

with Marlin W. Ulmer, Dirk C. Mattfeld, & Barrett W. Thomas. EURO Journal on Transportation and Logistics, 2020:9(2), 100008.

Rigorous methods have outpaced rigorous models, thus making it difficult to engage in rigorous science. Our route-based Markov decision process model makes it easier to connect dynamic routing problems with the route-based methods typically used to solve them.

Read the Paper
Courier on a motorcycle

Offline-Online Approximate Dynamic Programming for Dynamic Vehicle Routing with Stochastic Requests

with Marlin W. Ulmer, Dirk C. Mattfeld, & Marco Hennig. Transportation Science, 2019:53(1), 185-202.

Featured in the 2021 special issue "A Deeper Look at Transportation Science by Topic Area"

On-demand packages and food delivered to our doorstep at a moment's notice have become staples of modern living. The paper develops reinforcement learning techniques that anticipate demand and develop routes across space and time.

Read the Paper
Chalkboard illustration of a decision tree

A Rollout Algorithm Framework for Heuristic Solutions to Finite-Horizon Stochastic Dynamic Programs

with Barrett W. Thomas & Jeffrey W. Ohlmann. European Journal of Operational Research, 2017:258(1), 216-229.

How to make decisions in sequence and in the face of uncertainty with performance guarantees. The paper unifies and generalizes rollout algorithms.

Read the Paper
SAP office building

Partnering with Practice: How Partnerships can be Developed, Shared, and Managed

with Don Hardaway, Roel Harryvan, & Frank Wang. Communications of the Association for Information Systems, 2016:38(6), 145-156.

The holy grail of business education is integration of academics and industry. The paper describes our experience working closely with a major consulting firm in the classroom.

Read the Paper
Semi-truck on the highway

Restocking-Based Rollout Policies for the Vehicle Routing Problem with Stochastic Demand and Duration Limits

with Barrett W. Thomas & Jeffrey W. Ohlmann. Transportation Science, 2016:50(2), 591-607.

Dynamically routing vehicles in the face of uncertain demand is a fundamental challenge in modern logistics. The paper demonstrates the value of preemptive capacity replenishment within a lookahead mechanism.

Read the Paper
Courier on a motorcycle

A Rollout Algorithm for Vehicle Routing with Stochastic Customer Requests

with Marlin W. Ulmer, Dirk C. Mattfeld, & Marco Henig. Logistics Management, 2016, 217-227.

Couriers and parcel delivery firms must manage logistics without knowing where and when demand will occur. The paper proposes a method to plan routes now with explicit consideration of future demand.

Read the Paper
Multi-compartment semi-truck

A Priori Policy Evaluation and Cyclic-Order-Based Simulated Annealing for the Multi-Compartment Vehicle Routing Problem with Stochastic Demands

European Journal of Operational Research, 2015:241(2), 361-369.

What do waste collection, fuel distribution, and grocery transport have in common? They all utilize multi-compartment vehicles. The paper develops a method to manage the logistics of these problems in the face of uncertain demand.

Read the Paper
A sign displaying: vote here

Election Day Routing of Rapid Response Attorneys

Information Systems and Operational Resesarch, 2014:52(1), 1-9.

Even without politics, elections can be messy. The paper recounts methods for statewide management of volunteer resources during the 2012 US presidential election.

Read the Paper
Semi-trucks on a highway

Rollout Policies for Dynamic Solutions to the Multi-Vehicle Routing Problem with Stochastic Demand and Duration Limits

with Jeffrey W. Ohlmann & Barret W. Thomas. Operations Research, 2013:61(1), 138-154.

Uncertain demand is the bane of the logistics planner, but it doesn't have to be. The paper develops methods to dynamically adjust route plans in response to realized demand. It uses well understood notions of static routes to make decisions on the fly.

Read the Paper
Semi-truck on a highway

Cyclic-Order Neighborhoods with Application to the Vehicle Routing Problem with Stochastic Demand

with Jeffrey W. Ohlmann & Barret W. Thomas. European Journal of Operational Research, 2012:217(2), 312-323.

Vehicle routing problems come in many flavors, but often share a similar underlying structure. The paper exploits this structure to develop a solution methodology applicable to a broad range of problems.

Read the Paper
Woman in a wheelchair in the hallway of a nursing home

Nursing Home Care Quality: Insights from a Bayesian Network Approach

with Wooseung Jang & Marilyn Rantz. The Gerontologist, 2008:48(3), 338-348.

Part 1 of 2. The first paper in the pair discusses practical takeaways from using Bayesian networks to predict and manage quality of care.

Read the Paper
Graphical depiction of a Bayesian network

Assessing Nursing Home Care Quality Through Bayesian Networks

with Wooseung Jang. Health Care Management Science, 2008:11(4), 382-392.

Part 2 of 2. The second paper in the pair outlines the more technical aspects of using Bayesian networks to predict and manage quality of care.

Read the Paper

Software

Taxis on a crowded street

pyhailing: An OpenAI Gym Environment for the Control of a Ridehailing Fleet

Nicholas D. Kullman. Python Package Index.

Use 2018 data from Manhattan as the stage for developing AI ride-sharing strategies. The software accompanies the paper titled "Dynamic Ridehailing with Electric Vehicles."

Get the Code
Map to a charging station

frvcpy: An Open-Source Solver for the FRVCP

with Nicholas D. Kullman, Aurelien Froger, & Jorge E. Mendoza. Python Package Index.

The fixed route vehicle charging problem underlies many problems in the management of electric vehicles. The software accompanies the paper titled "Electric Vehicle Routing with Public Charging Stations."

Get the Code
Graphs of the pressure parameter in the compressed annealing algorithm

Djinni: A Templatized C++ Framework with Python Bindings for Heuristic Search

with Robert Hansen, Tristan Thiede, Jeffrey W. Ohlmann, & Barrett W. Thomas. Computational Infrastructure for Operations Research (COIN-OR).

The software implements compressed annealing and simulated annealing, both metaheuristics for combinatorial optimization problems. If you have a basic heuristic for your problem, Djinni can make it better.

Get the Code