Algorithm for optimal trades along a fixed route

Question

Imagine you are in charge of a cargo ship:

• travelling along a fixed route or loop (A, B, C, D, A...)
• has a maximum cargo capacity

At each stop you can:

• buy commodities, up to your cargo capacity, or sell cargo that you have already bought
• each stop has different prices for each commodity
• for simplicity, you can't run out of money for buying
• also for simplicity, cargo amounts are infinitely divisible, so there's no knapsack-problem-like issues

What algorithm can I use to determine the best commodities and amount to buy/sell at each stop, to make the most profit?

The solution is not just to buy low and sell high because you have limited cargo space, and there's a tradeoff between carrying profitable cargo between many stops and doing more trades at each stop. For example: given a route A -> B -> C, two commodities (apples, oranges) and the following prices:

Stop | Apples | Oranges
-----+--------+--------
   A |     $1 |     $1
   B |     $2 |     $1
   C |     $4 |     $3

The best action would be to buy apples at A and sell them at C, for a profit of $3 * capacity. But if oranges were to appreciate to $3 at B, then it would be better to buy oranges at A, sell them at B and buy apples, and sell the apples at C, for a total profit of ($2 + $2) * capacity.

Answer 1

Draw a graph with nodes for each port. From each port to every other port draw an edge for each commodity, weight the edge with the profit earned from hauling the commodity along that port-port hop. So now you have a weighted multigraph. For completeness you'll want to add edges from C back to A with 0 weight -- there's no profit hauling apples or oranges from C to A.

This is a flow network, there are lots of algorithms. A simple instance such as this might yield nicely to linear programming.

Unless there are limits on the supply and demand for apples and oranges at any or each of the ports there's nothing to be gained by hauling part cargoes, nor hauling mixed cargoes.

My quick sketch suggests that you make as much money taking a shipload of apples from A to B and then another shipload of apples from B to C as you do by hauling a shipload of apples direct from A to C. So that's another odd result of the simplicity of the problem as posed.

OP writes there's a tradeoff between carrying profitable cargo between many stops and doing more trades at each stop but there is no expression of such a tradeoff in the question; if there is a tradeoff it doesn't emerge from the numbers.

I expect that, as OP adds complexity to the model, it remains a flow network problem but the choice of algorithm becomes more interesting.

Answer 2

I would probably program it like this:

First determine all possible trade routes

A-B
B-C
C-A

A-C
B-A
C-B

Then calculate most profitable trade between each route

foreach (item in items)
  profit = (item.a.ask - item.b.bid) * (cargosize/item.size)
  if (profit> highestprofit)
    selecteditem = item
    highestprofit = profit

=> zero out negative profits and unset item (empty cargohold)

Determine possible combinations and total profit:

A-B,B-C,C-A
A-C, C-A
A-B, B-A
B-C, C-B

Answer 3

You could also just brute force it
For every port and every product enter -1 0 1 for sell, hold, buy
You will end up with (port * product) ^ 3 options to evaluate
Run through them all and see which is the maximum profit
You could eliminate sell if the port is the low price of the product
And you can eliminate buy if the port is the high price of the product

I got it working

For and infinite loop I just run it like 3 times
I test several inputs and it always settled on by the 2nd pass

On the first pass you cannot sell something you don't yet have

On the last pass don't buy anything you are not going to sell

I made capacity 2*3*5*7*11 for even divisibility
If you want more than 11 products then add more primes

Also you never need to buy more than 1 product per port. If there is tie then splitting changes nothing. You can get into uneven devision problem with splits.

This is an answer for one pass.

Answer 4

Capacity constraints are a headache to model, but it can be solved with linear programming.

Max Z = Sum_i,j (P_i,j * X_i,j)
subject to:
    Carried_at_i = Sum_j (X_j<=i,j>i)            for all i
        //Kind of a rough sketch, not sure about this one.
        //e.g. Since it's a round trip, j<i could mean something different, etc.
    Carried_at_i <= Capacity                     for all i
    X_ij >= 0                                    for all i, j

where

• i, j are locations
• P is the profit of buying at i and selling at j
• X is the quantity bought at i and sold at j

Answer 5

Either I'm missing something or the answer is really simple:

• Assume that buying prices and selling prices are the same at each port and that there is no charge for loading/unloading.
• At each stop, you can unload/sell everything and buy/load new cargo. This has the same effect as selling/unloading only part of the cargo, because you can always buy the same type again.

With this reasoning, the cargo mix in each leg can be calculated independently from the cargo mix in any other leg. Since the sequence of ports is given, you load the cargo with the highest price difference to the next port at each leg.