期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 312, 期 3, 页码 840-854出版社
ELSEVIER
DOI: 10.1016/j.ejor.2023.07.032
关键词
Integer programming; Logic-based Benders decomposition; Simulation; Resource allocation; Shift scheduling
This article proposes a new approach to integrating simulation into the optimization model, which solves stochastic resource allocation problems and derives strong Benders cuts. The approach is tested on nursing home shift scheduling and airport check-in counter allocation problems, achieving exact solutions within a reasonable amount of time.
Operations Research practitioners often want to model complicated functions that are difficult to encode in their underlying optimisation framework. A common approach is to solve an approximate model, and then use a simulation to evaluate the true objective value of one or more solutions. We propose a new approach to integrating simulation into the optimisation model itself. The idea is to run the simulation at each incumbent solution to a master problem. The simulation results are then used to guide the trajectory of the optimisation model itself using logic-based Benders cuts. We test the approach on a class of stochastic resource allocation problems with monotonic performance measures. We derive strong novel Benders cuts that are provably valid for all problems of the given form. We consider two concrete examples: a nursing home shift scheduling problem, and an airport check in counter allocation problem. While previous papers on these applications could only approximately solve realistic instances, we are able to solve them exactly within a reasonable amount of time. Moreover, while those papers account for the inherent variance of the problem by including estimates of the underlying random variables as model parameters, we are able to compute sample-average approximations to optimality with up to 100 scenarios.(c) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license ( http://creativecommons.org/licenses/by/4.0/ )
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据