0
$\begingroup$

In a graph with N nodes, where each node represents a house and is labeled from 0 to N-1, an adjacency matrix graph[i][j] indicates the distance from node i to node j.

Consider a list of tuples [[init_1, target_1], ..., [init_k, target_k]], representing delivery requests. Each tuple, like [[1, 2], [2, 3], [5, 3]], requires a delivery person to transport food from init_i to target_i (e.g., from houses 1, 2, 5 to houses 2, 3). Each delivery person can carry an unlimited amount of items/orders at same time.

There is also a list of delivery personnel [v1, v2, ..., vn], where each vi indicates the current location (node) of the i-th delivery person. Assuming all personnel move at the same speed and ignore the stopping time at each node, how can one assign a route to each (a list of houses for pickup and delivery) to minimize the maximum time taken by any delivery person?

$\endgroup$
2
  • $\begingroup$ Can the delivery persons carry more than one order at a time? $\endgroup$
    – Steven
    Nov 11, 2023 at 20:28
  • $\begingroup$ @Steven Yes. Each delivery person can carry an unlimited amount of items. $\endgroup$
    – maplemaple
    Nov 11, 2023 at 21:47

1 Answer 1

1
$\begingroup$

The problem is unlikely to admit any efficient solution since it is NP-Hard even when there is only one delivery person and, for all edges $(u,v)$ in the graph, the distance between $u$ and $v$ is $1$.

To see this let $G=(V, E)$ be the graph and let $V = \{v_1, \dots, v_n\}$. Construct a new graph $H = (V', E')$ where $V' = V \cup \{ s, u_1, \dots, u_n\}$ (where $s$ and $u_1, \dots, u_n$ are new nodes) and $E' = E \cup \{ (s,v_i) \mid i =1,\dots, n\} \cup \{ (u_i, v_i) \mid i= 1,\dots, n \}$ (if you are interested in directed graphs then add also the revers edges $(v_i, u_i)$).

Let $s$ be the starting location of the only delivery person. There are $n$ deliveries, the $i$-th delivery requires food to be transported food $u_i$ to $v_i$.

There is a route on $H$ that delivers all the food and has length at most $3n$ if and only if $G$ is hamiltonian.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.