Capacitated Vehicle Routing Problem

This repository contains algorithms to solve the CVRP (Capacitated Vehicle Routing Problem) in C++

Build Status

Algorithms:

  1. Greedy Solution
  2. Local Search (Run on each vehicle separately; search restricted to the selected vehicle’s initial route) (LS)
  3. Local Search (LS)
  4. Tabu Search (TS)
  5. Genetic Algorithm (GA)
  6. Simulated Annealing (SA)
  7. Hybrid Algorithms (Using the solution found using one of the algorithms above as the input/starting point for another) (HA)

To build and run:

git clone https://github.com/vss2sn/cvrp.git
cd cvrp
mkdir build
cd build
cmake .. && make -j4
./cvrp

Code Overview:

  1. The code contains Problem, Solution and Vehicle classes. Each algorithm implementation has its own class and inherits the Solution class.
  2. The problem is setup using the Problem class which specifies the number of nodes (centres/dropoff points), maximum demand, number of vehicles, their capacity, the grid range and the type of distribution. The demand for each centre as well as its location is randomly generated.
  3. A base class called Solution has been created to store the basic elements of the solution in a user friendly format. This includes a vector of instances of the Vehicle class.
  4. The Vehicle class stores the vehicle id, the route it takes, the total capacity, the number of units still left in the vehicle, and the cost associated with the vehicle’s route. The << operator is overloaded to show the status of the node and vehicle respectively. PrintVehicleRoute() prints only the route of the vehicle.
  5. The Solution class also contains a virtual method called Solve(). Each algorithm class overrides the Solve() method.
  6. The Solution class also contains a method called PrintSolution(option) with the an input option (option) to print vehicles’ statuses or routes in addition to the total cost and validity of the solution.

Documentation:

  1. Documentation can be found on GitHub pages.
  2. It has been created using Doxygen, and pip3 packages Sphinx (sphinx==1.8.31), Breathe (breathe==4.12.0), Exhale (exhale==0.2.2),Read the Docs Sphinx Theme (sphinx_rtd_theme==0.4.3) and m2r.

Overview of Algorithm Implementations

For a brief overview on the implementations of the algorithms, please refer to this document.

Notes:

  1. The documentation for private functions (such as operators in the GASolution class) has been made available to aid understanding.
  2. Custom hybrid algorithms, that involve feeding in the solution of 1 algorithm to another can easily be implemented, as the structure allows the extraction of solution from the algorithm classes. An example is shown at the end of main.cpp.

Visualization:

This repository (optionally) uses SFML for visualization. It can be installed using sudo apt install libsfml-dev. To run with SFML, include the header file graphics_utils.hpp in main.cpp, and use the function DisplaySolution(<solution>), passing in the solution to e displayed, and build the code with cmake .. -DDISPLAY_SOLUTION=ON, or modify its value in ProjectSpecificSettings.cmake.

TODOs:

  1. Read in problem from a file.
  2. Consider adding plot of best solution cost vs time.
  3. Consider adding savings algorithm
  4. Consider adding maximum distance constraint
  5. Consider modifying to allow heterogeneous vehicles.
  6. Consider adding multiple knapsack solver for initial solution if greedy solution fails, as well as a sanity check to check whether demand exceeds supply.
  7. Consider adding in a clustering algorithm to break large problems into a vector of small problems.
  8. Refactor genetic algorithm to use a struct

Contents:

Indices and tables