Where Popularity Bias Enters Time-Windowed Itinerary Planning at City Scale

Planning a day of visits for a user, such as museums, cafés, or theme-park rides, means choosing places they will like and ordering them so each is reached while it is open and before the day runs out. At the scale of a real city with thousands of venues, no exact planner can search every venue. Practical systems therefore shortlist a few dozen candidates by predicted preference and then solve the ordering problem over that shortlist. We argue that this pipeline creates popularity bias in two places that current debiasing methods never touch. The first is the check-in counts used to measure popularity: they are inflated by how long a venue is open, not only by how much people like it. The second is the shortlist itself: venues open all day compete in every hour, while niche venues with narrow opening windows are crowded out before the planner ever sees them.

The proposal has two parts. First, we estimate popularity per hour of availability rather than per venue, so that a venue open two hours is not judged against one open fourteen. Second, we build the shortlist separately for each time slot of the day, so that every venue competes only against others open at the same time, using a debiased score. An exact planner then works on the shortlist and keeps every tour feasible by construction. The bet is that this recovers long-tail venues in tours at almost no runtime cost. Existing score-level debiasing applied in front of a standard shortlist recovers them in item rankings but not in the tours users actually receive.

Core Claim

Three bodies of work each handle one piece of this problem. Debiasing methods for recommendation treat popularity as a property of a static user–item graph. MACR subtracts an estimated direct popularity effect at test time, using a causal graph that separates "users click popular items" from genuine user–item match. DAP proves that graph convolutions pull users toward high-degree items (influence growing as $d_i^{3/2}$ in degree $d_i$) and subtracts a cluster-level "popularity gravity" vector after training. Adap-τ controls the growth of embedding length for frequent items with an adaptive temperature.

These papers motivate our problem. They show that the bias is real and that it can be corrected at the score level. None of them models time-dependent availability, and none of them follows the corrected scores through a constrained combinatorial step. Time-windowed trip planning has the opposite gap. Personalized Trip Recommendation with POI Availability and Uncertain Traveling Time solves itineraries under opening intervals with dominance-pruned state expansion; its relaxed variant SE-SR stays within 1% of optimal "happiness" on Yelp. Its preference scores, however, are a static rating model, and it was run on limited city data. TLR-M_UI predicts the next venue and its queue time with a transformer. It does no formal debiasing and leaves full itinerary planning to future work.

We claim two things. First, in time-windowed domains the observed visit count of venue $i$ factors roughly as

$$c_i \approx a_i \cdot w_i,$$

where $a_i$ is the venue's appeal per available hour and $w_i$ is its total open time over the observation period. Debiasing on raw $c_i$, as MACR and inverse-propensity methods do, therefore conflates "liked" with "open long." Second, the scalability step of top-$K$ shortlisting by score reintroduces the bias even after the scores are corrected. Wide-window venues occupy shortlist slots that narrow-window venues could only have used at specific times.

The fix pairs availability-normalized popularity, $\log(c_i / w_i)$, used as the confounder in a MACR-style subtraction, with slot-stratified shortlisting. Its goal is tour-level exposure of the tail, which differs from the item-level tail recall that prior work optimizes.

Research Program

The system has three components.

The first is the scorer. We train a standard preference model (LightGCN or a sequential transformer) on check-in sequences. At inference we subtract a learned direct effect of availability-normalized popularity, exactly following MACR's counterfactual inference except for the confounder.

The second is a slot reachability index. This is the scalability component. The day is cut into slots of length $\Delta$ (we will sweep 30 to 90 minutes). For each venue we precompute which slots it is open in and store a coarse travel-time grid. At query time, given a start point and a time budget, the index returns the venues that are reachable and open in each slot, without touching the full venue set. We then take the top $k$ debiased-score venues per slot. The union, at most $k$ times the number of slots, forms the shortlist.

The third is the planner. SE-SR-style dominance-pruned state expansion runs on the shortlist, so hard windows are enforced structurally rather than appended as features. Jinhui Yi et al. document that appending windows as features leads to severe schedule violations, which is why we enforce them in the planner.

We deliberately do not adopt hub-centric scaling such as the core-fringe GNN or RWDISK's hub sinks. Both route computation through high-degree nodes, and in this domain those nodes are exactly the popular venues. Slot stratification is a non-hub decomposition: it partitions by time, not by degree. It also avoids the failure mode that kept HLGP restricted to window-free routing, namely spatial partitions breaking temporal coupling between distant stops.

Opening windows must be specified for every venue. Massive-STEPS has no published opening hours, so for it we derive empirical windows from the time-of-day distribution of check-ins. We will report how sensitive results are to this estimate. For the Yelp-derived data used by the trip-recommendation paper, we use the stated opening intervals. A known risk is circularity: windows estimated from check-ins inherit the same exposure we are correcting for. The synthetic study below is designed to measure how much this matters.

Baselines

The naive reference is the undebiased pipeline: a preference model scored on raw counts, a global top-$K$ shortlist, and the same exact planner. Every system uses the same planner, the same total shortlist size, and the same per-query time limit. This isolates where bias enters from how well tours are optimized.

The strongest existing competitor is the same pipeline with MACR's counterfactual subtraction using raw counts. MACR is the most effective score-level debiaser in the file, with average HR@20 gains of 153% over matrix factorization and 241% over LightGCN across five benchmarks MACR. A second strong competitor is DAP, applied post hoc to the LightGCN scorer. DAP reports Gowalla tail Recall +23.96% and tail NDCG +28.27% with overall metrics up 1–5% DAP. Adap-τ (9% average gain Adap-τ) is included as the normalization-style debiaser. All scorers share a backbone, training data, and an equal hyperparameter search budget. Each debiasing strength is tuned on the same validation split under the same overall-accuracy floor.

No reported result was found on Lacuna for tour-level tail exposure or tour hit rate on Massive-STEPS or any time-windowed itinerary benchmark, so every baseline number is produced by our own runs. The closest published quality anchors are SE-SR's within-1% gap to exact search on Yelp Personalized Trip Recommendation and TLR-M_UI's Edinburgh F1@5 of 0.1613 TLR-M_UI. We will reproduce the latter as a next-venue sanity check on the city data.

Two ablations isolate the key ingredients: availability normalization with a global shortlist, and slot-stratified shortlisting with raw-count MACR. Beating MACR-with-raw-counts means two things together. Tail-venue share in tours must rise by a margin exceeding seed variance. Tour hit rate on held-out visits must not drop more than one point. The ablations must also show which ingredient carries the gain.

Why not just…?

Why not just apply MACR or DAP to the scorer and keep the standard shortlist? This is the main threat, and it is a real one. If the shortlist is not where bias re-enters, it will match our method. The slot-stratification ablation settles this directly. We will also report the fraction of debiased-top-ranked tail venues that are dropped at shortlisting versus dropped by the planner for infeasibility. If almost none are dropped at shortlisting, we will narrow the claim to availability normalization alone.

Why not just enlarge the shortlist? With a large enough $K$ the tail gets in. The cost is that state expansion grows sharply with candidate count, which is why the exact methods were only shown on limited data. We will trace tail exposure against planner runtime as $K$ grows. Slot stratification must reach a given exposure level at clearly lower runtime. If brute-force $K$ reaches it within the query time limit on Massive-STEPS-scale cities, the scalability half of the claim fails.

Why not just add a tail-coverage reward to the tour objective? A diversity or tail bonus in the planner's prize is simple. It still does not address the confounded popularity estimate, though. It also cannot help venues that never reach the shortlist. We include it as a baseline with the bonus weight tuned, and we test it in combination with our shortlist to check whether the two are complementary.

Why not just use inverse propensity weighting on raw counts? MACR's authors report that it is unstable and hard to tune MACR. More to the point, using raw counts as propensities inherits the availability confound. We run it with propensities $c_i$ and with $c_i/w_i$. This turns it into a second test of whether normalization, rather than the debiasing family, is what matters.

Proposed Experiments

The decisive first check is synthetic. We simulate cities with known per-hour appeal $a_i$, heterogeneous windows $w_i$, and users who visit under travel and time-budget limits. We then ask which popularity estimate recovers $a_i$, and which pipeline yields tours whose venue frequencies match those of an oracle planner with true appeal. If raw-count debiasing is not measurably worse than availability-normalized debiasing here, the first claim is dead. The same simulation will also test the circularity risk by estimating windows from simulated check-ins instead of using true ones.

On real data we use three settings. The first is the Massive-STEPS cities, which have thousands of venues; its reported entropy–accuracy correlation of r = −0.646 already signals heavy category skew. The second is Halder et al.'s theme-park and city sets, which have 20–40 venues per park and 242 in Melbourne. The third is the Yelp trip-planning setup. The small sets allow exact planning over all venues. That lets us measure the quality gap that shortlisting introduces, with a target within 1–2% of full exact search, matching the SE-SR tolerance.

Each user's held-out day of visits serves as ground truth. Our metrics are tour hit rate, tail-venue share in generated tours, and coverage of narrow-window venues. We also report window-violation rate, which should be zero by construction, and per-query latency. Using Massive-STEPS' 2012–13 versus 2017–18 split, we train on the early period and test on the late period to check that per-hour normalization is more robust to drift than raw counts.

The project succeeds if the full method raises tail and narrow-window coverage in tours over MACR-with-raw-counts at equal hit rate and runtime, and the ablations attribute the gain. It fails informatively if score-level debiasing alone already closes the gap.