-
作者：Toriello, Alejandro; Haskell, William B.; Poremba, Michael
作者单位：University System of Georgia; Georgia Institute of Technology; University of Southern California
摘要：We propose a dynamic traveling salesman problem (TSP) with stochastic arc costs motivated by applications, such as dynamic vehicle routing, in which the cost of a decision is known only probabilistically beforehand but is revealed dynamically before the decision is executed. We formulate this as a dynamic program (DP) and compare it to static counterparts to demonstrate the advantage of the dynamic paradigm over an a priori approach. We then apply approximate linear programming (ALP) to overco...
-
作者：Levin, Yuri; Nediak, Mikhail; Bazhanov, Andrei
作者单位：Queens University - Canada
摘要：We consider a dynamic pricing problem for a monopolistic company selling a perishable product when customer demand is both uncertain and occurs in batches that must be fulfilled as a whole. The seller can price-discriminate between different sized batches by setting different unit prices. The problem is modeled as a stochastic optimal control problem to find an inventory-contingent dynamic pricing policy that maximizes the expected total revenues. We find the optimal pricing policy and prove s...
-
作者：Hu, Ming; Yang, Yi
作者单位：University of Toronto; Zhejiang University
摘要：We consider the classic continuous-review N stage serial inventory system with a homogeneous Poisson demand arrival process at the most downstream stage (Stage 1). Any shipment to each stage, regardless of its size, incurs a positive fixed setup cost and takes a positive constant lead time. The optimal policy for this system under the long-run average cost criterion is unknown. Finding a good worst-case performance guarantee remains an open problem. We tackle this problem by introducing a clas...
-
作者：Contreras, Ivan; Fernandez, Elena
作者单位：Concordia University - Canada; Universite de Montreal; Universitat Politecnica de Catalunya
摘要：This paper highlights how a general class of hub location problems can be modeled as the minimization of a real-valued supermodular set function. Well-known problems such as uncapacitated hub location, p-hub median, and hub arc location, among others, are shown to be particular cases of this class. Two integer programming formulations are introduced and compared. One uses path-based variables, frequently employed in hub location, whereas the other exploits properties of supermodular functions....
-
作者：Cote, Jean-Francois; Dell'Amico, Mauro; Iori, Manuel
作者单位：Laval University; Universita di Modena e Reggio Emilia
摘要：We study the strip packing problem, in which a set of two-dimensional rectangular items has to be packed in a rectangular strip of fixed width and infinite height, with the aim of minimizing the height used. The problem is important because it models a large number of real-world applications, including cutting operations where stocks of materials such as paper or wood come in large rolls and have to be cut with minimum waste, scheduling problems in which tasks require a contiguous subset of id...
-
作者：Chen, Wei; Dawande, Milind; Janakiraman, Ganesh
作者单位：University of Texas System; University of Texas Dallas
摘要：We study fixed-dimensional stochastic dynamic programs in a discrete setting over a finite horizon. Under the primary assumption that the cost-to-go functions are discrete L-\tau-convex, we propose a pseudo-polynomial time approximation scheme that solves this problem to within an arbitrary prespecified additive error of epsilon > 0. The proposed approximation algorithm is a generalization of the explicit-enumeration algorithm and offers us full control in the trade-off between accuracy and ru...
-
作者：Manou, Athanasia; Economou, Antonis; Karaesmen, Fikri
作者单位：National & Kapodistrian University of Athens; Koc University
摘要：We consider a transportation station, where customers arrive according to a Poisson process. A transportation facility visits the station according to a renewal process and serves at each visit a random number of customers according to its capacity. We assume that the arriving customers decide whether to join the station or balk, based on a natural reward-cost structure. We study the strategic behavior of the customers and determine their symmetric Nash equilibrium strategies under two levels ...
-
作者：Brown, David B.; Smith, James E.
作者单位：Duke University
摘要：We consider the information relaxation approach for calculating performance bounds for stochastic dynamic programs (DPs). This approach generates performance bounds by solving problems with relaxed nonanticipativity constraints and a penalty that punishes violations of these nonanticipativity constraints. In this paper, we study DPs that have a convex structure and consider gradient penalties that are based on first-order linear approximations of approximate value functions. When used with per...
-
作者：Arlotto, Alessandro; Gans, Noah; Steele, J. Michael
作者单位：Duke University; University of Pennsylvania; University of Pennsylvania
摘要：We identify a rich class of finite-horizon Markov decision problems (MDPs) for which the variance of the optimal total reward can be bounded by a simple linear function of its expected value. The class is characterized by three natural properties: reward nonnegativity and boundedness, existence of a do-nothing action, and optimal action monotonicity. These properties are commonly present and typically easy to check. Implications of the class properties and of the variance bound are illustrated...
-
作者：Cho, Soo-Haeng; Jang, Hoon; Lee, Taesik; Turner, John
作者单位：Carnegie Mellon University; Korea Advanced Institute of Science & Technology (KAIST); University of California System; University of California Irvine
摘要：This paper studies the problem of simultaneously locating trauma centers and helicopters. The standard approach to locating helicopters involves the use of helicopter busy fractions to model the random availability of helicopters. However, busy fractions cannot be estimated a priori in our problem because the demand for each helicopter cannot be determined until the trauma center locations are selected. To overcome this challenge, we endogenize the computation of busy fractions within an optim...
