Home > Research > Publications & Outputs > Local search heuristic for the optimisation of ...

Electronic data

  • ICCCEEE19

    Rights statement: ©2019 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

    Accepted author manuscript, 330 KB, PDF document

    Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License

Links

Text available via DOI:

View graph of relations

Local search heuristic for the optimisation of flight connections

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

Published
Close
Publication date20/04/2020
Host publicationInternational Conference on Computer, Control, Electrical, and Electronics Engineering (ICCCEEE)
PublisherIEEE
Number of pages4
ISBN (Electronic)9781728110066
ISBN (Print)9781728110073
<mark>Original language</mark>English

Abstract

Kiwi.com proposed a real-world NP-hard optimisation problem with a focus on air travelling services, determining the cheapest connection between specific areas. Despite some similarities with the classical TSP problem, more complexity is involved that makes the problem unique. It is Time-dependent, Asymmetric and involves areas that contain sets of cities from which exactly one is visited. In addition to this, infeasibility adds more complexity to the problem since there are no flights available between specific points in the network for certain days. While solving such computationally difficult problems, exact methods often fail, particularly when the problem instance size increases; Then alternative approaches, such as heuristics, are preferred in problem solving. In this study, we present an effective local search method for solving Kiwi.com problem. The empirical results show the success of the approach, which embeds four simple operators, on most of the released instances.

Bibliographic note

©2019 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.