How A*pex Optimizes Hyperloop Route Planning

Designing a Hyperloop route isn’t as simple as connecting two dots on a map. Each potential segment has its own trade-offs considering cost of construction, travel time, environmental impact, route curvature, and lots more. Taking all of these criteria into account, a single “shortest path” algorithm like the vanilla A* algorithm might not cut it anymore.

This is why I found the paper A*pex: Efficient Approximate Multi-Objective Search on Graphs by Han Zhang, so insightful into a potential approach we use to tackle managing multiple factors when planning our route. This is because it reframes how we can search for a list of good enough solutions when perfect optimality might be computationally unrealistic.

So why does Multi-Objective A* help us with Hyperloop Design? Traditional A* finds the best path by minimizing a single cost, such as distance. But in the Hyperloop’s case, we’re balancing multiple objectives where each forms its own cost component, meaning that every edge in our route graph carries a vector of costs, not just a single weight.

This paper also discusses existing flavors of the A* algorithm, like NAMOA* or PP-A* that handle two objectives, and how they become infeasible when used to consider three or more factors. The authors introduced A*pex, a variant of A* that brings three main improvements. First, Compact Representation, where instead of storing every path, A*pex represents sets of similar paths with a single “apex-path pair” that is representative of the combinations of these similar ones. This dramatically reduces memory and runtime. Next, when deciding how to determine the tolerance we have when considering a route as similar, this approach adds an approximation factor (ε) so users can define a tolerance, ε, for how much different a path can be on each factor while still being considered acceptable. For Hyperloop planning, this means, for example, I can find routes that are within 2% of optimal travel time but reduce cost by 20%. Finally, for generalization to a Multi-Objective Space, unlike PP-A*, which was limited to bi-objective problems, A*pex scales to any number of objectives and this is crucial to our use case with hyperloops when balancing so many factors.

Working with the A*pex algorithm mentioned in this paper with Hyperloop routing opens the potential approach where, instead of generating one “most optimal route,” we can generate candidate routes that respect multiple constraints. This allows route planners to visualize trade-offs and pick the most suitable route on a case-by-case basis