Solving dynamic TSP with evolutionary approach in real time

Aimin Zhou; Lishan Kang; Zhenyu Yan

doi:10.1109/CEC.2003.1299769

Solving dynamic TSP with evolutionary approach in real time

Aimin Zhou
, Lishan Kang
, Zhenyu Yan

Research output: Contribution to conference › Paper › peer-review

37 Scopus citations

Abstract

Many real world optimization problems are time-dependent and some of them can be modeled by the dynamic TSPs (DTSPs). A DTSP is harder than a general TSP, which is a NP-hard problem, because the city number and the cost matrix of a DTSP are time varying. Although DTSP is a very common and important model in real world systems, few literatures have discussed this related issues. There are many open questions about DTSP urgently needed to be answered. We first give a mathematical model and the optimization objective for DTSP. Then we discuss why evolutionary algorithms (EAs) are effective for solving DTSPs and give some key points for designing efficient DTSP EAs. By defining three dynamic operators, we proposed an evolutionary algorithm for DTSPs. The experiments show the new algorithm is suitable for solving DTSPs. At the end, we also give some preliminary ideas for reinforcing the efficiency of EAs for DTSPs.

Original language	English
Pages	951-957
Number of pages	7
DOIs	https://doi.org/10.1109/CEC.2003.1299769
State	Published - 2003
Externally published	Yes
Event	2003 Congress on Evolutionary Computation, CEC 2003 - Canberra, ACT, Australia Duration: 8 Dec 2003 → 12 Dec 2003

Conference

Conference	2003 Congress on Evolutionary Computation, CEC 2003
Country/Territory	Australia
City	Canberra, ACT
Period	8/12/03 → 12/12/03

Access to Document

10.1109/CEC.2003.1299769

Cite this

@conference{6c27fd9189324cc78d1cf84f266b7381,

title = "Solving dynamic TSP with evolutionary approach in real time",

abstract = "Many real world optimization problems are time-dependent and some of them can be modeled by the dynamic TSPs (DTSPs). A DTSP is harder than a general TSP, which is a NP-hard problem, because the city number and the cost matrix of a DTSP are time varying. Although DTSP is a very common and important model in real world systems, few literatures have discussed this related issues. There are many open questions about DTSP urgently needed to be answered. We first give a mathematical model and the optimization objective for DTSP. Then we discuss why evolutionary algorithms (EAs) are effective for solving DTSPs and give some key points for designing efficient DTSP EAs. By defining three dynamic operators, we proposed an evolutionary algorithm for DTSPs. The experiments show the new algorithm is suitable for solving DTSPs. At the end, we also give some preliminary ideas for reinforcing the efficiency of EAs for DTSPs.",

author = "Aimin Zhou and Lishan Kang and Zhenyu Yan",

year = "2003",

doi = "10.1109/CEC.2003.1299769",

language = "英语",

pages = "951--957",

note = "2003 Congress on Evolutionary Computation, CEC 2003 ; Conference date: 08-12-2003 Through 12-12-2003",

}

TY - CONF

T1 - Solving dynamic TSP with evolutionary approach in real time

AU - Zhou, Aimin

AU - Kang, Lishan

AU - Yan, Zhenyu

PY - 2003

Y1 - 2003

N2 - Many real world optimization problems are time-dependent and some of them can be modeled by the dynamic TSPs (DTSPs). A DTSP is harder than a general TSP, which is a NP-hard problem, because the city number and the cost matrix of a DTSP are time varying. Although DTSP is a very common and important model in real world systems, few literatures have discussed this related issues. There are many open questions about DTSP urgently needed to be answered. We first give a mathematical model and the optimization objective for DTSP. Then we discuss why evolutionary algorithms (EAs) are effective for solving DTSPs and give some key points for designing efficient DTSP EAs. By defining three dynamic operators, we proposed an evolutionary algorithm for DTSPs. The experiments show the new algorithm is suitable for solving DTSPs. At the end, we also give some preliminary ideas for reinforcing the efficiency of EAs for DTSPs.

AB - Many real world optimization problems are time-dependent and some of them can be modeled by the dynamic TSPs (DTSPs). A DTSP is harder than a general TSP, which is a NP-hard problem, because the city number and the cost matrix of a DTSP are time varying. Although DTSP is a very common and important model in real world systems, few literatures have discussed this related issues. There are many open questions about DTSP urgently needed to be answered. We first give a mathematical model and the optimization objective for DTSP. Then we discuss why evolutionary algorithms (EAs) are effective for solving DTSPs and give some key points for designing efficient DTSP EAs. By defining three dynamic operators, we proposed an evolutionary algorithm for DTSPs. The experiments show the new algorithm is suitable for solving DTSPs. At the end, we also give some preliminary ideas for reinforcing the efficiency of EAs for DTSPs.

UR - https://www.scopus.com/pages/publications/4344591316

U2 - 10.1109/CEC.2003.1299769

DO - 10.1109/CEC.2003.1299769

M3 - 论文

AN - SCOPUS:4344591316

SP - 951

EP - 957

T2 - 2003 Congress on Evolutionary Computation, CEC 2003

Y2 - 8 December 2003 through 12 December 2003

ER -

Solving dynamic TSP with evolutionary approach in real time

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this