Adaptive orienteering problem with stochastic travel times

被引：24

作者：

Dolinskaya, Irina ^{[1
]}

Shi, Zhenyu ^{[1
]}

Smilowitz, Karen ^{[1
]}

机构：

[1] Northwestern Univ, Dept Ind Engn & Management Sci, 2145 Sheridan Rd, Evanston, IL 60208 USA

来源：

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW | 2018年 / 109卷

基金：

美国国家科学基金会;

关键词：

Orienteering problem; Adaptive path; Dynamic programming; Variable neighborhood search; Search and rescue; VARIABLE NEIGHBORHOOD SEARCH; SALESMAN PROBLEM; SERVICE TIMES; PATH; OPTIMIZATION; CUSTOMERS;

D O I：

10.1016/j.tre.2017.10.013

中图分类号：

F [经济];

学科分类号：

02 ;

摘要：

In this paper, we evaluate the extent to which one can increase the likelihood of collecting greater reward in an orienteering problem with stochastic travel times by adapting paths between reward nodes as travel times are revealed. We evaluate whether this adaptivity impacts the choices of reward nodes to visit in a setting where the agent must commit to reward nodes before commencing operations. We explore the computational challenges of adding adaptive consideration in the selection of reward nodes to visit and examine the extent to which one can capture some of the benefits of adaptivity with a simpler model.

引用

页码：1 / 19

页数：19

共 34 条

[1]

[Anonymous], 2007, WILEY SERIES PROBABI

[2]

[Anonymous], 2010, HDB METAHEURISTICS

[3] AN ANALYSIS OF STOCHASTIC SHORTEST-PATH PROBLEMS [J].

BERTSEKAS, DP ;

TSITSIKLIS, JN .

MATHEMATICS OF OPERATIONS RESEARCH, 1991, 16 (03) :580-595

[4] A PRIORI OPTIMIZATION [J].

BERTSIMAS, DJ ;

JAILLET, P ;

ODONI, AR .

OPERATIONS RESEARCH, 1990, 38 (06) :1019-1033

[5]

Bomdorfer Ralf, 2010, 1008 ZIB, V7, P14195

[6] The orienteering problem with stochastic travel and service times [J].

Campbell, Ann M. ;

Gendreau, Michel ;

Thomas, Barrett W. .

ANNALS OF OPERATIONS RESEARCH, 2011, 186 (01) :61-81

[7] Approximating the stochastic knapsack problem:: The benefit of adaptivity [J].

Dean, BC ;

Goemans, MX ;

Vondrák, J .

45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2004, :208-217

[8]

Dijkstra EW., 1959, NUMER MATH, V1, P269, DOI 10.1007/BF01386390

[9] Finding the k shortest paths [J].

Eppstein, D .

SIAM JOURNAL ON COMPUTING, 1998, 28 (02) :652-673

[10] A two-stage approach to the orienteering problem with stochastic weights [J].

Evers, Lanah ;

Glorie, Kristiaan ;

van der Ster, Suzanne ;

Barros, Ana Isabel ;

Monsuur, Herman .

COMPUTERS & OPERATIONS RESEARCH, 2014, 43 :248-260

← 1 2 3 4 →