The Optimal Transportation System: A Problem Statement

Meryl FioritiBlog

Have you ever ridden a train on Thanksgiving weekend?
Does your commute home begin at 5 p.m.?
Do you know someone who isn’t sure how they’ll get to their next doctor’s appointment, or even to the grocery store?  

Surely we’ve all experienced these issues, and if we haven’t, we know someone who has. The aforementioned problems are mundane, inconvenient, and some could even impact an individual’s well-being, yet all are accepted under the current state of public transit in our country.

What if it didn’t have to be this way?

At first glance, public transit behaves like a classic optimization problem. We have a certain amount of demand (riders), we have a certain amount of resources (vehicles), and we need to deliver each rider to a specified destination within some time frame, preferably by traveling the shortest distance, and using the least amount of time. Simplified, this looks a lot like a classic Traveling Salesman Problem.  

For those of you who aren’t familiar with this theory, it is “a problem in graph theory requiring the most efficient (i.e., least total distance) Hamiltonian cycle a salesman can take through each of n cities. No general method of solution is known, and the problem is NP-hard” (Traveling Salesman Problem, 2019). In layman’s terms, the Traveling Salesman Problem asks for a solution to the problem of having to visit a set number of places only once, while traveling the shortest distance possible. It’s the lazy-man’s errand-running strategy.

The solution is NP-hard (can not be completed in polynomial time) for this algorithm, but the solution has been shown to be reasonably approximated by heuristics such as ant colony optimization, genetic algorithms, simulated annealing, and other swarm intelligence solutions. These are the same algorithms operating at the heart of many recognizable artificial intelligence solutions, and they aim to approximate natural systems’ behaviors.

One example of this is the theory behind ant colony optimization algorithms. As the name suggests, ant colony optimization algorithms aim to reproduce the search behavior of an ant colony. Ants use a positive feedback loop to communicate to the rest of the colony which path leads to the best food. The scouts wander out, dropping a trail of pheromones that act as breadcrumbs as they go. If the ant finds a “solution” (in his case, something edible), he retraces his steps and drops a stronger trail of pheromones so that other ants can read his signature and follow his “success” path to the food. In the digitized version of this, a search algorithm with multiple iterations (or ants) is implemented. Each of the digitized ants records its path to success, and the strength of its solution, so that the next iteration can retrace the most successful steps and eventually land at a local optima, or the best possible solution (as far as it can tell). In essence, ants operate their own perfect transit system. Due to their swarm intelligence they’re able to find a close to perfect solution to their issue of finding food every day, and data scientists have figured out how to model this behavior using machine learning techniques.  

At this point you may be thinking, “Okay great, why don’t we just use this technique to fix our transit systems and call it a day?” Human behavior and expectations generally will not allow for an optimal solution. Ultimately, finding an optimal solution is not “fair” to all individuals in the system, and it has no memory of how long you’ve been waiting. It only knows that making you the next drop off would not be the solution that minimizes some given criteria, perhaps miles traveled. We can’t simply load everyone onto a bus and expect them to accept no estimation of when they will be allowed off. Imagine, you’ve been on a bus for 40 minutes for a trip that should have taken 20, and when you ask the driver why you haven’t been dropped off yet the only answer they are able to provide is that “it wasn’t optimal.”

This dichotomy of transit, the balance between the optimal solution and what our riders expect, is exactly the line that TransLoc is dedicated to balancing on. We strive to make transit as available and optimal as possible while making sure that it is a positive experience for all riders.

Check out this webinar if you’re interested in seeing how a technical approach to mobility plays out in the real world, or follow this link to learn more about TransLoc, Inc. and our mission.