How many solutions does RouteFinder explore?


Route planning problems in the fields of transportation, distribution, logistics or field service management fall into the Vehicle Routing Problem (VRP) family. There are many subsets of these problems from the simpler Traveling Salesman Problem (TSP), to the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). RouteFinder attempts to solve all of these problems.

In general, these problems are considered np-hard combinatorial optimization problems. The decisions that have to be determined to find what is called a "solution" vary based on the type of problem (TSP vs CVRPTW), but typically all are dealing with the assignment of a service order to a vehicle and the sequencing of stops on the vehicle route.

This is a well and actively studied problem, and many methods and algorithms have been proposed. It is still considered a challenging topic for researchers since there is still a large margin of improvement in solving problems with real-world operations sizes and requirements.

To help you understand how hard it is to solve a problem in this family of problems, suppose we have a set of vehicles and 10x that number of service orders. In the following table you can see the number of possible solutions you should explore to find the best solution. For the purposes of these numbers, a feasible solution includes those where service orders are not serviced.


Vehicles Stops Solutions
5 50
2.4 * 10^70
10 100
9.9 * 10^170
15 150
9.4 * 10^282
20 200
2.1 * 10^402
50 500
9.5 * 10^1204
100 1000
1.2 * 10^2711