Here is the result of some recent work I have done playing around with optimizations in general.
A new route through 72 system with rare goods.
The 72 systems are those where the stations are nearer than 50000Ls.
Data source is attached and was retrieved from
https://docs.google.com/spreadsheets/d/17Zv55yEjVdHrNzkH7BPnTCtXRs8GDHqchYjo9Svkyh4/edit#gid=0
which is listed in this thread:
https://forums.frontier.co.uk/showthread.php/63119-Rare-Commodities-List!
Have a look in 3D:
https://plot.ly/~RexKraemer/158.embed
This is the route as a list of systems:
The optimization problem (travelling salesman) was solved using julia 0.5, http://julialang.org/, and here is the code:
The result is not optimal (only near optimal). Because of problems with heuristics some systems (orange in the 3D plot) had to be removed to find a intermediate solution. These systems have been incrementally added to the intermediate solution afterwards.
I don't know if there still are any rare commodity traders out there. This profession seems to be outdated today. Anyways, I had some fun doing this stuff and if somebody can make use of it I am glad.
Good luck and fly safe, CMDRs
A new route through 72 system with rare goods.
The 72 systems are those where the stations are nearer than 50000Ls.
Data source is attached and was retrieved from
https://docs.google.com/spreadsheets/d/17Zv55yEjVdHrNzkH7BPnTCtXRs8GDHqchYjo9Svkyh4/edit#gid=0
which is listed in this thread:
https://forums.frontier.co.uk/showthread.php/63119-Rare-Commodities-List!
Have a look in 3D:
https://plot.ly/~RexKraemer/158.embed
This is the route as a list of systems:
Code:
¦ Row ¦ System ¦ Station ¦
+-----+-----------------------------+------------------------------------------------------------------------¦
¦ 1 ¦ 39 Tauri ¦ Porta ¦
¦ 2 ¦ Fujin ¦ Futen Spaceport ¦
¦ 3 ¦ Witchhaul ¦ Hornby Terminal ¦
¦ 4 ¦ Jotun (permit) ¦ Icelock ¦
¦ 5 ¦ HIP 10175 ¦ Stefanyshyn-Piper Station ¦
¦ 6 ¦ Momus Reach ¦ Tartarus Point ¦
¦ 7 ¦ Hecate ¦ RJH1972 ¦
¦ 8 ¦ Thrutis ¦ Kingsbury Dock ¦
¦ 9 ¦ Damna ¦ Nemere Market ¦
¦ 10 ¦ Volkhab ¦ Vernadsky Dock ¦
¦ 11 ¦ Alacarakmo ¦ Weyl Gateway ¦
¦ 12 ¦ Rajukru ¦ Snyder Terminal ¦
¦ 13 ¦ HIP 80364 ¦ Stasheff Colony ¦
¦ 14 ¦ Kongga ¦ Laplace Ring ¦
¦ 15 ¦ Esuseku ¦ Savinykh Orbital ¦
¦ 16 ¦ Ochoeng ¦ Roddenberry Gateway ¦
¦ 17 ¦ Wulpa ¦ Williams Gateway ¦
¦ 18 ¦ Nguna ¦ Biggle Hub ¦
¦ 19 ¦ Kachirigin ¦ Nowak Orbital ¦
¦ 20 ¦ Vanayequi ¦ Clauss Hub ¦
¦ 21 ¦ Kinago ¦ Fozard Ring ¦
¦ 22 ¦ Karetii ¦ Sinclair Platform ¦
¦ 23 ¦ Heike ¦ Brunel City ¦
¦ 24 ¦ Helvetitj ¦ Friend Orbital ¦
¦ 25 ¦ Eleu ¦ Finney Dock ¦
¦ 26 ¦ Orrere ¦ Sharon Lee Free Market ¦
¦ 27 ¦ Uszaa ¦ Guest Installation ¦
¦ 28 ¦ Diso ¦ Shifnalport ¦
¦ 29 ¦ Leesti ¦ George Lucas,George Lucas ¦
¦ 30 ¦ Lave ¦ Lave Station ¦
¦ 31 ¦ Shinrarta Dezhra (permit) ¦ Jameson Memorial ¦
¦ 32 ¦ CD-75 661 ¦ Kirk Dock ¦
¦ 33 ¦ Baltah'Sine ¦ Baltha'sine Station ¦
¦ 34 ¦ HR 7221 ¦ Veron City ¦
¦ 35 ¦ Phiagre ¦ Greeboski's Outpost ¦
¦ 36 ¦ Coquim ¦ Hirayama Installation ¦
¦ 37 ¦ Xihe ¦ Zhen Dock ¦
¦ 38 ¦ Tiolce ¦ Gordon Terminal ¦
¦ 39 ¦ Chi Eridani ¦ Steve Masters station ¦
¦ 40 ¦ Tanmark ¦ Cassie-L-Peia ¦
¦ 41 ¦ Utgaroar ¦ Fort Klarix ¦
¦ 42 ¦ Delta Phoenicis ¦ Trading post ¦
¦ 43 ¦ Aerial ¦ Andrade Legacy ¦
¦ 44 ¦ Belalans ¦ Boscovich Ring ¦
¦ 45 ¦ Quechua ¦ Crown Ring ¦
¦ 46 ¦ Rapa Bao ¦ Flagg Gateway ¦
¦ 47 ¦ Holva ¦ Kreutz Orbital ¦
¦ 48 ¦ Yaso Kondi ¦ Wheeler Market ¦
¦ 49 ¦ Kamitra ¦ Hammel Terminal ¦
¦ 50 ¦ Njangari ¦ Lee Hub ¦
¦ 51 ¦ Wuthielo Ku ¦ Tarter Dock ¦
¦ 52 ¦ Eshu ¦ Shajn Terminal ¦
¦ 53 ¦ Goman ¦ Gustav Sporer Port ¦
¦ 54 ¦ Karsuki Ti ¦ West Market ¦
¦ 55 ¦ Jaroua ¦ Mccool City ¦
¦ 56 ¦ Irukama ¦ Blaauw City ¦
¦ 57 ¦ Ngurii ¦ Cheranovsky City ¦
¦ 58 ¦ Toxandji ¦ Tsunenaga Orbital (black market available at Alvares Dock - 7300 Ls) ¦
¦ 59 ¦ Sanuma ¦ Dunyach Gateway ¦
¦ 60 ¦ Any Na ¦ Libby Orbital ¦
¦ 61 ¦ Arouca ¦ Shipton Orbital ¦
¦ 62 ¦ Deuringas ¦ Shukor Hub ¦
¦ 63 ¦ Neritus ¦ Toll Ring ¦
¦ 64 ¦ Aegaeon ¦ Schweikart Station ¦
¦ 65 ¦ AZ Cancri ¦ Fisher Station ¦
¦ 66 ¦ Ethgreze ¦ Bloch Station ¦
¦ 67 ¦ Bast ¦ Hart Station ¦
¦ 68 ¦ Zeessze ¦ Nicollier Hanger ¦
¦ 69 ¦ Vega (permit) ¦ Taylor City ¦
¦ 70 ¦ Altair ¦ Solo Orbiter ¦
¦ 71 ¦ Epsilon Indi ¦ Mansfield Orbiter ¦
¦ 72 ¦ George Pantazis ¦ Zamka Platform ¦
¦ 73 ¦ 39 Tauri ¦ Porta ¦The optimization problem (travelling salesman) was solved using julia 0.5, http://julialang.org/, and here is the code:
Code:
#Pkg.add("DataFrames")
#Pkg.add("JuMP")
#Pkg.add("GLPKMathProgInterface")
using JuMP
#using Gurobi
using GLPKMathProgInterface
#using CPLEXLink
using DataFrames
path="c:\\Data\\EliteDangerous\\RareGoodsRoute"
cd(path)
raw = readtable("RareCommoditiesList_rev1384.txt",separator=';')
maxDistance=50000
#startSystemName="Aerial"
raw=raw[raw[:,:distance] .< maxDistance,:]
raw=raw[raw[:,:illegal] .== 0,:]
raw=raw[raw[:,:System] .!= "Zaonce",:]
#remove not unique entries (e.g. Leesti)
N=size(raw)[1]
hold=fill(true,N)
raw[:,:distance]=[string(raw[x,:distance]) for x=1:N]
raw[:,:illegal]=[string(raw[x,:illegal]) for x=1:N]
raw[:,:Price]=[string(raw[x,:Price]) for x=1:N]
for system in unique(sort(raw[:System]))
multirow=(1:N)[raw[:System].==system]
if length(multirow)>1
for i in multirow[2:end]
raw[multirow[1],:Station]=string(raw[multirow[1],:Station],",",raw[i,:Station])
raw[multirow[1],:distance]=string(raw[multirow[1],:distance],",",raw[i,:distance])
raw[multirow[1],:Item]=string(raw[multirow[1],:Item],",",raw[i,:Item])
raw[multirow[1],:Price]=string(raw[multirow[1],:Price],",",raw[i,:Price])
raw[multirow[1],:illegal]=string(raw[multirow[1],:illegal],",",raw[i,:illegal])
raw[multirow[1],:MAXIMUM_CAP_t_]=string(raw[multirow[1],:MAXIMUM_CAP_t_],",",raw[i,:MAXIMUM_CAP_t_])
raw[multirow[1],:SUPPLY_RATE_t_]=string(raw[multirow[1],:SUPPLY_RATE_t_],",",raw[i,:SUPPLY_RATE_t_])
hold[i]=false
end
end
end
raw=raw[hold,:]
N=size(raw)[1]
coord=[raw[:x] raw[:y] raw[:z]]
alldist = zeros(N, N)
for i = 1:N
for j = i:N
d = norm(coord[i,1:3] - coord[j,1:3])
alldist[i,j] = d
alldist[j,i] = d
end
end
function findSubtour(n, sol)
# Initialize to no subtour
subtour = fill(false,n)
# Always start looking at city 1
cur_city = 1
subtour[cur_city] = true
subtour_length = 1
while true
# Find next node that we haven't yet visited
found_city = false
for j = 1:n
if !subtour[j]
if sol[cur_city, j] >= 1 - 1e-6
# Arc to unvisited city, follow it
cur_city = j
subtour[j] = true
found_city = true
subtour_length += 1
break # Move on to next city
end
end
end
if !found_city
# We are done
break
end
end
return subtour, subtour_length
end
function findAllSubtours(n, sol)
allSubtours=[]
citiesUsed=fill(true,n)
while true
# Initialize to no subtour
subtour = fill(false,n)
# Always start looking at city 1
cur_city = (1:n)[citiesUsed][1]
subtour[cur_city] = true
citiesUsed[cur_city] = false
subtour_length = 1
while true
# Find next node that we haven't yet visited
found_city = false
for j = 1:n
if !subtour[j]
if sol[cur_city, j] >= 1 - 1e-6
# Arc to unvisited city, follow it
cur_city = j
subtour[j] = true
citiesUsed[j] = false
found_city = true
subtour_length += 1
break # Move on to next city
end
end
end
if !found_city
# We are done
break
end
end
push!(allSubtours,subtour)
if length(citiesUsed[citiesUsed])==0
break
end
end
return allSubtours
end
function s(N,dist,preresult=Array{Float64}(0,0))
m = Model(solver=GLPKSolverMIP())
@variable(m,x[1:N,1:N],Bin)
@objective(m,Min,sum{dist[i,j]*x[i,j],i=1:N,j=i:N})
for i = 1:N
@constraint(m, x[i,i] == 0)
for j = (i+1):N
@constraint(m, x[i,j] == x[j,i])
end
end
for i = 1:N
@constraint(m, sum{x[i,j], j=1:N} == 2)
end
if size(preresult)!=(0,0)
for i = 1:size(preresult)[1], j = 1:size(preresult)[2]
if i!=j
if preresult[i,j]>=1.0-1e-06
@constraint(m,x[i,j]==1.0)
end
end
end
end
function subtourLazyConstraint(cb)
allSubtours=findAllSubtours(N,getvalue(x))
# Only one "subtour" with all cities, so we are done
if length(allSubtours)==1 && length(allSubtours[1])==N
return
end
for subtour in allSubtours
arcs_from_subtour = AffExpr()
arcsCount=0
for i = 1:N
if !subtour[i]
continue
end
for j = 1:N
if i == j
continue
elseif !subtour[j]
continue
else
if getvalue(x)[i,j] >= 1 - 1e-6
arcs_from_subtour += x[i,j]
arcsCount+=1
end
end
end
end
# Add the new subtour elimination constraint we built
@lazyconstraint(cb, arcs_from_subtour <= arcsCount-1 )
end
end
function subtourLazyConstraint2(cb)
# Find any set of cities in a subtour
subtour, subtour_length = findSubtour(N, getvalue(x))
if subtour_length == N
# This "subtour" is actually all cities, so we are done
return
end
# Subtour found - add lazy constraint
# We will build it up piece-by-piece (variable-by-variable)
arcs_from_subtour = AffExpr()
for i = 1:N
if !subtour[i]
# If this city isn't in subtour, skip it
continue
end
# Want to include all arcs from this city, which is in
# the subtour, to all cities not in the subtour
for j = 1:N
if i == j
# Self-arc
continue
elseif subtour[j]
# Both ends in same subtour
continue
else
# j isn't in subtour
arcs_from_subtour += x[i,j]
end
end
end
# Add the new subtour elimination constraint we built
@lazyconstraint(cb, arcs_from_subtour >= 2)
end
addlazycallback(m, subtourLazyConstraint2)
solve(m)
x
end
function showTour(N,r,start)
indices=zeros(Int,N+1)
index=1
#println(start)
indices[index]=start
index+=1
next=(1:N)[r[start,:].>0.8][1]
#println(next)
indices[index]=next
index+=1
laststart=start
while next!=start
lasttmp=next
nexttwo=(1:N)[r[next,:].>0.8]
next=nexttwo[nexttwo.!=laststart][1]
#println(next)
indices[index]=next
index+=1
laststart=lasttmp
end
indices
end
#coord=randn(N,3)
lastsystem=10
removedsystems=[]
solution=[]
result=[]
tour=[]
systems=[]
while lastsystem<=size(raw)[1]
systems=collect(1:lastsystem)
filter=fill(true,lastsystem)
filter[removedsystems]=false
systems=systems[filter]
N=length(systems)
dist = zeros(N, N)
for i = 1:N
for j = i:N
d = norm(coord[systems[i],1:3] - coord[systems[j],1:3])
dist[i,j] = d
dist[j,i] = d
end
end
solution=s(N,dist)
result=getvalue(solution)
tour=showTour(N,result,1)
if length(tour[tour.!=0])<N+1
push!(removedsystems,lastsystem)
end
lastsystem+=1
end
removedsystems=[Int(x) for x in removedsystems]
tour=systems[tour]
#as=findAllSubtours(N,result)
#(1:N)[as[1]]
addedsystems=[]
for removed in removedsystems
completetour=deepcopy(tour)
completetour=completetour[1:end-1]
i=2
nearest=sortperm(alldist[removed,:])[i]
nearestindex=findfirst(completetour,nearest)
while nearestindex==0
i+=1
nearest=sortperm(alldist[removed,:])[i]
nearestindex=findfirst(completetour,nearest)
end
cut=1
removefromresult=[ findfirst(systems,x) for x in completetour[nearestindex-cut:nearestindex+cut] ]
result[removefromresult,:]=0.0
result[:,removefromresult]=0.0
##splice!(completetour,nearestindex,[nearest,removed])
splice!(systems,removed,[removed,systems[removed]])
N=length(systems)
newresult=Array{Float64}(N,N)
for i = 1:N
for j = 1:N
if i>=removed
offseti=1
else
offseti=0
end
if j>=removed
offsetj=1
else
offsetj=0
end
if i==removed || j==removed
newresult[i,j]=0.0
else
newresult[i,j]=result[i-offseti,j-offsetj]
end
end
end
dist = zeros(N, N)
for i = 1:N
for j = i:N
d = norm(coord[systems[i],1:3] - coord[systems[j],1:3])
dist[i,j] = d
dist[j,i] = d
end
end
solution=s(N,dist,newresult);
result=getvalue(solution);
tour=showTour(N,result,1)
if length(tour[tour.!=0])<N+1
println("break")
break
end
push!(addedsystems,removed)
tour=systems[tour]
end
#Pkg.add("PlotlyJS")
#Blink.AtomShell.install()
using Blink
using Plotly
plot_result1=raw[removedsystems,[:System,:x,:y,:z]]
plot_result1[:System]=[x[1:min(100,length(x))] for x=plot_result1[:System] ]
plot_result2=raw[tour,[:System,:x,:y,:z]]
plot_result2[:System]=[x[1:min(100,length(x))] for x=plot_result2[:System] ]
trace1=scatter3d(;
x=plot_result1[:,:x],
y=plot_result1[:,:y],
z=plot_result1[:,:z],
mode="markers+text",
text=convert(Array{String,1},plot_result1[:,:System]),
textposition="top center",
)
trace2=scatter3d(;
x=plot_result2[:,:x],
y=plot_result2[:,:y],
z=plot_result2[:,:z],
mode="lines+markers+text",
text=convert(Array{String,1},plot_result2[:,:System]),
textposition="top center",
)
data=[trace2,trace1]
layout = Layout(;
title="72 Systems 3d-Route",
showlegend=false,
margin=attr(l=0, r=0, b=0, t=150)
)
myPlot = Plotly.plot(data,layout)
myPlotThe result is not optimal (only near optimal). Because of problems with heuristics some systems (orange in the 3D plot) had to be removed to find a intermediate solution. These systems have been incrementally added to the intermediate solution afterwards.
I don't know if there still are any rare commodity traders out there. This profession seems to be outdated today. Anyways, I had some fun doing this stuff and if somebody can make use of it I am glad.
Good luck and fly safe, CMDRs
Last edited: