Date of Degree
PhD (Doctor of Philosophy)
First Committee Member
Second Committee Member
de Matta, Renato
Third Committee Member
Motivated by the management of sales representatives who visit customers to develop customer relationships, we present a stochastic orienteering problem on a network of queues, in which a hard time window is associated with each customer and the representative may experience uncertain wait time resulting from a queueing process at the customer.
In general, given a list of potential customers and a time horizon consisting of several periods, the sales representative needs to decide which customers to visit in each period and how to visit customers within the period, with an objective to maximize the total reward collected by the end of the horizon. We start our study with a daily orienteering problem, which is a subproblem of the general problem. We focus on developing a priori and dynamic routing strategies for the salesperson to implement during a day.
In the a priori routing case, the salesperson visits customers in a pre-planned order, and we seek to construct a static sequence of customers that maximizes the expected value collected. We consider two types of recourse actions. One is to skip a customer specified by an a priori route if the representative will arrive late in the customer's time window. The other type is to leave a customer immediately after arriving if observing a sufficiently long queue (balking) or to leave after waiting in queue for a period of time without meeting with the customer (reneging). We propose customer-specific decision rules to facilitate the execution of recourse actions and derive an analytical formula to compute the expected sales from the a priori route. We tailor a variable neighborhood search (VNS) heuristic to find a priori routes.
In the dynamic routing case, the salesperson decides which customer to visit and how long to wait at each customer based on realized events. To seek dynamic routing policies, 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 customer or go to another customer. If departing the current customer, it chooses the customer to whom to go in the second stage. We demonstrate the value of our modeling and solution approaches by comparing the dynamic policies to a priori solutions with recourse actions.
Finally, we address the multi-period orienteering problem. We consider that each customer's likelihood of adopting the representative's product stochastically evolves over time and is not fully observed by the representative. The representative can only estimate the adoption likelihood by meeting with the customer and the estimation may not be accurate. We model the problem as a partially observed Markov decision process with an objective to maximize the expected sales at the end of the horizon. We propose a heuristic that decomposes the problem into an assignment problem to schedule customers for a period and a routing problem to decide how to visit the scheduled customers within the period.
We study a problem motivated by routing sales representatives to visit customers for developing customer relationships. We consider that each customer can only be accessed during a time window and the representative may experience uncertain wait time resulting from a queue of others at the customer. We first address a daily routing problem where the representative needs to decide which customers to visit and how to visit the customers within a day. We develop two type of solution approaches for the daily problem. One is an a priori routing strategy, in which the salesperson visits customers in a pre-planned order, and we seek to construct a sequence of customers that maximizes the expected value collected. The other is a dynamic routing strategy, in which the salesperson decides which customer to visit and whether to wait at a customer based on realized information, such as the arrival time and the observed queue length at the customer. We then present a multi-period routing problem, where each customer's likelihood of adopting the representative's product may change over time and is not fully observed by the representative. The representative can only estimate the adoption likelihood by meeting with the customer but the estimation may not be accurate.
publicabstract, Dynamic Programming, Heuristic, Orienteering Problem, Queueing, Time Window
xi, 142 pages
Includes bibliographical references (pages 138-142).
Copyright 2015 Shu Zhang
Zhang, Shu. "Stochastic orienteering on a network of queues with time windows." PhD (Doctor of Philosophy) thesis, University of Iowa, 2015.