Traveling Salesman
TravelingSalesmanProblem
OperationsResearchModels.TravelingSalesman.TravelingSalesmanProblem
— TypeTravelingSalesmanProblem
Description
A data structure to hold the problem definition of the traveling salesman problem.
Fields
distancematrix::Matrix{Real}
: The distance matrix representing the distances between cities.
solve
OperationsResearchModels.solve
— Methodsolve(problem::TravelingSalesmanProblem; popsize = 100, ngen = 1000, pcross = 0.8, pmutate = 0.01, nelites = 1)::TravelingSalesmanResult
Description
Given a matrix of distances wrapped in a TravelingSalesmanProblem, returns a TravelingSalesmanResult with the best route and its cost.
Arguments
problem::TravelingSalesmanProblem
: a TravelingSalesmanProblem instance containing the distance matrixpopsize::Int
: the population size. Default is 100ngen::Int
: the number of generations. Default is 1000pcross::Float64
: the crossover probability. Default is 0.8pmutate::Float64
: the mutation probability. Default is 0.01nelites::Int
: the number of elites. Default is 1
Returns
TravelingSalesmanResult
: a custom data type that holds the best route and its cost
Example
pts = Float64[
0 0;
0 1;
0 2;
1 2;
2 2;
3 2;
4 2;
5 2;
5 1;
5 0;
4 0;
3 0;
2 0;
1 0;
]
n = size(pts, 1
distmat = zeros(n, n)
for i in 1:n
for j in 1:n
distmat[i, j] = sqrt(sum((pts[i, :] .- pts[j, :]).^2))
end
end
result = solve(TravelingSalesmanProblem(distmat), ngen = 1000, popsize = 100, pcross = 1.0, pmutate = 0.10)
TravelingSalesmanResult
OperationsResearchModels.TravelingSalesman.TravelingSalesmanResult
— TypeTravelingSalesmanResult
Description
A data structure to hold the result of the traveling salesman problem.
Fields
route::Vector{Int}
: The best route found.cost::Float64
: The cost of the best route.