Title
A memetic algorithm for the orienteering problem with hotel selection A memetic algorithm for the orienteering problem with hotel selection
Author
Faculty/Department
Faculty of Applied Economics
Publication type
article
Publication
Amsterdam ,
Subject
Economics
Mathematics
Source (journal)
European journal of operational research. - Amsterdam
Volume/pages
237(2014) :1 , p. 29-49
ISSN
0377-2217
ISI
000335626200003
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
Abstract
In this paper, a memetic algorithm is developed to solve the orienteering problem with hotel selection (OPHS). The algorithm consists of two levels: a genetic component mainly focuses on finding a good sequence of intermediate hotels, whereas six local search moves embedded in a variable neighborhood structure deal with the selection and sequencing of vertices between the hotels. A set of 176 new and larger benchmark instances of OPHS are created based on optimal solutions of regular orienteering problems. Our algorithm is applied on these new instances as well as on 224 benchmark instances from the literature. The results are compared with the known optimal solutions and with the only other existing algorithm for this problem. The results clearly show that our memetic algorithm outperforms the existing algorithm in terms of solution quality and computational time. A sensitivity analysis shows the significant impact of the number of possible sequences of hotels on the difficulty of an OPHS instance. (C) 2014 Elsevier B.V. All rights reserved.
E-info
https://repository.uantwerpen.be/docman/iruaauth/a171a5/aac7658.pdf
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000335626200003&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000335626200003&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000335626200003&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle