The Minimum Vacation Cost Problem: A Novel Generalization of the Traveling Salesman Problem with Vertex Costs and Flexible Time Windows

Abstract

This thesis presents and explores the Minimum Vacation Cost Problem (MVCP), a novel combinatorial optimization problem and generalization of the classical Traveling Salesman Problem (TSP). The MVCP models the realistic problem of a traveler planning a vacation itinerary through multiple cities with a fixed constraint on trip length but flexibility in the time windows to spend in each city. While previous scholars have explored variations of the TSP with similar characteristics to the MVCP, the MVCP is novel in introducing: (1) the use of a flexible time window (with upper and lower bound constraints [a, b]) to optimize over price variations in time, and (2) the consideration of time-dependent vertex costs (i.e. hotel costs) in optimizing overall itineraries. In this work, we present an integer programming formulation for representing and solving the MVCP. Additionally, we present two computational algorithms, a brute-force search algorithm and shortest-path algorithm with subgradient optimization, that are able to find optimal solutions to the problem. We also introduce newly developed problem instances using commercial flight and hotel price data to test our algorithms’ performance, and provide a comprehensive analysis of performance in response to various parameters (including number of cities, trip length, and time window constraints). Finally, we analyze MVCP solutions across hundreds of itineraries in the US and find that solving the MVCP results in a 27.09% reduction in travel costs on average. We thus conclude that optimization of multi-city travel itineraries using the MVCP can create substantial cost savings for travelers.