I've just finished the lecture "Introduction to Optimization", so I know something about linear programming, and came across the following game on lumosity.com:
The goal of the game is to pick up all the animals and return them to their houses, by driving the car. The distance, from object (= {Point, Animal, House}) to object is always 1. You can only drive on roads. You are allowed to pass an animal without picking it up. The car's capacity for animals is 4. Find a quickest route. (In the game your gas is limited (25 in the picture) which corresponds to the optimal distance.)
Can this problem be formulated as a linear program? And if so, how? Does this kind of problem have a name?
My fist idea was to do a network with edge cost. Then I thought about the traveling salesman problem, or a transportation problem, or a flow problem, but they don't quite fit.
My best ansatz so far is this:
An s-t-flow network for every animal, where there is an in and an out edge for every connection. A flow network for the car, where only the source is defined.
Let $x_{i,j,k}$ be the number of times animal $k\in\{1,...,n\}$ is transported from node i to node j. Let $x_{i,j,0}$ be the number of times the car drives from node i to node j. Let $s_k$ be animal k's node, and $t_k$ be animal k's home node. Let $s_0$ the car's node.
From the s-t-flow networks follows:
$\sum_i x_{l,i,k}-x_{i,l,k}=0,\forall l\notin\{s_k,t_k\},\forall k\in\{1,...,n\}$
$\sum_i x_{s_k,i,k}-x_{i,s_k,k}=1,\forall k\in\{1,...,n\}$
$\sum_i x_{t_k,i,k}-x_{i,t_k,k}=-1,\forall k\in\{1,...,n\}$
$x_{i,j,k} \in \mathbb{N}_0, \forall i,j,k$
Since an animal can't travel without the car: $x_{i,j,0} \geq x_{i,j,k}, \forall k\in\{1,...,n\}$
And thus the objective becomes: min $\sum_{i,j} x_{i,j,0}$
The restrictions for the car:
$\sum_i x_{l,i,0}-x_{i,l,0}\leq 0,\forall l\notin\{s_0\}$
$\sum_i x_{s_0,i,0}-x_{i,s_0,0}=-1$
Now all that is missing, is the restriction on the car's capacity. How would one do that?
