Several variants and generalizations of the Or-opt heuristic for the Symmetric Traveling Salesman Problem are developed and compared on random and planar instances. Some of the proposed algorithms are shown to significantly improve upon the standard 2-opt and Or-opt heuristics.

Lookahead strategies- which consist of forecasting (exactly or heuristically) the potential of a trajectory in a search algorithm- are used in many solving methods, as for instance, in constraint programming. In the context of tabu search, we have conducted experiments on the idea of selecting the movement that would be the first one on the way to the best reachable solution using up to L movements. As visiting all the L-neighborhood is clearly impractical in most situations, only the w_i best moves are scouted on the ith step of the lookahead, with w_i quickly decreasing until it reaches 1 at the final Lth step. After the lookhead, only the first movement from the incumbent to the best solution found is performed and we reapeat the procedure. The algorithm has been implemented to solve the TSP with 2-opt movements. As the lookahead is costly in nature, data structures that allow to practically find the w_i best 2-opts in a linear time have been developped. Also, the lookahead procedure is only used for intensification purposes. For medium-sise TSPLIB instances, the resulting algorithm significantly improves the quality of solutions to a level that is usually reserved to more sophisticated movements.

The Team Orienteering Problem (TOP) is the generalization to the case of multiple tours of the Orienteering Problem, known also as Selective Traveling Salesman Problem. A set of potential customers is available and a profit is collected for the visit of each customer. A fleet of vehicles is available to visit the customers, within a given time limit. The profit of a customer can be collected by one vehicle at most. The objective is to identify the customers which maximize the total collected profit while satisfying the given time limit for each vehicle. We propose two variants of a tabu search algorithm and a variable neighborhood search algorithm for the solution of the TOP and show that each of these algorithms beats the already known heuristics. Computational experiments are made on standard instances and on randomly generated instances.

Le but de cette présentation consiste à étudier le problème de tournées des intervenants en santé pour les visites à domicile. Dans un premier temps, nous décrivons et nous formulons les différentes contraintes propres au contexte des visites à domicile entre autres les contraintes de prises de sang, de continuité des soins et la possibilité de répartir les services des intervenants entre secteurs. À partir de là, nous dégageons notre modèle qui peut être vu comme une généralisation du problème multi voyageurs de commerce avec fenêtres de temps. Dans un second temps, nous abordons la résolution du problème en utilisant deux approches de résolution. La première approche utilise une liste d’attente temporaire pour les patients non encore visités. La seconde utilise une mémoire adaptative. Les deux approches sont basées sur la méthode tabou standard et la différence principale entre ces deux approches est que la première est surtout destinée à réduire le nombre d’intervenants alors que la deuxième est plutôt orientée vers l’optimisation du coût total. Nous présentons également quelques résultats de comparaison des deux approches sur une série de problèmes tests tirés de la littérature. Mots-clefs : Problème de visites à domicile, tournées des intervenants, méthode tabou, mémoire adaptative.