Behaviour of a Hybrid ILS Heuristic on the Capacitated Profitable Tour Problem
| Autor: | Rachid Ouafi, Wahiba Ramdane Cherif-Khettaf, Hayet Chentli |
|---|---|
| Přispěvatelé: | OPTImisation Methods for Integrated SysTems (OPTIMIST), Department of Networks, Systems and Services (LORIA - NSS), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Iterative Local Search
Mathematical optimization Vehicle Routing Problem Computer science business.industry Heuristic 05 social sciences 050301 education 02 engineering and technology [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Constraint (information theory) Variable (computer science) Vehicle routing problem 0202 electrical engineering electronic engineering information engineering Heuristics 020201 artificial intelligence & image processing Local search (optimization) Routing (electronic design automation) business 0503 education Variable neighborhood search |
| Zdroj: | 7th International Conference on Operations Research and Enterprise Systems 7th International Conference on Operations Research and Enterprise Systems, Jan 2018, Funchal, Portugal. pp.115-123, ⟨10.5220/0006630401150123⟩ ICORES |
| DOI: | 10.5220/0006630401150123⟩ |
| Popis: | International audience; In the present paper, we study the behaviour of a hybrid Iterative Local Search heuristic (ILS). A Large Neighborhood Search heuristic (LNS) and a Variable Neighborhood Descent with Random neighborhood ordering (RVND) are used in the local search phase of the proposed ILS. The approach is evaluated on a well-known variant of the Vehicle Routing Problem (VRP) called Capacitated Profitable Tour Problem (CPTP). In this variant, the vehicles are no longer required to visit all the customers. However, a specific profit is obtained each time a customer is visited. The goal of the CPTP is to design routes with maximum difference between collected profits and routing costs, which satisfy the capacity constraint of the vehicles. The experimental study consists in comparing different combinations of ILS, LNS and RVND. The computational results show that the hybridization of the three heuristics leads to better solutions. Furthermore, comparisons with a Variable Neighborhood Search and two Tabu Searches from the literature indicates that our hybrid approach is competitive |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|