1
$\begingroup$

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

courier-problem-example

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:

  1. 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.
  2. How to describe a walk using variables?
  3. How to accumulate the time units took until some step in the walk?
  4. How to express and accumulate the wasted "stay" time?

Note:

  1. The solution is not restricted to Integer programming.

  2. This is a cross-post from math.se which does not receive answers in more than 20 days.

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

Improve this question
$\endgroup$
7
  • $\begingroup$ Are there any restrictions on the solution, or does a solution of the form "this problem is decidable because there's a (nonconstructive) $O(2^{2^{2^n}})$ algorithm" count? $\endgroup$
    – Tom van der Zanden
    Nov 17, 2015 at 13:21
  • $\begingroup$ @TomvanderZanden First, it should be an algorithm. Second, the algorithm should be practically efficient (for example, there are $\le$100 places.). However, it can be an approximation algorithm or a heuristic method. Thanks for pointing this out. $\endgroup$
    – hengxin
    Nov 17, 2015 at 13:32
  • 1
    $\begingroup$ Generally, this problem is NP-hard since if you let $r = 0$ and $d = \text{(something super large)}$ be constant functions, then you're looking for a solution to TSP, i.e. this reduces TSP to your problem. I thought I had a nice reduction the other way around as well, but I don't. $\endgroup$
    – G. Bach
    Nov 17, 2015 at 17:58
  • $\begingroup$ @G.Bach Yes, you are right. Actually, about two months ago, I had a similar (maybe simpler; with less constraints) problem and I guessed it is NP-hard, which was proved by @Dennis Kraft. That is why I am trying Integer programming, approximate algorithms, or heuristic methods. Sorry that I forgot to mention this and thanks for your efforts. $\endgroup$
    – hengxin
    Nov 18, 2015 at 1:39
  • $\begingroup$ You can try constraint propagation, you can get an approximate or exact solution, depending on how long you're willing to wait (of course you'll use exponentially large time and space in the worst case). $\endgroup$
    – randomsurfer_123
    Nov 18, 2015 at 21:08

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.