Optimizing Delivery Routes in a Graph-Based Network to Minimize Maximum Delivery Time

Question

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?

Answer 1

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.