Have you ever solved a Rubik’s Cube? If not, maybe you’ve solved a Sudoku puzzle, or even just a maze on the back of a cereal box. If you have ever solved one of these things, then congratulations! You’ve solved a Non-deterministic Polynomial problem! This terminology could sound quite intimidating, but you don’t need a math degree to understand the fundamentals, because you actually come across Polynomial (P), and Non-deterministic Polynomial (NP), problems everyday.
Polynomials are functions of n raised to different powers, like n^2 or n^3. And polynomial time means that if a problem involves n elements (e.g. the number of bus stops on a route, or the number of units on a Rubik’s cube), the time that it takes a computer to find the optimal solution to the problem will be roughly some polynomial function of n.
A “P problem” takes a computer “polynomial time” to complete, while an “NP-Hard problem” takes exponential time to solve because there is no known algorithm that can solve it in polynomial time. As the name suggests, NP-hard problems are much more difficult than P problems. If you’re wondering how scheduling could get so complicated, here is a brief example:
Imagine you have three hours to schedule three one-hour meetings with Alex, Bob, and Carol. In this simple case, there are six options.
Of course, in this scenario, all six of the above options will work fine. But as you know, people have busy schedules, and preferences of their own. Imagine you receive the following requests from Alex, Bob, and Carol:
- Alex is only free until 11:30 am, but he would like to meet with you for a full hour.
- Bob would prefer to meet after 10 am, and if you meet him beforehand he might be unprepared, so the meeting will last for 90 minutes.
- Carol wants to meet with Alex for one hour before meeting with you, and if she can do this, then her meeting with you will only need to be 30 minutes.
On top of these requests, you may have your own preferences. Maybe you have lots of other work to do and wish to conserve your own time as much as possible, or maybe you care most about meeting Alex’s needs, and less so about those of Carol and Bob. What’s more, if a fourth person were to ask you to set up a meeting, your dilemma would become four times more complicated, with 24 options. Furthermore, if 10 people want to meet with you, there are 3.6 billion options (almost half of the Earth’s population!), and if 20 people want to meet with you, there are 2.4 quintillion (2.4* 10^18) possibilities (that’s about one-third of the number of grains of sand on Earth). As preferences and necessities vary, and especially as more people are added to your schedule, the number of possibilities — and with it, the difficulty of finding the optimal scenario — increases rapidly.
Optibus is helping companies tackle similar near-impossible problems related to their bus scheduling. It is no easy task. Our algorithm processes systems of hundreds to thousands of vehicles and drivers, taking into account the non-negotiable considerations as well as the preferred qualities, and produces optimal results. Some elements that we have to consider include: network and route plans, bus stops and depot locations, timetable alignment, vehicle type and capacity, drivers’ shift preferences, electric vehicle charging, regulatory requirements, and performance KPIs.
Regardless of whether or not a transportation company is publicly funded, it should provide commuters with the best service at the lowest cost. The difference between an optimal and sub-optimal solution could be millions of dollars per year; that’s bad news for companies and tax-payers alike. The typical optimization algorithm takes a few hours to a few days to complete, even with lots of computing power. And if finding optimal solutions takes a day or more, it’s simply not realistic for a company to run different scenarios in order to find the scenario that works best, especially in the case of changing conditions (e.g. road closures).
At Optibus, we solve complex optimization problems in a matter of minutes, or even seconds. Our algorithm divides the problem into many subproblems that can be solved with more individualized algorithms. For example, we have a sub-algorithm that greatly reduces calculation time by quickly eliminating scenarios that are not realistic.
One of the interesting innovations resulting from our efficient usage of cloud computing for our algorithms is called “distributed optimization.” Using on-demand cloud resources (rather than on-premise installations), and using carefully designed algorithms that allow parallelization, we can solve many problems in parallel (i.e. simultaneously), so the overall optimization problem can be completed much faster. Furthermore, with each optimization, users are able to easily see how much that plan will cost them, and they can adjust their test scenarios accordingly.
The consequence of our innovation is that optimizing transportation schedules can now be a simple and efficient process for transportation operators. Our technology takes care of the tedious, yet crucial, components of transit systems so that the transportation industry can direct their focus (and budget) towards planning great service.
