# Problem Formulation

## Spatial-Temporal Taxi Zone Recommendation

### Definition

Given a taxi driver's current state $(z_t, t)$ where $z_t \in \{1, 2, \ldots, 263\}$ is the current zone and $t$ is the current timestamp, the goal is to recommend a set of **top-3 zones** $R = \{z_1^{\star}, z_2^{\star}, z_3^{\star}\}$ that maximizes the driver's expected cumulative revenue over a planning horizon.

### State Space

The state space is defined as:

$$\mathcal{S} = \mathcal{Z} \times \mathcal{T}$$

where:
- $\mathcal{Z} = \{1, 2, \ldots, 263\}$: NYC taxi zones (TLC definition)
- $\mathcal{T} = \{(d, s) : d \in \{0,\ldots,6\}, s \in \{0,\ldots,47\}\}$: discretized time with weekday $d$ and half-hour slot $s$

This yields $|\mathcal{S}| = 263 \times 336 = 88{,}368$ distinct states.

### Action Space

At each state, the driver chooses a destination zone $a \in \mathcal{Z}$ to relocate to. The action space is the full set of 263 zones.

### Objective

Find a policy $\pi: \mathcal{S} \rightarrow \mathcal{Z}^3$ that maximizes:

$$\mathbb{E}\left[\sum_{k=0}^{K} \gamma^k \cdot R(s_k, a_k)\right]$$

where:
- $R(s_k, a_k)$ is the immediate reward (expected fare) at step $k$
- $\gamma \in [0, 1]$ is the discount factor
- $K$ is the planning horizon

### Reward Model

The reward for relocating to zone $z$ from state $s = (d, \text{slot})$ is:

$$R(s, z) = p_{\text{pickup}}(z, s) \cdot \bar{f}(z, s)$$

where:
- $p_{\text{pickup}}(z, s) = \frac{D(z, s)}{D(z, s) + \lambda}$ is the pickup probability with half-saturation parameter $\lambda$
- $D(z, s)$ is the historical pickup demand at zone $z$ during slot $s$
- $\bar{f}(z, s)$ is the mean fare amount for trips originating at zone $z$ during slot $s$

### Transition Dynamics

After a successful pickup at zone $z$, the driver transitions to the dropoff zone $z'$ with probability:

$$P(z' | z) = \frac{N(z \rightarrow z')}{\sum_{z''} N(z \rightarrow z'')}$$

where $N(z \rightarrow z')$ is the historical count of trips from zone $z$ to zone $z'$.

### Relocation Cost

Moving from zone $z_i$ to zone $z_j$ incurs a time cost $\tau(z_i, z_j)$ computed via Dijkstra's shortest path on the road network. The effective utility is discounted by:

$$U_{\text{effective}}(z_j) = \frac{U(z_j)}{\lfloor \tau(z_i, z_j) / 30 \rfloor + 1}$$

### Evaluation Metrics

| Metric | Formula | Description |
|--------|---------|-------------|
| **NDCG@3** | $\frac{1}{\lvert Q\rvert}\sum_{q} \frac{DCG_q}{IDCG_q}$ | Normalized discounted cumulative gain |
| **Hit@3** | $\frac{1}{\lvert Q\rvert}\sum_{q} \mathbb{1}[\text{argmax}_z U_q(z) \in R_q]$ | Fraction of queries where top-1 ideal zone is in recommendations |
| **Top-1 Utility** | $\frac{1}{\lvert Q\rvert}\sum_{q} U_q(r_1^{(q)})$ | Mean reference utility of the top-ranked recommendation |
| **Avg Daily Fare** | $\frac{1}{N}\sum_{i=1}^{N} F_i$ | Mean total fare earned per simulated day |

### Constraints

- **Real-time**: Recommendation latency must be < 10 ms per query
- **Data**: Only historical trip data available (no real-time demand signals)
- **Stationarity**: Demand patterns assumed to follow weekly seasonality