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

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?

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

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.