# Delivering to two or more locations in one go while respecting deadlines?

Assume that I have a business where people can place product orders. Each order must be delivered within a time limit, say $$x$$ minutes.
I need 15 minutes to make each product. However, multiple products can be made in parallel.

Assume that I know my storage (i.e., the products that were previously made and are stored), the products that are being made by the present time, and the product orders. I also have a complete weighted graph $$G = (V, E)$$ where the nodes are the delivery destinations and the edges are the time needed to travel between two nodes.

The problem is: How can I compute the maximum amount of products that I can deliver at multiple locations while respecting the deadline of $$x$$ minutes for all products?

Let's give an example. Assume that $$O = \{o_1, \cdots, o_m\}$$ are the product orders and $$V = \{v_1, \ldots, v_n\}$$ represents their delivery points. An order $$o_1$$ is finished and I only have to wait one minute for order $$o_2$$ to finish. Furthermore, I can go from my business/deposit to both places in less than $$x-1$$ minutes, I will surely wait for $$o_2$$ to finish. However, if I can't pass through both $$v_1$$ and $$v_2$$ within 15 minutes, thus I won't wait for order $$o_2$$ to finish.

My question is: How can I do this with multiple delivery orders coming all the time? What if I have more than one deliveryman? I don't need an optimal solution, just a good approximation is fine.

• IIUC, I think you could repeatedly solve TSP on the most urgent $k$ orders, increasing $k$ until the trip takes $x$ minutes, and then execute that plan. – j_random_hacker Apr 15 '19 at 10:04