When a university faced issues with its shuttle system, it turned to students and a mathematical theorem to find solutions that worked.

By George Richardson

ON A CRISP JANUARY MORNING, I was discussing with Roque Perez-Velez, management engineering coordinator at University of Florida (UF) Health, our shuttle predicament: How can we identify and correct the inefficiencies present in our current shuttle system?
UF Health Shands Hospital operates several shuttle routes to serve both patients and employees, offering a single transportation method between several surrounding health care facilities. One of the goals of the system is to have a wait time for any shuttle at any stop of 15 minutes or less. Unfortunately, these complimentary shuttles currently do not meet the target wait time of 15 minutes, leading to frustration for passengers trying to get to their various destinations around the medical campus.

We obviously want to provide the best possible experience to shuttle users. In our conversation, Pe­rez-Valez indicated that there are several methods available to allow us to identify and correct inefficien­cies in the system, by analyzing and changing route structures, stops, paths, and other qualities that are sources of ineffectiveness. Perez-Valez’s background in industrial enginnering, as well as his position as adjunct faculty in the industrial and systems engineer­ing (ISE) department of the University of Florida, has equipped him with the tools and techniques necessary to address this kind of problem.
Perez-Valez suggested an optimization methodolo­gy that aims to get shuttles to be within the 15-minute wait time goal by eliminating bottlenecks in the shuttle routes. These bottlenecks include, but are not limited to, minimizing left turns, avoiding high-traffic areas, and adjusting route stops based on use. These changes require little effort on the part of UF Health Shands administration but can pro­vide tremendous value to passen­gers. Because this is not a simple op­timization modeling methodology, Perez-Valez enlisted Michael Lucic to provide the research capabilities needed to solve this problem. Lucic is a graduating senior under the ISE program.

After careful consideration, Lucic suggested to Perez-Valez modeling the shuttle system with the trav­eling salesman problem (TSP), which determines the shortest path between all stops. The TSP asks, “Given a list of stops and the distances between each pair of stops, what is the shortest possible route that visits each stop and returns to the origin stop?” The TSP is a problem in combinatorial optimization, important in operations research. A sub-field of applied mathemat­ics, operations research is a discipline that deals with the application of advanced analytical methods to help make better decisions.

Under Perez-Valez’s mentoring and supervision, Lucic led a team of students in field observations, data collection, and testing to ensure that proposed route changes were feasible for shuttle drivers to implement.

UF Health Shands operates several complimentary shuttle routes to assist employees and patients in mov­ing around the various hospitals and parking areas in the main medical region at the southeastern section of the UF campus. The red, blue, and purple lines serve UF Health Shands employees while the pink, green, and yellow lines assist patients. In particular, the yellow line patient route serves patients with special requests for additional locations not normally serviced by the shuttle system.

After analyzing the quantitative and qualita­tive data, the team real­ized that there was a need to consider rerouting the pink, blue, and green lines to make significant improvements to the operation of those routes. The team used the TSP and the nearest neighbors heuristic to attempt a quantitative approach at improving the routes. Recall, the solution to TSP is the shortest Hamiltonian cycle or the fastest way to travel between all points in a network where we end up back where we started. On a TSP, the number of steps needed to solve the problem grows astronomically fast as complexity increases.
We needed to use a heuristic algorithm (which finds solutions to problems traditional methods can’t, but uses approximations and may not be 100 percent accurate) to efficiently solve this problem by approx­imating a close-to-optimal result. We optimized the routes by modeling each as a fully connected directed graph (or digraph), where the vertices represented the stops for the route, the directed edges represented the shortest route from one stop to another, and the edges are weighted based on the expected travel time driving between those two stops.

To find a feasible solution, we used the nearest neighbors heu­ristic, which works by selecting a node on the graph and select­ing the next node that directly connected to the previous node with the shortest connecting distance until all nodes have been selected. We used this spe­cific heuristic because the graph is fully connected—each vertex connects to all other vertices directly in both directions, and a fully connected graph has all other vertices as direct neighbors. Because we used a heuristic, optimality is not guaranteed, but the results are a good approximation.

Pink Line Recommendations

• Perez-Valez observed the current state of the system and used the data to solve route optimization problem.
• Estimate of updated route cycle time: 24 minutes/cycle
• Average current route cycle time: 38 minutes/cycle
• UF Health Shands Hospital operates several shuttle routes to serve both patients and employees, offering a single transportation method between several surrounding health care facilities.

After running these models for 10,000 replica­tions and analyzing the results, we concluded that the green and blue line routes needed no changes, as the best cycles outputted by the model all matched with the current green and blue line setups. In the pink line, there was one significant change—we found that having the shuttles travel from the house to either the veterans’ or cancer hospital is best ac­complished by driving a different route. With these changes, the team was able to accomplish its goal: 15 minutes or less wait times.
Did it work? It did! Using operation research tools, such as the TSP, can solve difficult problems such as our own shuttle predicament.

Read the article here.

Impressive project! To read the student team’s full conclusions and their final report, visit parking.org/resource-center and search for keywords “shuttle predicament.”

GEORGE RICHARDSON is manager, transportation, and parking, with the University of Florida Health Shands Hospital. He can be reached at richge@shands.ufl.edu.

THE PARKING PROFESSIONAL | SEPTEMBER 2018 | PARKING.ORG/TPP