Dynamic Orienteering on a Network of Queues

作     者：Zhang, Shu Ohlmann, Jeffrey W. Thomas, Barrett W. 

作者机构：Chongqing Univ Sch Econ & Business Adm Chongqing 400044 Peoples R China Univ Iowa Dept Management Sci Tippie Coll Business Iowa City IA 52242 USA 

出 版 物：《TRANSPORTATION SCIENCE》 (运输科学)

年 卷 期：2018年第52卷第3期

页      面：691-706页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0823[工学-交通运输工程] 

基　　金：National Natural Science Foundation of China Humanity and Social Science Foundation of the Chinese Ministry of Education [16YJC630169] Fundamental Research Funds for the Central Universities [106112017CDJXY020018] 

主　　题：stochastic orienteering dynamic routing time windows queueing approximate dynamic programming rollout algorithms 

摘      要：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.