EVE Online - MST not Traveling Salesman?

Whilst writing the introduction post, thinking about the various pieces I've worked on over the years, one problem came to mind. The problem feels initially like the traveling salesman problem and looks something like this:

I have a number of locations, each with goods at them. I want to find the best route to take to collection all my stuff.

Sound like traveling salesman right? Well, it did to me. As I thought about it tonight though, I wondered if there wasn't a better approach.

The way of traveling between systems in EVE is via Jump gates. This makes travel akin to traveling a directed graph. The second think I realized is that whilst there are cycles in the graph, the are secondary paths, and the majority of significant paths within a region are largely typified by a tree.

I'm thinking that it might be possible to approximate the problem from a gnarly traveling salesman situation into a minimum spanning tree problem with a few assumptions that are reasonable.

Of course at this point, my knowledge of minimum spanning tree is pretty limited, but I know enough to be dangerous! I've got a weighted graph and I'm not afraid to use it!!

Introduction

This is going to be my blog about the world of Mathematics I'm discovering anew as a 30-something programmer.

I did a fair bit of math in school then university. I went to university in the UK, and did some large amount toward A-Level math, though I ended up dropping it. I studied Music at university in my first year, then switched to Computer Science. I didn't complete the degree, moving to the USA instead to marry.

Over the last ten+ years as a computer programmer, I've brushed up against my love for math here and there. I did some work on music recognition a number of years ago that had me using Fourier Transforms, did some work on various 3D rendering pieces which had me doing Euclidean geometry. I started working on pieces for EVE Online, which had me delve into some graph theory, some more fun Euclidean geometry including convex hull determination, and a hybrid between graph theory and geometry that looked kind of like minimum spanning tree with some minimum distance tree thrown in.

I was getting kind of antsy at my current job at the time which had descended into IT and refactoring hell with no end in sight when an opportunity arose within the company to work on Data Science. I jumped at the chance, and have been delving in to the wonderful world of data science for the last few months and getting my Math groove back on.