Skip navigation
Please use this identifier to cite or link to this item:
Title: The Minimum Vacation Cost Problem: A Novel Generalization of the Traveling Salesman Problem with Vertex Costs and Flexible Time Windows
Authors: Gu, Janie
Advisors: Ahmadi, Amirali
Department: Operations Research and Financial Engineering
Class Year: 2015
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.
Extent: 96 pages
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Operations Research and Financial Engineering, 2000-2017

Files in This Item:
File SizeFormat 
PUTheses2015-Gu_Janie.pdf1.85 MBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.