Knowledge that Transforms

In “Asymmetric Multidepot Vehicle Routing Problems: Valid Inequalities and a Branch-and-Cut Algorithm,” Uit het Broek, Schrotenboer, Jargalsaikhan, Roodbergen, and Coelho present a generic branch-and-cut framework to solve routing problems with multiple depots on directed graphs. They present new valid inequalities that eliminate subtours, enforce tours to be linked to the same depot, and enforce bounds on the number of customers in a vehicle tour. This is embedded in a branch-and-cut scheme that also contains generalized and adapted versions of valid inequalities that are well known for related routing problems. The authors show that the new inequalities tighten root node relaxations considerably. In combination with a simple but effective upper-bound procedure, only requiring a MIP solver and a smart reduction of the problem size, the authors show that the overall framework solves instances of considerably larger size to optimality than have been reported in the literature.

On-time delivery is of utmost importance in today’s urban logistics. However, travel times are uncertain and classical deterministic routing solutions often fail to ensure timely delivery. In this paper, a robust solution that exploits travel times data to determine the best routes for maximal timely delivery is proposed. A new decision criterion is introduced, the service fulfillment risk index (sri), which accounts for both the late arrival probability and its magnitude. Together with Wasserstein distance–based ambiguity in travel times, sri can be evaluated efficiently in closed form. In addition, an exact branch-and-cut approach and a meta-heuristic algorithm are developed to minimize sri with a given travel cost. Simulation studies demonstrate that handling uncertainty improves service punctuality, and that incorporating ambiguity prevents overfitting. Most importantly, sri outperforms the canonical decision criteria of lateness probability and expected lateness duration.

In large-scale service systems, it is a common practice to organize customers with similar service requirements into a single queue served by a group of servers. This pooled queue structure is deemed highly efficient because the servers’ idleness will be minimized. In “To Pool or Not to Pool: Queueing Design for Large-Scale Service Systems,” Cao, He, Huang, and Liu demonstrate that the dedicated queue structure, under which each server has her own queue, could be more advantageous for improving the system’s service level. Moreover, the servers’ additional idleness induced by the dedicated queue structure will be negligible when the system scale is large. By solving a staffing problem, this study also intends to help service system designers answer the following question: To achieve a specified service-level objective in a more efficient manner, should the servers have a common queue or separate queues?

How to optimize posted price mechanisms? The sequential posted-price (SPP) mechanism is one of the widely used selling mechanisms in practice. In this mechanism, the seller presents each buyer with a price sequentially and the buyer can either accept or reject the mechanism's offer. Despite the widespread use of the SPP mechanism, the problem of optimizing prices in this mechanism has not been fully addressed. In a paper entitled, “Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms,” H. Beyhaghi, N. Golrezaei, R. Paes Leme, M. Pal, and B. Sivan construct SPP mechanisms by considering the best of two simple pricing rules: one that imitates the optimal mechanism and the other that posts a uniform price (same price for every buyer). Their simple pricing rules can be easily generalized to the setting with multiple units and yield the first improvement over long-established approximation factors.

Mass transit remains the most efficient way to service a densely packed commuter population. However, reliability issues and increasing competition in the transportation space have led to declining ridership across the United States, and transit agencies must also operate under tight budget constraints. Recent attempts at using bus network redesign to improve ridership have attracted attention from various transit authorities. However, the analysis seems to rely on ad hoc methods, for example, considering each line in isolation and using manual incremental adjustments with backtracking. We provide a holistic approach to designing a transit network using column generation. Our approach scales to hundreds of stops, and we demonstrate its usefulness on a case study with real data from Boston.

It has been realized for a long time that network effects play an important role in how market participants compete with each other. Arguably, companies like Facebook and Google are able to gain immense market power by leveraging the network effects of their consumers, despite potential competitors. This paper investigates how the dynamics play out in duopoly competition. We find that when the network effects per unit of consumption are weak, the competitors can co-exist and gain even market shares. As network effects become stronger, it is unstable, and even impossible, for the firms to coexist, and one firm emerges victorious, taking the majority of the market. The study provides a theoretical analysis for commonly observed market phenomena. It may also have implications for antitrust legislation: Special policies need to be created to maintain a competitive market structure for products and services with strong network effects.

An OR look into zonal integration of electricity markets

When dealing with dynamic optimization problems, time consistency is a desirable property as it allows one to solve the problem efficiently through a backward recursion. The mean-risk problem is known to be time inconsistent when considered in its scalarized form. However, when left in its original bi-objective form, it turns out to satisfy a more general time consistency property that seems better suited to a vector optimization problem. In “Time Consistency of the Mean-Risk Problem,” Kováĉova and Rudloff introduce a set-valued version of the famous Bellman principle and show that the bi-objective mean-risk problem does satisfy it. Then, the upper image, a set that contains the efficient frontier on its boundary, recurses backward in time. Kováĉova and Rudloff present conditions under which this recursion can be exploited directly to compute a solution in the spirit of dynamic programming. This opens the door for a new branch in mathematics: dynamic multivariate programming.

Solving Inventory Models with Service-Level Constraints by Using a Deterministic Approximation

Financial institutions make decisions according to a model of uncertainty. At the same time, regulators often evaluate the risk exposure of these institutions using a model of uncertainty, which is often different from the one used by the institutions. How can one incorporate both views into a single framework? This paper provides such a framework. It quantifies the impact of the misspecification inherent to the financial institution data-driven model via the introduction of an adversarial player. The adversary replaces the institution's generated scenarios by the regulator's scenarios subject to a budget constraint and a cost that measures the distance between the two sets of scenarios (using what in statistics is known as the Wasserstein distance). This paper also harnesses statistical theory to make inference about the size of the estimated error when the sample sizes (both of the institution and the regulator) are large. The framework is explained more broadly in the context of distributionally robust optimization (a class of perfect information games, in which decisions are taken against an adversary that perturbs a baseline distribution).