Time-Constrained s-t Orienteering Problem

This project solves a time-constrained prize-collecting path planning problem using the Gurobi optimizer. The goal is to find a path that maximizes collected reward (or likelihood) without exceeding a total time budget.

📦 Requirements

• C++17 compatible compiler
• Gurobi Optimizer installed and licensed
• CMake ≥ 3.11
• OpenMP

Make sure the GUROBI_HOME environment variable is set properly:

export GUROBI_HOME=/path/to/gurobi

Build Instructions

mkdir build && cd build
cmake ..
make -j

Run the Solver

./ts <input_csv> <budget> <warm_start_flag>

• <input_csv>: Path to input CSV file with node information (default: ../filtered_GW191127_050227_7dt.csv)
• <budget>: Maximum allowed time (default: 1400)
• <warm_start_flag>: 1 to enable warm-start from a known path, 0 otherwise

Example:

./ts ../filtered_GW191127_050227_7dt.csv 1400 1

Output

• Results (including chosen path, total cost, and total prize) will be printed to stdout.

• They can also be written to a CSV file:

  ../result.csv
  
  

Code Structure

• main.cpp: Entry point, handles argument parsing
• ReadData.cpp: Parses input CSV and loads node information
• ILP_gurobi.cpp: Formulates and solves the ILP using Gurobi
• CMakeLists.txt: Build configuration

Notes

• A valid warm-start path is currently included only for a 1400 budget.