Teleporting Traveler, Optimal Profit Over Time Problem

Question

I am new to the whole traveling salesman problem, as well as to stackoverflow, so let me know if I say something that is not entirely correct.

Introduction:

I am trying to code a multiple trading algorithm with profit / time optimization for a game that includes several cities (nodes) in several countries (regions), where:

• The physical time required to move between two connected cities is always the same:
• Cities are not linearly connected (you can teleport between some cities at the same time);
• Some countries (areas) have teleport routes that make the shortest route accessible through other countries.
• The traveler (or merchant) has a limit on his wallet, the weight of his goods and the amount sold on a particular route. A trade route can span several cities.

---

Question parameters:

There is already a memory database (python: sqlite) that holds transactions based on their source and destination cities, the shortest paths between them as an array and quantity, as well as the limiting factor with its% return on total capital (or in the case when none of the factors is limited, and then just a method that gives the maximum return on total capital).

• I am trying to find the optimal profit for a specific given piece of time (i.e. 30 minutes)
• The act of crossing into a new city is actually simultaneous
• Usually it takes a certain amount of time (i.e. 2 minutes) to go on a city map.
• The act of initiating the first or any new transaction occurs at the same time as the intersection of one city map (i.e. 2 minutes).
• My starting point may actually not have valid trading (I would have to go to first / nearest / best)

---

Pseudo-solution so far

Optimization

First of all, I understand that since I have a limit on the time it takes and I know how long it takes for each jump (including -1 to enter the trade), I can limit the schedule for all transactions whose transitions are under or equal to max_hops=int(max_time/route_time) -1 . I cut out the elements of the trading database that do not fall under this time limit, trimming the cities with the shortest path lengths longer than max_hops .

I make another entry in the trade database, which includes the shortest paths between my current city and the starting cities of all existing transactions that are not my current city, and give them a 0% refund. I would limit them to where the number of city flights is less than max_hops , and I would also calculate whether the current city in the start city plus which shortest-path-hops trades will exceed max_hops and remove those that exceed this limit.

Then I take the remaining trades that are not (current_city->starting_city) and add trade routes with a 0% return between the entire destination and the starting cities if hops fail max_hops

Then I make the last prune for all cities that are not in the auction database, either as the starting city, destination city, or part of the shortest urban massifs.

Scheduled Search I am left with a (much) lesser deal schedule valid for the duration (i.e. 30 minutes).

Since all nodes that are connected are contiguous, by default all connections are weighted 1. I divide the% return by the number of transitions in the trade, then take it back and add +1 (this will mean weight 1.01 for a 100% return route). In the case where the yield is 0%, I add ... 2?

Then he must return the most profitable route ...

---

Question:

Mostly,

• How to add the ability to accept multiple routes when I left money or space, and continue to search for a route along the path discretely to individual trade routes? Due to the nature of the goods sold at several prices and quantities within the city, there would be many overlapping routes.

• How do I penalize a new trade route?

• Is graph search really useful in this situation?

On the side

3. What types of drafts / optimizations for the diagram should I (or should not) do?
4. Is my weighing method correct? I have a feeling that this will give me disproportionate weights. Should I use actual income instead of interest return?
5. If I code in python, are there libraries like python-graph suitable for my needs? Or will it save me a lot of overhead (as I understand it, graph search algorithms can be computationally intensive) to write a specialized function?
6. Is it better to use A * search?
7. Should I predict the shortest waypoints in the trading database and maximize the optimization, or should I leave it all to search on the chart?
8. Can you spot anything that I could improve?

Answer 1

I think that you have defined something that fits into a class of problems called inventory problems - routing. I assume that since you have both a product and a coin, the traveler buys and sells on the chosen route. Suppose first that ALL is determinate - all quantities of goods in demand, available offers, purchase and sale prices, etc. Known in advance. The stochastic version is becoming more complex (obviously).

One goal would be to maximize profits with a limit on wallet and merchandise. If the traveler has to return home, he looks like a tour, and if not, it looks like a way. Since you did not require the traveler to visit EVERY node, it is NOT a TSP. These good problems with the shortest paths are usually much simpler than solving TSP.

Due to lateral restrictions and a limited selection of next steps on each node - I would think about using dynamic programming for the first attempt at a solution method. This will help you list what you buy and sell at each stage, and there is a limited number of stages. In addition, since you set a time limit on the solution, this limits the space of selection states.

For those who suggested the Jikstra algorithm — you may be right — labeling agreements should include time, coins, and goods and corresponding profits. Maybe Jykstra’s assumptions may not work for this with the added complexity of profit. Until I thought it over.

Here is a link with a similar problem in the budget.

Good luck

Answer 2

If this is a game in which you play against people, I would suggest that the total size of the data space is actually quite limited. If so, I would be inclined to throw away all the bizarre pruning, as I doubt it is worth it.

Instead, what about a simple breadth-first search?

Create a list of all cities, mark them invisible

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 performs cities * maximum flight times. The inner loop runs once for each city. No memory allocation needed.

Now, for each city, see what you can buy here and sell there. When calculating the rate of return on trading, remember that growth is exponential, not linear. Twice the profit for a deal that takes twice as much, NOT a good deal! See how to calculate the internal rate of return.

If the current city does not have trade, do not worry about a full analysis, just look at the neighbors and run an analysis on them, adding one for each step.

If you have the CPU cycles that you need (and you could very well, anything that meant for a person to play would be a rather small data space), you can run an analysis for each city, adding at that time when required to get to the city.

Change Based on your comment, you have tons of processor power since the game does not work on your processor. I support my decision: check everything. I strongly suspect that it will take more time to get information about the route and trade than the optimal solution will be calculated.