Performance Optimization Guide
The VRP solver’s performance depends on multiple factors including problem size, constraint complexity, and configuration choices. This guide helps you understand and optimize solver performance for your specific use cases.Performance Fundamentals
What Affects Solve Time?
Performance Scaling
The solver’s time complexity increases with:- Number of jobs (O(n))
- Number of resources
- Number of time windows
- Basic constraints
Problem Size Guidelines
Small Problems (< 100 jobs)
Medium Problems (100-500 jobs)
Large Problems (500-2000 jobs)
Very Large Problems (> 2000 jobs)
Configuration for Performance
Essential Options
Maximum solve time in seconds. Balance between quality and speed.
Initial solution strategy. Options:
FIRST_FIT
: Fastest, lower qualityCHEAPEST_INSERTION
: BalancedAUTO
: Solver chooses based on problem
Optimization algorithm:
LATE_ACCEPTANCE
: Good for tight time windowsTABU_SEARCH
: Good for complex constraintsAUTO
: Adaptive selection
Performance-Oriented Settings
Distance Matrix Performance
Distance calculations significantly impact performance:Matrix Types by Speed
1
Euclidean (Fastest)
- No external API calls
- Instant calculation
- Lower accuracy
2
Haversine (Fast)
- No external API calls
- Quick calculation
- Good for aerial distance
3
Road Distance (Slower)
- External API calls
- Caching helps
- Most accurate
Distance Matrix Optimization
Caching Strategy:
- Pre-calculate frequently used distances
- Store in request for reuse
- Use
matrixId
for persistent caching - Limit unique locations
Constraint Impact on Performance
Low Impact Constraints
- Basic time windows
- Simple capacity checks
- Fixed assignments
- Priority values
Medium Impact Constraints
- Multiple time windows
- Multi-dimensional capacity
- Skill/tag matching
- Soft time preferences
High Impact Constraints
- Complex job relations
- Many-to-many dependencies
- Dynamic time calculations
- Alternative evaluations
Performance Tips:
- Minimize hard constraints
- Avoid unnecessary job relations
- Use reasonable time window widths
- Limit alternative calculations
Hardware Requirements
Minimum Requirements
- CPU: 2 cores
- Memory: 4GB RAM
- Network: 10 Mbps
- Storage: 1GB free
Recommended Specifications
- CPU: 4 cores
- Memory: 8GB RAM
- Network: 50 Mbps
- Storage: 5GB free
Performance Monitoring
Key Metrics to Track
Performance Indicators
Metric | Good | Warning | Critical |
---|---|---|---|
Time to First Feasible | < 20% of limit | 20-50% | > 50% |
Score Improvement Rate | > 1%/sec | 0.1-1%/sec | < 0.1%/sec |
Memory Usage | < 50% available | 50-80% | > 80% |
Move Evaluations/sec | > 1000 | 100-1000 | < 100 |
Optimization Strategies
1. Problem Decomposition
For very large problems, consider:1
Geographic Clustering
Divide by regions or zones
2
Temporal Splitting
Separate by time periods
3
Resource Grouping
Partition by vehicle types
4
Priority Batching
Process high-priority first
2. Incremental Solving
3. Parallel Processing
When possible, run multiple scenarios:4. Feature Toggling
Disable non-essential features for speed:Common Performance Issues
Issue: Slow Initial Solutions
Symptoms
Symptoms
- Long time to first feasible solution
- Many jobs unassigned initially
- Poor construction heuristic performance
Solutions
Solutions
- Relax hard constraints temporarily
- Use
FIRST_FIT
construction - Enable partial planning
- Reduce initial problem size
Issue: Plateau in Optimization
Symptoms
Symptoms
- Score stops improving
- Move count remains high
- No better solutions found
Solutions
Solutions
- Increase solve time
- Adjust weight balance
- Try different local search
- Add solution diversity
Issue: Memory Exhaustion
Symptoms
Symptoms
- Out of memory errors
- Slow garbage collection
- System thrashing
Solutions
Solutions
- Reduce problem size
- Disable explanation
- Limit move thread count
- Use geographic filtering
Best Practices
Performance Optimization Checklist:
- Start Simple: Begin with minimal constraints and features
- Measure Baseline: Record initial performance metrics
- Profile Problems: Identify specific bottlenecks
- Iterative Tuning: Make one change at a time
- Cache Aggressively: Reuse distance calculations
- Right-size Time: Don’t over-allocate solve time
- Monitor Production: Track real-world performance
- Document Settings: Record what works for your use case
Performance Benchmarks
Typical performance for well-configured problems:Jobs | Vehicles | Constraints | Time | Quality |
---|---|---|---|---|
50 | 5 | Basic | 5s | Optimal |
200 | 20 | Moderate | 30s | Near-optimal |
500 | 50 | Complex | 120s | Very good |
1000 | 100 | Complex | 300s | Good |
2000 | 200 | Moderate | 600s | Feasible |
Actual performance varies based on geographic distribution, constraint complexity, and hardware. Use these as rough guidelines only.