The Traveling Salesman Problem (TSP) is a well-known problem in mathematics used to determine the optimal travel path that visits all cities exactly once with the minimum cost. In the question table, the travel costs between cities are provided (not symmetric). Calculate the cost of all possible paths starting from city A that visit each city exactly once and return to A.
📌 Challenge Details and Links
Challenge Number: 90
Challenge Difficulty: ⭐⭐⭐⭐⭐
📥Download Sample File
📥Link to the solutions on LinkedIn
Solving the challenge of Traveling Salesman Problem with Power Query
Power Query solution 1 for Traveling Salesman Problem, proposed by Zoran Milokanović:
let
Source = Excel.CurrentWorkbook(){[Name = "Input"]}[Content],
H = Table.ColumnNames(Source),
S = Table.FromRows(
List.TransformMany(
List.Accumulate(
{1 .. List.Count(H) - 3},
List.Transform(List.Skip(H, 2), each {_}),
(b, n) => List.TransformMany(b, each List.Difference(List.Skip(H, 2), _), (i, _) => i & {_})
),
each {{H{1}} & _ & {H{1}}},
(i, _) => {
Text.Combine(_),
List.Sum(
List.Transform(
{0 .. List.Count(i)},
(p) => Record.Field(Source{[#"From To" = _{p}]}, _{p + 1})
)
)
}
),
{"Path", "Cost"}
)
in
SPower Query solution 2 for Traveling Salesman Problem, proposed by Brian Julius:
let
S = DataRaw,
UnPivOth = Table.TransformColumnTypes(
Table.UnpivotOtherColumns(S, {"From"}, "To", "Dist"),
{"Dist", Int64.Type}
),
Elements = Table.Skip(Table.Distinct(Table.SelectColumns(UnPivOth, "From")), 1),
RScript = R.Execute(
"library(combinat)#(lf)letterscol <- dataset$From#(lf)perms <- sapply(permn(letterscol), function(x) paste0(""A"", paste(x, collapse = """"), ""A""))#(lf)df_perms <- as.data.frame(perms, stringsAsFactors = FALSE)#(lf)names(df_perms) <- ""Path""",
[dataset = Elements]
),
Permuts = RScript{[Name = "df_perms"]}[Value],
Pairs = Table.AddColumn(
Permuts,
"PairSplit",
each [
a = [Path],
b = Text.ToList(a),
c = List.Transform(List.Positions(b), each List.FirstN(List.Skip(b, _), 2))
][c]
),
Expand = Table.ExpandListColumn(Pairs, "PairSplit"),
Extract = Table.TransformColumns(
Expand,
{"PairSplit", each Text.Combine(List.Transform(_, Text.From), ","), type text}
),
Split = Table.SelectRows(
Table.SplitColumn(
Extract,
"PairSplit",
Splitter.SplitTextByDelimiter(",", QuoteStyle.Csv),
{"From", "To"}
),
each [To] <> null
),
J = Table.Join(Split, {"From", "To"}, UnPivOth, {"From", "To"}),
G = Table.Group(J, {"Path"}, {{"Cost", each List.Sum([Dist])}})
in
GPower Query solution 3 for Traveling Salesman Problem, proposed by Alejandro Simón 🇵🇦 🇪🇸:
let
Source = Excel.CurrentWorkbook(){[Name="Table1"]}[Content],
Unpivot = Table.ToRows(Table.AddColumn(Table.UnpivotOtherColumns(Source, {"From To"}, "At", "V"), "A",
each [From To]&[At])[[A],[V]]),
Lista = Source[From To],
LAcc = List.Accumulate({1..List.Count(List.Skip(Lista))-1}, Table.FromColumns({List.Skip(Lista)}),
(s,c)=> Table.ExpandListColumn(Table.AddColumn(s, Text.From(c), (x)=>
let
a = Record.ToList(x),
b = List.RemoveMatchingItems(List.Skip(Lista),a)
in b), Text.From(c))),
Sol = Table.Combine(Table.AddColumn(LAcc, "B", each
let
a = {"A"}&Record.ToList(_)&{"A"},
b = List.Transform({0..List.Count(a)-2}, each a{_}&a{_+1}),
c = Table.FromRows({{Text.Combine(a), List.Sum(List.ReplaceMatchingItems(b, Unpivot))}}, {"Path", "Cost"})
in c)[B])
in
SolPower Query solution 4 for Traveling Salesman Problem, proposed by Yaroslav Drohomyretskyi:
let
S = Excel.CurrentWorkbook(){[Name = "Table1"]}[Content],
D = List.Skip(Table.ColumnNames(S), 2),
T = Table.RenameColumns(Table.FromList(D), {{"Column1", "1"}}),
CJ2 = Table.ExpandTableColumn(Table.AddColumn(T, "2", each T), "2", {"1"}, {"2"}),
CJ3 = Table.ExpandTableColumn(Table.AddColumn(CJ2, "3", each T), "3", {"1"}, {"3"}),
CJ4 = Table.ExpandTableColumn(Table.AddColumn(CJ3, "4", each T), "4", {"1"}, {"4"}),
Combo = Table.SelectRows(CJ4, each (List.Count(List.Distinct({[1], [2], [3], [4]})) = 4)),
Cost = Table.UnpivotOtherColumns(S, {"From To"}, "To", "V"),
Path = Table.SelectColumns(
Table.AddColumn(Combo, "Path", each "A" & [1] & [2] & [3] & [4] & "A"),
"Path"
),
Res = Table.AddColumn(
Path,
"Cost",
each
let
CharList = Text.ToList([Path]),
Pairs = List.Transform(
List.Zip({CharList, List.Skip(CharList) & {List.First(CharList)}}),
each [c1 = _{0}, c2 = _{1}]
),
R = List.Sum(
Table.ExpandTableColumn(
Table.NestedJoin(
Table.FromRecords(Pairs),
{"c1", "c2"},
Cost,
{"From To", "To"},
"t",
JoinKind.LeftOuter
),
"t",
{"V"},
{"V"}
)[V]
)
in
R
)
in
ResPower Query solution 5 for Traveling Salesman Problem, proposed by 🇮🇷 Navid Esmaeilzadeh اسماعیل زاده:
let
S=Excel.CurrentWorkbook(){[Name="Table1"]}[Content],
A = Table.UnpivotOtherColumns(S, {"From To"}, "T", "V"),
B = Table.CombineColumns(A,{"From To", "T"},Combiner.CombineTextByDelimiter("", QuoteStyle.None),"FT"),
C = Table.FromColumns({List.Transform(List.Select(List.Accumulate(List.Repeat(List.Skip(S[From To],1),List.Count(List.Skip(S[From To],1))), {""}, (s, c) => s & List.Transform(s, each _ & c)), each Text.Length(_)=4 and List.IsDistinct(Text.ToList(_))=true), each "A"&_&"A")},{"P"}),
D = Table.Distinct(C),
E = Table.AddColumn(D, "D", each Text.ToList([P])),
MF=(Path)=>
let
F1 = Table.FromColumns({Path},{"A"}),
F2 = Table.AddIndexColumn(F1, "I", 1, 1, Int64.Type),
F3 = Table.AddColumn(F2, "B", each try [A]&F2[A]{[I]} otherwise null),
F4 = Table.SelectRows(F3, each ([B] <> null)),
F5 = Table.SelectColumns(F4,{"B"})
in
F5,
F = Table.AddColumn(E, "MF", each MF([D])),
G = Table.SelectColumns(F,{"P", "MF"}),
H = Table.ExpandTableColumn(G, "MF", {"B"}, {"B"}),
I = Table.NestedJoin(H,{"B"},B,{"FT"},"T"),
J = Table.ExpandTableColumn(I, "T", {"V"}, {"V"}),
K = Table.Group(J, {"P"}, {{"Cost", each List.Sum([V]), type number}})
in
KPower Query solution 6 for Traveling Salesman Problem, proposed by Peter Tholstrup:
let
Source = Excel.CurrentWorkbook(){[Name = "Table1"]}[Content],
unpivot = Table.UnpivotOtherColumns(Source, {"From To"}, "To", "Cost"),
cost = Table.CombineColumns(unpivot, {"From To", "To"}, Text.Combine, "Leg"),
stops = {"B" .. "E"},
generate = (t) =>
[
stop_no = Text.From(Table.ColumnCount(t) + 1),
add = Table.AddColumn(t, stop_no, each stops),
expand = Table.ExpandListColumn(add, stop_no),
filter = Table.SelectRows(expand, each List.Sort(Record.ToList(_)) = stops),
result = if stop_no = "4" then filter else @generate(expand)
][result],
route = List.Transform(
Table.ToRows(generate(Table.FromRows(List.Split(stops, 1), {"1"}))),
each {"A"} & _ & {"A"}
),
rcd = List.Transform(
route,
each [
Route = _,
Path = Text.Combine(_),
Leg = List.Transform({0 .. 4}, each Route{_} & Route{_ + 1})
]
),
tbl = Table.ExpandListColumn(Table.FromRecords(rcd), "Leg"),
add_cost = Table.Join(tbl, "Leg", cost, "Leg"),
result = Table.Group(add_cost, "Path", {"Cost", each List.Sum([Cost])})
in
resultPower Query solution 7 for Traveling Salesman Problem, proposed by Szabolcs Phraner:
let
Source = ...,
Buffer = Table.Buffer(Source),
Start = {Table.FirstValue(Buffer)},
Cities = List.Skip(Buffer[From To]),
CreatePaths = List.Transform(GenPermutations(Cities), each Start & _ & Start),
CreateTable = Table.FromColumns({CreatePaths, CreatePaths}, {"Path", "Cost"}),
Result = Table.TransformColumns(
CreateTable,
{
{"Path", Text.Combine, type text},
{
"Cost",
(l) =>
List.Accumulate(
List.Numbers(0, List.Count(Cities) + 1),
0,
(s, c) => s + CalculateDistance(List.Range(l, c, 2))
),
Int64.Type
}
}
)
in
ResultSolving the challenge of Traveling Salesman Problem with Excel
Excel solution 1 for Traveling Salesman Problem, proposed by Bo Rydobon 🇹🇭:
=LET(
f,
+B3:B7,
s,
SEQUENCE(
,
ROWS(
f
)-1
),
p,
MID(
REDUCE(
"",
s,
LAMBDA(
a,
_,
TOCOL(
IFS(
ISERR(
FIND(
s,
a
)
),
a&s
),
3
)
)
),
s,
1
)+1, HSTACK(
BYROW(
p,
LAMBDA(
i,
CONCAT(
@f,
INDEX(
f,
i
),
@f
)
)
),
BYROW(
p,
LAMBDA(
i,
SUM(
INDEX(
C3:G7,
HSTACK(
1,
i
),
HSTACK(
i,
1
)
)
)
)
)
)
)Excel solution 2 for Traveling Salesman Problem, proposed by محمد حلمي:
=LET( s,
SEQUENCE(
,
4
), d,
MID(
REDUCE(
,
s,
LAMBDA(
a,
v,
VSTACK(
a,
TOCOL(
REPLACE(
a,
SEQUENCE(
,
v
),
,
v
)
)
)
)
),
s,
1
), i,
IFNA(
HSTACK(
1,
d+1,
1
),
1
), SORT(
HSTACK(
TOCOL(
BYROW(
INDEX(
B3:B7,
i
),
LAMBDA(
a,
CONCAT(
a
)
)
),
2
),
TOCOL(
BYROW(
INDEX(
C3:G7,
DROP(
i,
,
-1
),
DROP(
i,
,
1
)
),
LAMBDA(
a,
SUM(
a
)
)
),
2
)
)
)
)Excel solution 3 for Traveling Salesman Problem, proposed by محمد حلمي:
=LET(
s,
SEQUENCE(
,
4
), i,
IFNA(
HSTACK(
1,
MID(
REDUCE(
,
s,
LAMBDA(
a,
v,
VSTACK(
a,
TOCOL(
REPLACE(
a,
SEQUENCE(
,
v
),
,
v
)
)
)
)
),
s,
1
)+1,
1
),
1
), SORT(
HSTACK(
TOCOL(
BYROW(
INDEX(
B3:B7,
i
),
CONCAT
),
2
),
TOCOL(
BYROW(
INDEX(
C3:G7,
DROP(
i,
,
-1
),
DROP(
i,
,
1
)
),
SUM
),
2
)
)
)
)Excel solution 4 for Traveling Salesman Problem, proposed by Oscar Mendez Roca Farell:
=LET(
p,
SORT(
"A"&REDUCE(
"",
ROW(
1:4
),
LAMBDA(
i,
x,
TOCOL(
REPLACE(
i,
x+1-SEQUENCE(
,
x
),
,
MID(
"BCDE",
x,
1
)
)
)
)
)&"A"
),
VSTACK(
{"Path",
"Cost"},
HSTACK(
p,
MAP(
p,
LAMBDA(
b,
SUM(
XLOOKUP(
MID(
b,
ROW(
1:5
),
2
),
TOCOL(
B3:B7&C2:G2
),
TOCOL(
C3:G7
)
)
)
)
)
)
)
)Excel solution 5 for Traveling Salesman Problem, proposed by Julian Poeltl:
=LET(
P,
"A"&L_Permutations_Combinations(
"BCDE"
)&"A",
VSTACK(
HSTACK(
"Path",
"Cost"
),
HSTACK(
P,
MAP(
P,
LAMBDA(
A,
SUM(
XLOOKUP(
MID(
A,
SEQUENCE(
LEN(
A
)
),
2
),
TOCOL(
B3:B7&C2:G2
),
TOCOL(
C3:G7
),
0
)
)
)
)
)
)
)
L_Permutations_Combinations: =LAMBDA(CharsToCombine,
[UseonlyXLetters],
LET(CC,
CONCAT(
CharsToCombine
),
z,
IF(ISNUMBER(
--CC
)*(LEN(
CC
)=1),
1,
IF(
UseonlyXLetters,
3,
2
)),
Q,
LAMBDA(
Q,
CC,
TOCOL(
IF(
CC<2,
1,
REPLACE(
Q(
Q,
CC-1
),
SEQUENCE(
,
CC
),
0,
CC
)
)
)
),
p,
LAMBDA(
p,
CC,
LET(
T,
LEN(
CC
),
r,
RIGHT(
CC
),
UNIQUE(
TOCOL(
IF(
T<2,
r,
REPLACE(
p(
p,
LEFT(
CC,
T-1
)
),
SEQUENCE(
,
T
),
0,
r
)
)
)
)
)
),
v,
LAMBDA(
v,
x,
UseonlyXLetters,
IF(
UseonlyXLetters>1,
TOCOL(
v(
v,
x,
UseonlyXLetters-1
)&TRANSPOSE(
x
)
),
x
)
),
SORT(
CHOOSE(
z,
Q(
Q,
CC
),
p(
p,
CC
),
LET(
x,
UNIQUE(
LEFT(
p(
p,
CC
),
UseonlyXLetters
)
),
FILTER(
x,
BYROW(
x,
LAMBDA(
A,
CONCAT(
SORT(
MID(
A,
SEQUENCE(
,
UseonlyXLetters
),
1
),
1,
1,
1
)
)=A
)
)
)
),
UNIQUE(
LEFT(
p(
p,
CC
),
UseonlyXLetters
)
),
v(
v,
UNIQUE(
MID(
CC,
SEQUENCE(
LEN(
CC
)
),
1
)
),
UseonlyXLetters
)
)
)))Excel solution 6 for Traveling Salesman Problem, proposed by Julian Poeltl:
=LET(C,"BCDE",p,LAMBDA(p,C,LET(T,LEN(C),r,RIGHT(C),UNIQUE(TOCOL(IF(T<2,r,REPLACE(p(p,LEFT(C,T-1)),SEQUENCE(,T),0,r)))))),W,"A"&SORT(p(p,C))&"A",VSTACK(HSTACK("Path","Cost"),HSTACK(W,MAP(W,LAMBDA(A,SUM(XLOOKUP(MID(A,SEQUENCE(LEN(A)),2),TOCOL(B3:B7&C2:G2),TOCOL(C3:G7),0)))))))Excel solution 7 for Traveling Salesman Problem, proposed by Julian Poeltl:
=LET(
P,
"A"&L_Permutations_Combinations(
"BCDE"
)&"A",
VSTACK(
HSTACK(
"Path",
"Cost"
),
HSTACK(
P,
MAP(
P,
LAMBDA(
A,
SUM(
MAP(
MID(
A,
SEQUENCE(
LEN(
A
)
),
2
),
LAMBDA(
A,
XLOOKUP(
A,
TOCOL(
B3:B7&C2:G2
),
TOCOL(
C3:G7
),
0
)
)
)
)
)
)
)
)
)
L_Permutations_Combinations: =LAMBDA(CharsToCombine,
[UseonlyXLetters],
LET(CC,
CONCAT(
CharsToCombine
),
z,
IF(ISNUMBER(
--CC
)*(LEN(
CC
)=1),
1,
IF(
UseonlyXLetters,
3,
2
)),
Q,
LAMBDA(
Q,
CC,
TOCOL(
IF(
CC<2,
1,
REPLACE(
Q(
Q,
CC-1
),
SEQUENCE(
,
CC
),
0,
CC
)
)
)
),
p,
LAMBDA(
p,
CC,
LET(
T,
LEN(
CC
),
r,
RIGHT(
CC
),
UNIQUE(
TOCOL(
IF(
T<2,
r,
REPLACE(
p(
p,
LEFT(
CC,
T-1
)
),
SEQUENCE(
,
T
),
0,
r
)
)
)
)
)
),
v,
LAMBDA(
v,
x,
UseonlyXLetters,
IF(
UseonlyXLetters>1,
TOCOL(
v(
v,
x,
UseonlyXLetters-1
)&TRANSPOSE(
x
)
),
x
)
),
SORT(
CHOOSE(
z,
Q(
Q,
CC
),
p(
p,
CC
),
LET(
x,
UNIQUE(
LEFT(
p(
p,
CC
),
UseonlyXLetters
)
),
FILTER(
x,
BYROW(
x,
LAMBDA(
A,
CONCAT(
SORT(
MID(
A,
SEQUENCE(
,
UseonlyXLetters
),
1
),
1,
1,
1
)
)=A
)
)
)
),
UNIQUE(
LEFT(
p(
p,
CC
),
UseonlyXLetters
)
),
v(
v,
UNIQUE(
MID(
CC,
SEQUENCE(
LEN(
CC
)
),
1
)
),
UseonlyXLetters
)
)
)))Excel solution 8 for Traveling Salesman Problem, proposed by Kris Jaganah:
=LET(r,
B3:B7,
s,
ROWS(
r
),
t,
PERMUT(
s,
s
),
u,
MAP(SEQUENCE(
t,
,
0
),
LAMBDA(x,
LET(m,
LAMBDA(ME,
n,
a,
b,
LET(p,
IF(b=0,
0,
MOD(ROUNDDOWN(x/(a/b),
0),
b)+1),
IF(
p=0,
"",
INDEX(
n,
p
)&ME(
ME,
FILTER(
n,
n<>INDEX(
n,
p
)
),
a/b,
b-1
)
))),(m(
m,
r,
t,
s
))))),
v,
TAKE(
r,
1
),
w,
FILTER(
u,
LEFT(
u
)=v
)&v,
k,
TEXTSPLIT(
ARRAYTOTEXT(
TOCOL(
r&"-"&C2:G2&"-"&C3:G7
)
),
"-",
", "
),
HSTACK(
w,
MAP(
w,
LAMBDA(
y,
SUM(
XLOOKUP(
MID(
y,
{1;2;3;4;5},
2
),
BYROW(
TAKE(
k,
,
2
),
CONCAT
),
--TAKE(
k,
,
-1
)
)
)
)
)
))
Excel solution 9 for Traveling Salesman Problem, proposed by John Jairo Vergara Domínguez:
=LET(
p,
"A"&SORT(
REDUCE(
"",
ROW(
1:4
),
LAMBDA(
a,
v,
TOCOL(
REPLACE(
a,
SEQUENCE(
,
v
),
,
MID(
"BCDE",
v,
1
)
)
)
)
)
)&"A",
HSTACK(
p,
BYROW(