A solution to the INFORMS Growing Pains large scale vehicle routing optimization case study using Google OR-Tools.
The case study, which was based on a real customer problem submitted to The Institute for Operations Research and the Management Sciences (INFORMS), is a challenging capacitated vehicle routing problem with time windows (CVRP-TW) problem. CVRP-TW is a variation of the Vehicle Routing Problem (which itself is a generalization of the familiar Traveling Salesman Problem where the vehicles are limited by capacity and deliviries and/or pickups can only take place within certain times ranges (time windows). Such problems are common in logistics and fleet management.
In this case study, there are 123 locations to serve, which results in an extremely large combinatorial search space. It is usually impractical or impossible to find an optimal solution to a problem of this size. An approach used to find a good solution to these problems is Constraint Programming, which searches a large space of feasible solutions for one(s) which meet(s) the decision criteria. This implementation uses Google's open source suite of optimization and operations research tools Google OR-Tools to find a solution. The project walks through the implementation from start to finish showing how to process the data, apply the OR-Tools solvers to find a solution, and examine the results. The final solution presented here can probably be improved by running the solvers for a much longer time or on more powerful hardware.
There are three Python notebooks in this repo:
GrowingPains_EDA_DataPrep.ipynbexplores the data provided in the case study and prepares it for use with the solver.GrowingPains_ProblemSolution.ipynbsets up the problem constraints and solver, then runs the solver to find a solution. The solution time in the notebook is limited to only 15 minutes but increasing run time can potentially find better solutions. The cell outputs are removed to reduce notebook size. This code should really be run as a Python terminal script, but the notebook is useful for illustration. I will provide a script version of this in the future.GrowingPains_ProcessingResults.ipynbis for post-processing results. Some example tables and route maps are provided.