Minimum Latency Problem (MLP)

This repository contains a heuristic solver for the Minimum Latency Problem (MLP) implemented in C++17 and built with the Meson Build System.

The solution approach combines the metaheuristics GRASP, ILS, and RVND.

TODO

• Instance parser
• Feasibility check
• Constructive procedure
• Local search
• Perturbation
• Methaheuristic

Methaheuristics

• GILS (GRASP Iterated Local Search)

Constructive procedure

• Randomized Greedy Construction

Local search

• RVND (Randomized Variable Neighborhood Search)

Neighborhood

• SWAP
• 2-OPT
• OR-OPT

Perturbation

• DOUBLE-BRIDGE:

Getting started

Prerequisites

• Meson Build System
• C++ 17

How to build the project

1. Setup release and debug builds:

meson setup build --buildtype=release
meson setup build_debug --buildtype=debug

2. Compile build:

meson compile -C <build or build_debug>

3. Run:

From the root directory:

./<build or build_debug>/src/asp <instance file path>