Vehicle Fleet Routing Optimization Framework

This framework implements optimization methods for solving the Capacitated Vehicle Routing Problem (CVRP). It provides a modular architecture supporting both exact Mixed-Integer Linear Programming (MILP) solvers and metaheuristic approaches for fleet routing optimization.

Mathematical Formulation

The Capacitated Vehicle Routing Problem is formulated as a MILP problem where the objective is to minimize total travel distance while satisfying customer demands and vehicle capacity constraints.

Objective Function

Minimize the total distance traveled by all vehicles:

minimize: Σ Σ d_ij * x_ij

where d_ij is the distance between locations i and j, and x_ij is a binary variable indicating whether edge (i,j) is traversed.

Constraints

• Capacity Constraints: Total demand served by each vehicle cannot exceed vehicle capacity
• Visit Constraints: Each customer must be visited exactly once by exactly one vehicle
• Flow Conservation: Vehicles must enter and exit each customer location

Solver Approaches

Mixed-Integer Linear Programming (MILP)

• Exact optimization using IBM CPLEX
• Miller-Tucker-Zemlin (MTZ) subtour elimination formulation
• Guarantees optimal solutions for small to medium instances
• Best for instances requiring provably optimal results

Heuristic Methods

• Google OR-Tools routing library
• Guided Local Search (GLS) metaheuristic
• Efficient for large-scale instances (1000+ customers)
• Provides high-quality solutions in reasonable time

Table of Contents

• Requirements
• Installation
• Quick Start
• Configuration
• Usage
• Project Structure
• Solvers
• Output
• Contributing
• License

Requirements

• Python 3.9 or higher
• OR-Tools (free, open-source)
• IBM CPLEX (optional, requires license) - Available free for academics via IBM Academic Initiative

Installation

1. Python Dependencies

Install required Python packages:

pip install -r requirements.txt

2. Solvers

The framework supports two optimization engines:

OR-Tools

• Free and open-source
• No license required

CPLEX

• Requires IBM CPLEX license
• Available free for academics via IBM Academic Initiative

Quick Start

Run the optimization using the default configuration:

python main.py

This will solve a CVRP instance with 1200 customers using OR-Tools and generate visualizations in the output/ directory.

For quick testing with a smaller instance (10 customers):

# Edit main.py
config = load_config("configs/config_mini.yaml")

To use the CPLEX solver, uncomment the CPLEX solver section in main.py.

Configuration

Configuration files are stored in the configs/ directory in YAML format.

Instance Parameters

Parameter	Description	Default
num_customers	Number of customers to serve	1200
num_vehicles	Maximum number of vehicles	40
vehicle_capacity	Capacity per vehicle (in units)	30
grid_size_km	City grid dimensions (square)	14.17
num_density_centers	Urban cluster centers	5
gaussian_std_km	Standard deviation for urban clusters	1.0
seed	Random seed for reproducibility	0

Example Configuration

instance:
  num_customers: 1200
  num_vehicles: 40
  vehicle_capacity: 30
  grid_size_km: 14.17
  num_density_centers: 5
  gaussian_std_km: 1.0
  edge_band_km: 1.0
  seed: 0

solver:
  use_instance_constraints: true

Usage

Basic Run

python main.py

Custom Configuration

Create a new YAML file in configs/ and load it in main.py:

config = load_config("configs/my_config.yaml")

Project Structure

.
├── main.py                     # Entry point: Orchestrates solver execution
├── run_vrp.py                  # Core logic: Problem setup and solver invocation
├── configs/                    # Configuration files
│   ├── config.yaml            # Default configuration (1200 customers)
│   └── config_mini.yaml       # Test configuration (10 customers)
├── solvers/                    # Solver implementations
│   ├── vrp_solver_ortools.py  # OR-Tools heuristic solver
│   └── vrp_solver_cplex.py    # CPLEX MILP solver
├── utils/                      # Utility modules
│   ├── config_loader.py       # YAML configuration loader
│   ├── instance.py            # VRP instance generator
│   └── plot_utils.py          # Visualization utilities
├── output/                     # Results directory (auto-generated)
│   └── run_TIMESTAMP/         # Timestamped results
└── requirements.txt           # Python dependencies

Solvers

CPLEX Solver (MILP)

Method: Mixed-Integer Linear Programming
Formulation: Miller-Tucker-Zemlin (MTZ) subtour elimination constraints
Approach: Branch-and-cut exact optimization

The CPLEX solver formulates the CVRP as a MILP and uses exact optimization algorithms to find provably optimal solutions. The MTZ formulation introduces additional variables u_i to eliminate subtours through the constraints:

u_i - u_j + Q*x_ij ≤ Q - q_j  for all i,j ∈ customers

where Q is vehicle capacity and q_j is customer j's demand.

Use Cases:

• Small to medium instances (< 100 customers)
• When optimal solutions are required
• Academic research requiring optimality guarantees

Performance:

• Provides optimality certificates
• Runtime grows exponentially with problem size
• May require hours for large instances

OR-Tools Solver (Heuristic)

Method: Metaheuristic optimization
Algorithm: Guided Local Search (GLS)
Initial Solution: Path Cheapest Arc strategy
Time Limit: 60 seconds (configurable)

The OR-Tools solver uses constraint programming combined with local search metaheuristics. GLS escapes local optima by temporarily penalizing features of the current solution, allowing exploration of the solution space.

Use Cases:

• Large-scale instances (> 100 customers)
• When fast solutions are needed
• Production environments requiring reliability

Performance:

• Finds high-quality solutions in seconds to minutes
• Typically within 1-5% of optimal for medium instances
• Scales well to 1000+ customer problems

Output

Results are saved in output/run_TIMESTAMP/solver_name/ containing:

Generated Files

city_plot.png

• Customer distribution visualization
• Urban clusters (Gaussian) and rural customers (uniform)
• Depot location and density centers

routes_plot.png

• Optimized vehicle routes
• Each route shown in different color
• Depot and customer nodes

summary.json

• Solver name and configuration
• Total distance traveled
• Number of vehicles used
• Problem parameters

Example Output

{
    "solver": "ortools",
    "total_distance": 1234.56,
    "vehicles_used": 35,
    "params": {
        "num_customers": 1200,
        "num_vehicles": 40,
        "vehicle_capacity": 30
    }
}

Results & Performance

Small Instance (config_mini.yaml)

• 10 customers, 6 vehicles
• OR-Tools: < 1 second
• CPLEX: < 5 seconds
• Both achieve optimal solutions

Large Instance (config.yaml)

• 1200 customers, 40 vehicles
• OR-Tools: ~60 seconds (near-optimal)
• CPLEX: May require hours (exact optimal)

Extending the Framework

This framework is designed to be extensible. You can add new solvers, constraints, or optimization objectives by following the modular architecture.

Adding a New Solver

1. Create a new file in solvers/: vrp_solver_mysolver.py

2. Implement a function with this signature:

def solve_cvrp_mysolver(coords, distance, demand, vehicle_capacity, num_vehicles, depot):
    # Your solver implementation
    return {
        "routes": [[0, 1, 2, 0], [0, 3, 4, 0]],
        "total_distance": 123.45,
        "vehicles_used": 2
    }

3. Call it in main.py:

run_solver(
    solver_name="mysolver",
    config=config,
    solver_fn="solvers.vrp_solver_mysolver.solve_cvrp_mysolver"
)

License

This project is licensed under the MIT License - see the LICENSE file for details.