Source-linked AI summary
Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints
Andrew Soroka, German Mikhelson, Alexander Mescheryakov, Sergey Gerasimov
TL;DR
Route optimization with realistic constraints becomes difficult as exact methods face exponential complexity. This paper develops Smart Routes to compare exact, heuristic, and deep-learning approaches for CVRPTW, finding that heuristics and JAMPR provide near-exact quality faster on smaller instances while exact methods scale poorly on larger ones.
Problem
Exact CVRPTW methods face exponential complexity as instance size grows, motivating evidence on effective solution-quality and search-time trade-offs.
Method
The paper develops Smart Routes and compares SCIP with LKH, 2-OPT, 3-OPT, OR-Tools, and JAMPR for CVRPTW.
Results
For 50-point instances, heuristic and reinforcement-learning solutions stayed within 5% of SCIP, while for 100-point instances exact methods took 13 times longer initially and incurred up to 50% higher route costs.
Takeaways & Limitations
Heuristic and neural approaches offer a better solution-quality/search-time trade-off than exact methods for the tested 50-point instances, while exact methods become impractical at 100 points.
Takeaways & Limitations
Experiments use SOFT CVRPTW settings that allow unvisited points, penalizing them through the missed_nodes cost term.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper addresses vehicle routing under increasing problem dimensions and realistic constraints, especially customer time windows, service times, and vehicle capacities. It introduces Smart Routes as a platform integrating exact, heuristic, and deep reinforcement approaches while comparing common optimization methods.
- Motivation: Vehicle Routing Problems aim to reduce transport resource costs, route expenses, and cargo delivery time, but growing customer and city counts make efficient resource use increasingly difficult.Shorter routes can improve resource utilization while maintaining service quality.
- Problem: Realistic routing must account for customer time windows, service times, and vehicle capacities while balancing solution quality against search time as problem dimensions increase.Developing and modifying algorithms under multiple constraints remains challenging.
- Contributions: The paper contributes the Smart Routes platform and a comparative analysis of common route-optimization methods, including heuristics, deep reinforcement networks, and the exact SCIP method.The comparison focuses on constrained vehicle-routing problems.
- System: Smart Routes integrates exact, heuristic, and deep reinforcement approaches for varied vehicle-routing problems and supports both logistics practitioners and testing of new ideas.The system is designed as a one-stop platform for route-optimization experimentation.
2. Related work
The related work organizes route-optimization methods into heuristic, exact, and deep-learning approaches. It emphasizes gaps in prior comparisons, particularly limited use of exact methods, problem sizes, and realistic constraints.
- Prior studies often omit exact approaches, consider limited problem sizes, or exclude constraints, motivating a more complete comparison of route-optimization algorithms.
- Heuristic algorithms: Heuristic methods comprise constructive heuristics, which quickly build high-quality feasible solutions, and metaheuristics, which explore solution spaces more flexibly but at higher computational cost.
- Exact algorithms: Exact approaches formulate linear or mixed-integer linear programs and use methods including Branch&Bound, Cutting Plane, and Branch&Cut to obtain integer solutions or prove infeasibility.
- Exact algorithms: MILP solvers such as CPLEX, SCIP [1], and Gurobi implement multiple exact algorithms, but high dimensionality and integer variables can make memory use and solution time grow exponentially.
- Deep learning: Deep-learning work began with Nazari et al.'s Pointer Network adaptation for CVRP, replacing the RNN encoder with a shared-parameter linear layer, followed by Kool et al.'s [12] attention-based transformer model.
3. Algorithms and models
The section presents exact, classical heuristic, and deep reinforcement-learning approaches for constrained vehicle-routing problems. It focuses on local search, SCIP, OR-Tools, and a modified JAMPR model with trainable constraint-specific masks.
- Classical heuristics: Local-search heuristics were selected for their balance between solution quality and search efficiency, while also supporting metaheuristic and genetic algorithms [18].
- Classical heuristics: The main classical heuristic is Lin-Kernighan [2], which repeatedly applies improving route exchanges from feasible or randomized initial routes until no further improvement is found.
- Exact optimization: SCIP [1] solves mixed-integer optimization using methods including Branch&Bound, cutting planes, constraint propagation, heuristics, decomposition, and integer programming.
- Optimization frameworks: OR-Tools was included as a versatile framework for vehicle-routing, combinatorial, linear, integer, scheduling, and related optimization problems.
- Deep reinforcement learning: The modified JAMPR model [4] uses attention-based encoder-decoder reinforcement learning and adds trainable constraint-specific masks to alter the decoder policy.Routes are constructed incrementally as a sequential decision process, with node features such as coordinates, cargo weights, and time windows encoded before decoding.
4. System Smart Routes
Smart Routes is a web-based platform for solving and comparing vehicle-routing algorithms under common constraints, with support for large-scale and real-world datasets. Its modular architecture integrates exact, heuristic, and neural methods, custom algorithms, visualization, metrics, and API access.
- System requirements: Smart Routes supports VRP constraints including vehicle capacity and time windows, scales to approximately 1000 points, and processes real-world data in a specified format.The platform also supports experiments across classical heuristic, exact, and deep reinforcement network approaches.
- System architecture: The platform comprises Dataset, Algorithm, and Solution modules for data preparation, algorithm training and evaluation, metric generation, route visualization, and web interaction.Users select the problem type, algorithm, time limit, dataset, and optional generation parameters before receiving route results.
- System architecture: For each task, users obtain the final route cost and customer visitation order, alongside two graphs showing metrics and the complete graphical route.The metric graph demonstrates route-cost changes within the specified time limit, while the visualizer displays the route itself.
- Extensibility: Users can integrate custom VRP algorithms by inheriting from base classes and implementing required methods, while built-in approaches cover classic heuristics, exact methods, and neural methods.This extensibility addresses the time required to understand and implement models in existing toolkits and the growing search time of exact methods on larger instances.
- Platform advantages: Smart Routes simplifies experimentation through automatic route visualization, performance charts, an API for built-in approaches, and a user-friendly interface.The authors describe these features as simplifying development, testing, and experimentation compared with existing software.
5. Data
The study evaluates CVRPTW algorithms under SOFT settings, where unvisited points are skipped and penalized. Experiments use Solomon R201 instances with problem sizes of 50 and 100 and specified capacities, horizons, and service durations.
- Problem setting: CVRPTW instances use SOFT settings that permit skipping unvisited points, which are excluded from routes and increase the missed_nodes penalty.This setup evaluates algorithm behavior when multiple constraints are present simultaneously.
- Instances: Experiments select Solomon reference instances based on R201 statistics for problem sizes of 50 and 100 points.
- Instance parameters: Truck capacities are Q50 = 750 and Q100 = 1000, with a0 = 0 and b0 = 1000 for both problem sizes.The service duration hi is uniformly set to 10 for each point.
6. Experiments
Experiments on 50- and 100-point CVRPTW instances compared SCIP with classical heuristics and JAMPR using Smart Routes. Exact methods achieved strong final solutions but required substantially more time, while JAMPR and heuristics quickly produced competitive solutions, especially at 100 points.
- Experimental setup: Experiments used 100 artificial instances each for 50- and 100-point problems, with time limits of 100 and 200 seconds; SCIP received 1000 and 2000 seconds.The Smart Routes platform simplified parameter setup, and tasks were parallelized across available processors.
- Overall comparison: Doubling problem dimension increased SCIP solution time roughly 14-fold, indicating limited applicability of exact methods for instances with 100 or more points.The comparison is summarized in Figure 3, whose axes report average solution time and average route cost.
- 50-point instances: For 50-point instances, SCIP eventually achieved the best solution, but heuristics and JAMPR produced suboptimal solutions within seconds and were faster by an order of magnitude.After about 10 seconds, SCIP was inferior to LKH, OR-Tools, and JAMPR; after 100 seconds, SCIP surpassed them, with the final JAMPR–SCIP gap below 5%.
- 100-point instances: 13× longer: SCIP needed more than 900 seconds for its first 100-point solution, while JAMPR and OR-Tools reached similar plateaus; SCIP’s first solution was about 50% costlier.Within the allocated 2000 seconds, SCIP still did not achieve an optimal solution.
- 100-point instances: For 100-point instances, JAMPR outperformed classical heuristics in solution quality and exact methods in time to find a solution.JAMPR’s initial greedy solution had approximately 10% better GAP than LKH, and its final GAP surpassed LKH by around 50%.
7. Conclusions
The conclusions show that heuristic and reinforcement-learning approaches provide fast, near-exact solutions for 50-point CVRPTW instances, while exact methods become impractical at 100 points. The Smart Routes platform supports solving and comparing these approaches for future route-optimization research.
- Scope: The study compares SCIP [1] with heuristic and learning-based approaches for the Capacitated Vehicle Routing Problem with Time Windows.Exact optimization becomes challenging as problem size increases because of exponential complexity.
- Platform contribution: All reported metrics were obtained using the Smart Routes platform, which supports multiple solution approaches and facilitates research and result comparison.The authors present the platform as an important component for future research on route optimization with diverse constraints.
- Experimental results: For 50-point instances, classical heuristics and reinforcement-learning approaches provided fast suboptimal solutions within 5% GAP of SCIP results.These results indicate that both approaches can offer effective alternatives to the exact method.
- Experimental results: For 100-point instances, exact methods required 13 more time to find an initial solution and produced up to 50% higher route costs during optimization.They could not provide an optimal solution within the given time, while JAMPR and OR-Tools surpassed classical heuristics in solution quality.