Monday, October 11, 2010

My Travelling Salesman Problem In Eve Online

The Travelling Salesman Problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.  In Eve Online, we call it picking up your datacores.

On Saturday I returned to New Eden needing to pick up datacores and facing the travelling salesman problem, with a twist.  All the very smart people who look into solving the problem never took into account the possibility that the salesman could get mugged and how to minimize that risk. What was the most efficient path to visit my research agents?  Thanks to the star map and the fact I only had to worry about visiting 4 stations, I was able to use a brute force approach.  With the parameters I set out, I came up with the optimum approach, but I will return to that subject later.

The first stretch of the trip took me 35 jumps.  Ouch!  But I needed the practice, since I was flying my Cheetah and between my trip to Bulgaria and playing Dragon Age, I was sadly out of practice flying stealthy.  After making my first pick-up (I thought), I felt ready to head into low-sec.

Now, one of the things I like about my research agent in low-sec is that the neighborhood is usually quiet.  Usually.  But when I jumped into the first system, I spotted a Unista.  So I said hi in local and he waved back, indicating that he probably wasn't hunting anyone.  But I did spot him on the outbound gate and he sure looked like a bait ship.  But since Eve University is a NRDS corporation, I decided to go ahead and make the jump, because there probably wasn't a pirate on the other side.

When I jumped through, I found out I was right.  No pirates but a 4-5 ship Unista gang that was jumping out of the system as I was jumping in.  Since this group looked like they meant business, I didn't wave and distract them and just proceeded to go to the station to make the next pick-up.  But it was only then that I realized I forgot to load the datacores I purchased at the first stop into my cargo hold.  D'oh!  Time to go back to the first station.

Remember I stated that the system was usually quiet?  When I jumped into the low-sec border region again, there were 2 Harbingers and a Hurricane at the gate with bad standings.  Since I wasn't scouting, I didn't look at them any closer and warped to a bookmark overlooking the outbound gate.  No one was at that gate so I quickly jumped through.

After picking up the datacores, I jumped back into low-sec to find, nothing.  The systems had returned to the level of activity I was used to and I zipped into the station, made the pick-up, and zipped out of low-sec. 

Having avoided getting mugged in low-sec, I ran into another problem.  After making the pickup at the third station I realized I was going to have more than 200 datacores.  A nice problem to have, except that my Cheetah's cargo hold only holds 200.  Solving the traveling salesman problem does no good if you input 4 stops but really need to make 5.  The fifth stop was to a station one system out of my path selling small secure containers, where I picked up two to increase my capacity to 240. 

I did discover one additional fact about my path.  The traveling salesman problem assumes only traveling to each city once.  But if I am willing to pass through the system where my low-sec agent resides twice, I can shave 14 jumps off my trip.  And that is a time saving this carebear may risk.

No comments:

Post a Comment