2019年秋哈尔滨工业大学演化计算大作业——遗传算法解决旅行商问题_tra

TSPLIB 95

Gerhard Reinelt

Universit¨at Heidelberg

Institut f¨ur Angewandte Mathematik

Im Neuenheimer Feld 294

D-69120 Heidelberg

Gerhard.Reinelt@IWR.Uni-Heidelberg.DE

TSPLIB is a library of sample instances for the TSP (and related problems) from various

sources and of various types. Instances of the foll owing problem classes are availa bl e.

Asymmetric traveli ng salesman probl em (ATSP)

Given a set o f n nodes and distances for each pair of nodes, find a roundtrip of minimal

total length visiting each node exactly once. In this case, the distance from node i to node

j and the dist ance from node j to node i may be different.

Sequential ordering problem (SOP)

This problem is an asymmetric traveling salesman problem with additional constraints.

Given a set of n nodes and distances for each pair of nodes, find a Hamiltonian path from

node 1 to node n of mi ni mal length which takes given precedence constraints int o account.

Each precedence constraint requires that some node i has to be visited before some other

node j.

nodes and starts and terminates at the depo t. (Remark: In some data files a collection of

alternate depo ts is g iven. A CVRP is then given by selecting one of these depots.)

Except, for the Hamiltonian cycle problems, all problems are defined on a complete graph

and, at present, all distances are i nteger numbers. There is a possibility to require that

certain edges appear in the solutio n of a problem.

1

1. The file format

Each file consists o f a specification part and of a data part. The specification part

contains information on the fil e format and on its contents. The data part contains explicit

data.

formation for the correct interpretation of the keyword has t o be known. Below we give a

list of al l available keywords.

1.1.1 NAME : <string>

Identifies the data file.

1.1.2 TYPE : <string>

Specifies the type of t he data. Possible types are

For a TSP or ATSP, the dimension is t he number of its nodes. For a CVRP, it is the tota l

number of nodes and depots. For a TOUR file it is the dimension of the corresponding

problem.

1.1.5 CAPACITY : <integer>

Specifies the truck capacity in a CVRP.

1.1.6 EDGE

Specifies how the edge weights (or distances) are given. The values are

1.1.7 EDGE

Describes the format of the edge weights i f they are given explicitly. The values are

1.1.7 EDGE

1.1.9 NODE

Specifies whether coordinates are associated with each node (which, for example may be

used for eit her graphical display or distance computations). The values are

The default va lue is NO COORDS.

The default value is COORD

1.1.11 EOF :

Terminates the input data. T hi s entry is optional.

1.2 The data part

Depending on the choice of specifications some additional data may be required. These

data are given in corresponding data sections following the specification part. Each dat a

section begins with the corresp onding keyword. The length of the section is either implicitly

known from the format specification, or the section is terminated by an appropriate end-

of-section identifier.

1.2.1 NODE COORD SECTION :

Node coordinates are given in this section. Each line i s of the form

1.2.3 DEMAND

SECTION :

The demands of all nodes of a CVRP are given in the form ( per line)

The first integer specifies a node number, the second its demand. The depot nodes must

also occur in t hi s section. Their demands are 0.

1.2.4 EDGE DATA SECTION :

Edges of a graph are specified in either of the two formats allowed in the EDGE

DATA FORMAT

entry. If the type is EDGE LIST, then the edges are given as a sequence of lines of t he form

1.2.5 FIXED EDGES SECTION :