The Gargantuan, Magical and Nebulous Pilgrimage

[Jah'bastah II]

~
travel over 1 MegaLy and
visit 434 of the best and
beautiful places in the galaxy
~
partake in the greatest adventure and
ultimate explorer's challenge with literally
over 9000 hours worth of content
~

​

 

[Orvidius]

Can someone help me find/create a 3D Travelling Salesman algorithm in python to find the optimal route between all the waypoints? I think it's pretty ok now, but with more waypoints it might get tricky.

What's funny is that I've been programming in a variety of ways for 30 years, and never had the need to write a traveling salesman algorithm. That could be very useful here though. I've also done very little Python. So I can't promise anything, and if anyone else here wants to take a stab, please feel free.

Otherwise I'm toying with one in Perl right now. As with most things in computer science, there's a multitude of solutions and algorithms out there, with a wide range of advantages and disadvantages. To keep things simple, I'm trying to write a brute force algorithm that takes some inspiration from the "Branch and Bound" method to at least be slightly faster than an exhaustive search. I think this is fine for small lists. (Keeping in mind, that even a few hundred waypoints is still a pretty small list. If it were 100,000 items (or millions), that would be a different story).

 

[Orvidius]

This probably isn't much help, since my current script doesn't have the requirement of returning to the starting position. It's just a shortest path to hit them all once, which of course wants to put Maledictus Luna last.

EDIT: Test output removed. Too buggy.

EDIT 2: A fundamental design flaw was resulting in just quickly returning a "nearest neighbor" solution. A true brute-force approach also isn't ideal even with as few as 100 locations, since the execution time would be "100!" (100 factorial). This definitely needs at least a Branch & Bound method, or a fuzzy solution or something.

 

[Jah'bastah II]

I think machine learning could be of great use here. I made a spreadsheet I can invite you to with a distance matrix (in guess-timate jumps, for whatever ship range is put in). Alternatively, we could base a neural net on the distance matrix and set a pseudo-optimal distance for the entire route and set the failure cost of the neural net. I might just program it in raw python, but I've got so little spare time lately...

ML aside, I think a sort of clustering + Ant Colony Optimisation hybrid might be the way to go, since a lot of the locations are clustered around hotspots (local bubble, SagA*, Colonia, Beagle Point) and I haven't found a good 3D solution to the TSP. Here's a suggestion:

1) pick a random point, add vertices to points within a certain range (D) if they don't have two already. Move to a new random point and repeat to make all the clusters
2) find the smallest distance between each two clusters and add as vertex
3) where there are three vertices on one point, delete the vertex that connects to the nearest point that also has 3 vertices

4a) repeat 1 to 3 for different ranges D and different starting points (diff seed/iteration for the random point selection)
4b) add a weight to the vertices each time you do this (pheromone)

5) let the pheromones (vertex weight) show you the optimal path

See any holes in this?

Whatever we come up with, we should call it The Spaceman Pilgrimage Problem.

 

[Alec Turner]

Excellent idea! I was surprised to not see BD-12 1172 (Spirograph nebula) on your list (maybe I missed it) because I reckon' that's one of the most beautiful systems in the galaxy.

The-most-beautiful-system-in-the-galaxy

 

[Jah'bastah II]

/added

I thought I had it in there!! I saw your thread (or at least the name 'spirograph nebula') when I searched the forums for interesting locations, but I've been multitasking when I compiled the list so I must have missed it. This is what I hope this thread and the GMNP will turn into btw, a means to share all the best stuff and add it as part of a scenic route. I'm gonna add more of the nebulae and interesting locations this evening.

 

[Alec Turner]

OK, let's have a checklist of a few more "obvious" candidates in case they've slipped your net.

Mitterand Hollow (Epsilon Indi)

"The planet of Death" (SPOIHAAE XE-X D2-9)

"Glowing Green Giants"

You might also get some inspiration from Orvidius' fantastic heat map (turn on the POI markers to see what some of those popular hotspots relate to).

https://edastro.com/galmap/

 

[Jah'bastah II]

OK, let's have a checklist of a few more "obvious" candidates in case they've slipped your net.

Mitterand Hollow (Epsilon Indi)

"The planet of Death" (SPOIHAAE XE-X D2-9)

"Glowing Green Giants"

You might also get some inspiration from Orvidius' fantastic heat map (turn on the POI markers to see what some of those popular hotspots relate to).

https://edastro.com/galmap/

• CHECK: New Africa - Mitterand Hollow (one of the first ones on my list and inspiration for this route)
• SPOIHAAE XE-X D2-9 /added, looks cool! (is that the one from YouTube: Ghost Giraffe's tourist videos?) (EDIT: Yes, it is, I forgot where to look but I was planning on adding it too. See below)
• CHECK: Glowing Green Giants, I haven't included all of them but I might as well... There's bound to be some uniqueness to each find, like the proximity of a landable and the star type near it.
• Orvidiu's fantastic heat map: thanks, I'll have a look!
• Youtube's Ghost Giraffe also rode a mountain into orbit, apparently on Nervi 3 a /added

I'm still looking for that epic ringed star that spans more than a couple AU.

 

[Alec Turner]

• Youtube's Ghost Giraffe also rode a mountain into orbit, apparently on Nervi 3 a /added

Note that although Mount Neverest is still there, FD adjusted the planets boundary zone so it's no longer possible to ride the mountain into orbit. That said I was still going to suggest that location as it is still a huge mountain.

 

[Lance 'Spacecat' D.]

I recommend the Dryau Awesomes, it's not listed in many places but as quite possibly the craziest sky in the Elite Galaxy... Well, you gotta see it to believe it sometime. Neutron with a gas giant in absurdly close proximity, then a nearby small gas giant (ringed) with a big waterworld dancing with it, and two moons you can land on.

Name: The Dryau Awesomes
System: DRYAU AUSMS KG-Y E3390

reference: https://forums.frontier.co.uk/showt...pedition-Hub?p=6598194&viewfull=1#post6598194

 

[Orvidius]

I remember reading that on the whole, humans and machine-learning algorithms tend to achieve similar results, and similar success rates on the Traveling Salesman Problem. That's probably worth considering here.

The TSP is a difficult problem indeed, but I've been intrigued by some of the solutions out there. The Branch and Bound is super non-intuitive, but looks like it's computationally efficient, relatively speaking.

I've toyed with some simple bounding in an otherwise brute-force approach, and nothing I've tried so far speeds up the process anywhere near what would be required. I might try the B&B approach if I can wrap my brain around it. That's a big "if".

 

[Orvidius]

I think a sort of clustering + Ant Colony Optimisation hybrid might be the way to go, since a lot of the locations are clustered around hotspots (local bubble, SagA*, Colonia, Beagle Point) and I haven't found a good 3D solution to the TSP. Here's a suggestion:

This could be a good idea too. Hmmm, lots to consider.

 

[Jah'bastah II]

Note that although Mount Neverest is still there, FD adjusted the planets boundary zone so it's no longer possible to ride the mountain into orbit. That said I was still going to suggest that location as it is still a huge mountain.

Noted!

I recommend the Dryau Awesomes, it's not listed in many places but as quite possibly the craziest sky in the Elite Galaxy... Well, you gotta see it to believe it sometime. Neutron with a gas giant in absurdly close proximity, then a nearby small gas giant (ringed) with a big waterworld dancing with it, and two moons you can land on.

Name: The Dryau Awesomes
System: DRYAU AUSMS KG-Y E3390

reference: https://forums.frontier.co.uk/showt...pedition-Hub?p=6598194&viewfull=1#post6598194

/added, + the silvery highway and one of the fumarole ones (won't add everything in that thread, but I'll have a look later)

I remember reading that on the whole, humans and machine-learning algorithms tend to achieve similar results, and similar success rates on the Traveling Salesman Problem. That's probably worth considering here.

The TSP is a difficult problem indeed, but I've been intrigued by some of the solutions out there. The Branch and Bound is super non-intuitive, but looks like it's computationally efficient, relatively speaking.

I've toyed with some simple bounding in an otherwise brute-force approach, and nothing I've tried so far speeds up the process anywhere near what would be required. I might try the B&B approach if I can wrap my brain around it. That's a big "if".

Alright, let us know! I'm gonna dedicate the next few days to this problem. The fact that comparatively very little 3D TSP research has been done makes this all the more fun. I'm sure third party tools like EDD, EDSM, spansh.co.uk and the likes might find this optimisation useful as well.

 

[Orvidius]

Alright, let us know! I'm gonna dedicate the next few days to this problem. The fact that comparatively very little 3D TSP research has been done makes this all the more fun. I'm sure third party tools like EDD, EDSM, spansh.co.uk and the likes might find this optimisation useful as well.

Actually I'm starting to think you might be on the right track with the ant colony, the more I think about it. The thing is, even with Branch & Bound, the number of permutations to consider can grow quite large, and B&B has the added requirement of storing, inheriting, and altering large matrices at each node. From what I've been reading, the success/performance of the B&B method often is dependent on how good of a heuristic you can use to set an initial bound, and having a node queue with a smart sort ordering for "best first" processing (instead of "depth first" etc). So we could put a huge amount of effort into this, and still have something that performs poorly for a data set of this size. A smart heuristic or geometric approach might be better in that regard, and produce results that are good enough.

I actually don't think the 3D aspect is particularly difficult in this case. All that really matters is the linear distance between waypoints, and in terms of a TSP algorithm, that can still easily translate into a simple cost matrix. And it's a symmetrical one too, which avoids the added complexity of an asymmetrical cost matrix.

Anyway, I might shelve the B&B TSP algorithm for the moment (though I'm still tempted to code one anyway, just because).

 

[Jah'bastah II]

Actually I'm starting to think you might be on the right track with the ant colony, the more I think about it. The thing is, even with Branch & Bound, the number of permutations to consider can grow quite large, and B&B has the added requirement of storing, inheriting, and altering large matrices at each node. From what I've been reading, the success/performance of the B&B method often is dependent on how good of a heuristic you can use to set an initial bound, and having a node queue with a smart sort ordering for "best first" processing (instead of "depth first" etc). So we could put a huge amount of effort into this, and still have something that performs poorly for a data set of this size. A smart heuristic or geometric approach might be better in that regard, and produce results that are good enough.

I actually don't think the 3D aspect is particularly difficult in this case. All that really matters is the linear distance between waypoints, and in terms of a TSP algorithm, that can still easily translate into a simple cost matrix. And it's a symmetrical one too, which avoids the added complexity of an asymmetrical cost matrix.

Anyway, I might shelve the B&B TSP algorithm for the moment (though I'm still tempted to code one anyway, just because).

Yeah, I picked the ACO because I expect it to return close to optimal (97.5-100%) really fast, even with 200-300 points in 3D (considering most will hang near the galactic plane, the third dimension shouldn't matter much in most cases, but shorter denser routes and the occasional Y-axis detour will benefit from keeping the Y-axis coords). Anyway, clustering + pheromones seems to me the most efficient way. Clustering to skip a lot of "ant work" and it will be quite fast.

Edit: I added a "Gargantuan Magical and Nebulous Pilgrimage" patch.

(link to big version)

Edit2: I think the devs put my route to private because I was refreshing too much in the sorting process.... will publish again once I reach 200 waypoints later this evening

 

[Jah'bastah II]

I updated the route and it now contains the following 200 waypoints:

Spoiler

Egnaix GW-V e2-0

Egnaix XJ-Z e30 (Heliotropeia Monoceratos)

Mynoaw NY-K b37-55 (Mynoaw Nebula)

Eeshorks SD-B d3065

Greae Phio LS-L c23-797

Boepp XA-D d13-1042 (Kaw Nebula)

Iowhail WY-S e3-8736

Froarks XJ-R e4-1363 (Froarks Planetary Nebula)

Froarks JH-T d4-353

Blae Hypue NH-V e2-9

Clookuia AR-U c16-2

Circinus Pulsar (The Circinus Pulsar)

Phrooe Flyuae QE-Y d1-44 (Speculo System)

Pueliae SH-P c20-0

Rhadia AA-A h59 (Hawking´s Dream)

NGC 3199 Sector KX-T b3-0

Eta Carina Sector JM-W d1-1

Skull and Crossbones Neb. Sector FG-Y e6

NGC 2244 CDZ 132

Rosette Sector GW-W d1-97

GCRV 4925 (NGC 2371)

Monkey Head Sector QD-S b4-0

Cyoidai GH-U e3-3 (Sunny Side Down (Planetary Nebula) / Cyoidai GH-U Supernova Remnant)

Crab Pulsar

NGC 1931 Sector HW-W c1-13

BD+50 886 (NGC 1491)

Soul Sector LC-V c2-16

2MASS J02351897+6131236 (Fireflies)

Heart Sector NS-T b3-1

BD+55 191 (NGC 281)

Bubble Sector PD-S b4-4 (Bubble Nebula)

S171 29

Cave Sector FB-X c1-5 (Cave Nebula)

SHB2004 Trumpler 37 12-2113

BD+66 1066

Cocoon Sector EL-Y d19

Crescent Sector GW-W c1-8 (Medusa's Rock)

V1357 Cygni

North America Sector GC-K a9-1

Veil East Sector DL-Y d54

Veil West Sector DL-Y d68 (Funfair Geysers / Veil Nebula West)

BD+22 3878 (Dumbbell Nebula)

HIP 14769

HIP 17403

Aries Dark Region GW-W d1-34

Nervi (Mount Nerverest)

Epsilon Indi

Pomeche

Witch Head Sector DL-Y d22

HIP 31384

BD-12 1172 (Spirograph Nebula)

The Veil

Trapezium Sector CB-W c2-3

Trapezium Sector AF-Z c5 (Flame Nebula)

Trapezium Sector XO-Y b1-0 (Altered Hortensia)

Trapezium Sector AF-Z c0 (Barnard's Loop)

Orion Dark Region KC-V c2-0 (The Orion Dark Region Nebula)

HD 49368 (Hades Edge)

Cone Sector GW-W c1-5

R Monocerotis (Hubble's Variable Nebula)

HIP 38064 (Collinder 140 Open Cluster)

Vela Dark Region LC-V c2-29 (Vela Dark Region)

HIP 41908 (Baton's Plantation)

Chamaeleon Sector PD-S b4-2

Musca Dark Region ZB-I a11-0

Corona Austr. Dark Region PD-S b4-3

Ophiuchus Dark Region B Sector PD-S b4-2

IC 4604 Sector FB-X c1-19

HD 148937

NGC 6188 Sector HW-W c1-11

Cat's Paw Sector PD-S b4-7

Thor's Eye

Herschel 36 (Lagoon Nebula)

Trifid Sector DH-K a9-6 (Trifid Nebula)

Omega Sector PD-S b4-0 (Omega Nebula)

Eagle Sector PD-S b4-5

Cl Pismis 16

Prieluia GH-B c27-16 (Prieluia's Furnace)

Plaa Ain KS-A b2-5

Pru Aescs UO-V b30-7

Flyiedge RW-W d1-4

Flyiedgai MX-E c26-10

Skaude AL-X e1-28 (Rusty Net)

Skaudai LC-V f2-10

Prua Phoe TS-B d126

Clookia NK-M d8-431 (Ewoks Rest)

Blaa Phoe JX-T e3-26 (Helium Paradox)

Dryooe Flyou YT-A e1844 (Bartender Nebula)

Spoihaae XE-X d2-9 (Monde de la Mort (World of Death))

Rodentia

Colonia (Jaques Station / Animula Spires / The Mosta-Murdoch Raceway)

Spoihaae EW-V e2-670

Dryooe Prou HH-C d267 (The Clover Nebula)

Screake SJ-Y d1-265 (Pink Elephants)

Oephaif GE-E b1-10 (Green Lantern Nebula)

Grea Hypooe ZZ-O d6-19

Ellaid AA-A h5

Zejoo WM-Q b52-2

Dehoae FL-W d2-0 (Seashell Nebula)

Bloo Dryue ND-I d10-19 (Circulum)

Eullobs EL-Y e7 (Fireball Fumaroles)

Fraufooe AA-A h8 (Angustia Trinity)

Byooe Thio AA-A g1 (Bary’s Wonderland)

Ovomly PD-R d5-3 (Ovomly Rings)

Thraikoo PS-U e2-4 (Thracian Nebula)

Crooki PX-V c17-5 (Lonely Lantern Nebula)

Grea Hypae WU-O e6-4 (Enigma Depot)

Floasly TE-X d2-25 (Floasly Glowing Green Giant)

Floagh FI-B d13-1 (Looking Glass Nebula)

Screakoi WO-G c11-1 (Karmeliet)

Hypoea Flyiae CW-V e2-0 (Phorcys Black Hole)

Pha Flaae HT-H d10-56 (Trefoil)

Dryu Chraea FH-D d12-49 (Maledictus Luna)

Eol Groa UG-K d9-89 (Creme Brulee Geysers)

Eolls Graae PG-E b15-4 (Bendurion's Present)

Juemeou GN-S e4-18 (Odysseus's Rest)

Phooe Auf HV-I c24-0 (Fountain of Starlight)

Guenae SB-I b57-0 (Turqoise Fountain)

Pyroomeou GE-C c28-0

Phreia Flyou JT-P b22-2 (Valley of Vapour)

Phooe Aob OU-V b7-0

Phreia Flyou FG-V d3-116 (La Vita Nuova)

Phreia Flyou UB-A b32-0 (Blessed Nebula)

Juenoe EG-Y g1913 (Dance of Cerberus)

Eord Gree UU-X e1-1268

Eimbaisys JC-V e2-352

Pha Scroi GS-I d10-64 (Minerva's Pyrope)

Screakou EW-N e6-5997 (La vie en Rose)

Scheau Flyi GH-U e3-3617 (Flos Nebula)

Wepooe AA-A h509 (Chief's Pride)

Dumbaa XJ-R e4-5596 (Blue Lilies Nebula)

Theau Pri FB-W e2-25 (Pink Marshmallow)

Dryaa Pruae GG-Y e5180 (The 'Neutron' Nebula)

Dryau Ausms KG-Y e3390 (The Dryau Awesomes)

Leamuae SI-T e3-4236

Shrogea MH-V e2-1763 (Black in Green (Tourist Installation))

Dumbae SY-I d9-2339

Hypuae Audst OF-E d12-978

Croomaa RD-A d14-1524

Juenae OX-U e2-8852 (Hengist Nebula)

Eok Bluae MU-V c16-2452

Eok Gree TO-Q e5-3167 (Green Crystal Stellar Remnant)

Iwhaind AA-A g1771 (Niteo Gigans)

Scheau Byoe XJ-P d6-1080

Hypiae Briae KM-W d1-2603

Hypiae Briae FR-N e6-3007

Vegnue VK-E d12-1019

Gooreia WO-Z e131 (Our Lady's Modesty)

Dryiquae OI-B d13-0

Bleethue KR-A b15-0 (Beetle Nebula)

Phroea Gree PU-D d13-3163 (Starfish Nebula)

Teqo EB-V c16-5 (Mt Fuji Nebula)

Vegnae YE-R e4-121 (Scroll Of Thoth)

Vegneia BF-R e4-735 (Segnao Starburst (Segnao-2))

Greethia SS-U e2-48 (Lapislazuli Nebula)

Myoangooe KD-S e4-2 (Winds Of Enlil)

Myoangooe AA-A h1 (Throne Of Marduk)

Hyphokooe AA-A h62 (Gates Of Apzu / Lower Boreas Depot)

Trignai MT-Q e5-28 (Trignai Blend)

Eactaisky IR-N e6-2 (Eactaisky Stellar Remnant)

Flyoo Groa SO-Z e0 (Alastor)

Eufarb UT-Z d13-37 (Shadow Geysers)

Bya Freau SO-Z d13-5 (Seven Sages)

Truecha ZK-P e5-25 (Hypatia’s Lighthouse)

Greae Bluae YE-A g3 (Lights Of Alexandria)

Pyriveae FK-C d14-72 (The Nest)

Pyrivo HW-V e2-8 (Fly Trap Nebula)

Thuecheae MT-Q e5-8 (The Seldowitch Nebula)

Tyroerts AA-A g2 (Will-o'-Wisp)

Byeia Free WR-W b56-0 (Misty Mountains of Byeia Free)

Striechooe HO-D c14-2 (Hula Hop)

Smootoae VE-R d4-134 (Shadow Earth)

Drooteou PW-I a36-4 (Derthek's Folly (also known as 'Counter Point'))

Preae Chruia AA-A h0 (Titans of Preae Chruia)

Auphails AA-A h45

Qauthoea WM-W d1-40 (Vendetta's Gate)

Ooctarbs CP-E c25-1 (Frozen Arcadia)

Eictach ES-I d10-3 (Beauty and The Beast)

Cheia Eoq TJ-U b22-0 (Solitude-Silentium Canyons)

Qauthe ON-B d13-2 (Silent Raindrops)

Byoo Chraei AA-A f0 (Furthest Fireflies)

Hyiechou AI-J b36-0 (Sisyphos' Rock)

Grie Prao LH-E b59-1 (Sacrebleu)

Prai Pruae CL-Y g0 (Minerva's Crown)

Flyai Flyuae XJ-A c2 ('Flying Flea' Nebula)

Bleethuia FF-A e1 (Proximity Rock)

Flimbuae GY-P d6-7 (Roche Terminal)

Flimbuae CA-A e2 ('Eye of Horror')

Eock Bluae TW-V c2-0

Cloomaa YE-R e4-113 (Damselfly Nebula)

Pheia Auscs AL-T c5-155 (Heavenly Mists)

Eorm Phyloi OY-Z d37 (Aether Nebula)

Umbaists XJ-A e6237 (Allium Nebula)

Smasiae QT-Q d5-70 (The Smasiae Red Giant Binary Pair)

Dryio Blue LJ-X d2-629 ('Trinus' Blue)

Eord Bla HW-W f1-611

Sluenoe CL-Y g4 (Nadir)

Dryaa Prao PJ-G d11-89

I'm wanna add 40-50 more nebula (mostly the beautiful and obscure planetary ones in and around the core), but only If I can find 50 otherwise very interesting systems/stars/planets/moons.

• Missing interesting spots in the regions around the middle and ends of the Sag-Ca Arm and the Outer Arm.
• Haven't found a lot of unicorn orbits/rotationals except the dangerclose ones (planets in stars heat zone), fast orbiting moon Mitterand Hollow and a fast rotating star + ring yet unlisted on EDSM.
• I'm gonna have a look at the EGO records tomorrow.
• It is becoming quite clear that this route warrants an expedition!

 

[Orvidius]

The current route, in the current order on EDSM is now 563,365.71 ly long. Yikes! That's quite the expedition!

 

[Mengy]

What an awesome route for a trip.

 

[Jah'bastah II]

The current route, in the current order on EDSM is now 563,365.71 ly long. Yikes! That's quite the expedition!

Ok, I might just do the Travelling Spaceman Problem first then.

Edit: Found a decent library. I'm going to either remove the Y-axis from the coords anyway or see if I can easily add the Y-axis to the library code.

The ACO is working smoothly on the 2D version of my route (I'm gonna let it run for an hour or so). Currently improved the total distance from 563.365.71 (+ the additional waypoints I added later on) to (edit) 545,656.90 Ly. A WHOPPING 3.2%!! (couple thousand iterations, solution #6)

Code:

Spoiler

import pants
import math

nodes = []

waypoints = {"Egnaix XJ-Z e30": (6005.9375, 22287.1875),
"Mynoaw NY-K b37-55": (4690.6875, 18940.34375),
"Eeshorks SD-B d3065": (1562.34375, 16905.5),
"Greae Phio LS-L c23-797": (1354.03125, 16593.125),
"Boepp XA-D d13-1042": (-446.53125, 16697.59375),
"Boepp UE-Q e5-2104": (-550.03125, 16610.34375),
"Iowhail WY-S e3-8736": (-1649.5625, 16333.875),
"Froarks XJ-R e4-1363": (-481.8125, 15101.1875),
"Froarks JH-T d4-353": (-400.40625, 14710.9375),
"Blae Hypue NH-V e2-9": (1196.40625, 12301.65625),
"Clookuia AR-U c16-2": (2915.09375, 12491),
"Circinus Pulsar": (10852.09375, 13081),
"Phrooe Flyuae QE-Y d1-44": (17916.40625, 23444.875),
"Pueliae SH-P c20-0": (18017.8125, 13897.28125),
"Rhadia AA-A h59": (21392.21875, 12392.8125),
"Blie Aewsy IX-A d1-2": (19631.6875, 11883.34375),
"Thailau AA-A h49": (18597.28125, 4859.375),
"NGC 3199 Sector KX-T b3-0": (14574.15625, 3511.90625),
"Eta Carina Sector JM-W d1-1": (8561.71875, 2714.40625),
"CD-41 4893": (8157.03125, -599.03125),
"Skull and Crossbones Neb. Sector FG-Y e6": (13384.3125, -6763.71875),
"NGC 2244 CDZ 132": (2400.59375, -4834.71875),
"Rosette Sector GW-W d1-97": (2345.21875, -4741.25),
"GCRV 4925": (661.46875, -4084.0625),
"Monkey Head Sector QD-S b4-0": (1135.09375, -6296.5625),
"Crab Pulsar": (558.5, -6941.75),
"NGC 1931 Sector HW-W c1-13": (-742.8125, -6960.78125),
"BD+50 886": (-4907.96875, -8711.21875),
"Soul Sector LC-V c2-16": (-5099.3125, -5497.8125),
"Heart Sector NS-T b3-1": (-5319.25, -5287.15625),
"2MASS J02351897+6131236": (-4192.71875, -4190.625),
"BD+55 191": (-6660.25, -4345.59375),
"Bubble Sector PD-S b4-4": (-6570.5, -2680.28125),
"S171 29": (-2443.5625, -1333.5),
"Cave Sector FB-X c1-5": (-2244.84375, -825.78125),
"SHB2004 Trumpler 37 12-2113": (-2657.4375, -431.25),
"BD+66 1066": (-2842.375, -323.875),
"Cocoon Sector EL-Y d19": (-3175.21875, -244.96875),
"Crescent Sector GW-W c1-8": (-4842.1875, 1252.21875),
"V1357 Cygni": (-7095.375, 2396.8125),
"North America Sector GC-K a9-1": (-1891.03125, 149.65625),
"Veil East Sector DL-Y d54": (-1916.34375, 490.375),
"BD+22 3878": (-958.21875, 535.5),
"HIP 14769": (-330.96875, -481.28125),
"HIP 17403": (-93.6875, -367.625),
"Maia": (-81.78125, -343.375),
"Aries Dark Region GW-W d1-34": (-56.0625, -247.1875),
"Nervi": (-74.75, 35.84375),
"Epsilon Indi": (3.125, 7.125),
"Pomeche": (56.65625, 3.09375),
"HIP 31384": (513.09375, -439.8125),
"Witch Head Sector DL-Y d22": (378.21875, -722.90625),
"BD-12 1172": (577.875, -819.25),
"The Veil": (593.3125, -1071.125),
"Trapezium Sector CB-W c2-3": (538.53125, -1139.25),
"Trapezium Sector AF-Z c5": (625.75, -1198.53125),
"Trapezium Sector XO-Y b1-0": (619.75, -1224.3125),
"Trapezium Sector AF-Z c0": (617.03125, -1224.5625),
"Orion Dark Region KC-V c2-0": (603.3125, -1337.6875),
"HD 49368": (757.46875, -1424.375),
"Cone Sector GW-W c1-5": (854.71875, -2025.75),
"R Monocerotis": (1210.3125, -2744.1875),
"HIP 38064": (1152.9375, -478.25),
"Vela Dark Region LC-V c2-29": (991.0625, -48.96875),
"HIP 41908": (843.9375, -108.375),
"Chamaeleon Sector PD-S b4-2": (482.875, 307.90625),
"Musca Dark Region ZB-I a11-0": (425.90625, 267.5),
"Corona Austr. Dark Region PD-S b4-3": (-9.4375, 490.1875),
"Ophiuchus Dark Region B Sector PD-S b4-2": (-44.40625, 487.625),
"IC 4604 Sector FB-X c1-19": (64.03125, 565.65625),
"HD 148937": (548.6875, 1274.71875),
"NGC 6188 Sector HW-W c1-11": (1705.75, 4054),
"Cat's Paw Sector PD-S b4-7": (852, 5426.75),
"Thor's Eye": (-439.84375, 4205.15625),
"Herschel 36": (-468, 4474.625),
"Trifid Sector DH-K a9-6": (-637.65625, 5161.90625),
"PW2010 210": (-1337.9375, 5305.6875),
"Omega Sector PD-S b4-0": (-1432.0625, 5308.125),
"Gria Drye OC-B d1-211": (-1451.65625, 5435),
"Eagle Sector PD-S b4-5": (-2046.75, 6689.28125),
"Cl Pismis 16": (965.1875, 8094.40625),
"Prieluia GH-B c27-16": (899.59375, 9060.8125),
"Plaa Ain KS-A b2-5": (869.5625, 9219.5),
"Pru Aescs UO-V b30-7": (-3170.625, 8561.28125),
"Flyiedge RW-W d1-4": (-4102.125, 8064.6875),
"Flyiedgai MX-E c26-10": (-6369.15625, 9035.65625),
"Ellaisms QX-U e2-43": (-5469.9375, 9673.84375),
"Skaude AL-X e1-28": (-4708.625, 9571.75),
"Skaude AA-A h216": (-4804.59375, 10127.65625),
"Skaudai LC-V f2-10": (-5398.25, 10401.65625),
"Prua Phoe TS-B d126": (-5539.65625, 10481.15625),
"Xeehia GT-G d11-8": (-4793.84375, 11421.46875),
"Crookaae DL-Y g18": (-3935.5, 12387.46875),
"Clookia NK-M d8-431": (-3745.8125, 12472.125),
"Blaa Phoe NC-D d12-230": (-5377.90625, 15398),
"Blaa Phoe JX-T e3-26": (-5899.96875, 15074.65625),
"Blua Hypa HT-F d12-1226": (-7010.28125, 12817.625),
"Eor Aoscs AA-A h256": (-7296.34375, 17427.9375),
"Dryoea Flyuae AA-A g392": (-7698.09375, 18141.3125),
"Dryooe Flyou YT-A e1844": (-9191.59375, 18282.125),
"Spoihaae XE-X d2-9": (-9346.125, 19659.0625),
"Colonia": (-9530.5, 19808.125),    
"Rodentia": (-9530.53125, 19787.375),
"Spoihaae EW-V e2-670": (-9526.96875, 19910.96875),
"Dryooe Prou FF-Z d696": (-9378.28125, 20786.59375),
"Dryooe Prou HH-C d267": (-9875.8125, 20760.25),
"Screake SJ-Y d1-265": (-9955.75, 20872.71875),
"Oephaif GE-E b1-10": (-10807.4375, 16889.3125),
"Grea Hypooe ZZ-O d6-19": (-11952.75, 13590.53125),
"Ellaid AA-A h5": (-9506.8125, 9935.0625),
"Zejoo WM-Q b52-2": (-15778.1875, 11586.21875),
"Dehoae FL-W d2-0": (-15796.75, 9459.46875),
"Bloo Dryue ND-I d10-19": (-17091.5, 4942.25),
"Eullobs EL-Y e7": (-18821.375, 4326.96875),
"Fraufooe AA-A h8": (-25665.65625, 1732.34375),
"Byooe Thio AA-A g1": (-25253.0625, 3364.34375),
"Ovomly PD-R d5-3": (-19778.21875, 7113.1875),
"Thraikoo PS-U e2-4": (-18646, 7135.9375),
"Crooki PX-V c17-5": (-23057.3125, 12528.84375),
"Grea Hypae WU-O e6-4": (-19434.09375, 14144.78125),
"Floasly TE-X d2-25": (-17387.15625, 14558),
"Floagh FI-B d13-1": (-20463.84375, 15481.1875),
"Screakoi WO-G c11-1": (-22379.4375, 21178.1875),
"Hypoea Flyiae CW-V e2-0": (-26612, 22475.34375),
"Pha Flaae HT-H d10-56": (-22980.9375, 24145.34375),
"Dryu Chraea FH-D d12-49": (-23799.71875, 29480.125),
"Eol Groa UG-K d9-89": (-20477.21875, 30527.28125),
"Eolls Graae PG-E b15-4": (-18874.84375, 29977.375),
"Juemeou GN-S e4-18": (-19204.5, 26659.84375),
"Phooe Auf HV-I c24-0": (-15057.25, 26889.65625),
"Guenae SB-I b57-0": (-14382.6875, 27041),
"Pyroomeou GE-C c28-0": (-15793.3125, 25757.375),
"Phreia Flyou JT-P b22-2": (-15357.0625, 23746.90625),
"Phooe Aob OU-V b7-0": (-14739.96875, 23417.65625),
"Phreia Flyou FG-V d3-116": (-14327, 23596.875),
"Phreia Flyou UB-A b32-0": (-14503.84375, 23947.90625),
"Juenoe EG-Y g1913": (-8931.1875, 26846.46875),
"Eord Gree UU-X e1-1268": (-7631.8125, 30067.40625),
"Eimbaisys JC-V e2-352": (-4968, 30248.8125),
"Pha Scroi GS-I d10-64": (-9453.84375, 24186.96875),
"Dryee Free IM-W e1-14": (-7705.03125, 21086.6875),
"Screakou EW-N e6-5997": (-5743.78125, 21914.25),
"Scheau Flyi GH-U e3-3617": (-5783.40625, 22683.90625),
"Wepooe AA-A h509": (-4809.34375, 24133),
"Dumbaa XJ-R e4-5596": (-4252.625, 22780.84375),
"Theau Pri FB-W e2-25": (-3979.625, 20042.75),
"Dryaa Pruae GG-Y e5180": (-2197.53125, 20979.34375),
"Dryau Ausms KG-Y e3390": (-1523.75, 20976.59375),
"Leamuae SI-T e3-4236": (945.28125, 20129.25),
"Shrogea MH-V e2-1763": (971.03125, 21307.3125),
"Dumbae SY-I d9-2339": (-542.71875, 22837.96875),
"Hypuae Audst OF-E d12-978": (-26.125, 25627.53125),
"Croomaa RD-A d14-1524": (-79.6875, 25810.375),
"Juenae OX-U e2-8852": (652.46875, 26400.375),
"Eok Bluae MU-V c16-2452": (292.46875, 27839.71875),
"Eok Gree TO-Q e5-3167": (-1502.9375, 30671.1875),
"Iwhaind AA-A g1771": (-3602.40625, 32338.25),
"Scheau Byoe XJ-P d6-1080": (-5380.5, 35360.09375),
"Hypiae Briae KM-W d1-2603": (-6270.125, 34975.375),
"Hypiae Briae FR-N e6-3007": (-5975.3125, 36014.90625),
"Vegnue VK-E d12-1019": (-5684.34375, 37168.5),
"Gooreia WO-Z e131": (-5436.84375, 38817.3125),
"Plaa Free XE-R d4-382": (-2331.1875, 40333.71875),
"Dryiquae OI-B d13-0": (-4353.15625, 41088.4375),
"Bleethue KR-A b15-0": (-7171.15625, 37657.8125),
"Phroea Gree PU-D d13-3163": (-6833.40625, 37191.21875),
"Teqo EB-V c16-5": (-8294.625, 36797.53125),
"Vegnae YE-R e4-121": (-10916.96875, 36858.625),
"Vegneia BF-R e4-735": (-11623.40625, 36943.6875),
"Greethia SS-U e2-48": (-11818.75, 37864.3125),
"Myoangooe KD-S e4-2": (-11535.96875, 42045.90625),
"Myoangooe AA-A h1": (-11484.4375, 42231.96875),
"Trignai MT-Q e5-28": (-16355.875, 40895.34375),
"Eactaisky IR-N e6-2": (-19483.84375, 43610.375),
"Flyoo Groa SO-Z e0": (-26482.4375, 50335.125),
"Eufarb UT-Z d13-37": (-20650.3125, 53916.8125),
"Bya Freau SO-Z d13-5": (-9463.53125, 47512.46875),
"Pyriviae NY-Y d1-66": (-11166.9375, 54191.125),
"Truecha ZK-P e5-25": (-7584.78125, 53765.46875),
"Greae Bluae YE-A g3": (-5905.03125, 54076),
"Pyriveae FK-C d14-72": (-1235.5625, 55221.65625),
"Pyrivo HW-V e2-8": (-1498.25, 54503),
"Thuecheae MT-Q e5-8": (-2270.5, 53714.3125),
"Tyroerts AA-A g2": (-2085.75, 50391.0625),
"Byeia Free WR-W b56-0": (-1821.96875, 47520.34375),
"Striechooe HO-D c14-2": (-709.40625, 48207.5),
"Smootoae VE-R d4-134": (38.96875, 51819.53125),
"Drooteou PW-I a36-4": (51.5625, 51800.53125),
"Preae Chruia AA-A h0": (2647.5625, 49355),
"Auphails AA-A h45": (2605.21875, 50753.625),
"Qauthoea WM-W d1-40": (3668.21875, 55440.625),
"Cheia Eoq TJ-U b22-0": (11402.09375, 58302.875),
"Eictach ES-I d10-3": (8299.75, 60046.9375),
"Ooctarbs CP-E c25-1": (11459.53125, 60177.4375),
"Qauthe ON-B d13-2": (17571.5, 56444.375),
"Byoo Chraei AA-A f0": (16586.625, 54280.4375),
"Hyiechou AI-J b36-0": (20185.46875, 48362.71875),
"Grie Prao LH-E b59-1": (21885.3125, 47567.75),
"Prai Pruae CL-Y g0": (17879.09375, 42374.53125),
"Flyai Flyuae XJ-A c2": (17926.28125, 37360.59375),
"Bleethuia FF-A e1": (17817.40625, 37388.84375),
"Flimbuae GY-P d6-7": (18057.875, 27718.15625),
"Flimbuae CA-A e2": (18265.09375, 27124.125),
"Eock Bluae TW-V c2-0": (16058.75, 27219.8125),
"Cloomaa YE-R e4-113": (9578.8125, 25449.125),
"Pheia Auscs AL-T c5-155": (8340.25, 26071.59375),
"Eorm Phyloi OY-Z d37": (6548.3125, 27246.28125),
"Umbaists XJ-A e6237": (5231.59375, 29802.03125),
"Smasiae QT-Q d5-70": (4260.0625, 32717.5),
"Dryio Blue LJ-X d2-629": (3920.5625, 28683.6875),
"Eord Bla HW-W f1-611": (3621.59375, 27999.34375),
"Sluenoe CL-Y g4": (5168.4375, 26556.09375),
"Dryaa Prao PJ-G d11-89": (8361.90625, 21723.28125),
"Hyphokooe AA-A h62": (-10969.90625, 44395.5),
"Cyoidai GH-U e3-3": (663.1875, -6773.4375 ),
"2MASS J02351897+6131236" : (-4192.71875, -4190.625 ),
"Veil West Sector DL-Y d68": (-1398.25, 418.90625 ),
"Egnaix GW-V e2-0": (6124.28125, 22529.3125)}

for key, value in waypoints.items():
    nodes.append(value)

def euclidean(a, b):
    return math.sqrt(pow(a[1] - b[1], 2) + pow(a[0] - b[0], 2))

world = pants.World(nodes, euclidean)

solver = pants.Solver(alpha=1.61,beta=14,rho=0.9,limit=30000,ant_count=128,Q=4)

solutions = solver.solutions(world)

j = 0

best = float("inf")
for solution in solutions:
  j += 1

  assert solution.distance < best
  best = solution.distance
  pilgrimage = []
  for i in solution.tour:
      pilgrimage.append(list(waypoints.keys())
[list(waypoints.values()).index(i)])
  for i in pilgrimage:
      print(i)
  print("===========================================================")
  print(j,": ", best)
  print("===========================================================")

Edit: I really don't know what I was gonna write after this...

 

[Lance 'Spacecat' D.]

Hearing this talk of algorithms is taking me waaaaay back, 25 years ago I used to tinker with that kind of thing. I suspect science advanced a bit since the old 'A*' or Dijkstra's algorithm, I take it?

Or is it still 'an oldie but a goodie'?

(Since the galaxy's pretty flat, I bet a 2D algorithm would give 'good enough' results. And Dijkstra's works on distances between points anyway, I think?)