Algorithm to find the optimal trade route (negative cycle with lowest cost per edge in a digraph)

Question

Given the following problem (a slightly simplified description of trading in the computer game Escape Velocity: Nova (system map)):

• Given a set of (solar) systems.
• Each system is connected by hyperspace travel route to one or more other systems; each route connects two systems.
• Making a hyperspace jump has a cost in dollars (covering fuel costs). The cost is the same no matter which jump you're making.
• Each system has a trading center with various commodities (food, metal, equipment, etc.) available for trade at a given price. The price varies between systems.
• To keep it simple we'll say you can only hold a single unit of a single commodity at any given time.
• A trade route is a series of hyperspace jumps that start and end in the same system (a loop), buying and selling commodities along the way.
• The profit of a trade route is defined as profit made by buying and selling commodities along the way minus the total cost of the hyperspace jumps made.

I want to be able to answer questions like the following:

1. What's the most profitable trade route?
2. What's the most profitable trade route starting and ending in a specific system?
3. What's the most profitable trade route involving fewer than X jumps?
4. What's the most profitable trade route involving fewer than X jumps starting and ending in a specific system?

---

I plan to model this as a digraph:

1. Each system is a vertex.
2. For each hyperspace travel route add two edges (one in each direction) connecting the two vertexes with a weight equal to the cost of making a hyperspace jump.
3. For each system
   • for each commodity available in that system
     • for each system where the price of the commodity is lower than in the current system (we'll never make a profit if the cost at the destination is higher so we omit those edges)
       • add an edge from the current system to that system with weight of (number of jumps to reach that system) * (cost per jump) - (difference in price of the commodity) (i.e. profit to be made by buying in the current system and selling in the destination system)

---

I believe the technical description of what I'm after is (for question 1): given the above digraph what's the negative cycle with the lowest average cost per edge.

I realize I can use a breadth-first search to answer questions 3 and 4 as long as the maximum number of jumps is small enough that I don't run out of memory, but I suspect it won't be practical to answer 1 or 2 this way.

I've read though the Solving Problems by Searching chapter in AI: A Modern Approach but as far as I can tell the algorithms there require positive edge weights.

A bit of Googling found me the Bellman–Ford algorithm and while that supports negative edge weights my understanding is that it doesn't give accurate costs when negative cycles are involved.

Are there any algorithms I can use to solve this problem more efficiently?

Answer 1

This is not a traveling salesman problem if there is no prohibition on revisiting a system.

The problem for Question 1 is canonically referred to as the minimum mean cycle problem, which has polynomial-time algorithms. This is a subroutine in some min-cost flow algorithms.

Question 2 is sort of ill-defined because there won't be a best route in general; you'll want to fly to the best loop, do it a bunch of times (the more the better), and fly back.

Questions 3 and 4 can be addressed by expanding the digraph with a time dimension (where one unit of "time" is one jump) and then computing shortest paths on the resulting acyclic digraph.

Answer 2

Look into Traveling Salesperson Problems and optimization.

You are basically optimizing a TSP for all your four questions.

The specific details will vary based on your problem size (if you have 10 nodes you can just brute force it, if you have 1000 you will have to be more efficient).

The wikipedia site on TSPs suggests a large number of algorithms to use. It looks like you could use a modified Ant Colony Optimization method based on the total value of the entire trip (ie your first and second questions).