An exact algorithm for team orienteering problems |
| |
Authors: | Sylvain Boussier Dominique Feillet Michel Gendreau |
| |
Institution: | (1) LGI2P, Ecole des Mines d’Alès - Site EERIE, Parc Scientifique Georges Besse, 30035 Nimes Cedex 1, France;(2) Laboratoire d’informatique d’Avignon, Université d’Avignon et des pays de Vaucluse, 339 Chemin des Meinajaries, Agroparc B.P. 1228, Avignon Cedex 9, France;(3) Centre de recherche sur les transports, Université de Montréal, 6128 succursale centre-ville, Montréal, Canada, H3C 3J7 |
| |
Abstract: | Optimising routing of vehicles constitutes a major logistic stake in many industrial contexts. We are interested here in the
optimal resolution of special cases of vehicle routing problems, known as team orienteering problems. In these problems, vehicles
are guided by a reward that can be collected from customers, while the length of routes is limited. The main difference with
classical vehicle routing problems is that not all customers have to be visited. The solution method we propose here is based
on a Branch & Price algorithm. It is, as far as we know, the first exact method proposed for such problems, except for a preliminary
work from Gueguen (Methodes de résolution exacte pour problémes de tournées de véhicules. Thése de doctorat, école Centrale
Paris 1999) and a work from Butt and Ryan (Comput Oper Res 26(4):427–441 1999). It permits to solve instances with up to 100
customers.
|
| |
Keywords: | Selective vehicle routing problem with time windows Team orienteering problem Column generation Branch & price Routing problems with profits |
本文献已被 SpringerLink 等数据库收录! |
|