iRB-Lab/py-ga-VRPTW

What it solves

This project provides a Python implementation to solve the Vehicle Routing Problem with Time Windows (VRPTW). It aims to find optimal routes for a fleet of vehicles to deliver goods to a set of customers, ensuring that each customer is visited within a specific time window and that vehicle capacity limits are not exceeded.

How it works

The project uses a Genetic Algorithm (GA) to evolve potential routing solutions. It represents a route as an "individual" (chromosome) consisting of a sequence of customers. The process involves:

• Decoding: Converting the sequence of customers into actual sub-routes based on vehicle capacity and time constraints.
• Evaluation: Calculating the fitness of a solution based on transportation costs, vehicle start-up costs, and penalties for arriving too early (wait cost) or too late (delay cost).
• Selection: Using Roulette Wheel Selection to choose individuals for the next generation.
• Crossover: Applying Partially Matched Crossover (PMX) to combine traits from two parent solutions.
• Mutation: Using an inverse operation to randomly reverse segments of a route to maintain genetic diversity.

Who it’s for

This tool is designed for those interested in logistics engineering, operations research, or students studying genetic algorithms and their application to combinatorial optimization problems.

Highlights

• Benchmark Support: Includes support for Solomon's VRPTW benchmark problems (Random, Clustered, and mixed types).
• Flexible Data Input: Supports problem instances in both text and JSON formats, with a utility to convert between them.
• Customizable Instances: Allows users to define and run the algorithm on their own customized routing data.
• Detailed GA Implementation: Provides clear implementations of the core GA components: selection, crossover, mutation, and fitness evaluation.