Multi-period orienteering with uncertain adoption likelihood and waiting at customers

We introduce a multi-period orienteering problem in which a salesperson visits customers to provide information on product and service offerings that may lead to eventual adoptions at the end of the problem horizon. Upon arriving at a customer, the salesperson may experience uncertain wait time that delays or prevents the salesperson from meeting with the customer within the customer’s time window. A customer’s adoption probability evolves stochastically from period to period depending on whether the salesperson meets with the customer. To maximize the expected sales accrued from product adoptions at the end of the horizon, the salesperson must decide in which period(s) to visit the customers and what sequence to visit the customers within each period. We formally model this problem as a Markov decision process. To overcome the computational challenges induced by the large state and action space, we propose a two-stage heuristic approach to facilitate decision making. In the first stage, we solve an assignment problem to determine which customers to visit in the current period. In the second stage, we solve a routing problem to determine the sequence to visit the selected customers. In the computational experiments, we demonstrate the effectiveness of our heuristic methods.