Model: Consider an undirected, weighted, complete graph $G = (V, E = V \times V, w: E \to \mathbb{N}^{+}, r: V \to \mathbb{N}^{+}, d: V \to \mathbb{N}^{+})$. $s \in V$ is a source vertex.
$G$ describes a transportation network, where $V$ represents places, $E$ represents roads connecting them, $w(e)$ represents the time it takes to travel along $e$.
Imagine that a courier, initially standing at $s$, needs to deliver goods to all the other places. The consignee at place $v \in V$ ($v \neq s$) has specified a release time $r(v)$ and a deadline $d(v)$; the good for this place can only be signed for during the period $[r(v), d(v)]$. Assume that the time for sign is negligible.
The courier is free to stay at any place for an arbitrarily long time. However, it costs $c$ dollars for each time unit wasted in this way. Notice that in some scenarios, the courier has to "waste" some time to finish its job. See the example below.
Problem: Suppose the time is initially $0$ and it starts ticking immediately when the courier leaves $s$. The last good is delivered at time $T$. The goal of the task is to deliver goods to all the places (other than $s$) while minimizing $T + c \cdot (\text{units of all the wasted time})$.
An example: Consider the graph shown in the figure below.
The solution $s \to^{4} a \to^{1} a \text{ (delivering)} \to^{1} b \text{ (delivering)}$ takes $6$ time units, of which $1$ time unit is wasted, so the value of the objective function is $6 + c$.
Another solution $s \to^{2} b \to^{1} b \text{ (delivering)} \to^{1} a \to^{1} a \text{ (delivering)}$ takes $5$ time units, of which $2$ time units are wasted, so the value of the objective function is $5 + 2c$.
Want Help: I am trying to solve this problem by using Integer Programming. But I don't know how to start and I have identified some challenges to me:
- Each edge can be travelled along more than once. Thus, the binary decision variables $x_{ij}$, denoting for each edge $e_{ij}$ that whether it is travelled or not, are not sufficient.
- How to describe a walk using variables?
- How to accumulate the time units took until some step in the walk?
- How to express and accumulate the wasted "stay" time?
Note:
The solution is not restricted to Integer programming.
This is a cross-post from math.se which does not receive answers in more than 20 days.
About two months ago, I had a similar (maybe simpler; with less constraints) problem which was proved NP-hard by @Dennis Kraft (see also the comment from @G. Bach). That is why I am trying Integer programming, approximate algorithms, or heuristic methods.