Capacitated Vehicle Routing Problem (CVRP) Solver

This project contains an implementation to solve the Capacitated Vehicle Routing Problem (CVRP), a well-known combinatorial optimization problem. The goal is to find a set of optimal routes for a fleet of vehicles, originating from a central depot, to serve a set of customers with known demands. The objective is to minimize the total cost (often the total distance) without exceeding the maximum capacity of each vehicle.

---

🎯 Problem Description

The CVRP can be defined as follows:

• There is a single central depot.
• There is a fleet of vehicles, each with a maximum capacity $Q$.
• A set of customers, each with a specific demand $d_i$.
• The goal is to determine a set of routes that:
  1. Start and end at the depot.
  2. Minimize the total distance traveled by all vehicles.
  3. Satisfy the demand of all customers.
  4. Respect the capacity constraint: the total load of each route must not exceed $Q$.

---

🛠️ Installation

To run this project, you need to clone the repository and install the required dependencies.

1. Clone the repository:

   git clone [https://github.com/giulio93/Capacitated-Vehicle-Routing-Problem.git](https://github.com/giulio93/Capacitated-Vehicle-Routing-Problem.git)
   cd Capacitated-Vehicle-Routing-Problem

2. Create a virtual environment (recommended):

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

3. Install dependencies: This project uses [Google OR-Tools] and other libraries. Install them using pip. (Modify this section if you use different libraries, e.g., Gurobi, CPLEX, or just numpy/pandas)

   pip install -r requirements.txt

   If you don't have a requirements.txt file, list the necessary packages here:

   pip install ortools pandas matplotlib

---

🚀 Usage

To run the solver, launch the main script from the command line.

(Replace main.py with your main script's name and update the arguments)

python main.py --file "data/instance_A.vrp"

Possible Arguments:

-- file: (Required) Path to the problem instance file (e.g., in TSPLIB .vrp format).

-- num_vehicles: (Optional) Maximum number of vehicles to use.

-- timeout: (Optional) Maximum execution time in seconds for the solver.

Example Output

Running the script will display the optimal (or sub-optimal) solution found, including:

Total cost (distance): The total value of the objective function.

Vehicle Routes: The list of customers served by each vehicle and the transported load.

Solution found!
Total distance: 450.8
--------------------
Vehicle 1:
Route: Depot -> Customer 3 -> Customer 5 -> Customer 12 -> Depot
Load: 95/100
Distance: 120.2
--------------------
Vehicle 2:
Route: Depot -> Customer 1 -> Customer 8 -> Depot
Load: 70/100
Distance: 90.5
--------------------

...