Applications – OR and Management Sciences – Page 69

Risk Aversion to Parameter Uncertainty in Markov Decision Processes with an Application to Slow-Onset Disaster Relief

Published: 2019/02/23, Updated: 2019/06/21

Integer Programming, Stochastic Programming, Supply Chain Management chance constraints, disaster relief, humanitarian supply chains, markov decision processes, parameter uncertainty, value-at-risk

In classical Markov Decision Processes (MDPs), action costs and transition probabilities are assumed to be known, although an accurate estimation of these parameters is often not possible in practice. This study addresses MDPs under cost and transition probability uncertainty and aims to provide a mathematical framework to obtain policies minimizing the risk of high long-term … Read more

Dynamic Discretization Discovery Algorithms for Time-Dependent Shortest Path Problems

Published: 2019/02/21, Updated: 2022/08/06

Network Optimization, Transportation dynamic discretization discovery, fastest paths, minimum duration paths, time dependent travel times, time discretization, time-expanded networks

Finding a shortest path in a network is an iconic optimization problem. We focus on settings in which the travel time on an arc in the network depends on the time at which traversal of the arc begins. In such settings, reaching the sink as early as possible is not the only objective of interest. … Read more

Optimizing the Recovery of Disrupted Multi-Echelon Assembly Supply Chain Networks

Published: 2019/02/21

Applications - OR and Management Sciences multi-echelon assembly supply chain, scheduling, supply chain disruption

We consider optimization problems related to the scheduling of multi-echelon assembly supply chain (MEASC) networks that have applications in the recovery from large-scale disruptive events. Each manufacturer within this network assembles a component from a series of sub-components received from other manufacturers. We develop scheduling decision rules that are applied locally at each manufacturer and … Read more

Time-Dependent Shortest Path Problems with Penalties and Limits on Waiting

Published: 2019/02/21, Updated: 2020/04/11

Network Optimization, Transportation complexity, shortest path, time-dependent travel time, time-expanded network

Waiting at the right location at the right time can be critically important in certain variants of time-dependent shortest path problems. We investigate the computational complexity of time-dependent shortest path problems in which there is either a penalty on waiting or a limit on the total time spent waiting at a given subset of the … Read more

A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints

Published: 2019/02/19

Gonzalo Lera-Romero

Juan José Miranda-Bront

Branch and Cut Algorithms, Transportation

In this paper we study the time-dependent profitable tour problem with resource con-straints (TDPTPRC), a generalization of the profitable tour problem (PTP) which includes variable travel times to account for road congestion. In this problem, the set of customers to be served is not given and must be determined based on the profit collected when … Read more

Algorithms for the circle packing problem based on mixed-integer DC programming

Published: 2019/02/14

Yoshiko Ikebe

Satoru Masuda

Takayuki Okuno

(Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences circle packing, mixed integer dc programming, nonlinear optimization

Circle packing problems are a class of packing problems which attempt to pack a given set of circles into a container with no overlap. In this paper, we focus on the circle packing problem proposed by L{\’o}pez et.al. The problem is to pack circles of unequal size into a fixed size circular container, so as … Read more

Improved Flow-based Formulations for the Skiving Stock Problem

Published: 2019/02/12

(Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Combinatorial Optimization arcflow model, cutting and packing, ilp, skiving stock problem

Thanks to the rapidly advancing development of (commercial) MILP software and hardware components, pseudo-polynomial formulations have been established as a powerful tool for solving cutting and packing problems in recent years. In this paper, we focus on the one-dimensional skiving stock problem (SSP), where a given inventory of small items has to be recomposed to … Read more

Chance-Constrained Bin Packing Problem with an Application to Operating Room Planning

Published: 2019/02/01, Updated: 2020/06/29

Jinlin Li

Sanjay Mehrotra

Shanshan Wang

Applications - OR and Management Sciences bilinear integer program, bin packing, branch-and-cut, chance-constrained stochastic programming, operating room planning, valid inequalities

We study the chance-constrained bin packing problem, with an application to hospital operating room planning. The bin packing problem allocates items of random size that follow a discrete distribution to a set of bins with limited capacity, while minimizing the total cost. The bin capacity constraints are satisfied with a given probability. We investigate a … Read more

Scheduling jobs with a V-shaped time-dependent processing time

Published: 2019/02/01, Updated: 2020/09/09

Helmut Sedding

Approximation Algorithms, Scheduling

In the field of time-dependent scheduling, a job’s processing time is specified by a function of its start time. While monotonic processing time functions are well-known in the literature, this paper introduces non-monotonic functions with a convex, piecewise-linear V-shape similar to the absolute value function. They are minimum at an ideal start time, which is … Read more