Solving a generalized traveling salesperson problem with stochastic customers

In this paper, a probabilistic generalized traveling salesperson problem (PGTSP) is introduced to address several applications. In the PGTSP, each customer belongs to a cluster that consists of a set of customers. Whether or not any given customer will be present during actual operations is known a priori only probabilistically. The PGTSP seeks the minimum expected length tour to visit a subset of all customers such that the tour traverses each cluster at least once. If when implementing the tour it is revealed that there is no demand for service within the cluster to which a customer stop belongs, that stop will be skipped. An exact solution algorithm based on the integer L-shaped method and three tour construction-based heuristics for quickly solving this problem are described in the paper. Computational experiments were conducted to assess computational requirements and solution quality of the proposed solution techniques. These experiments show that the exact method is able to solve small- and moderate-size problems to optimality. In addition, one of the proposed heuristics (the MMI heuristic), in particular, gives good approximate solutions (often a few percent from optimal) in very reasonable computational time.