An adaptive heuristic for the Capacitated Team Orienteering Problem

详细信息    查看全文

• 作者：Asma Ben-Said^* ; ^{asma.ben-said@hds.utc.fr" class="auth_mail" title="E-mail the corresponding author} ; Racha El-Hajj^* ; ^** ; ^{racha.el-hajj@hds.utc.fr" class="auth_mail" title="E-mail the corresponding author} ; Aziz Moukrim^* ; ^{aziz.moukrim@hds.utc.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Capacitated Team Orienteering Problem ; iterative local search ; adaptive destruction/construction heuristic
• 刊名：IFAC-PapersOnLine
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：49
• 期：12
• 页码：1662-1666
• 全文大小：429 K

文摘

The Capacitated Team Orienteering Problem (CTOP) is a new variant of the well-known Team Orienteering Problem (TOP) where an additional constraint is imposed on the vehicles capacities. By associating a profit and a demand to each customer, the objective of solving CTOP is to select the set of customers to be served in such a way that the total amount of profits collected from the visited customers is maximized, while respecting all the resource limitations, i.e., maximum length limit and maximum capacity of each vehicle. We present in this paper a new adaptive heuristic to solve CTOP. Our method is based on an adaptive iterative destructive constructive heuristic, which adjusts its parameters according to the solution progress. Computational experiments applied on the benchmark of CTOP show the effectiveness of our proposed method, which provided some results of high quality with a competitive computational time. Moreover, an improvement was found in the score of one of the hardest instances of the benchmark.