BAYESIAN RANKING AND SELECTION MODEL FOR THE SECOND-BEST NETWORK PRICING PROBLEM

We adopt a Bayesian ranking and selection (R&S) model to solve the Second-best Network Pricing Problem (SNPP) in transportation. The objective of SNPP is to find an optimal subset of links and toll levels so as to minimize the total travel time on the network. It is an NP-hard problem with a large number of candidate solutions. We consider every combination of tollable link(s) and toll levels as an "alternative", and the problem's objective function value is regarded as a "reward", with uncertainties modeled by normal perturbations to the travel demand. We use a linear belief based Knowledge Gradient sampling policy to maximize the expected reward, with Monte Carlo sampling of the hyperparameters used to reduce the choice set size. Simulation experiments for a benchmark network show the effectiveness of the proposed method and its superior performance to a Sample Average Approximation based Genetic Algorithm.