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 条

[21] Impact of travel time models on quality of real-time routing instructions [J].

Miller-Hooks, E ;

Yang, BY .

TRANSPORATION NETWORK MODELING 2003: PLANNNING AND ADMINISTRATION, 2003, (1857) :21-29

[22]

Miller-Hooks E, 2001, NETWORKS, V37, P35, DOI 10.1002/1097-0037(200101)37:1<35::AID-NET4>3.0.CO

[23]

2-G

[24] Variable neighborhood search [J].

Mladenovic, N ;

Hansen, P .

COMPUTERS & OPERATIONS RESEARCH, 1997, 24 (11) :1097-1100

[25]

Papapanagiotou V., 2013, Lecture Notes in Management Science, V5, P143

[26] Record breaking optimization results using the ruin and recreate principle [J].

Schrimpf, G ;

Schneider, J ;

Stamm-Wilbrandt, H ;

Dueck, G .

JOURNAL OF COMPUTATIONAL PHYSICS, 2000, 159 (02) :139-171

[27]

Sevkli Z, 2006, LECT NOTES COMPUT SC, V4263, P134

[28] Algorithms for a stochastic selective travelling salesperson problem [J].

Tang, H ;

Miller-Hooks, E .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2005, 56 (04) :439-452

[29] An integer L-shaped algorithm for time-constrained traveling salesman problem with stochastic travel and service times [J].

Teng, SY ;

Ong, HL ;

Huang, HC .

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2004, 21 (02) :241-257

[30] Anticipatory route selection [J].

Thomas, BW ;

White, CC .

TRANSPORTATION SCIENCE, 2004, 38 (04) :473-487

← 1 2 3 4 →