​
VRP Constraint System

The Vehicle Routing Problem solver uses a sophisticated constraint system to transform business rules into optimized routes. This guide explains the fundamental concepts, types of constraints, and how they work together to create feasible and efficient solutions.

​
What Are Constraints?

Constraints are rules that define what makes a valid solution. They represent real-world limitations and preferences:

​
Constraint Hierarchy

The VRP solver organizes constraints into three levels:

​
1. Hard Constraints (Mandatory)

Must be satisfied for a feasible solution. Violations make the solution invalid.
  • Vehicle capacity limits
  • Required time windows
  • Skill/equipment requirements
  • Legal driving limits
  • Shift boundaries

​
2. Medium Constraints (Important)

Should be satisfied but can be violated if necessary. Used for strong preferences.
Medium constraints are less common but useful for:
  • Overtime penalties (when overtime is allowed but discouraged)
  • Strong customer preferences
  • Priority job sequencing

​
3. Soft Constraints (Optimize)

Preferences that improve solution quality. Always violated to some degree - the goal is minimization.
  • Minimize travel time
  • Minimize wait time
  • Balance workload
  • Minimize vehicles used
  • Customer preferences

​
How Constraints Work

​
Constraint Evaluation Process

1

Input Validation

The solver first validates that constraints are properly configured and compatible.
2

Initial Solution

Creates an initial solution, possibly violating many constraints.
3

Hard Constraint Resolution

Focuses on eliminating hard constraint violations through moves and swaps.
4

Soft Constraint Optimization

Once feasible, optimizes soft constraints while maintaining feasibility.
5

Continuous Improvement

Iteratively improves the solution until time limit or optimal solution is found.

​
Constraint Interactions

Constraints often interact and conflict with each other:
Conflict: Tight time windows may require more vehicles to minimize travel.Resolution: The solver balances based on weights:
{
  "weights": {
    "minimizeResourcesWeight": 3600,  // High cost for extra vehicle
    "travelTimeWeight": 1  // Lower priority
  }
}
Conflict: Optimal routes might exceed vehicle capacity.Resolution: Hard capacity constraints force route splits, soft constraints optimize the splits.
Conflict: Skilled resources may get overloaded.Resolution: Workload balancing weights compete with skill requirements:
{
  "weights": {
    "workloadSpreadWeight": 100  // Strong preference for balance
  }
}

​
Built-in Constraints

The VRP solver includes many pre-configured constraints:

​
Capacity Constraints

Types:
  • Single dimension (weight OR volume)
  • Multi-dimensional (weight AND volume AND count)
  • Dynamic (changes with pickups/deliveries)

​
Time Constraints

Categories:
  • Time Windows: When jobs can be serviced
  • Shift Times: When resources can work
  • Drive Time: Maximum continuous driving
  • Service Duration: How long jobs take
Time constraints often cascade - arriving late at one job affects all subsequent jobs.

​
Skill/Tag Constraints

Match job requirements with resource capabilities: 
{
  "job": {
    "tags": [
      {"name": "plumbing", "hard": true},    // Must have
      {"name": "certified", "hard": false}   // Preferred
    ]
  },
  "resource": {
    "tags": ["plumbing", "electrical", "certified"]  // Has all needed tags
  }
}

​
Relation Constraints

Define dependencies between jobs:
  • SEQUENCE: Order matters, gaps allowed
  • SAME_TRIP: Must be on same route
  • PICKUP_AND_DELIVERY: Paired operations
  • SAME_TIME: Synchronized arrival

​
Constraint Configuration

​
Weight System

Weights determine the relative importance of soft constraints: 
{
  "weights": {
    "travelTimeWeight": 1,
    "priorityWeight": 1,
    "workloadSpreadWeight": 1,
    "minimizeResourcesWeight": 1
  }
}

​
Weight Guidelines

Weight Setting Best Practices:
  1. Start with defaults (all weights = 1)
  2. Identify underperforming objectives
  3. Increase weights by 5-10x to see impact
  4. Fine-tune based on results
  5. Document your weight choices

​
Making Constraints Configurable

Design flexible constraints for different scenarios: 
{
  "hardTimeWindow": {
    "from": "08:00",
    "to": "18:00",
    "hard": true
  },
  "preferredTimeWindow": {
    "from": "09:00",
    "to": "12:00",
    "hard": false,
    "weight": 50
  }
}

​
Constraint Patterns

​
Pattern 1: Graceful Degradation

Start strict, then relax if needed:
1

Attempt Strict

{"partialPlanning": false, "timeWindows": {"hard": true}}
2

If Infeasible, Relax

{"partialPlanning": true, "timeWindows": {"hard": false, "weight": 100}}
3

Further Relaxation

{"partialPlanning": true, "timeWindows": {"hard": false, "weight": 10}}

​
Pattern 2: Progressive Tightening

Start loose, then optimize: 
// Phase 1: Get feasible solution
{
  "options": {
    "partialPlanning": true,
    "weights": {"minimizeResourcesWeight": 1}
  }
}

// Phase 2: Optimize quality
{
  "options": {
    "partialPlanning": false,
    "weights": {"minimizeResourcesWeight": 3600}
  }
}

​
Pattern 3: Multi-Objective Balancing

Balance competing objectives: 
{
  "weights": {
    "travelTimeWeight": 1,        // Baseline
    "workloadSpreadWeight": 20,   // Important
    "urgencyWeight": 50,          // More important
    "priorityWeight": 100         // Most important
  }
}

​
Performance Impact

Different constraints have varying computational costs:

​
Low Impact

  • Basic capacity checks
  • Simple time windows
  • Fixed assignments

​
Medium Impact

  • Multi-dimensional capacity
  • Overlapping time windows
  • Skill matching

​
High Impact

  • Complex job relations
  • Many soft constraints
  • Fine-grained time slots
Performance Optimization:
  1. Use hard constraints sparingly
  2. Combine related soft constraints
  3. Set reasonable time windows
  4. Limit job relations complexity
  5. Use appropriate solve time limits

​
Debugging Constraints

When solutions aren’t meeting expectations:
1

Check Feasibility

# Get explanation
GET /v2/vrp/jobs/{id}/explanation
Look for hard constraint violations first.
2

Analyze Weights

Compare soft constraint scores to understand trade-offs.
3

Test Incrementally

Add constraints one at a time to identify conflicts.
4

Use Partial Planning

Allow some jobs to be unassigned to understand bottlenecks.

​
Best Practices

Constraint Design Guidelines:
  1. Start Simple: Begin with essential hard constraints only
  2. Validate Early: Test feasibility with a subset of data
  3. Document Rules: Explain why each constraint exists
  4. Monitor Impact: Track how constraints affect solution quality
  5. Iterate: Refine based on real-world results
  6. Balance: Avoid over-constraining - flexibility enables optimization

Scoring System

Deep dive into score calculation

Advanced Constraints

Specific constraint features

Performance Guide

Optimize constraint performance

Unassigned Reasons

Debug constraint violations