Vehicle Routing Problem Solver using Genetic Algorithm

A Python implementation of a Genetic Algorithm to solve the Vehicle Routing Problem (VRP). This project demonstrates how to find optimal or near-optimal routes for multiple vehicles to serve a set of locations from a central depot.

Features

• Solves the Capacitated Vehicle Routing Problem (CVRP)
• Multi-objective optimization (minimize total distance and balance vehicle loads)
• Interactive visualization of routes
• Configurable number of locations and vehicles
• Detailed evolution statistics

Requirements

• Python 3.7+
• NumPy
• Matplotlib
• DEAP (Distributed Evolutionary Algorithms in Python)

Installation

1. Clone the repository:

   git clone https://github.com/Rajdeep-naha/VRP-Genetic_Algorithm.git
   cd VRP-Genetic_Algorithm

2. Create and activate a virtual environment (recommended):

   python -m venv venv
   source venv/bin/activate  # On Windows: venv\Scripts\activate

3. Install the required packages:

   pip install -r requirements.txt

Usage

Run the main script:

python main.py

The program will:

1. Generate random locations
2. Run the genetic algorithm optimization
3. Display the best routes found
4. Show visualizations of the routes and evolution progress

Configuration

You can modify the following parameters in vrp_ga/config.py:

• NUM_LOCATIONS: Number of locations to visit (default: 10)
• NUM_VEHICLES: Number of vehicles available (default: 3)
• MAP_WIDTH and MAP_HEIGHT: Size of the map (default: 100x100)
• POPULATION_SIZE: Size of the genetic algorithm population (default: 100)
• GENERATIONS: Number of generations to run (default: 50)
• CROSSOVER_RATE: Probability of crossover (default: 0.8)
• MUTATION_RATE: Probability of mutation (default: 0.2)

Output

The program will display:

• Progress of the genetic algorithm
• Best solution found with total distance and balance metrics
• Visual representation of the routes
• Evolution of the population's fitness over generations

Example Output

Generating random locations...
Generated 10 locations

Setting up genetic algorithm...

Starting genetic algorithm optimization...
gen     nevals  avg                             min
0       100     [717.2366877     71.20440608]  [461.09477629   10.02940893]
...

Optimization complete!
Best solution found with total distance: 421.15 and balance: 8.24

Vehicle Routes: --------------------------------------------------
Vehicle 1: Depot -> Loc 2 -> Loc 5 -> Loc 8 -> Depot
Vehicle 2: Depot -> Loc 1 -> Loc 3 -> Loc 7 -> Depot
Vehicle 3: Depot -> Loc 4 -> Loc 6 -> Loc 9 -> Depot

Generating visualizations...

Project Structure

• main.py: Entry point of the application
• vrp_ga/: Main package
  • __init__.py: Package initialization
  • config.py: Configuration parameters
  • data.py: Data generation and utility functions
  • genetic_algorithm.py: Core genetic algorithm implementation
  • visualization.py: Plotting and visualization functions
• requirements.txt: List of Python dependencies

License

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

Author

Rajdeep Naha

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.