Solving a generalized traveling salesperson problem with stochastic customers

Solving a generalized traveling salesperson problem with stochastic customers

0.00 Avg rating0 Votes
Article ID: iaor20082791
Country: United Kingdom
Volume: 34
Issue: 7
Start Page Number: 1963
End Page Number: 1987
Publication Date: Jul 2007
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.