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 PowCoder代写 加微信 powcoder
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
(N−1 ) ∑ 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. (N−1 )
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代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com