Travelling Thief Problem Solver

This project is a Crystal implementation of heuristic algorithms to solve the Travelling Thief Problem [1]

Environment

Prerequisites

• Linux OS
  • Debian
  • Ubuntu
  • Manjaro
• Crystal 0.32.1

Algorithms

• RES_GLS (default) [2]
• DMA

Initialization

Plan

• empty
• greedy

Tour

• nearest
• lkh

Compilation

crystal build --release  program/ttp-cli.cr 

Usage

./ttp-cli --if <instance.ttp> --lkh-file <lkh.exe> [options] 


  --if=                [*]       Instance to solve
  --of=                [STDOUT]  Output file of the final solution
  --duration=          [60]      Stop criterion in seconds
  --lkh-file=          [*]       LKH library executable
  --tour-init=         [nearest] Tour Initialization heuristic
  --plan-init=         [greedy]  Plan initialization heuristic
  --evo-file=          [-]       Output file of the evolution of the solution 
  --evo-span=          [1]       Time in seconds between evolution measures
  --method=            [resgls]  Algorithms
    * resgls
    * dma
  --min-ls-time=       [1.0]     Minimum time used in local-search
  --min-dist=          [0.5]     Initial distance for penalization
  -v, --version        Show version 
  -h, --help           Show this help

  * required 
  - optional

Examples

Solving the instance 'instance.ttp' using the default algorithm (RES_GLS) using a stopping criterion of 600 seconds. The solution its printed to the standard output.

./ttp-cli --if instance.ttp --duration 600 --lkh-file lkh.exe

Solving the instance 'instance.ttp' with the default algorithm (RES_GLS) using a stopping criterion of 600 seconds. The initial solution is created using the 'nearest' greedy heuristic for the tour and with an 'empty' plan.

./ttp-cli --if instance.ttp --lkh-file lkh.exe --duration 600 --tour-init nearest --plan-init empty

Solve instance 'instance.ttp' with the default algorithm (RES_GLS) and saving the current solution in 'evolution.evo' file, every second 2 seconds.

./ttp-cli --if instance.ttp --lkh-file lkh.exe --evo-file evolution.evo --evo-span 2

Important Notes

• Make sure the "lkh.exe" file is executable: chmod +x lkh.exe the source code for the library (LKH v2.0.9 July 2008) can be found it the authors page LKH
• The TTP data [3] is removed from the instances/ folder. The TTP instances are avaiable at : TTP Instances and solutions

Updates

• 21 Jan 2020 - Update to Crystal 0.32.1 (2019-12-18)

Contact information

nifr91@gmail.com

References

[1] M. R. Bonyadi, Z. Michalewicz, and L. Barone, “The travelling thief problem: the first step in the transition from theoretical problems to realistic problems,” in Evolutionary Computation (CEC), 2013 IEEE Congress on. IEEE, 2013, pp. 1037–1044.

[2] A Guided Local Search Approach for the Travelling Thief Problem

[3] S. Polyakovskiy, M. R. Bonyadi, M. Wagner, Z. Michalewicz, and F. Neumann, “A comprehensive benchmark set and heuristics for the traveling thief problem,” in Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation. ACM, 2014, pp. 477–484.