Anti-overlapping objectives ineffective for route separation in large VRPTW instances

[shubham441996]

Issue Description

Problem Summary

Despite implementing multiple anti-overlapping strategies using built-in VRP objectives (balance-distance, compact-tour, balance-activities), generated routes exhibit significant geographical overlap, creating inefficient "spaghetti-like" routing patterns that are operationally problematic.

Expected Behavior

Routes should demonstrate clear territorial separation:

• Each vehicle serves orders in distinct geographical areas
• Minimal route crossing and overlap
• Nearby orders clustered to same vehicle
• Compact, territory-based route assignment

Actual Behavior

Current solutions produce highly overlapping routes:

• 80% of route pairs show geographical overlap
• Routes frequently cross each other
• Adjacent orders served by different vehicles
• Poor spatial clustering despite using spatial objectives

Environment

• VRP Solver: Latest version from this repository
• Problem Format: Pragmatic JSON
• Integration: Python via vrp-cli
• Platform: Linux
• Solver Configuration: 1200s timeout, 15000 generations

Dataset Characteristics

• Orders: 1,800 delivery locations
• Service Area: ~50km × 40km urban region
• Constraints: Time windows, vehicle capacity, mandatory breaks
• Vehicle Types: Multiple types with different capacities
• Order Density: High density in urban clusters

Attempted Solutions

1. Basic Anti-Overlapping

{
  "objectives": [
    {"type": "minimize-unassigned"},
    {"type": "minimize-tours"},
    {"type": "balance-distance"},
    {"type": "minimize-cost"}
  ]
}

2. Spatial Clustering

{
  "objectives": [
    {"type": "minimize-unassigned"},
    {"type": "minimize-tours"},
    {"type": "compact-tour", "job_radius": 8000},
    {"type": "balance-distance"},
    {"type": "balance-activities"},
    {"type": "minimize-cost"}
  ]
}

3. Territorial Focus

{
  "objectives": [
    {"type": "minimize-unassigned"},
    {"type": "minimize-tours"},
    {"type": "compact-tour", "job_radius": 7000},
    {"type": "multi-objective", "strategy": {"name": "weighted-sum", "weights": [5, 1]}, "objectives": [
      {"type": "balance-distance"},
      {"type": "minimize-cost"}
    ]}
  ]
}

Parameter Variations Tested

• job_radius: 3km to 15km range
• Objective weights: Various combinations prioritizing spatial objectives
• Fleet size: Both constrained and expanded fleet configurations
• Solver time: 5 minutes to 20 minutes
• Multi-objective strategies: Sum, weighted-sum with different weights

Quantitative Results

Overlap Analysis

Route Overlapping Analysis:
├── Total Routes: 35 (varies by strategy)
└── Verdict: HIGH SPAGHETTI LEVEL

Route Characteristics

Route Distribution:
├── Route Spread: Min=2.1km, Max=15.3km, Avg=8.7km
├── Orders per Route: Min=45, Max=75, Avg=58
└── Center Distances: Too small relative to route spreads

Solution Quality

• ✅ 100% order assignment achieved
• ✅ All constraints satisfied (time win

code.txt

dows, capacity, breaks)

• ✅ Valid solutions generated consistently
• ❌ Poor territorial separation persists across all strategies

Specific Questions

1. Are there objectives specifically designed for territorial/zonal routing beyond compact-tour?

2. Should job_radius parameters be calculated differently for large urban datasets with high order density?

3. Is there a way to enforce non-overlapping geographical zones as hard constraints rather than soft objectives?

4. Would custom constraints be more effective than the current objective-based approach for territorial separation?

5. Are there solver parameters or configuration options that prioritize spatial separation over cost optimization?

Business Impact

This affects real-world logistics operations:

• Driver confusion from frequently intersecting routes
• Inefficient service territories impacting customer relationships
• Operational complexity despite mathematically optimal solutions
• Reduced delivery efficiency in practice

Minimal Reproduction Case

The issue can be reproduced with:

1. Large urban VRP dataset (1000+ orders)
2. High geographical order density
3. Any of the anti-overlapping objective configurations above
4. Standard solver parameters

Request for Guidance

Looking for advice on:

• Enhanced anti-overlapping strategies or undocumented objectives
• Custom constraint implementation for territorial routing
• Parameter tuning recommendations for large urban datasets
• Alternative approaches within the VRP framework

Any guidance on achieving better territorial route separation would be greatly appreciated, as current objective combinations seem insufficient for this use case.

code.txt

vrp_data_DIE_request.json

[reinterpretcat]

Hi,

built-in objectives for reducing overlap are highly experimental. You can develop your own model for your use case by extending the solver when using it as library (not through json format). Here is example of custom objective: https://github.com/reinterpretcat/vrp/blob/master/vrp-core/examples/custom_objective.rs

Check also other examples to understand internal model and how to extend it.