Drone Dispatch at Northfield University
Northfield University runs a parcel-drone service between a central hub and 40 locker stations. Three drones operate; each has a 2.4 kg payload limit and a 22-minute flight budget on a full charge, and charging takes 35 minutes. Requests arrive online with a pickup time window, a destination locker and a mass. The current dispatcher uses a greedy rule - assign the earliest-deadline request to the nearest idle drone - and it worked in trials with 8 lockers. With 40 lockers, late deliveries rose to 19% and two drones repeatedly queued for the same charging pad. The operations manager wants a simulation before changing the live system. A developer proposes modelling every locker, drone and request in detail, including locker door colour and parcel packaging. The budget allows one week of development and a 2 GB memory footprint for the simulator. The manager also wants to know whether the greedy rule itself is the problem.
1. Define an abstraction for the simulator. State two details you would omit and justify each omission in terms of the decisions the simulation must support.
Read the worked answer
The abstraction should contain only entities whose state can change a decision the simulator must evaluate: drone (position, battery minutes remaining, payload, busy/idle/charging), request (pickup window, deadline, mass, origin, destination), locker station (location, whether it is a charging pad), and travel time between locations. The simulator must compare dispatch policies on lateness, drone utilisation and charging-queue length.
Two justified omissions:
- Locker door colour and parcel packaging: neither changes flight time, payload, battery use or charging. Including them adds state and development time without changing any measured output. With one week of development, this matters.
- Individual customer names and parcel contents: the scheduler only needs mass and time constraints. Names create no decision-relevant difference and raise data-protection issues.
Do not omit battery consumption, charging duration or travel time: those are exactly the constraints that produce the 19% lateness. A good abstraction is not “less detail”; it is detail selected by the questions the model must answer.
2. Decompose the simulator into three modules and give one interface between two of them. Explain why that boundary reduces coupling.
Read the worked answer
A sensible decomposition is:
- Request generator - produces requests with arrival times, deadlines, masses and locations.
- Dispatcher/scheduler - chooses which idle drone serves which pending request, and when a drone should charge.
- Simulation engine and metrics - advances time, applies travel and charging durations, detects missed deadlines, and records lateness, utilisation and queue length.
One interface: the engine exposes travel_time(drone_id, from_location, to_location, payload_kg) and charge_time(drone_id, current_battery). The dispatcher calls these functions but does not know how travel is calculated. This boundary reduces coupling because the dispatcher only sees feasibility and cost, not map geometry or battery chemistry. The engine can later use straight-line distance, a road graph or measured flight logs without changing scheduler code.
A second useful interface is assignments = scheduler.decide(pending_requests, drone_states, now). The engine supplies state and receives assignments; the scheduler does not mutate drone objects directly. This makes it possible to swap greedy, look-ahead and optimal schedulers for comparison, which is the point of the simulation.
3. Explain why the greedy rule can produce the observed 19% lateness at 40 lockers. Describe a better algorithm and evaluate whether it is practical within the development budget.
Read the worked answer
The greedy rule is myopic. It considers the earliest deadline and the nearest idle drone, but not the effect on later requests or on charging. At 8 lockers, travel times were short and a wrong assignment cost little. At 40 lockers, a wrong assignment can consume most of a drone’s 22-minute budget.
Example conflict: at 10:00, request A is due at 10:18 at a locker 12 minutes away with a 0.5 kg parcel; request B is due at 10:25 at a locker 4 minutes away. A drone has 20 minutes of battery left. Greedy sends the nearest idle drone to A, which takes 12 minutes out and leaves the drone unable to reach B without charging. B misses its deadline even though a different assignment could have served both. The 35-minute charge also creates a queue that greedy does not model.
A better approach is rolling-horizon look-ahead: every 2 minutes, solve a small assignment problem over pending requests and the next, say, 20 minutes, minimising weighted lateness plus charging-queue delay. With 3 drones and 40 lockers, a branch-and-bound or integer-programming search is small. It is practical if the team reuses a solver library rather than writing one; otherwise use a slack-based heuristic: priority = deadline − travel time − estimated charge wait. Test both in the simulator against the 19% baseline.