Project # 7

Assignment

The goal of the project is to implement the Canadian traveller Problem (CTP).

Problem description. This project deals with Canadian traveller problem (CTP). Imagine a traveller that have a map on which every road is associated with time that is needed to get through this road. Hovewer, this map may not be totally reliable, and the time needed to pass through on some of the roads may be different due to bad road conditions, or the pass will be impossible. The goal of this project is to provide an overview of the CTP, and implement its simple solution (heuristic or metaheuristic). The correctness of the solution will be demonstrated on experiments.

The goals of the project are:

1. study and describe the CTP
2. collect a library of CPT instances
3. implement a simple heuristic or metaheuristic (stochastic) CTP solution

References

1. Dror Fried; Solomon Eyal Shimony; Amit Benbassat; Cenny Wenner (2013). "Complexity of Canadian traveler problem variants". Theoretical Computer Science. 487: 1–16. arXiv:1207.4710. doi:10.1016/j.tcs.2013.03.016. S2CID 17810202.
2. David Karger; Evdokia Nikolova (January 28, 2008). Exact Algorithms for the Canadian Traveller Problem on Paths and Trees (PDF) (Report). Massachusetts Institute of Technology.
3. MATOUŠEK, R.; ŠOUSTEK, P.; DVOŘÁK, J.; BEDNÁŘ, J.: ACO in Task of Canadian Traveller Problem, 18th International Conference of Soft Computing, MENDEL 2012 (id 19255), pp.600-603, ISBN 978-80-214-4540-6, (2012), VUT článek ve sborníku ve WoS nebo Scopus akce: 18th International Conference on Soft Computing, MENDEL 2012, Brno University of Technology, 27.06.2012-29.06.2012