# Algorithm for optimal trades along a fixed route

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:

• 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.

• The problem is not sufficiently constrained. As such the right answer is to buy low and sell high. Otherwise there must be more information, such as cost of transport, freshness of product, duration to destination, market variations, etc.. Dec 23, 2016 at 3:17
• The constraint is the available cargo space. You cannot just buy infinite amounts of a commodity at a low price because you will run out of space. When your cargo ship is full, you also cannot buy other commodities in the mean time, so there's an opportunity cost to holding cargo between stops. Dec 23, 2016 at 4:09

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.

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
``````
• I think the problem is fixed route Dec 24, 2016 at 14:34
• That was not the problem, it was the constraint Jan 3, 2017 at 15:03

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.

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
//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

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