0
$\begingroup$

I've come up with a problem which we'll call the Trader's Route Problem (If it's an already understood problem that would be great as well, let me know). Say there exist N cities, with some arbitrary distance d between each city (not all need be the same distance), and as a trader, you want to make the most money possible in one day. You've figured out you can travel at most D units before the day ends, so we have a total distance restriction. Each city has a merchant which is willing to buy and sell items to you, and you've already figured out in advance that for any city, you have a set priority list pertaining to each city of which items to buy, and in what order, with every item on every list decreasing in potential profit value (each merchant need not have the same number of items for sale).

Now, how the problem works is that you start at some city C1 and buy item #1 from your priority list pertaining to C1, which if you sell at another city will net you a relative profit of P1 , you then travel to another city (exhausting the distance d between them so now you can travel at most D - d), sell the item from C1 and purchase item #1 from C2 with its own profit of P2. You continue traveling city to city, exhausting items from each merchant until you're unable to reach another city before the day ends.

NOTES: Every merchant will buy every item you bring them. You can revisit cities. You can visit a city with no more items to sell and they still buy your items from you, but you leave that city empty handed. You cannot sell items to the merchant you bought them from. You can only take one item at a time. You are given all relevant information regarding the profits of items, which items you'll buy if you visit each city and in what order, etc.

Given all of D, N, the P's of each item, your starting city, the distances between each city, and your priority purchasing list for each city, the problem is now determining your route in advance as to maximize total profit (P1 + P2 + ...).

I am in fact looking for an algorithm to solve this in any way faster than brute-force. I've tried to think of a way using dynamic programming to no luck, so implementing this in a non-brute-force fashion has so far has resulted in failure, and am curious if anyone else has the skills and background to create an algorithm that isn't just running through every combination. I believe this problem to be NP complete, though I haven't attempted proving it. Many thanks to all who read, and doubly so to those who'll attempt a solution. Any help, ideas, or questions are appreciated.

$\endgroup$
  • $\begingroup$ If I understood correctly, Travelling salesman problem, which is NP-hard, is a special case of your problem: For each city, let its list consist of only one item. All items have the same profit. Therefore, you just want to visit the maximum number of cities. $\endgroup$ – Dmitry Aug 5 at 18:46
  • $\begingroup$ @Dmitry Yes you are mostly right, that is an observation I didn't notice. I don't think that's an exact instance of the traveling salesman problem, but its a good lead. This may lead a more generalized approach, I'll think about it. Thanks alot. $\endgroup$ – Bryce219 Aug 5 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.