- Greedy Solution
- Local Search (Run on each vehicle separately; search restricted to the selected vehicle's initial route) (LS)
- Local Search (LS)
- Tabu Search (TS)
- Genetic Algorithm (GA)
- Simulated Annealing (SA)
- Hybrid Algorithms (Using the solution found using one of the algorithms above as the input/starting point for another) (HA)
git clone https://github.com/vss2sn/cvrp.git
cd cvrp
mkdir build
cd build
cmake .. && make -j4
./cvrp
- Algorithms
- Instructions
- Table of contents
- Code Overview
- Documentation
- Overview of Algorithm Implementations
- Notes
- Visualization
- TODOs
- The code contains
Problem
,Solution
andVehicle
classes. Each algorithm implementation has its own class and inherits theSolution
class. - 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. - A base class called
Solution
has been created to store the basic elements of the solution in a user friendly format. This includes avector
of instances of theVehicle
class. - 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. - The
Solution
class also contains a virtual method calledSolve()
. Each algorithm class overrides theSolve()
method. - The
Solution
class also contains a method calledPrintSolution(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 can be found on GitHub pages.
- It has been created using
Doxygen
, and pip3 packagesSphinx
(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
) andm2r
.
For a brief overview on the implementations of the algorithms, please refer to this document.
- The documentation for private functions (such as operators in the
GASolution
class) has been made available to aid understanding. - 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
.
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
.
- Read in problem from a file.
- Consider adding plot of best solution cost vs time.
- Consider adding savings algorithm
- Consider adding maximum distance constraint
- Consider modifying to allow heterogeneous vehicles.
- Consider adding multiple knapsack solver for initial solution if greedy solution fails, as well as a sanity check to check whether demand exceeds supply.
- Consider adding in a clustering algorithm to break large problems into a
vector
of small problems. - Refactor genetic algorithm to use a struct