Three Essays On Fully Sequential Ranking And Selection Problems

Ranking and selection(R&S)is an effective simulation algorithm to solve stochastic optimization problems.Especially in some real-life cases,there may be many difficulties in formulating a theoretical model or obtaining an analytical solution.However,it is often possible to obtain an optimal solution using a R&S algorithm.The R&S problem can be addressed by following two general approaches: the frequentist approach and the Bayesian approach.Although both approaches aim at finding the optimal solution,the goals they pursued are not the same.The goal of the frequentist approach is to choose the optimal solution with the required probability of correct selection(PCS).However,the goal of the Bayesian approach is to maximize the posterior PCS by allocating the finite computation budget.In this sense,many Bayesian procedures may not provide a guaranteed PCS.In many situations,frequentist procedures tend to be more conservative,which means that it requires more samples than Bayesian procedures to achieve the same required PCS level.Therefore,improving the efficiency of the frequentist approach has always been an important research question.We propose two methods to improve the efficiency of frequentist procedures in Chapter 2 and Chapter 3,respectively.In addition,using R&S algorithms to solve practical problems is also one of the research questions worthy of further exploration.In Chapter 4,we apply the R&S algorithm to obtain the optimal consumer incentive plan in a free-float bikesharing system(FFBS),which can assist operators to improve revenue and consumer service level of FFBS.In Chapter 2,we propose an algorithm to choose a proper initial sample size(ISS)in frequentist approach to improve the efficiency.In certain fully sequential R&S procedures,such as Rinott's procedure(Rinott(1978))and the KN procedure(Kim and Nelson(2001)),because the variance of each system is unknown,it is inevitable to select some samples in the initial stage,which are called initial samples,to estimating sample variance.We find that because the sample variance estimated by the initial samples will not be updated during the running of the algorithm,the selection of the ISS has great impact on the total sample size(TSS)of the algorithm.If the ISS is too small,it will increase the inaccuracy of variance estimation.As a result,the TSS will be increased to ensure that the probability of selecting the optimal solution meets the requirement.If the ISS is too large,it may cause the ISS to be larger than the TSS,and also result in a waste of samples.In order to select the appropriate ISS,we first establish a functional relationship between the ISS and TSS.By solving a TSS minimization problem,we then propose an algorithm to select the ISS.To illustrate the efficiency of our algorithm,we combine it with the KN procedure and propose KN-ISS procedure.Through comprehensive numerical experiments,compared with the KN procedure,KN-ISS procedure can improve the efficiency significantly,that is,the TSS can be reduced by 30%-50%.In addition,the KN-ISS procedure can be applied to a variety of different mean and variance parameter settings and still achieve the desired PCS.After considering the problem of ISS,a natural extension is to consider how to allocate samples in the fully sequential procedures.In Chapter 3,we propose an adaptive sampling rule,which not only guarantees the PCS,but also effectively improves the efficiency of frequentist algorithms.In the frequentist approach,because the estimated sample variance of each system will not be updated during the running of the algorithm,most frequentist algorithms use a balanced sampling rule,which means that the number of samples allocated by different systems is the same.This sample allocation strategy also facilitates the demonstration of the statistical validity of the algorithm.In contrast,many Bayesian procedures are designed from an on-line point of view,which can sequentially update the mean and variance information to adaptively determine which alternative should be simulated next.Then,it is reasonable to design an unequal sample allocation rule.In the allocation strategy of Bayesian approach,more samples are often allocated to systems that are more likely to be the optimal solution,so as to speed up the selection and improve the efficiency of the algorithm.Jennison et al.(1980)and Jennison et al.(1982)argue that the sample allocation idea in the Bayesian approach can also be applied to the frequentist approach and propose an unbalanced sampling rule for common variance scenario.Hong(2010)extends their results to uncommon variance scenario and propose a variance-dependent sampling rule which is obtained by solving a TSS minimization problem of any two systems.Motivated by these results,we propose a new adaptive sampling rule in the frequentist approach and prove the asymptotically statistical validity of the proposed procedure.By solving a TSS minimization problem of all systems,we construct a parameter index based on the sample mean,sample variance and sample size of each system.In the process of running the procedure,the parameter index can be updated continuously.Then the samples can be allocated according to the numeric value of the parameter index.Through comprehensive numerical experiments,this sampling rule can effectively improve the efficiency of the procedure and deliver the required PCS.It can reduce the TSS by 40%-60% compared with the KN procedure and UVP procedure(Hong(2010)).Given the TSS,compared with OCBA procedure(Chen et al.(2000)),our procedure improves the PCS by 10%-20%.In Chapter 4,we implement the fully sequential R&S procedures on a real-life problem,which is to choose the best customer incentive plan to help the operator to rebalance the bicycles in a FFBS.FFBS has increased in popularity as a sustainable travel mode in recent years,especially in the urban areas of China.Despite the convenience such systems offer to customers,it is not easy to maintain an effective balance in the distribution of bikes.On the one hand,the unbalanced bike-sharing system will block traffic and occupy public resources in some hot spots.On the other hand,it will lead to some points lack of vehicles,which will reduce the level of consumer service and the efficiency of FFBS.In Chapter 4,we consider the dynamic rebalancing problem for FFBS systems,whereby user-based tactics are employed by incentivizing users to perform repositioning activities.In studying this problem,we find that FFBS operator lacks data,such as consumer types,destinations,riding times,arrival rates,especially when entering a new market.From a theoretical perspective,methodologies such as robust optimization(RO)can be deployed to resolve the limited information optimization problem.Nevertheless,approaches in RO such as the max-min objective and minimax regret objective may not be suitable given the various stochastic components regarding the demand patterns in our problem,which may bring more challenges in deriving concise analytical results.Instead of using model-driven methods to obtain analytical results,we present a procedure based on a R&S method,a well-adopted approach in simulation optimization,to choose the optimal incentive plan.This method can also be applied to a limited information scenario where a firm enters a new market.We describe the system dynamics in detail,and formulate a profit maximization problem with a constraint on customer service level.Through numerical studies,we first establish that our procedure can select the optimal incentive plan in a wide range of scenarios.Second,under our incentive plan,the profit and service level can be improved significantly compared with the scenario without incentive provision.Third,in most cases,our procedure can achieve the optimal solution with a reasonable sample size.