Randomized Policy Optimization for Optimal Stopping

Optimal stopping is the problem of determining when to stop a stochastic system in order to maximize reward, which is of practical importance in domains such as finance, operations management and healthcare. Existing methods for high-dimensional optimal stopping that are popular in practice produce deterministic linear policies — policies that deterministically stop based on the … Read more

Approximate Dynamic Programming for Crowd-shipping with In-store Customers

Crowd-shipping has gained significant attention as a last-mile delivery option over the recent years. In this study, we propose a variant of dynamic crowd-shipping model with in-store customers as crowd-shippers to deliver online orders within few hours. We formulate the problem as a Markov decision process and develop an approximate dynamic programming (ADP) policy using … Read more

Dynamic Repositioning in Free-Floating Bike Sharing Systems Using Approximate Dynamic Programming

In bike sharing systems, the spatiotemporal imbalance of bike flows leads to shortages of bikes in some areas and overages in some others, depending on the time of the day, resulting in user dissatisfaction. Repositioning needs to be performed timely to deal with the spatiotemporal imbalance and to meet customer demand in time. In this … Read more

Random-Sampling Multipath Hypothesis Propagation for Cost Approximation in Long-Horizon Optimal Control

In this paper, we develop a Monte-Carlo based heuristic approach to approximate the objective function in long horizon optimal control problems. In this approach, we evolve the system state over multiple trajectories into the future while sampling the noise disturbances at each time-step, and find the weighted average of the costs along all the trajectories. … Read more

Dynamic optimization for airline maintenance operations

The occurrence of unexpected aircraft maintenance tasks can produce expensive changes in an airline’s operation. When it comes to critical tasks, it might even cancel programmed flights. Despite of it, the challenge of scheduling aircraft maintenance operations under uncertainty has received limited attention in the scientific literature. We study a dynamic airline maintenance scheduling problem, … Read more

A Dynamic Mobile Production Capacity and Inventory Control Problem

We analyze a problem of dynamic logistics planning given uncertain demands for a multi-location production-inventory system with transportable modular production capacity. In such systems, production modules provide capacity, and can be moved from one location to another to produce stock and satisfy demand. We formulate a dynamic programming model for a planning problem that considers … Read more

Revisiting Approximate Linear Programming Using a Saddle Point Approach

Approximate linear programs (ALPs) are well-known models for computing value function approximations (VFAs) of intractable Markov decision processes (MDPs) arising in applications. VFAs from ALPs have desirable theoretical properties, define an operating policy, and provide a lower bound on the optimal policy cost, which can be used to assess the suboptimality of heuristic policies. However, … Read more

From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming

We consider linear programming (LP) problems in infinite dimensional spaces that are in general computationally intractable. Under suitable assumptions, we develop an approximation bridge from the infinite-dimensional LP to tractable finite convex programs in which the performance of the approximation is quantified explicitly. To this end, we adopt the recent developments in two areas of … Read more

The Dynamic Dispatch Waves Problem for Same-Day Delivery

We study same-day delivery systems by formulating the Dynamic Dispatch Waves Problem (DDWP), which models a distribution center where geographically located delivery orders realize dynamically throughout the day. At each decision epoch (wave), the system’s operator chooses whether or not to dispatch a vehicle route loaded with orders ready for service, to minimize vehicle travel … Read more

Approximate Dynamic Programming for a Class of Long-Horizon Maritime Inventory Routing Problems

We study a deterministic maritime inventory routing problem with a long planning horizon. For instances with many ports and many vessels, mixed-integer linear programming (MIP) solvers often require hours to produce good solutions even when the planning horizon is 90 or 120 periods. Building on the recent successes of approximate dynamic programming (ADP) for road-based … Read more