A Linear Programming Application for Generating Running Routes Based on Individual Preferences
Yoav Levanoni, Owen Works, Antonio da Silva, Jill Speece · 2024
We present the first application to utilize linear programming to generate running routes. Route generation is beneficial for runners visiting new and unfamiliar locations. Current applications forgo linear programming, utilizing various other methods to create custom routes. Our objective is to create a linear programming model that produces optimal closed-loop routes based on user preferences. The model proposed is an extension of ATSP [1]. The model processes a street network. One set of decision variables represent the inclusion of network edges in the optimal solution, and the second set of decision variables are the sequence variables in which the route nodes are selected. The objective function minimizes the total distance traveled in the route. A modification of the flow conservation constraint is introduced to ensure that a node can be visited and departed at most once. Novel constraints that force the solver to optimize for distance, elevation, and route friendliness are introduced in the model. Subtour elimination constraints found in the Miller-Tucker-Zemlin ATSP formulation are introduced to prevent subtours and ensure connectivity. The model UI is implemented as a website. This enabled feedback for verification and validation testing. Athletes input parameters such as their starting location, preferred distance, terrain type, and elevation to help further optimize their route. In conclusion, the linear programming model helps runners plan the most optimal running routes according to their preferences.