Asia-Pacific Journal of Operational Research

AlphaGo and its successors AlphaGo Zero and AlphaZero made international headlines with their incredible successes in game playing, which have been touted as further evidence of the immense potential of artificial intelligence, and in particular, machine learning. AlphaGo defeated the reigning human world champion Go player Lee Sedol 4 games to 1, in March 2016 in Seoul, Korea, an achievement that surpassed previous computer game-playing program milestones by IBM’s Deep Blue in chess and by IBM’s Watson in the U.S. TV game show Jeopardy. AlphaGo then followed this up by defeating the world’s number one Go player Ke Jie 3-0 at the Future of Go Summit in Wuzhen, China in May 2017. Then, in December 2017, AlphaZero stunned the chess world by dominating the top computer chess program Stockfish (which has a far higher rating than any human) in a 100-game match by winning 28 games and losing none (72 draws) after training from scratch for just four hours! The deep neural networks of AlphaGo, AlphaZero, and all their incarnations are trained using a technique called Monte Carlo tree search (MCTS), whose roots can be traced back to an adaptive multistage sampling (AMS) simulation-based algorithm for Markov decision processes (MDPs) published in Operations Research back in 2005 [Chang, HS, MC Fu, J Hu and SI Marcus (2005). An adaptive sampling algorithm for solving Markov decision processes. Operations Research, 53, 126–139.] (and introduced even earlier in 2002). After reviewing the history and background of AlphaGo through AlphaZero, the origins of MCTS are traced back to simulation-based algorithms for MDPs, and its role in training the neural networks that essentially carry out the value/policy function approximation used in approximate dynamic programming, reinforcement learning, and neuro-dynamic programming is discussed, including some recently proposed enhancements building on statistical ranking & selection research in the operations research simulation community.

In this paper, we report our work on the flight recovery problem for China Eastern Airlines. Traditionally, the flight recovery problem is often modeled as an integer or mixed integer linear programming problem. However, such a model cannot take many complex constraints and uncertainties in real applications. Furthermore, we have found solutions obtained based on such a model difficult to implement in their existing operations, as in the case of CEA. Therefore, we propose a simulation-based approach, which works well with their existing operations. Our work demonstrates the potentials of simulation based methods in the study of the flight recovery problem, and possibly other similar problems.

Real-time decision making has acquired increasing interest as a means to efficiently operating complex systems. The main challenge in achieving real-time decision making is to understand how to develop next generation optimization procedures that can work efficiently using: (i) real data coming from a large complex dynamical system, (ii) simulation models available that reproduce the system dynamics. While this paper focuses on a different problem with respect to the literature in RL, the methods proposed in this paper can be used as a support in a sequential setting as well. The result of this work is the new Generalized Ordinal Learning Framework (GOLF) that utilizes simulated data interpreting them as low accuracy information to be intelligently collected offline and utilized online once the scenario is revealed to the user. GOLF supports real-time decision making on complex dynamical systems once a specific scenario is realized. We show preliminary results of the proposed techniques that motivate the authors in further pursuing the presented ideas.

In the past decades we have witnessed a paradigm-shift from scarcity of data to abundance of data. Big data and data analytics have fundamentally reshaped many areas including operations research. In this paper, we discuss how to integrate data with the model-based analysis in a controlled way. Specifically, we consider techniques to quantify input uncertainty and the decision making under input uncertainty. Numerical experiments demonstrate that different ways in decision making may lead to significantly different outcomes in a maintenance problem.

Customer self-pickup, offered as an option at most distribution centers, can provide flexible service times and save operational costs. Customers can either choose to self-pickup their demand or to have it delivered by a traditional way. At each customer point, the delivery demand is split, with the amount depending on the service and personal characteristics. In this situation, how to efficiently locate distribution centers and route deliveries becomes a vital problem for express companies that has not been studied in the literature. In this paper, for the first time, we propose a mathematical programming model for optimizing the location-routing problem with split demand (LRP-SD), together with a delivery ratio analysis model to predict self-pickup and delivery demand. To adapt the model to real-world cases, two heuristics as used in large-scale simulation-based optimization are devised and implemented. One is biogeography-based optimization (BBO) for solution speed, and the other is an adaptive large neighborhood search (ALNS) for solution quality. The two algorithms are compared using real data from a Shanghai-based express delivery company.

We propose a random search algorithm for seeking the global optimum of an objective function in a simulation setting. The algorithm can be viewed as an extension of the MARS algorithm proposed in Hu and Hu (2011) for deterministic optimization, which iteratively finds improved solutions by modifying and sampling from a parameterized probability distribution over the solution space. However, unlike MARS and many other algorithms in this class, which are often population-based, our method only requires a single candidate solution to be generated at each iteration. This is primarily achieved through an effective use of past sampling information by means of embedding multiple nested stochastic approximation type of recursions into the algorithm. We prove the global convergence of the algorithm under general conditions and discuss two special simulation noise cases of interest, in which we show that only one simulation replication run is needed for each sampled solution. A preliminary numerical study is also carried out to illustrate the algorithm.

Traditionally, simulation has been used as a tool of design to estimate, compare and optimize the performance of different system designs. It is rarely used in making real-time decisions due to the long computation delay of executing simulation models. However, with the fast growth of computing capability, we have observed more and more works on reusing simulation efforts for repeated experiments with the help of data analytics tools, and the target of these works is to solve real-time decision problems. In this paper, we distill the important features of these works and summarize a new simulation framework, called offline-simulation-online-application (OSOA) framework, which treats simulation as a data generator, applies state-of-the-art analytics tools to build predictive models, and then uses the predictive models for real-time applications. In this paper, we illustrate how to apply the OSOA framework on estimation, ranking and selection and simulation optimization, and provide a prospect of this new framework.