[SOLVED] CS Traveling Salesman Problem Formulation

Traveling Salesman Problem Formulation

Examples of Optimisation Problems
A salesman must travel passing through N cities. Each city must be visited once and only once. He/she must finish where he/she was at first.

Copyright By Assignmentchef assignmentchef

The path between each pair of cities has a distance (or cost).
Traveling Salesman
Problem: find a sequence of cities that minimises traveling distance (or cost), where each city appears once and only once.

x1 x2 x3 x4 x5
Traveling Salesman Problem Formulation
Design variables represent a candidate solution.
Sequence x of N cities to be visited, where cities are in C. C is a set containing the N cities to be visited.
The search space is all possible sequences of cities.
Objective function defines the cost of a solution.
__ __ __ __ __
Total_distance(x) =
sum of distances between consecutive cities in x + distance from last city to the origin.
To be minimised.
[Optional] Solutions must satisfy certain constraints.
Each city must appear once and only once in x (explicit constraint). Salesman must return to the city of origin (implicit constraint).
Only cities in C must appear in x (implicit constraint).

Traveling Salesman Problem Formulation
Design variables represent a candidate solution.
The design variable is a sequence x of N cities, where xi {1,, N}, i {1,, N}.
The N cities to be visited are represented by values {1,,N}.
The search space is all possible sequences of N cities, where cities are in {1,,N}.
Objective function defines the cost of a solution.
For each city i in {1,,N}, N 1, if xj = i i {1,, N}, 1(xj = i) = 1 1(xj = i) = 0, if xj = i
(N1 ) Dxi,xi+1
__ __ __ __ __
x1 x2 x3 x4 x5 Each city must appear once and only once in x (explicit constraint).
minimise totalDistance(x) =
where Dj,k is the distance of the path between cities j and k.
+ DxN,x1 [Optional] Solutions must satisfy certain constraints.

Traveling Salesman Problem Formulation
i {1,, N}, N 1(x = i) = 1 1(x = i) = 1, if xj = i
j=1 j j i{1,,N},hi(x)= N 1(xj =i) 1=0
0, if xj = i
{1,2,3,4,5}
__ __ __ __ __
0 +0 +1 +0 +0 = 1 0 +1 +0 +0 +0 = 1
x1 x2 x3 x4 x5 ij
Sum3: 0 +0 +0

Objective function defines the cost of a solution. (N1 )
minimise totalDistance(x) = Dxi,xi+1 + DxN,x1 i=1
where Dj,k is the distance of the path between cities j and k. [Optional] Solutions must satisfy certain constraints.
For each city i, hi(x) = 0
Traveling Salesman Problem Formulation
Design variables represent a candidate solution.
The design variable is a sequence x of N cities, where xi {1,, N}, i {1,, N}.
The N cities to be visited are represented by values {1,,N}.
The search space is all possible sequences of N cities, where cities are in {1,,N}.

constraints.
Next How to deal with constraints?
Traveling salesman problem formulation, including

CS: assignmentchef QQ: 1823890830 Email: [email protected]