Running Algorithms on dataset: rc108.txt
Best-Known Solution (BKS) Route Cost: 1114.2
BKS solution:
Route #1: 2 6 7 8 46 4 45 5 3 1 100
Route #2: 12 14 47 17 16 15 13 9 11 10
Route #3: 33 32 30 28 26 27 29 31 34 93
Route #4: 41 42 44 43 40 38 37 35 36 39
Route #5: 61 81 94 71 72 54 96
Route #6: 64 51 76 89 18 48 19 20 66
Route #7: 65 83 57 24 22 49 21 23 25 77
Route #8: 69 98 88 53 78 73 79 60 55 70 68
Route #9: 82 99 52 86 87 59 97 75 58 74
Route #10: 90
Route #11: 92 95 67 62 50 63 85 84 56 91 80
Hybrid Genetic Search (HGS) Route Cost: 1114.2
HGS solution:
Route #1: 12 14 47 17 16 15 13 9 11 10
Route #2: 82 99 52 86 87 59 97 75 58 74
Route #3: 65 83 57 24 22 49 21 23 25 77
Route #4: 64 51 76 89 18 48 19 20 66
Route #5: 92 95 67 62 50 63 85 84 56 91 80
Route #6: 33 32 30 28 26 27 29 31 34 93
Route #7: 61 81 94 71 72 54 96
Route #8: 41 42 44 43 40 38 37 35 36 39
Route #9: 2 6 7 8 46 4 45 5 3 1 100
Route #10: 90
Route #11: 69 98 88 53 78 73 79 60 55 70 68
Guided Local Search (GLS) Route Cost: 1266.9
GLS solution:
Route #1: 71 72 44 43 40 38 37 35 36 39
Route #2: 98 82 90 53 78 73 79 2 60
Route #3: 92 67 32 30 28 26 27 29 31 34 93
Route #4: 65 99 24 22 20 49 21 23 25 77
Route #5: 95 51 76 89 33 50 62 91 80
Route #6: 12 14 47 17 16 15 13 9 11 10
Route #7: 88 6 7 8 46 4 45 5 3 1 100 55
Route #8: 69 70 61 81 94 96 54 41 42 68
Route #9: 83 52 57 86 87 59 97 75 58 74
Route #10: 64 19 48 18 63 85 84 56 66
Ant Colony Optimization (ACO) Route Cost: 1321.8459204561746
ACO solution:
Route #1: 69 98 88 82 99 52 86 74 57 83 66 91
Route #2: 65 64 51 76 89 85 63 62 56 80
Route #3: 90 53 73 79 78 60 55 68
Route #4: 33 28 30 32 34 31 29 27 26
Route #5: 72 71 93 94 81 61 54 96 100 70
Route #6: 2 45 5 8 7 6 46 4 3 1
Route #7: 41 42 44 38 39 40 36 35 37 43
Route #8: 19 21 23 18 48 49 22 20 24 25
Route #9: 12 14 47 17 16 15 11 10 9 13
Route #10: 59 58 87 97 75 77
Route #11: 92 95 84 50 67
Simulated Annealing (SA) Route Cost: 1237.620141359753
SA solution:
Route #1: 7 8 46 4 45 5 3 1 100 55
Route #2: 64 51 76 89 63 85 84 56 91
Route #3: 69 98 53 12 15 16 17 47 14
Route #4: 90 82 9 13 11 10
Route #5: 61 42 44 40 39 38 37 35 36 43
Route #6: 65 52 86 77 25 23 57
Route #7: 88 60 78 73 79 6 2 70 68
Route #8: 92 67 62 34 50 94 96
Route #9: 99 87 59 97 75 58 74
Route #10: 83 24 22 19 18 48 21 49 20 66
Route #11: 81 93 71 72 41 54
Route #12: 95 33 32 30 28 26 27 29 31 80
Algorithms - - No. of Routes - - Costs - - Gap(%) - - Runtime(seconds)
BKS - - - - - - 11 - - - - - - - - - - 1114.2 - - - -
HGS - - - - - - 11 - - - - - - - - - - 1114.2 - - 0.0 - - - - 300.137736082077
GLS - - - - - - 10 - - - - - - - - - - 1266.9 - - 13.7 - -- - 300.0492959022522
ACO - - - - - - 11 - - - - - - - - - - 1321.8 - - 18.63 - - - 877.1980187892914
SA - - -- - - - 12 - - - - - - - - - - 1237.6 - - 11.08 - - - 416.80780506134033
This repository provides a comprehensive comparison and implementation of several heuristic and metaheuristic algorithms for solving the Vehicle Routing Problem with Time Windows (VRPTW). Developed as part of a master's thesis, the project offers reproducible experiments, insightful analysis, and visualizations of solutions across different algorithms.
- Project Overview
- Features
- Technologies Used
- Project Structure
- Algorithms Implemented
- How to Run
- Visualizations
- Results & Comparison
- Screenshots
- Keywords
- Contact
The VRPTW is a classic combinatorial optimization problem that extends the Vehicle Routing Problem (VRP) by adding time windows for customer visits. This project benchmarks and compares several well-known algorithms on standard datasets (e.g., Solomon's instances) and visualizes their performance.
Algorithms Compared:
- Hybrid Genetic Search (HGS)
- Guided Local Search (GLS)
- Ant Colony Optimization (ACO)
- Simulated Annealing (SA)
- Modular implementation for each algorithm
- Benchmarking against Best-Known Solutions (BKS)
- Visual comparison of routes and costs
- Reproducible experiments via fixed seeds (with options to randomize)
- Interactive Jupyter notebook for experiment walkthroughs
- Easily extensible for new algorithms or datasets
- Python 3.x: Core programming language
- NumPy, pandas: Data manipulation and analysis
- matplotlib: Visualization of routes and performance
- OR-Tools: Used in GLS for routing optimization
- pyVRP: Framework for HGS implementation
- Jupyter Notebook: Interactive analysis and visualization
.
├── main.py # Main script to run all algorithms and generate results
├── solver.ipynb # Jupyter Notebook for interactive exploration
├── aco/ # Implementation of Ant Colony Optimization
├── gls/ # Implementation of Guided Local Search
├── sa/ # Simulated Annealing code
├── hgs/ # Hybrid Genetic Search code
├── bks.py # Processes Best-Known Solutions (BKS)
├── plot.py # Visualization utilities
├── data/ # Benchmark datasets (Solomon .txt and .sol)
├── requirements.txt # Python dependencies
├── README.md # Project documentation
A metaheuristic that evolves a population of solutions using selection, crossover, and mutation. Implementation is based on the pyVRP library and supports customizable stopping criteria.
Example Usage:
from pyvrp import Model, read
from pyvrp.stop import MaxRuntime
def solve_with_hgs(input_path, runtime):
INSTANCE = read(input_path, instance_format="solomon", round_func="trunc1")
model = Model.from_data(INSTANCE)
result = model.solve(stop=MaxRuntime(runtime), seed=0) # Can randomize 'seed'
return resultEnhances local search by penalizing overused solution components, implemented using OR-Tools, and allows for time-limited optimization.
Example Usage:
from gls.base_solver import Solver
from gls.instance_loader import load_instance
def solve_with_gls(input_path, runtime):
data = load_instance(input_path)
solver = Solver(data)
solver.create_model()
solver.solve_model({"time_limit": runtime})
return solver.get_solution()A population-based metaheuristic that simulates ant foraging behavior using pheromone trails to discover optimal routes.
A probabilistic algorithm that explores the solution space by occasionally accepting worse solutions, allowing escape from local minima.
python -m venv .venv
# Activate the virtual environment:
# Linux/Mac:
source .venv/bin/activate
# Windows:
.venv\Scripts\activate
pip install -r requirements.txtTo run all algorithms and generate comparative results:
python main.pyFor a step-by-step interactive analysis:
jupyter notebook solver.ipynb- Visualizations of the generated routes and algorithm performance are created using
matplotlib. You can customize these plots inplot.py. - Results are saved and/or displayed as images for direct comparison.
The following table summarizes the results of each algorithm on the rc108.txt dataset:
| Algorithm | Route Cost | No. of Routes | Gap (%) | Runtime (s) |
|---|---|---|---|---|
| BKS | 1114.2 | 11 | 0 | - |
| HGS | 1114.2 | 11 | 0.0 | 300.14 |
| GLS | 1266.9 | 10 | 13.7 | 300.05 |
| ACO | 1321.8 | 11 | 18.63 | 877.20 |
| SA | 1237.6 | 12 | 11.08 | 416.81 |
See the detailed solution routes and costs for each algorithm in the section below.
All images are retained from the original README and illustrate the route solutions for each algorithm.
- Vehicle Routing Problem (VRP)
- Time Windows
- Metaheuristics
- Genetic Algorithm
- Ant Colony Optimization
- Simulated Annealing
- Guided Local Search
- Solomon Dataset
- Routing Optimization
- Visualization
- Benchmarking
For questions, feedback, or collaboration:
Arnob Mahmud
Email: [email protected]
Thank you for exploring this project!