A variable space search heuristic for the Capacitated Team Orienteering Problem

Asma Ben-Said (), Racha El-Hajj () and Aziz Moukrim ()
Additional contact information
Asma Ben-Said: Sorbonne universités
Racha El-Hajj: Sorbonne universités
Aziz Moukrim: Sorbonne universités

Journal of Heuristics, 2019, vol. 25, issue 2, No 5, 273-303

Abstract: Abstract The Capacitated Team Orienteering Problem (CTOP) is a variant of the well-known Team Orienteering Problem where additional capacity limitation constraints are considered for each vehicle. Solving CTOP consists of organizing a set of routes that maximize the total profit collected from the served customers while taking into consideration the capacity and travel time limitation for each vehicle. In this paper, we propose a variable space search heuristic to solve CTOP. Our algorithm alternates between two search spaces: the giant tour and routes search spaces. We develop a hybrid heuristic as a framework for our algorithm composed of a combination between Greedy Randomized Adaptive Search Procedure and Evolutionary Local Search. Several local search techniques were developed in each search space to improve the quality of the solutions and the giant tours. A dedicated optimal split procedure and a concatenation technique are performed to ensure the link between the search spaces. This approach shows its high performance on the benchmark of CTOP, and proves its competitiveness in comparison to the other heuristic methods available in the literature as it yields to strict improvements with small computational time.

Keywords: Vehicle routing; Capacitated Team Orienteering Problem; Variable space search; Local search (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-018-9395-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:25:y:2019:i:2:d:10.1007_s10732-018-9395-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-018-9395-8

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().