Algorithm for a min cost problem

Question

Given are $n$ people who arrive at point $p$. They all need transport by bus to point $q$. Every bus trip from $p$ to $q$ has a cost of $K$, no matter how many people are inside the bus. The arrival time of a person at point $p$ is equal to $t_i$. The total cost is equal to the number of buses times $K$ + the sum of the departure times at point $p$ of all $n$ people. I need to find a minimal cost algorithm for this problem. I need to find the initialization of the problem and a recurrence relation. Can someone help me with this? I am not sure where to start.

Answer 1

The departure time of any person is equal to his arrival time plus his waiting time. Since the arrival times are fixed, we need to minimize the cost of the buses plus the waiting times.

Now, when person $k$ gets on a bus, we have to decide whether to have the bus depart immediately, or to wait for person $k+1$.

Can you see how to proceed?

---

Let person $k$ arrive at time $t_k$ for $k=1,\dots,n$ where we may assume $t_1=0$. Let $$\Delta_k = t_k-t_{k+1},k=1,\dots,n-1.$$ Let $c_k$ be the minimum cost of transporting the first $k$ people, and let $b_k$ be the number of people waiting on the bus at time $t_k$. Then $c_1=K, b_1=1$ and $$ (c_{k+1},b_{k+1})=\cases{(K+c_k,1),&$b_k\Delta_k>K$\\(c_k+b_k\Delta_K, 1+b_k),&otherwise}$$

Here $b_k\Delta_k$ is the increase in waiting time until passenger $k+1$ arrives. We compare that to the cost of putting on another bus. If it is more, the current bus departs immediately, and there is one person waiting (passenger $k+1$ on the next bus.) If the cost is less, we increase the cost by the incremental waiting time, and increase the number of waiting passengers by $1$.

Answer 2

Take the arrival times of the $I$ passengers as $\{t_i\}_{i=1}^I$, $t_i < t_{i+1}$. Note that it never makes sense to dispatch a bus in between times, because that means some customer waited unnecessarily, and you could dispatch the bus earlier and reduce over all wait. There was no mention of random arrivals, but you could make this stochastic if you wanted; if arrivals were exponentially distributed, I am pretty sure the answer would be a very simple, "wait until $k^*$ people arrive, then dispatch a bus" where $k^*$ is just a function of the intensity of the Poisson process.

Let the state be $k_i$, the number of people who are waiting at time $t_i$ when the $i$-th person arrives. Let $J_i(k_i)$ be the value of having $k_i$ people waiting at the $i$-th arrival.

At time $T_I$, you should dispatch a bus regardless of $k_I$, since no one else is coming and you have at least one waiting customer. Having them wait forever would incur an infinite cost, so you should dispatch immediately.

So $J_I(k_I) = -K$, and at $I-1$, you have $k_{I-1}$ people already waiting as the $I-1$-st person arrives. If you wait until next period to dispatch, they all have to wait, and the value is $$ J_{I-1}(k_{I-1}) = -(k_{I-1}+1)(t_I-t_{I-1}) + J_I(k_{I-1}+1) = -(k_{I-1}+1)(t_I-t_{I-1}) -K $$ but if you dispatch now, the value is $$ J_{I-1}(k_{I-1}) = -K + J_I(0) = -2K $$ So you should dispatch only if $$ -2K > -(k_{I-1}+1)(t_I-t_{I-1}) - K $$ or $$ k_{I-1} > \dfrac{K}{t_I - t_{I-1}}-1. $$ So your value function is $$ J_I(k_{I-1}) = \min \left\lbrace -2K, -(k_{I-1}+1)(t_I-t_{I-1}) - K\right\rbrace. $$

Working backwards, at arrival $i$, by similar reasoning, we have $$ J_i(k_i) = \min \left\lbrace -K+J_{i+1}(0), -(k_i+1)(t_{i+1}-t_i) + J_{i+1}(k_{i}+1)\right\rbrace. $$ And you should dispatch if $$ -K+J_{i+1}(0) > -(k_i+1)(t_{i+1}-t_i) + J_{i+1}(k_{i}+1) $$ or $$ (k_i+1)(t_{i+1}-t_i) > J_{i+1}(k_{i}+1)-J_{i+1}(0)+K $$ or $$ k_i > \dfrac{J_{i+1}(k_{i}+1)-J_{i+1}(0)+K}{t_{i+1}-t_i}-1. $$

Are the Bellman equations and policy functions the recurrence relations you were referring to?

If you had an infinite planning horizon with discounting or stochastic arrivals (maybe time is discrete and with probability $\lambda$ a new passenger arrives each period or use continuous-time Markov chain methods and the Hamilton-Jacobi-Bellman equation) the reasoning is all pretty similar and the answers might even be simpler.