Teleporting Traveler, Optimal Profit over time Problem

Question

I'm new to the whole traveling-salesman problem as well as stackoverflow so let me know if I say something that isn't quite right.

Intro:

I'm trying to code a profit/time-optimized multiple-trade algorithm for a game which involves multiple cities (nodes) within multiple countries (areas), where:

• The physical time it takes to travel between two connected cities is always the same ;
• Cities aren't linearly connected (you can teleport between some cities in the same time);
• Some countries (areas) have teleport routes which make the shortest path available through other countries.
• The traveler (or trader) has a limit on his coin-purse, the weight of his goods, and the quantity tradeable in a certain trade-route. The trade route can span multiple cities.

---

Question Parameters:

There already exists a database in memory (python:sqlite) which holds trades based on their source city and their destination city, the shortest-path cities inbetween as an array and amount, and the limiting factor with its % return on total capital (or in the case that none of the factors are limiting, then just the method that gives the highest return on total capital).

• I'm trying to find the optimal profit for a certain preset chunk of time (i.e. 30 minutes)
• The act of crossing into a new city is actually simultaneous
• It usually takes the same defined amount of time to travel across the city map (i.e. 2 minutes)
• The act of initiating the first or any new trade takes the same time as crossing one city map (i.e. 2 minutes)
• My starting point might not actually have a valid trade ( I would have to travel to the first/nearest/best one )

---

Pseudo-Solution So Far

Optimization

First, I realize that because I have a limit on the time it takes, and I know how long each hop takes (including -1 for intiating the trade), I can limit the graph to all trades whose hops are under or equal to max_hops=int(max_time/route_time) -1. I cut elements of the trade database that don't fall within this time limit, pruning cities that have shortest-path lengths greater than max_hops.

I make another entry into the trades database that includes the shortest-paths between my current city and the starting cities of all the existing trades that aren't my current city, and give them a return of 0%. I would limit these to where the number of city hops is less than max_hops, and I would also calculate whether the current city to the starting city plus that trades shortest-path-hops would excede max_hops and remove those that exceded this limit.

Then I take the remaining trades that aren't (current_city->starting_city) and add trade routes with return of 0% between all destination and starting cities wheres the hops doesn't excede max_hops

Then I make one last prune for all cities that aren't in the trades database as either a starting city, destination city, or part of the shortest path city arrays.

Graph Search I am left with a (much) smaller graph of trades feasible within the time limit (i.e. 30 mins).

Because all the nodes that are connected are adjacent, the connections are by default all weighted 1. I divide the %return over the number of hops in the trade then take the inverse and add + 1 (this would mean a weight of 1.01 for a 100% return route). In the case where the return is 0%, I add ... 2?

It should then return the most profitable route...

---

The Question:

Mostly,

1. How do I add the ability to take multiple routes when I have left over money or space and keep route finding through path discrete to single trade routes? Due to the nature of the goods being sold at multiple prices and quantities within the city, there would be a lot of overlapping routes.

2. How do I penalize initiating a new trade route?

3. Is graph search even useful in this situation?

On A Side Note,

1. What kinds of prunes/optimizations to the graph should I (or should I not) make?
2. Is my weighting method correct? I have a feeling it will give me disproportional weights. Should I use the actual return instead of percentage return?
3. If I am coding in python are libraries such as python-graph suitable for my needs? Or would it save me a lot of overhead (as I understand, graph search algorithms can be computationally intensive) to write a specialized function?
4. Am I best off using A* search ?
5. Should I be precalculating shortest-path points in the trade database and maxing optimizations or should I leave it all to the graph-search?
6. Can you notice anything that I could improve?

Answer 1

If this is a game where you are playing against humans I would assume the total size of the data space is actually quite limited. If so I would be inclined to throw out all the fancy pruning as I doubt it's worth it.

Instead, how about a simple breadth-first search?

Build a list of all cities, mark them unvisited

Take your starting city, mark the travel time as zero

for each city: 
  if not finished and travel time <> infinity then 
    attempt to visit all neighbors, only record the time if city is unvisited
  mark the city finished
repeat until all cities have been visited

O(): the outer loop executes cities * maximum hops times. The inner loop executes once per city. No memory allocations are needed.

Now, for each city look at what you can buy here and sell there. When figuring the rate of return on a trade remember that growth is exponential, not linear. Twice the profit for a trade that takes twice as long is NOT a good deal! Look up how to calculate the internal rate of return.

If the current city has no trade don't bother with the full analysis, simply look over the neighbors and run the analysis on them instead, adding one to the time for each move.

If you have CPU cycles to spare (and you very well might, anything meant for a human to play will have a pretty small data space) you can run the analysis on every city adding in the time it takes to get to the city.

Edit: Based on your comment you have tons of CPU power available as the game isn't running on your CPU. I stand by my solution: Check everything. I strongly suspect it will take longer to obtain the route and trade info than it will be to calculate the optimal solution.

Answer 2

I think you've defined something that fits into a class of problems called inventory - routing problems. I assume since you have both goods and coin, the traveller is both buying and selling along the chosen route. Let's first assume that EVERYTHING is deterministic - all quantities of goods in demand, supply available, buying and selling prices, etc are known in advance. The stochastic version gets more difficult (obviously).

One objective would be to maximize profits with a constraint on the purse and the goods. If the traveller has to return home its looks like a tour, if not, it looks like a path. Since you haven't required the traveller to visit EVERY node, it is NOT a TSP. That's good - shortest path problems are generally much easier than TSPs to solve.

Because of the side constraints and the limited choice of next steps at each node - I'd consider using dynamic programming first attempt at a solution technique. It will help you enumerate what you buy and sell at each stage and there's a limited number of stages. Also, because you put a time constraint on the decision, that limits the state space of choices.

To those who suggested Djikstra's algorithm - you may be right - the labelling conventions would need to include the time, coin, and goods and corresponding profits. It may be that the assumptions of Djikstra's may not work for this with the added complexity of profit. Haven't thought through that yet.

Here's a link to a similar problem in capital budgeting.

Good luck !