Dynamic Orienteering on a Network of Queues

Shu Zhang (), Jeffrey W. Ohlmann () and Barrett W. Thomas ()
Additional contact information
Shu Zhang: School of Economics and Business Administration, Chongqing University, 400044 Chongqing, China
Jeffrey W. Ohlmann: Department of Management Sciences, Tippie College of Business, University of Iowa, Iowa City, Iowa 52242
Barrett W. Thomas: Department of Management Sciences, Tippie College of Business, University of Iowa, Iowa City, Iowa 52242

Transportation Science, 2018, vol. 52, issue 3, 691-706

Abstract: We introduce a stochastic orienteering problem on a network of queues in which the traveler must arrive and enter service at locations within the respective time windows to collect rewards, but the traveler may experience stochastic wait time at each location before service can begin. To maximize the expected rewards collected, the traveler must determine which locations to visit and how long to wait in queues at each location. We formally model the problem as a Markov decision process with the objective of maximizing the expected collected rewards. We investigate the existence of optimal control limits and examine conditions under which certain actions cannot be optimal. To solve the problem, we propose an approximate dynamic programming approach based on rollout algorithms. The method introduces a two-stage heuristic estimation that we refer to as compound rollout. In the first stage, the algorithm decides whether to stay at the current location or go to another location. If departing the current location, it chooses the next location in the second stage. We demonstrate the value of our modeling and solution approaches by comparing the dynamic policies to a-priori-route solutions with recourse actions.

Keywords: stochastic orienteering; dynamic routing; time windows; queueing; approximate dynamic programming; rollout algorithms (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/trsc.2017.0761 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:52:y:2018:i:3:p:691-706

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().