The Caravan Problem

Question

I want to make a simulation for fun about a caravan moving goods.

Let $G = (V, E)$ be a planar graph (towns and non-overlapping roads)

Let $N$ different tradeable goods exist (fish, iron, gold, $\ldots$)

Let each vertex (town) have a stockpile $\boldsymbol{S_i} \in \mathbb{Z}^N$ where $i$ is the index associated with the vertex ($i = 1, \ldots, |V|)$

The stockpile is the amount of goods stored at each vertex.

Let $\boldsymbol{D_i} \in \mathbb{Z}^N$ be a vector expressing how much a town "wants" a good. The value indicates a "target". If it's lower than the current stockpile then it should try to sell (get rid of good), if it's higher than it wants to buy (acquire this good).

Let the caravan be stationed at $v \in V$

The caravan starts with no goods and has infinite inventory space and has sufficient money to acquire any needed good. To move a good, the caravan first needs to purchase it at a town that has that good (ideally helping them reduce their target) and then moving on the graph and selling it to another town.

The caravan can see the entire graph, but can only move $M$ times.

1. How can the caravan move optimally to satisfy the demands of each town (minimize least squares of $S_i - D_i, \forall i \in 1, \ldots, N$? (I might want to change the exact details of the minimization function but assume OLS for now)) It is fine that caravan goes beyond a town's target to compensate for another town.

2. I'm assuming this algorithm would be slow, would it be possible to approximate it and make sure that the amount of tradeable goods doesn't change?

Answer 1

Its like a TSP with an order (caravan needs to buy before moving to sell)
assuming $ S_{i,n},D_{i,n}$ are known parameters then Define:
$ \tau_{i,n} = 1$ if town $i$ has $ S_i \gt D_i$(buy here) of good $n$,
$-1$ if $ S_i \lt D_i$(sell here), else 0
Let $ C_i$ be known cost of visiting a town $i$.
Variables
$ s_{i,n}=1$ if caravan sells good $n$ at town $i$
$ b_{i,n} = 1$ if good $n$ is purchased at town $i$
$ 0 \le V_{i} \le \vert V \vert $: is the order a town $i$ is visited. Can be 0 also if town is not visited at all.

Constraints you'd need
(1) $ \tau_{i,n} = b_{i,n}-s_{i,n}$
(2) $ s_{i,n}+b_{i,n} \le 1 \quad \forall i \ \ \forall n$

(3) $ \sum_{j: (i,j) \in E} b_{j,n} \le s_{i,n} \ \forall n$

(4) $ V_i \le \sum_n s_{i,n}+b_{i,n} \le MV_i$
(5) $ s_{i,n} + b_{j,n}-1 \le M(V_i - V_j) \quad \forall j \neq i \quad \forall i$
Or
(6) $ \sum_n\tau_{i,n}V_i \le \sum_n \tau_{j,n}\sum_j V_j \quad \forall j \neq i \quad \forall i$