The problem of route optimization with realistic constraints is becoming extremely relevant in the face of global urban population growth. While we are aware of approaches that theoretically provide an exact optimal solution, their application becomes challenging as the problem size increases because of exponential complexity. We investigate the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and compare solutions obtaining by exact solver SCIP with heuristic algorithms such as LKH, 2-OPT, 3-OPT, the ORTools framework, and the deep learning model JAMPR. We demonstrate that for problem of size 50 deep learning and classical heuristic solutions became close to SCIP exact solution but requires less time. Additionally for problems with size 100, SCIP exact methods around 13 times slower that neural and classical heuristics with the same route cost and on around 50% worse for the first feasible solution on the same time. To conduct experiments, we developed the Smart Routes platform for solving route optimization problems, which includes exact, heuristic, and deep learning models, and facilitates convenient integration of custom algorithms and datasets.
Figures & tables
Рис. 1: The JAMPR deep RL architecture modified to solve CPDPTW problems. Added block M+ of learnable masks applied to output of decoder (policy πθ ).
Рис. 2: Smart Routes System architecture. Three main blocks: 1) Dataset module is an entry point for all data manipulations, also stores prepared datasets and allows loading third-party data in a specified format; 2) Algorithm module responsible for train and evaluate all available algorithms on prepaired datasets. There is possibility to add user algorithm via special interfaces; 3) Solution module produces metrics, visualizes them and offers web interface for communication with system.
Algorithm Type
Framework
SCIP
Gurobi
OR-Tools
Smart Routes
Exact Approaches
+
+
+
+
Heuristic Approaches
+
+
+
+
Deep Reinforcement Approaches
—
—
—
+
Visualization of Results
—
—
—
+
Adding Custom Algorithms
—
—
—
+
Table 3
Рис. 3: Summary result of classical approaches, where each dot denotes the result of a specific algorithm on a given problem size. The horizontal line indicates the time required for the algorithm to achieve the best cost of the path, the vertical line indicates the best cost achievable by the algorithm. The orange line shows the applicability limit of exact approaches: on the left there is not enough time for the algorithm to provide a solution, the zone on the right is an area favorable for choosing exact approaches.
Рис. 4: Performance of the considered models on the CVRPTW with 50 points. Solid lines represent the results of approximate heuristic approaches. Dotted line represents the results of SCIP - the best cost achieved with the longest time. Dashed line represents JAMPR after 700 epochs of training - a fast suboptimal solution with subsequent asymptotic approximation to the heuristic. The figure has two scales: total cost (on the right) and the gap compared to the final best solution (on the left).
Рис. 5: Performance of the considered models on the CVRPTW with 100 points. Solid lines represent the results of approximate heuristic approaches. Dotted line represents the results of SCIP. Dashed line represents JAMPR after 23 epochs of training - a fast suboptimal solution with subsequent asymptotic approximation to the heuristic. Despite the considerable optimization time, SCIP failed to achieve the accuracy of JAMPR. The figure has two scales: total cost (on the right) and the gap compared to the final best solution (on the left).