Modeling quarantine during epidemics by mass-testing with drones

Leonid Sedov; Alexander Krasnochub; valentin polishchuk

Finally, to minimize the length L of the longest drone route (which directly impacts the makespan, i.e., the time to fly all routes and thus serve the entire population), we split the tours into N sets (we did this for every value of N in a range), so that every set becomes a route for a drone (the tours in the drone's set are executed one-by-one in an arbitrary order). When splitting the tours, the objective is to minimize the length of the longest route (i.e., to minimize the maximum total length of the tours in a route) --it is the longest route that is the "bottleneck" of our solution, defining the longest time that a person has to wait for the drone. This is exactly the Minimum Makespan Scheduling problem aka Load Balancing (because it balances the "load" of every drone) aka Multiprocessor Scheduling (the drones can be viewed as processors which have to collectively process the set of tasks --fly all given tours). We formulated the problem as an Integer Program (IP) and solved it using Gurobi solver [G20] (separately for each value of N). Specifically, in the IP the binary decision variable x dt was equal to 1 if the route for drone d included the tour t. The IP minimized the length L of the longest route (i.e., the objective function was L) subject to the constraints Σ d x dt = 1 for every tour t (meaning that every tour must be included in exactly one route) and the constraints To convert the longest route length L into the time needed to fly all the routes (the makespan), we assumed that the drones operate 12 hours per day and fly with the speed of 60km/h. We do not investigate other values of these two parameters because the time of serving the routes scales linearly with them: e.g., if the drones fly 24/7 (the authority shall decide whether it is wise to disturb people's sleep and distribute the tests also overnight in order to increase the testing intensity) or with twice the speed, the service time simply doubles, etc. We remark that, on the contrary, the dependence on the drone capacity C is not straightforward at all: changing C changes already the tours (in a way which is hard to predict a priori --the tours are output by the advanced Google OR-Tools optimization software), which of course influences the routes and their lengths. We therefore run our experiments separately for several values of C (for each C, we solve the Minimum Makespan Scheduling problem for each value of N). Refer to Figure 1 for the results showing the relation between N and the service time D.