Skip to content

Latest commit

 

History

History
48 lines (37 loc) · 4.86 KB

README.md

File metadata and controls

48 lines (37 loc) · 4.86 KB
Raw

Column-Generation-VRP-with-Custom-Labeling-Algorithm

This repository is part of my master’s thesis, "Enhancing Algorithm Efficiency for the Vehicle Routing Problem: A Heuristic Approach Based on Column Generation". The project focuses on improving algorithmic efficiency for solving the Vehicle Routing Problem (VRP) through a novel heuristic approach, utilizing column generation combined with a custom labeling algorithm.

The original research paper is available on this repository, click here to access it..

This project code is written and maintained by me, however, I would like to thank my supervisor, Prof. Alberto Santini, for his help.

If you have any questions or find any issues, please contact me at [email protected].

Requirements

  • C++ version 23 or later
  • Valid Gurobi library and license
  • Boost Graph Library

Usage

  1. Clone this repository: 
    git clone https://github.com/YUTAI-K/Column-Generation-VRP-with-Custom-Labeling-Algorithm.git
  2. Build the project. This project requires the boost graph library, which can be installed by following the instructions on its official website, or by using a package manager like apt for linux, Homebrew for macOS, or vcpkg for Windows.
  3. For a detailed explanation of the methods and algorithms used, please consult the paper.

Running the application

When executed, the console applciation will:

  • Prompts the user to input the number of customers to serve.
  • Prompts the user to input an integer for seeding, which guarantees reproducibility.
  • Asks the user to specify the capacity limit for the vehicles, instructions are provided.
  • Generates a random graph including customers and the starting & ending depot. Provides visualization.
  • Offers a choice among five algorithms, some of which I developed myself.
  • Solves the problem and reports the results.

Project Structure

The project source code is organized as follows:

  • src: Contains the source code.

    • main.cpp: Contains the main function of the project.
    • Graph.h: Defines basic graph structures, including functions to generate random graph instances and visualization/preprocessing functions.
    • Route.h: Contains route-related data structures and functions.
    • Solver.h: Defines the "Solver" structure used to solve VRP problems with different algorithms. Each algorithm is associated with a different method in this structure.
    • ShortestPath.h: Defines the "ShortestPathSolver" structure, a part of the "Solver" structure, used to solve the subproblem of the column generation algorithm, which is a resource-constrained shortest path problem with self-defined labeling algorithms. Each algorithm is associated with a unique method.
    • ElementaryLabel.h: Defines the structures and utils used in the "ShortestPathSolver" structure, including labels and resources.

  • CMakeLists.txt & CMakeSettings.json: The CMake files necessary for configuring the build conditions for the project.

  • FindGurobi.cmake: The CMake file necessary to find Gurobi on your computer, please visit the Gurobi Support Website for details.

  • vcpkg.json: The vcpkg file used to manage dependencies.