Hi Commanders,
Here is a little piece of software which calculates "optimized" routes. Code is written in julia (http://julialang.org/) which is free and available for all major platforms.
I used it to calculate the following rare goods round trip route:
The last column indicates the distance to the next systems. So, if your cargo bay is full, just count the distances and find your next target system.
This is the julia 0.4 code but you can just download the zip folder attached including rare goods system source file.
This was just some kind of programming exercise for me, but maybe somebody finds it usefull. Use it, analyze it, play with it, improve it, learn, have fun.
Download the rare goods list which is read in by the program:View attachment RareCommoditiesList.txt
CMDR Rex Kraemer
Here is a little piece of software which calculates "optimized" routes. Code is written in julia (http://julialang.org/) which is free and available for all major platforms.
I used it to calculate the following rare goods round trip route:
Code:
"System" "Station" "distance" "Item" "Price" "DistancesToNextSystems"
"Aerial" "Andrade Legacy" 180.0 "Edan Apples of Aerial" 621.0 " 61, 72, 94, 89, 70, 102, 109, 145, 171, 144"
"Jaroua" "Mccool City" 143.0 "Jaroua Rice" 385.0 " 45, 72, 64, 126, 161, 170, 204, 229, 199, 212"
"Irukama" "Blaauw City" 323.0 "Giant Irukama Snails" 1810.0 " 67, 88, 141, 159, 171, 209, 234, 191, 203, 234"
"Karsuki Ti" "West Market" 28.0 "Karsuki Locusts" 915.0 " 50, 148, 166, 187, 230, 255, 225, 238, 269, 303"
"Goman" "Gustav Sporer Port" 291.0 "Goman Yaupon Coffee" 1451.0 " 134, 170, 186, 224, 249, 230, 245, 274, 309, 248"
"Quechua" "Crown Ring" 120.0 "Albino Quechua Mammoth Meat" 2538.0 " 64, 62, 92, 116, 119, 133, 156, 203, 143, 124"
"Utgaroar" "Fort Klarix" 171.0 "Utgaroar Millennial Eggs" 1795.0 " 35, 80, 99, 88, 102, 128, 179, 135, 95, 75"
"Tanmark" "Cassie-L-Peia" 414.0 "Tanmark Tranquil Tea" 1814.0 " 47, 69, 65, 79, 102, 154, 107, 78, 71, 93"
"Witchhaul" "Hornby Terminal" 219.0 "Witchhaul Kobe Beef" 4520.0 " 26, 63, 71, 78, 132, 90, 86, 96, 135, 145"
"Momus Reach" "Tartarus Point" 413.0 "Momus Bog Spaniel" 1836.0 " 73, 77, 74, 128, 98, 99, 112, 157, 169, 166"
"George Pantazis" "Zamka Platform" 45.0 "Pantaa Prayer Sticks" 1827.0 " 15, 45, 91, 58, 27, 49, 110, 119, 103, 86"
"Zeessze" "Nicollier Hanger" 489.0 "Zeessze Ant Grub Glue" 380.0 " 33, 77, 55, 32, 59, 122, 130, 111, 89, 134"
"Bast" "Hart Station" 202.0 "Bast Snake Gin" 1089.0 " 58, 57, 63, 92, 155, 160, 140, 111, 154, 154"
"Ethgreze" "Bloch Station" 351.0 "Ethgreze Tea Buds" 3308.0 " 69, 93, 125, 188, 184, 155, 114, 140, 140, 141"
"AZ Cancri" "Fisher Station" 16.0 "Az Cancri Formula 42" 6442.0 " 60, 89, 144, 132, 112, 75, 121, 121, 123, 124"
"Epsilon Indi" "Mansfield Orbiter" 143.0 "Indi Bourbon" 978.0 " 32, 96, 100, 79, 62, 109, 109, 110, 112, 103"
"Tiolce" "Gordon Terminal" 158.0 "Tiolce Waste 2 Paste" 1153.0 " 65, 79, 64, 69, 113, 113, 113, 115, 103, 114"
"Phiagre" "Greeboski\'s Outpost" 85.0 "Giant Verrix" 6552.0 " 50, 66, 104, 136, 136, 136, 137, 113, 74, 119"
"Baltah\'Sine" "Baltha\'sine Station" 356.0 "Baltha\'sine Vacuum Krill" 825.0 " 40, 81, 109, 109, 110, 110, 70, 58, 91, 74"
"CD-75 661" "Kirk Dock" 339.0 "CD-75 Kitten Brand Coffee" 2373.0 " 47, 72, 72, 73, 73, 68, 97, 128, 106, 158"
"Shinrarta Dezhra (permit)" "Jameson Memorial" 347.0 "Waters of Shintara" 3710.0 " 54, 54, 56, 57, 63, 130, 164, 148, 202, 214"
"Leesti" "George Lucas" 257.0 "Leestian Evil Juice" 462.0 " 0, 3, 4, 97, 165, 185, 161, 221, 240, 195"
"Leesti" "George Lucas" 257.0 "Azure Milk" 4164.0 " 3, 4, 97, 165, 185, 161, 221, 240, 195, 184"
"Diso" "Shifnalport" 284.0 "Diso Ma Corn" 340.0 " 4, 99, 166, 186, 161, 221, 240, 197, 184, 177"
"Lave" "Lave Station" 302.0 "Lavian Brandy" 3543.0 " 98, 166, 184, 160, 220, 239, 197, 186, 178, 192"
"Arouca" "Shipton Orbital" 410.0 "Arouca Conventula Sweets" 1203.0 " 97, 121, 121, 177, 176, 124, 143, 128, 141, 162"
"Aerial" "Andrade Legacy" 180.0 "Edan Apples of Aerial" 621.0 " 61, 72, 94, 89, 70, 102, 109, 145, 171, 144"The last column indicates the distance to the next systems. So, if your cargo bay is full, just count the distances and find your next target system.
This is the julia 0.4 code but you can just download the zip folder attached including rare goods system source file.
Code:
#After installing julia you need to install this package once
# start julia and type at the command line:
# Pkg.add("DataFrames")
#
#For 3D route plotting with https://plot.ly/
# Pkg.add("Plotly")
##########################################################################
# Configure parameteres start here
#
#path to source file "Rare Commodities List.csv"
# Windows examples:
# path="d:\\Temp\\TSP"
# path="c:\\Data\\Oli\\Eigene Spiele\\EliteDangerous"
# Unix examples:
# path="/home/username/TSP"
# path="/data"
path="."
#maximum distance of station allowed to consider system
maxDistance=500
#number of cores to use
ncores=4
#starting system, as we calculate a round trip, this is the first and
# the last system in the result list
startSystemName="Aerial"
#
# end of configuration
##########################################################################
using DataFrames
addprocs(ncores)
cd(path)
# read raw data
raw = readtable("RareCommoditiesList.txt")
#
# prefilter the set of systems
#
#only use system when station distance is within some range
raw=raw[raw[:,:distance] .< maxDistance,:]
#no illegal rares
raw=raw[raw[:,:illegal] .== 0,:]
# dont consider Zaonce as you only get 1 egg
raw=raw[raw[:,:System] .!= "Zaonce",:]
function createDistances(distances,minDistances,minDistancesIndices)
numberSystems=size(distances)[1]
for col = 2:numberSystems
for row = 1:(col-1)
distance=round(sqrt((raw[col,:x]-raw[row,:x])^2+(raw[col,:y]-raw[row,:y])^2+(raw[col,:z]-raw[row,:z])^2))
distances[row,col]=distance
distances[col,row]=distance
end
end
for col = 1:numberSystems
minDistancesIndices[col,:]=sortperm(distances[col,:][:])[2:numberSystems]
minDistances[col,:]=distances[col,minDistancesIndices[col,:][:]]
end
end
#create distance matrix
numberSystems=size(raw,1)
distances=zeros(Int,(numberSystems,numberSystems))
minDistances=zeros(Int,(numberSystems,numberSystems-1))
minDistancesIndices=zeros(Int,(numberSystems,numberSystems-1))
#remove all systems which do not have at least two near neighbours
createDistances(distances,minDistances,minDistancesIndices)
maxDist=70
while true
good=[ (minDistances[i,1] < maxDist) && (minDistances[i,2] < maxDist) for i=1:size(minDistances)[1] ]
newraw=raw[good.==true,:]
if size(newraw) == size(raw)
break
end
raw=newraw
numberSystems=size(raw,1)
distances=zeros(Int,(numberSystems,numberSystems))
minDistances=zeros(Int,(numberSystems,numberSystems-1))
minDistancesIndices=zeros(Int,(numberSystems,numberSystems-1))
createDistances(distances,minDistances,minDistancesIndices)
end
startSystem=find(raw[:System].==startSystemName)
if length(startSystem) != 1
print(string("Start system \"",startSystemName,"\" not in list:\n"))
print(raw[:System])
print(string("\nUse another system as starting point!\n"))
startSystem=1
print(string("Setting start system to ",raw[:System][startSystem],"\n"))
end
import Base.pmap
function pmap(f,lst,minDistancesIndices,minDistances)
np = nprocs() # determine the number of processes available
n = length(lst)
results = cell(n)
i = 1
# function to produce the next work item from the queue.
# in this case it's just an index.
nextidx() = (idx=i; i+=1; idx)
@sync begin
for p=1:np
if p != myid() || np == 1
@async begin
while true
idx = nextidx()
if idx > n
break
end
results[idx] = remotecall_fetch(p,(args)->f(args...), Any[lst[idx],minDistancesIndices,minDistances,idx] )
end
end
end
end
end
results
end
function psplit(lst,ncores)
maxSize=20000
np = ncores
n = length(lst)
rest=n
available=np
indices1=[]
indices2=[]
idx1=0
idx2=0
size=convert(Int,(ceil(rest/available)))
nparts=min(np,n)
if size < maxSize
while rest>0
size=convert(Int,(ceil(rest/available)))
idx1=idx2+1
idx2=idx1+size-1
indices1=vcat(indices1,idx1)
indices2=vcat(indices2,idx2)
rest=rest-size
available-=1
end
else
size=maxSize
nparts=0
while rest>0
if rest < size
size=rest
end
idx1=idx2+1
idx2=idx1+size-1
indices1=vcat(indices1,idx1)
indices2=vcat(indices2,idx2)
rest=rest-size
nparts+=1
end
end
print(string("Split into ",nparts," parts. Part sizes:\n"))
results = cell(nparts)
for p=1:nparts
idx1=indices1[p]
idx2=indices2[p]
print(string(" Part ",p,": size=",idx2-idx1+1," from ",idx1," to ",idx2,"\n"))
results[p]=lst[idx1:idx2]
end
results
end
#
# this function is the core of the algorithm
# it adds to an existing route one new system N-times
# => this results in N new routes with one new system
# Example:
# Input route is [3,2,6]
# Result routes are e.g.
# [3,2,6,1]
# [3,2,6,4]
# [3,2,6,7]
# The numbers here are the indices of the system in DataFrame raw.
# The number of systems found to add depends on the arrays
# maxNextDistances
# maxNextCounts
#
@everywhere function expand(routes,minDistancesIndices,minDistances,p)
#
# maxNextDistances and maxNextCounts define the way
# the next system is added to the existing systems in a route
# - both are arrays and must have the same length
#
# maxNextDistances=[70,400]
# maxNextCounts=[2,2]
# We start with the first entry in maxNextDistances: 70
# The first entry in maxNextCounts is 2
# => find 2 systems which are less than 70 away from the last system in current route
# If we find at least one => ok, add the systems found to the current route
# creating as many new routes as systems found.
# If we find no system, go to the next index:
# maxNextDistances: 400
# maxNextCounts: 2
# => find 2 systems which are less than 400 away from the last system in current route
# If we find at least one => ok, add the systems found to the current route
# If we find no system and there is no more entry
# => the current route can not be expanded, delete it
#
# Working examples:
# maxNextDistances=[10,20,30,40,50,100,150,400]
# maxNextCounts=[1,1,2,3,4,4,5,5]
# Took 48 hours to calculate on a 128 GByte workstation, Cores used (ncores) 16
#
# maxNextDistances=[70,400]
# maxNextCounts=[2,2]
# Takes some minutes on i7, 16GByte Ram, Cores used (ncores) 4
#
# Not working:
# maxNextDistances=[1000]
# maxNextCounts=[numberSystems]
# This would calculate the complete Travelling Salesman Problem for all systems
# in your starting set. If you have super computer access you may tray with
# numberSystems > 12. On my workstation it may work with numberSystems=11, i dont try
# it will take to long to wait. We have all together 107 rare systems, try to
# calculate 107! , thats the size of the problem :-)
#
maxNextDistances=[70,400]
maxNextCounts=[2,2]
n=length(routes)
newRoutes=[]
numberSystems=size(minDistancesIndices)[2]
systemsInRoute=length(routes[1])
for routeIndex=1:n
maxNextDistanceIndex=1
route=routes[routeIndex]
currentSystem=route[systemsInRoute]
indices=1:numberSystems
usableNext=trues(numberSystems)
usableNext[findin(minDistancesIndices[currentSystem,indices],route)]=false
indices=indices[usableNext]
nextSystemsExpand=minDistancesIndices[currentSystem,indices][minDistances[currentSystem,indices] .< maxNextDistances[maxNextDistanceIndex]]
while length(nextSystemsExpand)==0 && maxNextDistanceIndex < length(maxNextDistances)
maxNextDistanceIndex+=1
nextSystemsExpand=minDistancesIndices[currentSystem,indices][minDistances[currentSystem,indices] .< maxNextDistances[maxNextDistanceIndex]]
end
nextSystemsExpand=nextSystemsExpand[1:min(maxNextCounts[maxNextDistanceIndex],length(nextSystemsExpand))]
newRoutes=vcat(newRoutes, [ vcat(route,i) for i=nextSystemsExpand ])
end
print(string(" ",p,": expanding ",n," routes finished\n"))
newRoutes
end
#
# calculate possible routes
#
systemsInRoute=1
currentSystem=startSystem
routes=collect(startSystem)
for system=1:(numberSystems-1)
print("start\n")
print(string(system," Number of routes: ",length(routes)," ; length of routes:",systemsInRoute,"\n"))
proutes=psplit(routes,ncores)
tic()
presult=pmap(expand,proutes,minDistancesIndices,minDistances)
toc()
newRoutes=[]
for j=1:length(presult)
newRoutes=vcat(newRoutes,presult[j])
end
if( length(newRoutes) > 0 )
routes=newRoutes
systemsInRoute+=1
else
break
end
print(string(system," Number of routes: ",length(routes)," ; length of routes:",systemsInRoute,"\n"))
print("end\n")
end
routes=[vcat(routes[i],startSystem) for i=1:length(routes)]
routeDistances=[[distances[routes[j][i],routes[j][i+1]] for i=1:(length(routes[j])-1)] for j=1:length(routes)]
#
# three possibilities to find the "best" route:
#
#minimize sum of route distances
shortestRouteIndex=sortperm([sum(routeDistances[j]) for j=1:length(routes)])[1]
shortestRoute=routes[shortestRouteIndex]
raw[shortestRoute,[:System,:Station,:distance,:Item,:Price]]
routeDistances[shortestRouteIndex]
#minimize the standard deviation of route distances
smallestStdRouteIndex=sortperm([std(convert(Array{Int,1},routeDistances[j])) for j=1:length(routes)])[1]
smallestStdRoute=routes[smallestStdRouteIndex]
raw[smallestStdRoute,[:System,:Station,:distance,:Item,:Price]]
routeDistances[smallestStdRouteIndex]
#minimize the maximum distance of route distances
smallestMaxRouteIndex=sortperm([maximum(routeDistances[j]) for j=1:length(routes)])[1]
smallestMaxRoute=routes[smallestMaxRouteIndex]
raw[smallestMaxRoute,[:System,:Station,:distance,:Item,:Price]]
routeDistances[smallestMaxRouteIndex]
#choose a result, I have chosen result smallestStdRoute
usedRoute=smallestStdRoute #set here
r1=r"\["
r2=r"\]"
maxDistancesToNextSystem=10
allDistances=[
join([
@sprintf("%4s",distances[usedRoute,usedRoute][[(i+1):systemsInRoute;1:(i-1)],i][j])
for j=1:maxDistancesToNextSystem
],",")
for i=1:systemsInRoute ]
allDistances=vcat(allDistances,allDistances[1])
result=raw[usedRoute,[:System,:Station,:distance,:Item,:Price]]
result[:DistancesToNextSystems]=allDistances
#print out the result
result
#or write it to a tab separated file:
#writetable("rareRoute.txt",result,separator='\t')
using Plotly
# dont use https, it seems to be broken because of libCURL
Plotly.signin("RexKraemer", "USE_YOUR_OWN_USER_AND_API_KEY",Dict("plotly_domain"=>"http://plot.ly", "plotly_api_domain"=>"http://api.plot.ly/v2"))
usedRoute=smallestStdRoute
plot_result=raw[usedRoute,[:System,:x,:y,:z]]
plot_result[:System]=[x[1:min(100,length(x))] for x=plot_result[:System] ]
trace1=Dict(
"x" => plot_result[:,:x],
"y" => plot_result[:,:y],
"z" => plot_result[:,:z],
"mode" => "lines",
"type" => "scatter3d",
"line" => Dict(
"color" => "#1f77b4",
"width" => 1
)
)
trace2=Dict(
"x" => plot_result[:,:x],
"y" => plot_result[:,:y],
"z" => plot_result[:,:z],
"mode" => "lines+markers+text",
"text" => convert(Array{ASCIIString,1},plot_result[:,:System]),
"textposition" => "top center",
"type" => "scatter3d"
)
data=[trace2]
layout = Dict(
"showlegend" => false,
"title" => "Route",
"margin" => Dict(
"l" => 0,
"r" => 0,
"b" => 0,
"t" => 0
)
)
response = Plotly.plot(data, Dict("layout" => layout, "filename" => "3d-route", "fileopt" => "overwrite"))This was just some kind of programming exercise for me, but maybe somebody finds it usefull. Use it, analyze it, play with it, improve it, learn, have fun.
Download the rare goods list which is read in by the program:View attachment RareCommoditiesList.txt
CMDR Rex Kraemer
Last edited:
