UMR CNRS 7253

Aziz Moukrim
Aziz Moukrim
Aziz Moukrim
Aziz Moukrim
Aziz Moukrim

Site Tools


en:top

The Team Orienteering Problem

Description

The Team Orienteering Problem (TOP) [2] comes from an outdoor game played in mountainous or forested areas. In this game a team of several players tries to collect as many reward points as possible within a given time limit. Similarly, TOP is the problem where a limited number of vehicles are available to visit customers from a potential set, the travel time of each vehicle being limited by a time quota, customers having different corresponding profits, and each customer being visited at most once. The aim of TOP is to organize an itinerary of visits so as to maximize the total profit.

We have developed two heuristic solutions

  • Memetic algorithm (MA algorithm) in [1].
  • Swarm intelligence technique (PSOMA and PSOiA algorithms) in [3, 4].

Available downloads


Route length validation

The euclidean distances are computed using double data type in C++ which is safe for a single computation within 18 decimal digits (GNU GCC 4.0+). Our rule to check if a route is valid is as follows: the travel length is computed in the order of clients that appear in the route and this value should be inferior or equal to the travel length limit (tmax value in Chao's instances).

People involved

References

[1] H. Bouly, D-C. Dang, and A. Moukrim. A memetic algorithm for the team orienteering problem. 4OR, 8(1): p49-70, 2010.
[2] I.-M. Chao, B. Golden, and E. A. Wasil. The team orienteering problem. European Journal of Operational Research, 88: p464-474, 1996.
[3] D-C. Dang, R. N. Guibadj, A. Moukrim: A PSO-based memetic algorithm for the team orienteering problem. EvoApplications (2) 2011: p471-480, 2011.
[4] D-C. Dang, R. N. Guibadj, A. Moukrim: An effective PSO-inspired algorithm for the team orienteering problem. Preprint accepted for publication in European Journal of Operational Research.


User Tools