Solving multi-objective dynamic travelling salesman problems by relaxation

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

7 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationGECCO '19 Proceedings of the Genetic and Evolutionary Computation Conference Companion
EditorsManuel López-Ibáñez
Place of PublicationNew York
Pages1999-2007
Number of pages9
DOIs
Publication statusPublished - 13 Jul 2019
EventGECCO 2019: The Genetic and Evolutionary Computation Conference - Prague Conress Centre, Prague, Czech Republic
Duration: 13 Jul 201917 Jul 2019
https://gecco-2019.sigevo.org/index.html/HomePage

Conference

ConferenceGECCO 2019
CountryCzech Republic
CityPrague
Period13/07/1917/07/19
Internet address

Keywords

  • multi-objective optimisation
  • global optimisation
  • optimal control
  • mixed integer nonlinear programming
  • memetic algorithms
  • aerospace

Fingerprint Dive into the research topics of 'Solving multi-objective dynamic travelling salesman problems by relaxation'. Together they form a unique fingerprint.

  • Cite this

    Ricciardi, L. A., & Vasile, M. (2019). Solving multi-objective dynamic travelling salesman problems by relaxation. In M. López-Ibáñez (Ed.), GECCO '19 Proceedings of the Genetic and Evolutionary Computation Conference Companion (pp. 1999-2007). New York. https://doi.org/10.1145/3319619.3326837