首页 | 本学科首页   官方微博 | 高级检索  
     检索      


An effective PSO-inspired algorithm for the team orienteering problem
Authors:Duc-Cuong Dang  Rym Nesrine Guibadj  Aziz Moukrim
Institution:1. Université de Technologie de Compiègne, Département Génie Informatique, Heudiasyc, CNRS UMR 7253, BP 20529, 60205 Compiègne, France;2. University of Nottingham, School of Computer Science, Jubilee Campus, Wollaton Road, Nottingham NG8 1BB, United Kingdom;3. VEOLIA Transport, MERCUR subsidiary, 32, boulevard Gallieni, 92442 Issy-les-Moulineaux, France
Abstract:The Team Orienteering Problem (TOP) is a particular vehicle routing problem in which the aim is to maximize the profit gained from visiting customers without exceeding a travel cost/time limit. This paper proposes a new and fast evaluation process for TOP based on an interval graph model and a Particle Swarm Optimization inspired Algorithm (PSOiA) to solve the problem. Experiments conducted on the standard benchmark of TOP clearly show that our algorithm outperforms the existing solving methods. PSOiA reached a relative error of 0.0005% whereas the best known relative error in the literature is 0.0394%. Our algorithm detects all but one of the best known solutions. Moreover, a strict improvement was found for one instance of the benchmark and a new set of larger instances was introduced.
Keywords:Vehicle routing  Knapsack problem  Interval graph  Optimal split  Swarm intelligence
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号