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.

  • 1
    $\begingroup$ 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. $\endgroup$ – j_random_hacker Apr 15 '19 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.