One of the most important applications of optimization is vehicle routing, in which the goal is to find the best routes for a fleet of vehicles visiting a set of locations. Usually, "best" means routes with the least total distance or cost. Here are a few examples of routing problems:
- A package delivery company wants to assign routes for drivers to make deliveries.
- A cable TV company wants to assign routes for technicians to make residential service calls.
- A ride-sharing company wants to assign routes for drivers to pick up and drop off passengers.
The most famous routing problem is the Traveling Salesman Problem (TSP): find the shortest route for a salesman who needs to visit customers at different locations and return to the starting point. A TSP can be represented by a graph, in which the nodes correspond to the locations, and the edges (or arcs) denote direct travel between locations. For example, the graph below shows a TSP with just four locations, labeled A, B, C, and D. The distance between any two locations is given by the number next to the edge joining them.
By calculating the distances of all possible routes, you can see that the shortest route is ACDBA, for which the total distance is 35 + 30 + 15 + 10 = 90.
The problem gets harder when there are more locations. In the example above, there are just six routes. But if there are ten locations (not counting the starting point), the number of routes is 362880. For 20 locations, the number jumps to 2432902008176640000. An exhaustive search of all possible routes would be guaranteed to find the shortest, but this is computationally intractable for all but small sets of locations. For larger problems, optimization techniques are needed to intelligently search the solution space and find an optimal (or near-optimal) solution.
A more general version of the TSP is the vehicle routing problem (VRP), in which there are multiple vehicles. In most cases, VRPs have constraints: for example, vehicles might have capacities for the maximum weight or volume of items they can carry, or drivers might be required to visit locations during specified time windows requested by customers. OR-Tools can solve many types of VRPs, including the following:
- Traveling salesman problem, the classic routing problem in which there is just one vehicle.
- Vehicle routing problem, a generalisation of the TSP with multiple vehicles.
- VRP with capacity constraints, in which vehicles have maximum capacities for the items they can carry.
- VRP with time windows, where the vehicles must visit the locations in specified time intervals.
- VRP with resource constraints, such as space or personnel to load and unload vehicles at the depot (the starting point for the routes).
- VRP with dropped visits, where the vehicles aren't required to visit all locations, but must pay a penalty for each visit that is dropped.
Limitations on solving vehicle routing problems
Vehicle routing problems are inherently intractable: the length of time it takes to solve them grows exponentially with the size of the problem. For sufficiently large problems, it could take OR-Tools (or any other routing software) years to find the optimal solution. As a result, OR-Tools sometimes returns solutions that are good, but not optimal. To find a better solution, change the search options for the solver. See Changing the search strategy for an example.
Note: We should add that there are other solvers, such as Concorde, dedicated to solving very large TSPs to optimality, which surpass OR-Tools in that area. However, OR-Tools provides a better platform for solving more general routing problems that contain constraints beyond those of a pure TSP.