Skip to content

Latest commit

 

History

History
54 lines (42 loc) · 1.83 KB

README.md

File metadata and controls

54 lines (42 loc) · 1.83 KB

Greedy Randomized Adaptive Search Procedure for Close Enough Orienteering Problem

Overview

Greedy Randomized Adaptive Search Procedure was extended for solving Close Enough Orienteering Problem. The method has been introduced in this article.

@inproceedings{stefanikova20greedy,
  title={Greedy randomized adaptive search procedure for close enough orienteering problem},
  author={{\v{S}}tefan{\'\i}kov{\'a}, Petra and V{\'a}{\v{n}}a, Petr and Faigl, Jan},
  booktitle={Proceedings of the 35th Annual ACM Symposium on Applied Computing},
  pages={808--814},
  year={2020},
  doi={10.1145/3341105.3374010}
}

CEOP Example

CEOP example

Instruction to build from source

The script dowlownds and install all needed libraries.

./install.sh

Instruction to run GRASP-based algorithm

To run the code, the sources (C++11) need to be compiled using make, see example.sh. (Tested on Ubuntu 18.04).

make

./grasp_ceop \
    --gui=cairo \
    --problem=./etc/op-chao_set64-rad0.5.txt \
    --budget=40 \
    --output=results.example \
    --waypoint-optimization=0 \
    --wait-to-click=0

Configuration

All possible configurations are shown by ./grasp_ceop -h. The configuration can be determined at launch by flags or in the grasp_ceop.cfg file.

The most important configuration flags:

FLAG VALUES DESCRIPTION
gui cairo, none enable/disable graphics visualization
problem problem file from ./etc directory problem desription file (position of nodes)
budget positive number OP budget
waypoint-optimization 0, 1 enable/disable waypoint optimization in the Local Search Phase
wait-to-click 0, 1 enable/disable waiting for click after redrawing new best path