Design dasher-to-order assignment algorithm

You are building a real-time 'dasher picker' that assigns delivery drivers (Dashers) to incoming orders. Define objective(s) (e.g., minimize ETA and cancellations, maximize fairness/earnings), constraints (driver capacity, distance, pickup/delivery windows, batching), and signals (location, status, vehicle type, ratings, surge). Propose data structures and an algorithm (e.g., greedy with priority queues, bipartite matching/flow, or scoring + auction) that scales under high churn with partial information. Analyze time/space complexity and discuss handling delayed locations, reassignments, and adversarial cases.

Online Dasher Assignment with Time Windows

You are given drivers and orders in a real-time delivery system. For each order, assign at most one driver using an online greedy policy at the order's ready_at time. Each driver has an id, location (x,y), vehicle type, rating, and available_at time. Each order has an id, pickup (px,py), dropoff (dx,dy), ready_at time, and required vehicle type. A driver is eligible for an order if: (1) the driver's vehicle matches the order's vehicle, (2) the driver is available at or before the order's ready_at, and (3) the Manhattan distance from the driver's current location to the order's pickup is <= max_pickup_distance. Among eligible drivers, choose the driver minimizing (pickup distance, -rating, driver id). After assignment, update the driver's location to the dropoff and set available_at to ready_at + (distance driver->pickup + distance pickup->dropoff). Process orders in non-decreasing ready_at; break ties by smaller order id. Return a list of [order_id, driver_id] for each input order index; use -1 for unassigned orders.

Constraints

• 1 <= len(drivers), len(orders) <= 2000
• All ids are unique integers
• Coordinates x,y,px,py,dx,dy are integers in [-10^6, 10^6]
• ready_at, available_at are integers in [0, 10^9]
• rating is a float in [0.0, 5.0]
• vehicle is a lowercase string; exact match required between driver and order
• Use Manhattan distance: |x1-x2| + |y1-y2|
• Orders are assigned immediately at ready_at; they cannot wait for a later driver
• Return one pair [order_id, driver_id] per input order; driver_id is -1 if no eligible driver exists

Examples

Example 1

Input: drivers = [{"id":1,"x":0,"y":0,"vehicle":"car","rating":4.9,"available_at":0},{"id":2,"x":5,"y":5,"vehicle":"bike","rating":4.8,"available_at":0}]
orders = [{"id":100,"px":1,"py":1,"dx":3,"dy":3,"ready_at":0,"vehicle":"car"},{"id":101,"px":7,"py":7,"dx":8,"dy":8,"ready_at":0,"vehicle":"bike"}]
max_pickup_distance = 10
Output: [[100, 1], [101, 2]]

Explanation: Order 100 chooses driver 1 (only eligible car, distance 2). Driver 1 becomes available at 0 + (2 + 4) = 6 at (3,3). Order 101 chooses driver 2 (bike, distance 4).

Example 2

Input: drivers = [{"id":5,"x":0,"y":0,"vehicle":"car","rating":4.8,"available_at":0},{"id":3,"x":0,"y":0,"vehicle":"car","rating":4.8,"available_at":0}]
orders = [{"id":42,"px":1,"py":0,"dx":0,"dy":0,"ready_at":0,"vehicle":"car"}]
max_pickup_distance = 5
Output: [[42, 3]]

Explanation: Both drivers are eligible with equal distance (1) and rating (4.8); tie breaks by smaller id, so driver 3 is chosen.

Hints

1. Sort orders by (ready_at, id) and process sequentially.
2. For each order, scan drivers to filter eligibility, then choose by the tuple (pickup_distance, -rating, driver_id).
3. Use Manhattan distance to avoid floating-point error.
4. Update driver state after assignment: new location is dropoff; available_at increases by pickup+delivery travel.
5. If many drivers, consider spatial bucketing or a regional index to speed eligibility checks.

Approach

Sort orders by readiness time and process online. For each order, filter drivers by vehicle match, availability at ready_at, and pickup distance threshold. Among eligible drivers, choose the one minimizing (pickup distance, -rating, id). Update the chosen driver's location and availability based on Manhattan travel time for pickup and delivery, then continue. Results are returned in the original order list order, using -1 when no driver is eligible.

• Time complexity: O(D * O)
• Space complexity: O(D + O)