A priori orienteering with time windows and stochastic wait times at customers

• We consider stochastic wait times resulting from queues of competing salespeople.
• The customer-specific recourse action is a novel addition to routing models.
• We derive an analytical formula for the expected reward from an a priori tour.
• We show the value of incorporating stochastic information into the routing model.

In the pharmaceutical industry, sales representatives visit doctors to inform them of their products and encourage them to become an active prescriber. On a daily basis, pharmaceutical sales representatives must decide which doctors to visit and the order to visit them. This situation motivates a problem we more generally refer to as a stochastic orienteering problem with time windows (SOPTW), in which a time window is associated with each customer and an uncertain wait time at a customer results from a queue of competing sales representatives. We develop a priori routes with the objective of maximizing expected sales. We operationalize the sales representative’s execution of the a priori route with relevant recourse actions and derive an analytical formula to compute the expected sales from an a priori tour. We tailor a variable neighborhood search heuristic to solve the problem. We demonstrate the value of modeling uncertainty by comparing the solutions to our model to solutions of a deterministic version using expected values of the associated random variables. We also compute an empirical upper bound on our solutions by solving deterministic instances corresponding to perfect information.