Genetic Algorithm for Electric Vehicle Routing Problem (EVRP)

A genetic algorithm implementation for solving the Electric Vehicle Routing Problem (EVRP) with multiple depots, energy constraints, and charging stations.

Overview

This project implements a genetic algorithm to solve the EVRP, which extends the classic Vehicle Routing Problem (VRP) by incorporating:

• Electric vehicles with limited battery capacity
• Multiple depots for vehicle operations
• Charging stations where vehicles can recharge their batteries
• Capacity constraints (vehicle load limits)
• Energy consumption during travel

The algorithm optimizes routes to minimize both total distance traveled and total charging time while respecting all constraints.

Problem Description

Given:

• A set of depots where vehicles start and end their routes
• A set of customers that must be visited (each with a demand)
• A set of charging stations where vehicles can recharge
• A fleet of electric vehicles with:
  • Limited cargo capacity
  • Limited energy/battery capacity
  • Energy consumption rate (per unit distance)

Find routes that:

• Visit all customers exactly once
• Respect vehicle capacity constraints
• Respect energy constraints (vehicles must reach charging stations/depot before running out of energy)
• Minimize the weighted combination of total distance and total charging time

Project Structure

Genetic-Algorithm-RSPKLU/
├── main.ipynb                  # Main genetic algorithm workflow
├── generatePopulation.py       # Population initialization and EVRP file parsing
├── fitness.py                  # Fitness function calculation
├── selection.py                # Selection strategies (Elitism + Tournament)
├── crossover.py                # BCRC crossover operator
├── mutation.py                 # Mutation operators (Inter-depot & Intra-depot)
├── data/
│   └── E-n32-k6-s7-edited.evrp # EVRP problem instance
└── README.md                   # This file

Key Components

1. Population Generation (generatePopulation.py)

• Parses EVRP format files
• Generates initial population with energy-aware route construction
• Ensures routes are feasible (respect capacity and energy constraints)
• Supports multi-depot assignments

Key Functions:

• parse_evrp_file(filepath): Parses EVRP problem instance file
• generate_initial_chromosome(evrp_data): Creates a single feasible chromosome
• generate_initial_population(evrp_data, population_size): Creates initial population

2. Fitness Function (fitness.py)

• Evaluates solution quality based on:
  • Total distance traveled (D)
  • Total charging time (C)
  • Fitness = w1 * D + w2 * C (default: w1=0.6, w2=0.4)
• Penalizes infeasible solutions (violates capacity or energy constraints)
• Returns detailed metrics (distance, charging time) when requested

Key Functions:

• fitness_function(chromosome, distance_matrix, evrp_data, ...): Calculates fitness score

3. Selection (selection.py)

• Elitism: Preserves best individuals directly
• Tournament Selection: Selects parents through competitive tournaments
• Combines both strategies for balanced exploration/exploitation

Key Functions:

• selection(population, fitness_scores, elite_size, tournament_size): Main selection operator
• get_elites(...): Extracts elite individuals
• run_tournament(...): Executes tournament selection

4. Crossover (crossover.py)

• BCRC (Best Cost Route Crossover): Route-based crossover operator
• Selects a random customer from parent 1
• Removes it from parent 2's routes
• Inserts it at the best position (lowest cost increase) across all routes
• Maintains route structure and feasibility

Key Functions:

• crossover(parent1, parent2, evrp_data, distance_matrix): Main crossover operator
• bcrc_crossover(...): Implements BCRC logic

5. Mutation (mutation.py)

Two types of mutations:

1. Inter-depot Mutation:

   • Identifies "border customers" (customers near multiple depots)
   • Moves customers between depots based on distance criteria
   • Helps explore multi-depot solution space

2. Intra-depot Mutation:

   • Swap: Exchanges positions of two customers
   • Inversion: Reverses a segment of the route
   • Insertion: Moves a customer to a different position
   • Improves route quality within the same depot

Key Functions:

• apply_mutation(chromosome, evrp_data, mutation_probability, beta): Main mutation operator
• inter_depot_mutation(...): Moves customers between depots
• intra_depot_mutation(...): Mutates routes within a depot

Data Format

The EVRP file format includes:

NAME: instance-name
TYPE: EVRP
VEHICLES: <number>
CAPACITY: <vehicle_capacity>
ENERGY_CAPACITY: <battery_capacity>
DIMENSION: <total_nodes>
STATIONS: <number_of_stations>

NODE_COORD_SECTION
<node_id> <x_coord> <y_coord>
...

DEMAND_SECTION
<node_id> <demand>
...

STATIONS_COORD_SECTION
<station_id>
...

DEPOT_SECTION
<depot_id>
...

Usage

Running the Genetic Algorithm

Open main.ipynb in Jupyter Notebook and execute the cells. The main workflow:

1. Initialize: Load EVRP data and create distance matrix
2. Generate Population: Create initial population of feasible solutions
3. Evolution Loop (for each generation):
   • Evaluate fitness
   • Select parents (Elitism + Tournament)
   • Create offspring via crossover
   • Apply mutations
   • Evaluate offspring
   • Replace population (keep best individuals)

Configuration Parameters

# Population parameters
pop_size = 50                    # Population size
max_generations = 100            # Maximum generations

# Selection parameters
elite_size = 5                   # Number of elite individuals
tournament_size = 3              # Tournament size

# Genetic operators
crossover_rate = 0.8             # Crossover probability
mutation_rate = 0.1              # Mutation probability

# Fitness weights
w1 = 0.6                         # Distance weight
w2 = 0.4                         # Charging time weight

# Energy parameters
battery_capacity = 162           # Energy capacity
consumption_rate = 1.0           # Energy per unit distance
charging_rate = 1.0              # Recharge rate

Features

• ✅ Multi-depot support: Vehicles can start/end at different depots
• ✅ Energy-aware routing: Routes respect battery capacity constraints
• ✅ Charging station integration: Automatic insertion of charging stops
• ✅ Capacity constraints: Respects vehicle load limits
• ✅ Multiple mutation types: Inter-depot and intra-depot mutations
• ✅ Visualization: Route visualization in Jupyter notebooks
• ✅ Invalid solution handling: Replaces infeasible solutions automatically

Algorithm Workflow

1. INITIALIZATION
   ├── Parse EVRP file
   ├── Build distance matrix
   └── Generate initial population

2. EVALUATION
   └── Calculate fitness for all chromosomes

3. EVOLUTION (repeat for max_generations)
   ├── SELECTION
   │   ├── Elitism: Keep best individuals
   │   └── Tournament: Select parents
   ├── CROSSOVER
   │   └── BCRC: Create offspring
   ├── MUTATION
   │   ├── Inter-depot: Move customers between depots
   │   └── Intra-depot: Optimize routes within depot
   ├── EVALUATION
   │   └── Calculate fitness for offspring
   └── REPLACEMENT
       └── Keep best individuals (elitism)

4. TERMINATION
   └── Return best solution found

Example Output

=== Data EVRP ===
Depot: [1, 31, 32]
Customers: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23]
Stations: [24, 25, 26, 27, 28, 29, 30]
Total Vehicles: 6
Capacity: 4500
Energy Capacity: 162

GENERATION 1/100
→ Selection: Choosing parents...
→ Crossover: Creating offspring...
→ Mutation: Mutating offspring...
→ Evaluation: Calculating fitness...
→ Replacement: Elitism strategy...

Best Fitness: 125.43
Best Distance: 112.50
Best Charging Time: 31.20

Requirements

• Python 3.x
• Jupyter Notebook
• NumPy (for distance calculations)
• Matplotlib (for visualization)

References

This implementation is based on genetic algorithm techniques for solving vehicle routing problems with electric vehicles, incorporating:

• Multi-depot routing strategies
• Energy constraint handling
• Border customer identification for inter-depot mutations
• BCRC crossover for route-based problems

License

This project is provided as-is for educational and research purposes.

Notes

• The algorithm uses a delimiter encoding (|) to separate routes in chromosomes
• Nodes are represented as integers (1-indexed)
• Fitness values are minimized (lower is better)
• Invalid solutions receive a large penalty (1e6) and are replaced automatically