Adaptive orienteering problem with stochastic travel times

Irina Dolinskaya; Zhenyu (Edwin) Shi; Karen Smilowitz

doi:10.1016/j.tre.2017.10.013

Adaptive orienteering problem with stochastic travel times

Irina Dolinskaya^*, Zhenyu (Edwin) Shi, Karen Smilowitz

^*Corresponding author for this work

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Article › peer-review

17 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	1-19
Number of pages	19
Journal	Transportation Research Part E: Logistics and Transportation Review
Volume	109
DOIs	https://doi.org/10.1016/j.tre.2017.10.013
State	Published - Jan 2018

Keywords

Adaptive path
Dynamic programming
Orienteering problem
Search and rescue
Variable neighborhood search

ASJC Scopus subject areas

Business and International Management
Civil and Structural Engineering
Transportation

Access to Document

10.1016/j.tre.2017.10.013

Cite this

@article{cd2fd3e127af4ed78d3b870be09379a3,

title = "Adaptive orienteering problem with stochastic travel times",

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

keywords = "Adaptive path, Dynamic programming, Orienteering problem, Search and rescue, Variable neighborhood search",

author = "Irina Dolinskaya and Shi, {Zhenyu (Edwin)} and Karen Smilowitz",

note = "Funding Information: The authors would like to thank Fernando Tavares for his assistance with implementation and numerical results. The authors also thank the anonymous reviewers, whose thorough and constructive feedback helped to improve this paper. This work has been in part funded by the National Science Foundation , Grant CMMI-1265786 : “Advancing Dynamic Relief Response: Integration of New Data Streams and Routing Models. This material is based upon work supported by (while serving at) the National Science Foundation. Any opinion, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.” Publisher Copyright: {\textcopyright} 2017",

year = "2018",

month = jan,

doi = "10.1016/j.tre.2017.10.013",

language = "English (US)",

volume = "109",

pages = "1--19",

journal = "Transportation Research, Part E: Logistics and Transportation Review",

issn = "1366-5545",

publisher = "Elsevier Limited",

}

TY - JOUR

T1 - Adaptive orienteering problem with stochastic travel times

AU - Dolinskaya, Irina

AU - Shi, Zhenyu (Edwin)

AU - Smilowitz, Karen

N1 - Funding Information: The authors would like to thank Fernando Tavares for his assistance with implementation and numerical results. The authors also thank the anonymous reviewers, whose thorough and constructive feedback helped to improve this paper. This work has been in part funded by the National Science Foundation , Grant CMMI-1265786 : “Advancing Dynamic Relief Response: Integration of New Data Streams and Routing Models. This material is based upon work supported by (while serving at) the National Science Foundation. Any opinion, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.” Publisher Copyright: © 2017

PY - 2018/1

Y1 - 2018/1

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

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

KW - Adaptive path

KW - Dynamic programming

KW - Orienteering problem

KW - Search and rescue

KW - Variable neighborhood search

UR - http://www.scopus.com/inward/record.url?scp=85033678468&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85033678468&partnerID=8YFLogxK

U2 - 10.1016/j.tre.2017.10.013

DO - 10.1016/j.tre.2017.10.013

M3 - Article

AN - SCOPUS:85033678468

SN - 1366-5545

VL - 109

SP - 1

EP - 19

JO - Transportation Research, Part E: Logistics and Transportation Review

JF - Transportation Research, Part E: Logistics and Transportation Review

ER -

Adaptive orienteering problem with stochastic travel times

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this