Effective Neighborhood Structures for the Generalized Traveling Salesman Problem
We consider the generalized traveling salesman problem in which a graph with nodes partitioned into clusters is given. The goal is to identify a minimum cost round trip visiting exactly one node from each cluster. For solving difficult instances of this p
- PDF / 486,342 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 91 Downloads / 228 Views
ract. We consider the generalized traveling salesman problem in which a graph with nodes partitioned into clusters is given. The goal is to identify a minimum cost round trip visiting exactly one node from each cluster. For solving difficult instances of this problem heuristically, we present a new Variable Neighborhood Search (VNS) approach that utilizes two complementary, large neighborhood structures. One of them is the already known generalized 2-opt neighborhood for which we propose a new incremental evaluation technique to speed up the search significantly. The second structure is based on node exchanges and the application of the chained Lin-Kernighan heuristic. A comparison with other recently published metaheuristics on TSPlib instances with geographical clustering indicates that our VNS, though requiring more time than two genetic algorithms, is able to find substantially better solutions. Keywords: Network Design, Generalized Traveling Salesman Problem, Variable Neighborhood Search.
1
Introduction
The Generalized Traveling Salesman Problem (GTSP) extends the classical Traveling Salesman Problem (TSP) and is defined as follows. We consider an undirected weighted complete graph G = V, E, c with node set V , edge set E, and edge cost function c : E →R+ . Node set V is partitioned into r pairwise r disjoint clusters V1 , V2 , . . . , Vr , i=1 Vi = V, Vi ∩ Vj = ∅, i, j = 1, . . . , r, i = j. V1
V2
p1
p2 V4
V3 p3
p4
V5 p5
Fig. 1. Example for a GTSP solution
J. van Hemert and C. Cotta (Eds.): EvoCOP 2008, LNCS 4972, pp. 36–47, 2008. c Springer-Verlag Berlin Heidelberg 2008
Effective Neighborhood Structures for the GTSP
37
A solution to the GTSP defined on G is a subgraph S = P, T with P = {p1 , p2 , . . . , pr } ⊆ V connecting exactly one node from each cluster, i.e. pi ∈ Vi for all 1 ≤ i ≤ r, and T ⊆ E being a round trip, see Fig. 1. The costs of such a round trip are its total edge costs, i.e. C(T ) = (u,v)∈T c(u, v), and the objective is to identify a solution with minimum costs. When edge costs satisfy the triangle inequality, even if we allow more than one node per cluster to be connected, an optimal solution of the GTSP always contains only one node from each cluster [11]. Obviously, the GTSP is NP-hard since it contains the classical TSP as the special case in which each cluster consists of a single node only. The GTSP finds practical application particularly in many variants of routing problems, e.g. when some good can be delivered to multiple alternative addresses of customers. Occasionally, such applications can be directly modeled as the GTSP, but more often the GTSP appears as a subproblem [9]. In this paper, we present a general Variable Neighborhood Search (VNS) approach [6] for heuristically solving this problem. As local improvement within VNS, we use Variable Neighborhood Descent (VND) based on two different types of exponentially large neighborhoods, which can be seen as dual to each other. One neighborhood structure is the generalized 2-opt, which has been introduced in [19]; f
Data Loading...
