Le 11/12/2015 par Ngueveu_Roadef :
Title: A generic dynamic programming-based selector operator for solving the Team Orienteering Problem
Tour locations problems (TLPs) or vehicle routing problems with optional visits are challenging because they require two levels of decisions: the selection of the locations to visit and the design of optimal routes to reach the selected locations. Among these problems are the (team) orienteering problems.
The orienteering problem (OP) is defined as follows. Given an undirected graph with edge weights and node prizes, the goal is to design a simple cycle of maximum total prize whose total weight/length does not exceed a given bound Lmax. The total prize is the sum of the prizes of the visited nodes and no node can be visited more than once. The team orienteering problem (TOP) is a generalization of the OP where m vehicles are available and the goal is to determine routes/cycles, each limited by Lmax, that maximise the total collected prize. No node can be visited more than once by one or several routes.
An efficient solution methodology has been developed for solving TLPs in general, and the OP in particular. It is based on a Selector operator which selects the best points worth visiting while meeting side constraints such as the maximum length Lmax. Selector uses dynamic programming over a graph whose set of nodes is constructed from the given locations and conducts the search over resource-constrained maximum profit paths in pseudo- polynomial time. It is a label-reaching algorithm where labels on a node are repeatedly extended to its successors until no new labels are created. Diverse mechanisms to control the exponential number of solutions are implemented within the operator and the resulting C++ code is available.
The objective of the internship is to extend the Selector algorithm to the TOP. This will first require the reading of relevant literature and the understanding of the C++ code available before making any extension/change. The resulting operator will then be embedded inside a metaheuristic algorithm known as adaptive large neighbourhood search (ALNS) composed of several destruction and construction sub-heuristics that are chosen at each iteration according to their historic performance. The main task of this process is to provide sequences of the n locations over which the adapted Selector operator will extract high-quality TOP solutions. Finally, the quality of the resulting algorithm will be evaluated over sets of medium and large benchmark instances/data sets from the literature.
Pour plus d'informations ou pour postuler à ce stage, se rendre à l'adresse:
https://www.laas.fr/boreal/web/fr/stage/voirStage/349.
