Solving multi-objective dynamic travelling salesman problems by relaxation

Ricciardi, Lorenzo A. and Vasile, Massimiliano; López-Ibáñez, Manuel, ed. (2019) Solving multi-objective dynamic travelling salesman problems by relaxation. In: GECCO '19 Proceedings of the Genetic and Evolutionary Computation Conference Companion. ACM, CZE, pp. 1999-2007. ISBN 9781450367486 (https://doi.org/10.1145/3319619.3326837)

Preview

Text. Filename: Ricciardi_Vasile_GECCO_2019_Solving_multi_objective_dynamic_travelling_salesman_problems_by_relaxation.pdf Accepted Author Manuscript Download (1MB)| Preview

Abstract

This paper describes a method to solve Multi-objective Dynamic Travelling Salesman Problems. The problems are formulated as multi-objective hybrid optimal control problems, where the choice of the target destination for each phase is an integer variable. The resulting problem has thus a combinatorial nature in addition to being a multi-objective optimal control problem. The overall solution approach is based on a combination of the Multi Agent Collaborative Search, a population based memetic multi-objective optimisation algorithm, and the Direct Finite Elements Transcription, a direct method for optimal control problems. A relaxation approach is employed to transform the mixed integer problem into a purely continuous problem, and a set of smooth constraints is added in order to ensure that the relaxed variables of the final solution assume an integer value. A special set of smooth constraints is introduced in order to treat the mutually exclusive choices of the targets for each phase. The method is tested on two problems: the first is a motorised Travelling salesman problem described in the literature, the second is a space application where a satellite has to de-orbit multiple debris. For the first problem, the approach is generating better solutions than those reported in the literature.

ORCID iDs

Ricciardi, Lorenzo A. ORCID: https://orcid.org/0000-0002-0895-7961

Vasile, Massimiliano ORCID: https://orcid.org/0000-0001-8302-6465

• Share and Export
  

  MPEG-21 DIDLRIOXX2 XMLBibTeXEP3 XMLMODSJSONRDF+N3Multiline CSVReferMETSRefWorksRIS (EndNote Online, Zotero, Ref manager, etc)RDF+XMLEndNoteASCII CitationOpenURL ContextObject in SpanAtomDublin CoreRDF+N-TriplesHTML CitationData Cite XMLOpenURL ContextObjectSimple Metadata
• Item metadata

  Item type:	Book Section
  ID code:	68878
  Dates:	Date Event 13 July 2019 Published 6 February 2019 Accepted
  Subjects:	Technology > Motor vehicles. Aeronautics. Astronautics
  Department:	Faculty of Engineering > Mechanical and Aerospace Engineering Strategic Research Themes > Ocean, Air and Space
  Depositing user:	Pure Administrator
  Date deposited:	17 Jul 2019 10:30
  Last modified:	27 Nov 2024 01:29
  URI:	https://strathprints.strath.ac.uk/id/eprint/68878