Applications – OR and Management Sciences

Multi-Product Newsvendor Problem with Customer-driven Demand Substitution: A Stochastic Integer Program Perspective

Categories Applications - OR and Management Sciences Tags , , , ,

This paper studies a multi-product newsvendor problem with customer-driven demand substitution, where each product, once run out of stock, can be proportionally substituted by the others. This problem has been widely studied in the literature, however, due to nonconvexity and intractability, only limited analytical properties have been reported and no efficient approaches have been proposed. … Read more

An Approximation Algorithm for Vehicle Routing with Compatibility Constraints

Categories Approximation Algorithms, Transportation Tags , ,

We study a multiple-vehicle routing problem with a minimum makespan objective and compatibility constraints. We provide an approximation algorithm and a nearly-matching hardness of approximation result. We also provide computational results on benchmark instances with diverse sizes showing that the proposed algorithm (i) has a good empirical approximation factor, (ii) runs in a short amount … Read more

Solving Time Dependent Traveling Salesman Problems with Time Windows

Categories Transportation Tags , , ,

We present a new solution approach for the Time Dependent Traveling Salesman Prob- lem with Time Windows. This problem considers a salesman who departs from his home, has to visit a number of cities within a pre-determined period of time, and then returns home. The problem allows for travel times that can depend on the … Read more

Provably High-Quality Solutions for the Meal Delivery Routing Problem

Categories Integer Programming, Optimization of Systems modeled by PDEs, Transportation Tags , , , , ,

Online restaurant aggregators with integrated meal delivery networks have become more common and more popular in the past few years. Meal delivery is arguably the ultimate challenge in last mile logistics: a typical order is expected to be delivered within an hour (much less if possible), and within minutes of the food becoming ready. We … Read more

A new approximation algorithm for unrelated parallel machine scheduling problem with release dates

Categories Approximation Algorithms, Scheduling, Semi-definite Programming

In this research, we consider the unrelated parallel machine scheduling problem with release dates. The goal of this scheduling problem is to find an optimal job assignment with minimal sum of weighted completion times. As it is demonstrated in the present paper, this problem is NP-hard in the strong sense. Albeit the computational complexity, which … Read more

Acyclic Mechanism Design for Freight Consolidation

Categories Game Theory, Supply Chain Management, Transportation Tags , ,

Freight consolidation is a logistics practice that improves the cost-effectiveness and efficiency of transportation operations, and also reduces energy consumption and carbon footprint. A “fair” shipping cost sharing scheme is indispensable to help establish and sustain the cooperation of a group of suppliers in freight consolidation. In this paper, we design a truthful acyclic mechanism … Read more

Monitoring With Limited Information

Categories Applications - OR and Management Sciences, Dynamic Programming, Robust Optimization Tags , , ,

We consider a system with an evolving state that can be stopped at any time by a decision maker (DM), yielding a state-dependent reward. The DM does not observe the state except for a limited number of monitoring times, which he must choose, in conjunction with a suitable stopping policy, to maximize his reward. Dealing … Read more

The Meal Delivery Routing Problem

Categories Applications - OR and Management Sciences Tags , , ,

We introduce the Meal Delivery Routing Problem (MDRP) to formalize and study an important emerging class of dynamic delivery operations. We develop optimization-based algorithms tailored to solve the courier assignment (dynamic vehicle routing) and capacity management (offline shift scheduling) problems encountered in meal delivery operations. Extensive computational experiments using instances with realistic size, geography, urgency … Read more

Layered graph approaches for combinatorial optimization problems

Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , , ,

Extending the concept of time-space networks, layered graphs associate information about one or multiple resource state values with nodes and arcs. While integer programming formulations based on them allow to model complex problems comparably easy, their large size makes them hard to solve for non-trivial instances. We detail and classify layered graph modeling techniques that … Read more