The Generalized Traveling Salesman Path Problem (GT-SPP) involves finding the shortest path from a location s to a location t that passes through at least one location from each of a set of generalized location categories (e.g., gas stations, grocery stores). This NP-hard problem type has many applications in transportation and location-based services. We present two exact algorithms for solving GTSPP instances, which rely on a unique product-graph search formulation. Our exact algorithms are exponential only in the number of categories (not in the total number of locations) and do not require the explicit construction of a cost matrix between locations, thus allowing us to efficiently solve many real-world problems to optimality. Experimental analysis on the road network of North America demonstrates that we can optimally solve large-scale, practical GTSPP instances typically in a matter of seconds, depending on the overall number and sizes of the categories.
展开▼
