Solving multi-objective dynamic travelling salesman problems by relaxation

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

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.
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

Fingerprint

Traveling salesman problem
Space applications
Transcription
Multiobjective optimization
Debris
Orbits
Satellites

Keywords

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

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
Ricciardi, Lorenzo A. ; Vasile, Massimiliano. / Solving multi-objective dynamic travelling salesman problems by relaxation. GECCO '19 Proceedings of the Genetic and Evolutionary Computation Conference Companion. editor / Manuel López-Ibáñez . New York, 2019. pp. 1999-2007
@inproceedings{eff6da2b487d4316956fc55209ee08b6,
title = "Solving multi-objective dynamic travelling salesman problems by relaxation",
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.",
keywords = "multi-objective optimisation, global optimisation, optimal control, mixed integer nonlinear programming, memetic algorithms, aerospace",
author = "Ricciardi, {Lorenzo A.} and Massimiliano Vasile",
year = "2019",
month = "7",
day = "13",
doi = "10.1145/3319619.3326837",
language = "English",
isbn = "9781450367486",
pages = "1999--2007",
editor = "{L{\'o}pez-Ib{\'a}{\~n}ez }, Manuel",
booktitle = "GECCO '19 Proceedings of the Genetic and Evolutionary Computation Conference Companion",

}

Ricciardi, LA & 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. New York, pp. 1999-2007, GECCO 2019, Prague, Czech Republic, 13/07/19. https://doi.org/10.1145/3319619.3326837

Solving multi-objective dynamic travelling salesman problems by relaxation. / Ricciardi, Lorenzo A.; Vasile, Massimiliano.

GECCO '19 Proceedings of the Genetic and Evolutionary Computation Conference Companion. ed. / Manuel López-Ibáñez . New York, 2019. p. 1999-2007.

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

TY - GEN

T1 - Solving multi-objective dynamic travelling salesman problems by relaxation

AU - Ricciardi, Lorenzo A.

AU - Vasile, Massimiliano

PY - 2019/7/13

Y1 - 2019/7/13

N2 - 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.

AB - 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.

KW - multi-objective optimisation

KW - global optimisation

KW - optimal control

KW - mixed integer nonlinear programming

KW - memetic algorithms

KW - aerospace

U2 - 10.1145/3319619.3326837

DO - 10.1145/3319619.3326837

M3 - Conference contribution book

SN - 9781450367486

SP - 1999

EP - 2007

BT - GECCO '19 Proceedings of the Genetic and Evolutionary Computation Conference Companion

A2 - López-Ibáñez , Manuel

CY - New York

ER -

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