Bayesian ranking and selection model for the Second-best Network Pricing Problem

Zhen Tan; H. Oliver Gao

doi:10.1109/WSC.2016.7822287

Bayesian ranking and selection model for the Second-best Network Pricing Problem

Zhen Tan
, H. Oliver Gao

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

4 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	2016 Winter Simulation Conference
Subtitle of host publication	Simulating Complex Service Systems, WSC 2016
Editors	Theresa M. Roeder, Peter I. Frazier, Robert Szechtman, Enlu Zhou
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2487-2498
Number of pages	12
ISBN (Electronic)	9781509044863
DOIs	https://doi.org/10.1109/WSC.2016.7822287
Publication status	Published - 2 Jul 2016
Externally published	Yes
Event	2016 Winter Simulation Conference, WSC 2016 - Arlington, United States Duration: 11 Dec 2016 → 14 Dec 2016

Publication series

Name	Proceedings - Winter Simulation Conference
Volume	0
ISSN (Print)	0891-7736

Conference

Conference	2016 Winter Simulation Conference, WSC 2016
Country/Territory	United States
City	Arlington
Period	11/12/16 → 14/12/16

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 11 Sustainable Cities and Communities

ASJC Scopus subject areas

Software
Modelling and Simulation
Computer Science Applications

Access to Document

10.1109/WSC.2016.7822287

Cite this

Tan, Z., & Gao, H. O. (2016). Bayesian ranking and selection model for the Second-best Network Pricing Problem. In T. M. Roeder, P. I. Frazier, R. Szechtman, & E. Zhou (Eds.), 2016 Winter Simulation Conference: Simulating Complex Service Systems, WSC 2016 (pp. 2487-2498). Article 7822287 (Proceedings - Winter Simulation Conference; Vol. 0). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/WSC.2016.7822287

Tan, Zhen ; Gao, H. Oliver. / Bayesian ranking and selection model for the Second-best Network Pricing Problem. 2016 Winter Simulation Conference: Simulating Complex Service Systems, WSC 2016. editor / Theresa M. Roeder ; Peter I. Frazier ; Robert Szechtman ; Enlu Zhou. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 2487-2498 (Proceedings - Winter Simulation Conference).

@inproceedings{dee3ce1731194c6b9d4155920fff8de7,

title = "Bayesian ranking and selection model for the Second-best Network Pricing Problem",

abstract = "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.",

author = "Zhen Tan and Gao, \{H. Oliver\}",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 2016 Winter Simulation Conference, WSC 2016 ; Conference date: 11-12-2016 Through 14-12-2016",

year = "2016",

month = jul,

day = "2",

doi = "10.1109/WSC.2016.7822287",

language = "English",

series = "Proceedings - Winter Simulation Conference",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2487--2498",

editor = "Roeder, \{Theresa M.\} and Frazier, \{Peter I.\} and Robert Szechtman and Enlu Zhou",

booktitle = "2016 Winter Simulation Conference",

address = "United States",

}

Tan, Z & Gao, HO 2016, Bayesian ranking and selection model for the Second-best Network Pricing Problem. in TM Roeder, PI Frazier, R Szechtman & E Zhou (eds), 2016 Winter Simulation Conference: Simulating Complex Service Systems, WSC 2016., 7822287, Proceedings - Winter Simulation Conference, vol. 0, Institute of Electrical and Electronics Engineers Inc., pp. 2487-2498, 2016 Winter Simulation Conference, WSC 2016, Arlington, United States, 11/12/16. https://doi.org/10.1109/WSC.2016.7822287

Bayesian ranking and selection model for the Second-best Network Pricing Problem. / Tan, Zhen; Gao, H. Oliver.
2016 Winter Simulation Conference: Simulating Complex Service Systems, WSC 2016. ed. / Theresa M. Roeder; Peter I. Frazier; Robert Szechtman; Enlu Zhou. Institute of Electrical and Electronics Engineers Inc., 2016. p. 2487-2498 7822287 (Proceedings - Winter Simulation Conference; Vol. 0).

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Bayesian ranking and selection model for the Second-best Network Pricing Problem

AU - Tan, Zhen

AU - Gao, H. Oliver

PY - 2016/7/2

Y1 - 2016/7/2

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85014179918

U2 - 10.1109/WSC.2016.7822287

DO - 10.1109/WSC.2016.7822287

M3 - Conference contribution

AN - SCOPUS:85014179918

T3 - Proceedings - Winter Simulation Conference

SP - 2487

EP - 2498

BT - 2016 Winter Simulation Conference

A2 - Roeder, Theresa M.

A2 - Frazier, Peter I.

A2 - Szechtman, Robert

A2 - Zhou, Enlu

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 Winter Simulation Conference, WSC 2016

Y2 - 11 December 2016 through 14 December 2016

ER -

Tan Z, Gao HO. Bayesian ranking and selection model for the Second-best Network Pricing Problem. In Roeder TM, Frazier PI, Szechtman R, Zhou E, editors, 2016 Winter Simulation Conference: Simulating Complex Service Systems, WSC 2016. Institute of Electrical and Electronics Engineers Inc. 2016. p. 2487-2498. 7822287. (Proceedings - Winter Simulation Conference). doi: 10.1109/WSC.2016.7822287

Bayesian ranking and selection model for the Second-best Network Pricing Problem

Abstract

Publication series

Conference

UN SDGs

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this