Title: Maui Travel Time
Author: Tara Graeve
Date: Winter Quarter 2021

Table of Contents

  1. Problem Statement
  2. Data
    2.1 Data Source
    2.2 Another Section
  3. Model Definition
  4. Model Solution
  5. Sensitivity Analysis
  6. Conclusions
    6.1 Tactical Information
    6.2 Strategic Information
  7. Model Limitations, Future Improvements and Challenges

1. Problem Statement

A traveler to Maui, Hawaii has compiled a list of destinations to visit. The traveler would like to mimimize their total travel time to each destination. The traveler has selected 7 possible destinations: Haleakala, Kaanapali Beach, Napili Beach, Wailea Beach, Black Rock Beach, Nakalele Blowhole, and Kapalua Bay. The traveler has provided certain requirements to adhere to, though sensitivity analysis will also be performed and presented to them. The initial requirements are: the traveler doesn't want to go to more than 5 of the places but must go to at least 3, they absolutely must visit Kaanapali Beach, and they only want to spend a maximum of 3.5 hours traveling between destinations. In order to optimize the travel times, an assignment linear programming model will be performed. We don't want to double up destinations, so there will also be a limit of at most 1 total selections of each destination.

Data was collected via the Apple Maps application at a specific moment in time to find travel times to each destination from each other destination. This data was compiled into a matrix that will serve as coefficients in the objective functions. Because we don't want to travel from a destination to itself, the coefficients will purposely be large to prevent the solver from choosing those pairs. The decision variables are binary, so ultimately the objective function will be a sum of each time coefficient multiplied by the binary (0/1) variable. Because travel times can vary, it will be helpful to perform a sensitivity analysis slightly varying times to account for traffic/time of day.

Back to Top

2. Data

2.1 Data Source

Data obtained via Apple Maps queries between destinations. Constraint data is fictitious based on a theoretical traveler.

2.2 Reading in Data

Back to Top

3. Model Definition

Back to Top

Define Constraints

4. Model Solution

Back to Top

5. Sensitivity Analysis

Number of Locations Min

No longer have to visit Kaanapali

Increasing Travel Time

Plots

Back to Top

6. Conclusions

6.1 Tactical Information

With the original constraints, the minimum travel time satisfying the requirements (3-5 locations, must visit Kaanapali, can't visit more than once, and travel less than 210 minutes) is 27 minutes. The traveler will be traveling from Kaanapali Beach to Black Rock Beach, from Napili to Kapalua Bay, and from Kapalua to Kaanapali Beach.

By changing the required amount of locations to 4, the optimal minimum travel time is 35 minutes. The traveler will travel from Kaanapali Beach to Black Rock Beach, Napili Beach to Kapalua Bay, Black Rock Beach to Kaanapali Beach, and Kapalua Bay to Napili Beach.

By changing the required amount of locations to 5, the optimal minimum travel time is 87 minutes. The traveler will travel from Kaanapali Beach to Black Rock Beach, from Napili Beach to Kapalua Bay, from Black Rock Beach to Nakalele Blowhole, from Nakalele Blowhole to Kaanapali Beach, and from Kapalua Bay to Napili Beach.

If the traveler doesn't absolutely have to go to Kaanapali Beach, the optimal minimum travel time is 14 minutes. The traveler will travel from Kaanapali to Black Rock Beach, from Napili to Kapalua Bay, and from Kapalua Bay to Napili Beach.

6.2 Strategic Information

Each increase in 1 minute travel time for all coefficents led to a 3 minute increase in the objective function, minimum travel time. All other factors equal, the relationship is linear and didn't have a big impact on the optimal mix.

Looking at the original solution, the traveler should start at Napili Beach and travel to Kapalua Bay, then travel from Kapalua Bay to Kaanapali Beach, and finally from Kaanapali Beach to Black Rock Beach. The three pairs chosen sequence together well, so this will absolutely lead to the minimal time. The traveler should have plenty of extra time to spend exploring the destinations since this amount of time is well below the traveler's maximum desired travel time.

With the 4 locations, the traveler should travel from Kaanapali Beach to Black Rock Beach and from Black Rock Beach back to Kaanapali Beach. The traveler should also travel from Napili Beach to Kapalua Bay and from Kapalua Bay back to Napili Beach. Due to the limitations of this model, this solution doesn't make a whole lot of sense for the traveler to use if they want to actually hit 4 locations with no duplications and thus circular routes. The increase in time between this solution and going to 3 destinations is only 8 minutes, so it's not adding a lot of time, though the discontinuity between the pairs means extra time that is not accounted for in the model would be tacked on in order to get to some destinations.

With visiting 5 locations, the traveler should travel from Black Rock to Nakalele Blowhole, then from Nakalele Blowhole to Kaanapali Beach. From Kaanapali Beach the traveler should travel back to Black Rock Beach. The traveler can complete his desire to reach 5 locations by going from Napili Beach to Kapalua Bay and back to Napili Beach from Kapalua Bay. The first three destinations make logical sense to sequence, however the second two provide duplication of pairs and incontinuity, so the minimum travel time given by the model will likely not hold up in this situation should the traveler choose it. This solution also adds a lot to the minimum travel time without the limitations of the model, so the opportunity cost is a lot higher than it is going from 3 locations to 4 locations.

Without visiting Kaanapali, the minimum travel time is cut roughly in half. There is again a discontinuity in the locations provided, as well as the traveler going from Napili to Kapalua Bay and from Kapalua Bay back to Napili. Despite the drastic decrease in time, this solution doesn't seem as feasible, especially considering the time added on to get between Black Rock Beach and Napili/Kapalua. Granted, eliminating the circular routes in each of the scenarios and visiting both without going back to the starting point will lead to a decrease, the time added will lead to a less mathematically optimal model. How much this could be is unclear and would need to be further explored.

Back to Top

7. Model Limitations, Future Improvements and Challenges

Back to Top

The biggest challenge for me was that the original idea I had for this project was way too complex for the scope of this class--that is I wanted to sequence them together, and that was simply beyond the scope of this class and what we have learned in pyomo. Initially I thought I could do this sort of like a transshipment model and use balance equations, but as I thought it through I realized that was not going to work how I originally thought. The limitations of this model are that it is in a sense a simplified version. Given more time and more advanced knowledge, I would ideally perform a model that would sequence the locations, much like a tool like the evolutionary solver would do in Excel. This would eliminate the duplication of pairs that led to circular routes in some of the sensitivity analysis optimal solutions, and it would lead to less manual construction of the routes. When analyzing the model as it is now, I took the pairs and sequenced them myself, whereas it would be good if the model did that for me. With more time and work on this model, it would ideally be retooled to be able to sequence the route and eliminate the circular travel pairs. I also might do an analysis of the constraints and see if I could add a constraint that would at least eliminate the circular pairs, if developing a full sequencing model was not possible.