# Captain Dispatch Algorithm — Phase 0 Analysis - **Inputs read in full:** `Captain App.pdf` (Work Plan v2.0, June 2026, FR-01…FR-23), `captain_nearest_first_batch_algorithm_v2.1.md` (algorithm design, source of truth for logic), `google_maps_cost_report_captain_app_ar.md` (cost model, v1.0), and the implementation prompt. - **Precedence applied:** v2.1 doc wins on algorithm logic; the PDF wins on product scope. - **Codebase read:** the existing Laravel project (`Driver`, `Order`, `DriverLocation`, `DriverAvailability`, `OrderService::suggestCaptains()`, `DistanceService`, the Feature 04–07 order lifecycle). This document proves understanding only. **No feature code has been written.** --- ## 1. The ecosystem, in my own words Kapitano is a multi-vendor e-commerce platform. Three parties complete a sale: | Party | Role | Owner | |---|---|---| | **Customer App** | browse, order, pay (prepaid or COD), track the captain live, rate | Kapitano | | **Vendor App / Panel** | list goods, manage stock and prices, prepare orders | Kapitano | | **Captain App** | receive assigned orders, pick up at the store, deliver, collect COD | a **separate delivery company** (may serve other clients later) | | **Dispatcher Dashboard** | approve captains, create/see orders, get ranked suggestions, **manually assign**, monitor | operations team | Captains are Employees (fixed schedule, attendance) or Freelancers (on demand). Each drives a company or personal vehicle. Accounts are self-registered and approved manually (FR-01…05, already built as Features 02–05 in this repo). ### Where this algorithm sits in the order lifecycle ``` order created (dashboard / future vendor feed) │ ▼ [ SUGGESTION ] ← this project: eligibility → capacity → effective location → │ geo filter → Top N → route matrix → batch check → Adjusted ETA → rank ▼ dispatcher reviews the ranked list, picks one (FR-06, FR-07: manual, always) │ ▼ [ ASSIGNMENT ] ← this project: revalidate → atomic conditional update → 30 s lock → │ RoutePlan v1 → push to captain (FR-08) + ETAs to customer ▼ captain: picked up → on the way → delivered / delivery_failed (FR-10, Features 06–07) │ ← this project: every stop completion / new batch order / deviation │ triggers a RoutePlan recompute + repaint fan-out ▼ customer rates the captain (FR-21) ``` The algorithm **never assigns**. It ranks, explains, and suggests. Assignment is the dispatcher's click, then the system revalidates and writes atomically. --- ## 2. Entity model ### Captain (existing `drivers` table, called "Driver" in code) State machine per v2.1 §16, expressed over existing + new columns: ``` ┌──────────┐ not approved │ PENDING │ (drivers.status ≠ approved → never eligible) └──────────┘ ┌──────────┐ │ OFFLINE │ driver_availabilities.is_online = false └────┬─────┘ │ go online ▼ ┌──────────┐ on_break = true → ON_BREAK (eligible = false, still online) │ IDLE │ active_orders = 0 └────┬─────┘ │ assign ▼ ┌──────────┐ │ BUSY:1 │ active_orders = 1 → "Batchable" └────┬─────┘ complete │ batch-assign ┌───────┴────────┐ ▼ ▼ IDLE ┌──────────┐ │ FULL │ active_orders = 2 = MAX_ACTIVE_ORDERS └────┬─────┘ │ one stop completes ▼ BUSY:1 (Batchable again) ``` - `active_orders` is **derived today** (count of orders in `assigned / picked_up / on_the_way`). The atomic assignment in v2.1 §28 needs a **stored counter** column (`drivers.active_orders`) so the conditional `UPDATE … WHERE active_orders < :max` works in one statement. The counter is decremented on `delivered` / `delivery_failed`. - `on_break` does not exist yet → new boolean on `driver_availabilities`. - `idle_since` (for the fairness tie-break) does not exist yet → new timestamp, set when the captain's last active order completes (or when they go online with none). ### Order (existing `orders` table) Status flow (existing enum, already enforced by `OrderStateMachine`): ``` pending → assigned → picked_up → on_the_way → delivered └→ delivery_failed (reason required) ``` Fields the algorithm needs: `pickup_lat/lng` (the store), `dropoff_lat/lng`, `payment_method` (prepaid / cash_on_delivery → Handoff Buffer), and a **delivery promise** (`promised_at`, new) for batch-acceptance rule 2. ### Store There is **no store entity** today: an order carries the pickup coordinates inline. The algorithm only needs the pickup point, so the MVP can keep "store = the order's pickup coordinates" and key the suggestion cache on those coordinates (rounded / geohashed). A `stores` table is an open question (§5). ### Assignment The act of handing an order to a captain. Today it is `orders.driver_id` + a `order_status_history` row. Adds: a `suggestion_id` reference on the assignment (which list the dispatcher chose from, and which rank) → the Suggestion Log. ### Suggestion (new: `order_suggestions` + `order_suggestion_candidates`) One row per list shown to a dispatcher: order, generated_at, radius used, `ranking_degraded`, routing elements consumed, ms spent per phase. One child row per candidate: rank, captain, state (idle / batchable / at-store), straight-line km, road ETA, remaining delivery ETA, handoff buffer, Adjusted ETA, DetourDelta, batch accepted/rejected + reason, stale-GPS badge. `chosen_rank` is written on assignment. This is KPI fuel (v2.1 §37, §40). ### RoutePlan (new: `route_plans`, versioned) Per captain: `version`, ordered `stops` JSON (`[{type: pickup|dropoff, order_id, lat, lng, eta_at, leg_seconds}]`), `polyline`, `total_seconds`, `trigger` (assigned / stop_completed / deviation / manual_reorder), `degraded` flag, `computed_at`. History is kept (support/audit); `drivers.current_route_plan_id` points at the live one. Every push carries `version`. ### Location (existing `driver_locations`, extended by Redis GEO) Today: one SQL row per captain, replaced on each ping (`lat, lng, accuracy, captured_at`). v2.1 §26-ب: live pings go to Redis GEO (`captains_live`), a second set `captains_effective` holds Idle → GPS / Busy → current drop-off, and SQL keeps history via a periodic batch flush. Staleness is tagged from `captured_at`. --- ## 3. The complete pipeline, end to end ``` ① ELIGIBILITY approved AND online AND NOT on_break AND active_orders < MAX(2) ② CAPACITY 0 → Idle, 1 → Batchable, 2 → Full (rejected before any distance math) ③ EFFECTIVE LOCATION Idle → last GPS (must be Fresh/Aging; Stale > 3 min → excluded, listed separately). Busy → current order's drop-off point. ④ GEO FILTER GEOSEARCH captains_effective BYRADIUS 5 km; if < N candidates → 8 km → 12 km (max). Straight-line × DETOUR_INDEX(1.3). Take Top N = 7. ⛔ NEVER call a routing API here. ⑤ AT-STORE STACKING A captain assigned an order from the SAME store who has not left it (or order A still preparing) and whose drop-off is near the new one → ranked #1 with badge "at-store batch"; no effective-location math. ⑥ ROUTE MATRIX ONE computeRouteMatrix call: N origins × 1 destination (store), TRAFFIC_UNAWARE, field mask = duration, distanceMeters, status. Timeout 1000 ms → ⑨ fallback. ⑦ ADJUSTED ETA Idle: RoadETA(captain → store) Busy: RemainingDeliveryETA (READ from live tracking / active RoutePlan — never a routing call) + HandoffBuffer(prepaid 3 / COD 5 min) + RoadETA(current drop-off → store) ⑧ BATCH CHECK Busy candidates only. DetourDelta = ETA(best insertion) − ETA(current route). Accept iff DetourDelta ≤ MAX_BATCH_DETOUR AND new order's ETA ≤ its delivery promise. Rejected → ranked lower / excluded per config, reason visible. ⑨ FALLBACK routing timeout / error → return ④'s geographic ranking with ranking_degraded: true + reason. Endpoint never 500s because of Google. ⑩ RANK ascending Adjusted ETA; candidates within TIE_BREAK_BAND (2 min) are tied → longest idle_since first. ⑪ SUGGESTION LOG persist the list + per-candidate reasons; cache 60–90 s keyed on store (pickup point) + candidate geohash. ⑫ DISPATCHER CONFIRM → ⑬ REVALIDATE (fresh eligibility + capacity + online + approved) ⑭ ATOMIC ASSIGN Redis SET NX EX 30 lock on captain id, then UPDATE drivers SET active_orders = active_orders + 1 WHERE id = ? AND active_orders < ? AND online AND approved → 0 rows = failed → dispatcher list refreshes. Same transaction: order → assigned, history row, suggestion chosen_rank. ⑮ ROUTE PLAN v1 computeRoute (traffic-aware, intermediates) → polyline + legs → persist → fan-out: captain (FCM data + realtime), customer ETA, dashboard. ⑯ IN-FLIGHT REPAINT triggers: 2nd order assigned / stop completed / deviation > 250 m for 30 s / manual reorder → rebuild stops (pickup precedes its own drop-off; at-store = one combined pickup then cheaper of 2 drop-off orders) → computeRoute → version n+1 → fan-out with version; clients keep the highest version; overlapping recomputes resolve to exactly one plan; routing outage → keep last valid plan, degraded flag, retry with backoff. Assert customer A's added delay ≤ MAX_BATCH_DETOUR. ``` **Key insight the design rests on (v2.1 §22):** the closest captain is not the fastest — C3 at 0.5 km but mid-delivery costs 9 min; C1 at 1.5 km idle costs 8 min. Phase 1 only filters; Phase 2 decides. --- ## 4. Configurable business values (nothing hardcoded) All will live in `config/dispatch.php` (env-backed), and the ✱ ones additionally in a `dispatch_settings` table editable from the dashboard, overriding config at runtime. | Key | v2.1 default | Where it acts | |---|---|---| | `MAX_ACTIVE_ORDERS` | 2 | eligibility, capacity, atomic assign | | `RADIUS_STEPS_KM` | [5, 8, 12] | geo filter expansion | | `TOP_N` | 7 | candidates sent to routing | | `DETOUR_INDEX` | 1.3 | straight-line → road estimate in Phase 1 | | `HANDOFF_BUFFER_PREPAID_MIN` ✱ | 3 | busy Adjusted ETA | | `HANDOFF_BUFFER_COD_MIN` ✱ | 5 | busy Adjusted ETA | | `GPS_AGING_MIN` / `GPS_STALE_MIN` | 1.5 / 3 | location staleness badge / exclusion | | `ROUTING_TIMEOUT_MS` | 1000 | routing engine → fallback | | `SUGGESTION_CACHE_TTL_S` | 60–90 (I will default 75) | suggestion cache | | `MAX_BATCH_DETOUR_MIN` ✱ | 5–7 (I will default 6) | batch acceptance, repaint assertion | | `TIE_BREAK_BAND_MIN` | 2 | fairness tie-break | | `REROUTE_DEVIATION_M` / `REROUTE_DEVIATION_S` | 250 / 30 | deviation reroute trigger | | `ASSIGN_LOCK_TTL_S` | 30 | Redis assignment lock | | `ROUTING_ENGINE` | `fake` until keys exist, then `google` (or `osrm`) | engine switch | | `BATCH_REJECTED_POLICY` | `rank_lower` (alt: `exclude`) | what to do with a failed batch check | Where the prompt gives a range, the middle value is the default and the range is documented in the runbook. --- ## 5. Assumptions and open questions ### What I found in the codebase (facts, not assumptions) - **Framework:** Laravel 13 (PHP 8.4), repository/service architecture, PHPUnit, Sanctum. - **Database:** MySQL-compatible locally — the XAMPP server is **MariaDB 10.4.32** (found during T1.2), with `explicit_defaults_for_timestamp = 0`, so every non-null timestamp column needs an explicit default; tests run on in-memory SQLite. CI (T1.5) targets MySQL 8. - **Redis:** `predis/predis` is installed, but **no Redis server and no `phpredis` extension exist on this machine**; `.env` says `REDIS_CLIENT=phpredis`, `CACHE_STORE=file`. - **Existing suggestion:** `OrderService::suggestCaptains()` = approved + active + online + has a location + **no in-progress order**, Haversine only, sorted by km. Busy captains are excluded outright (effective MAX = 1). This project replaces it behind the same endpoint. - **Google keys:** none configured. Per your instruction, `FakeRoutingEngine` (deterministic, Haversine-based synthetic ETAs) will be the engine for dev, tests and the demo; `GoogleRoutesEngine` will be implemented against the Routes API contract and verified with recorded fixtures, then switched on by config when keys arrive. ### Assumptions I will make unless you say otherwise 1. `on_break` is a new flag on `driver_availabilities`, toggled by the captain app (a new endpoint) and visible to the dispatcher. 2. Remaining delivery ETA for a busy captain is read from the captain's **active RoutePlan** (leg ETAs minus elapsed progress along the polyline from the latest GPS). Until a plan exists (legacy in-flight orders), it falls back to a Haversine estimate and is flagged. 3. "Delivery promise" = a new `orders.promised_at` timestamp; if null, batch rule 2 passes (documented in the runbook). 4. Customer-app ETA push = a persisted `customer_eta` per order + an event; the customer app itself is out of scope (no customer API exists here), so tests assert the emitted event. 5. Deviation detection runs on the GPS-ingestion path (server side, distance from the polyline), not on-device. 6. The **FR-07 deviation** (final ranking by Adjusted ETA instead of actual distance) is flagged by v2.1 §2 as needing formal sign-off. The response will always carry both `distance_km` and `adjusted_eta_min` so either reading is visible. ### Decisions taken (2026-09-14, answered by the product owner) | # | Question | Decision | |---|---|---| | 1 | Backend framework | **Laravel 13**, inside this codebase | | 2 | Database | **MySQL** (SQLite in-memory for tests) | | 3 | Single store per order? | **No — multi-pickup exists.** Modelled as **one order with many pickup stops** (`order_pickups`, ≤ 3 per order, each with store name + coordinates). Counts as ONE active order. Ranking anchor = the pickup **nearest the candidate's effective location**; the route matrix is N captains × K pickups in one call. The RoutePlan visits every pickup before the drop-off; the pickup sequence is optimised by the system (K ≤ 3 → at most 6 permutations). | | 4 | Routing engine for MVP | **Google via simulation:** `FakeRoutingEngine` for dev/tests/demo; `GoogleRoutesEngine` coded against the Routes API contract, verified with recorded fixtures, switched on by config when keys arrive. `OsrmEngine` left as a stub. | | 5 | Real-time channel | **FCM data messages + WebSocket (Laravel Reverb)** — both carry the RoutePlan version. | | 6 | Redis | **Install Redis on this machine and use it directly** (Redis GEO + `SET NX EX` lock). Client: `predis` (pure PHP, already installed) since the `phpredis` extension is absent. | | 7 | Store entity | Folded into #3: pickups carry the store name and coordinates inline on `order_pickups`; no separate `stores` table in the MVP. | | 8 | FR-07 sign-off | **Approved:** final ranking by Adjusted ETA; `distance_km` shown alongside. | | 9 | Batch rejected policy | **`rank_lower`** (visible with reason); `exclude` available by config. | **Consequence of #3 for the formulas (v2.1 extension, not a silent change):** ``` Idle: AdjustedETA = RoadETA(captain → nearest pickup of the order) Busy: AdjustedETA = RemainingDeliveryETA + HandoffBuffer + RoadETA(drop-off → nearest pickup) ``` The legs between the order's own pickups and to its drop-off are the same for every candidate, so they do not change the ranking; they are added only when checking the delivery promise and when building the RoutePlan. ### Questions — answered above; kept for the record **Mandatory (from the prompt):** 1. **Backend framework:** the project is Laravel. Confirm we build inside this codebase (not a new Node.js service). 2. **Database:** MySQL in production (SQLite in tests). Confirm. 3. **Single store per order?** Every order is picked up from **one** pickup point (no multi-vendor pickup in one order). v2.1 §45 Q11 flags this as blocking. 4. **Routing engine for MVP ranking:** Google-only behind the abstraction (simulated by `FakeRoutingEngine` until keys), or hybrid with an `OsrmEngine` also implemented now? 5. **Real-time channel to apps:** FCM-only (data messages), or FCM + WebSocket (Laravel Reverb / Socket.io)? This decides how the repaint reaches the captain app and the dashboard. **Additional (from my analysis):** 6. **Redis:** no server is installed here. Options: (a) install Redis (Memurai / WSL) and use it for real; (b) build the GEO + lock layer behind a `GeoIndex` / `LockStore` interface with a Redis implementation **and** an in-memory/SQL implementation used when Redis is absent (tests + this machine). I recommend (b) with Redis as the production driver — it also lets the whole E2E suite run without Redis. Confirm. 7. **Store entity:** keep "store = order pickup coordinates" (MVP, no schema change) or add a `stores` table now? 8. **FR-07 sign-off:** do you formally approve ranking by Adjusted ETA (with distance shown alongside), as v2.1 recommends? 9. **`BATCH_REJECTED_POLICY` default:** rank the captain lower (still assignable, reason shown) or exclude them from the list? Prompt E2E-13 allows either "per config".