4 · Time & bookings
This is the step from "find a path" to "run many drones at once". It's the heart of Fly-in, and it's one idea: every zone has a calendar.
Why a shortest path is not enough
On the fork map, the shortest route is 3 moves: start → junction → path_a → goal. Give that same route to all 4 drones and send them at once:
| zone (capacity) | turn 1 | turn 2 | turn 3 |
|---|---|---|---|
| junction (2) | D1D2D3D4 4 > 2 ✗ | ||
| path_a (1) | D1D2D3D4 4 > 1 ✗ |
Every route is fine on its own, but together they break the capacity rules. A plain shortest path only answers where. With capacities, you also need when.
The booking calendar
Give every zone a row and every turn a column. A cell says who is in that zone at the end of that turn. A drone may only enter a cell that still has room. This is the actual optimal solution for the fork map, 4 turns:
| zone (capacity) | turn 0 | turn 1 | turn 2 | turn 3 | turn 4 |
|---|---|---|---|---|---|
| start (∞) | D1D2D3D4 | D3D4 | · | · | · |
| junction (2) | · | D1D2 | D3D4 | · | · |
| path_a (1) | · | · | D1 | D3 | · |
| path_b (1) | · | · | D2 | D4 | · |
| goal (∞) | · | · | · | D1D2 | D1D2D3D4 |
Orange cells are full. Read a column top to bottom and you get one output line:
turn 1: D1-junction D2-junction
turn 2: D1-path_a D2-path_b D3-junction D4-junction
turn 3: D1-goal D2-goal D3-path_a D4-path_b
turn 4: D3-goal D4-goalstart-junction has max_link_capacity=2: at most 2 drones may start crossing it per turn. Turn 1: D1, D2 (full). Turn 2: D3, D4 (full). That's a second, smaller calendar, keyed by the connection.
How the calendar gets filled: one drone at a time
Plan D1 first and write its bookings into the calendar. Then plan D2 around those bookings, and so on. Nobody ever collides, because each drone only uses cells that are still free.
| Drone | Tries | Result |
|---|---|---|
| D1 | Calendar empty. Fastest route: junction (t1), path_a (t2), goal (t3). | Books all three. Arrives turn 3. |
| D2 | junction t1 has 1 slot left ✓. path_a t2 is full ✗, but path_b t2 is free ✓. | Takes the other branch. Arrives turn 3. |
| D3 | junction t1 is full ✗ (and so is the link). Waiting at start is always allowed. junction t2 ✓, path_a t3 ✓. | Waits one turn. Arrives turn 4. |
| D4 | Same wait. junction t2 has 1 slot left ✓. path_a t3 full ✗, path_b t3 ✓. | Arrives turn 4. Done: 4 turns total. |
"Waiting" isn't a special case. It's just a move from a zone to the same zone, one turn later, and it needs a free slot like any other move.
The search space: (zone, turn) instead of zone
Here is the trick that makes it work. Copy the graph once per turn and stack the copies side by side. Each dot is a state "in zone Z at turn T". A move goes one column right and changes row. A wait goes one column right and stays in the row. Now a normal BFS/Dijkstra on this picture automatically respects time.
(zone, turn).2. From a state you can wait (same zone, turn+1) or move to a neighbour (turn+1, or turn+2 into a restricted zone), but only into slots that still have room.
3. Search for the earliest state whose zone is the goal.
4. Book every slot on that route, then plan the next drone.
Where does the calendar live in your code?
Not in the models (they're static, remember page 1). It belongs to the planner. In Python it can simply be a counter keyed by (zone_name, turn):
zone_use[("junction", 1)] = 2 # junction holds 2 drones at the end of turn 1
link_use[(frozenset({"start", "junction"}), 1)] = 2"Is there room?" becomes zone_use[(z, t)] < capacity(z), where capacity is the Network method from page 2 that returns "unlimited" for start and end.
Two valid ways to use it
Plan everything first
Plan all drones before turn 1, then just print the calendar column by column. Simple to debug: the plan is fixed.
Plan during the run
Each turn, give a route to every drone that doesn't have one yet (the "railway dispatcher" approach). More flexible, a bit more moving parts.
Both use the same calendar. Pick the one you can explain best.
Check yourself
- Why does D3 wait, and how does the search "know" to wait?
- What two things does a move need to be free: which calendars?
- Why do the start and goal rows never fill up?
- If junction had capacity 1, how many turns would the fork map take?