Time-window feasibility

Deep dive

How it works

In: a sequence of nodes with windows [a, b] and service times, travel times, and a candidate change (insert, move, swap) · Out: feasible or not, plus the time-warp penalty for soft windows · State: per route, prefix and suffix segments (duration, earliest, latest, warp) · Cost: check O(1); refresh O(route length) after an accepted move

Notation: start t_i, window [a_i, b_i], service s_i, travel d_ij. Arrival A_j = t_i + s_i + d_ij, start t_j = max(A_j, a_j), wait W_j = t_j - A_j; feasible iff t_j <= b_j everywhere.

1. Forward pass: earliest start E_j = max(a_j, E_i + s_i + d_ij); infeasible if E_j > b_j.
2. Backward pass: latest start L_i = min(b_i, L_j - s_i - d_ij). L_i - E_i is the slack of stop i.
3. Forward time slack (Savelsbergh 1985): F_i = min over j >= i of (waits after i up to j, plus b_j - t_j): how far the start at i can be pushed without breaking a later window.
4. Insert u between i and j: t_u = max(t_i + s_i + d_iu, a_u) must be <= b_u; the tail is pushed by t_u + s_u + d_uj - t_j (minus W_j), and the insertion is feasible iff that push is <= F_j (Savelsbergh 1985/1992).
5. Segment concatenation (Vidal et al. 2015) covers any rearrangement. A segment is (dur, tw, early, late): any start in [early, late] takes dur and incurs warp tw. Merge with edge d: at = f.dur - f.tw + d; dtw = max(0, f.early + at - s.late); wait = max(0, s.early - at - f.late); then dur = f.dur + s.dur + d + wait, tw = f.tw + s.tw + dtw, early = max(f.early, s.early - at) - wait, late = min(f.late, s.late - at) + dtw.
6. Move test: keep prefixes P[i] and suffixes S[j]. A candidate is a few kept pieces concatenated (insert: P[i] ++ u ++ S[j]; 2-opt*: P[i] ++ S'[j] from another route). Evaluate the merge chain, read tw.
7. After an accepted move, rebuild data of the two touched routes only.

Soft windows. Price instead of reject. With time warp (a late start is clamped to b and the clock is rewound) tw is the penalised quantity: cost = distance + w * tw, O(1) per check (Vidal et al. 2013, 2015). Linear lateness propagates delay and composes less simply; solvers handle it as a soft bound on a time variable (OR-Tools SetCumulVarSoftUpperBound).

Code

Hard windows, one route, Manhattan travel. insert_ok is the O(1) merge chain; simulate is the O(n) oracle; main asserts they agree.

use std::time::Instant;

#[derive(Clone, Copy)]
struct Seg { dur: i64, tw: i64, early: i64, late: i64 } // start in [early, late] gives time warp tw

struct Node { x: i64, y: i64, a: i64, b: i64, s: i64 } // window [a, b], service s

fn dist(p: &Node, q: &Node) -> i64 { (p.x - q.x).abs() + (p.y - q.y).abs() }
fn single(n: &Node) -> Seg { Seg { dur: n.s, tw: 0, early: n.a, late: n.b } }

// Concatenation (Vidal et al. 2015): first, edge of length d, second. O(1).
fn merge(f: Seg, d: i64, s: Seg) -> Seg {
    let at = f.dur - f.tw + d;                        // arrival at second, relative to start
    let dtw = (f.early + at - s.late).max(0);         // arrive after the window closes
    let wait = (s.early - at - f.late).max(0);        // must wait even when starting latest
    Seg { dur: f.dur + s.dur + d + wait,
          tw: f.tw + s.tw + dtw,
          early: f.early.max(s.early - at) - wait,
          late: f.late.min(s.late - at) + dtw }
}

// prefix[i] = nodes 0..=i, suffix[i] = nodes i..; node 0 and last are the depot.
fn build(r: &[usize], ns: &[Node]) -> (Vec<Seg>, Vec<Seg>) {
    let n = r.len();
    let (mut p, mut q) = (vec![single(&ns[r[0]]); n], vec![single(&ns[r[n - 1]]); n]);
    for i in 1..n { p[i] = merge(p[i - 1], dist(&ns[r[i - 1]], &ns[r[i]]), single(&ns[r[i]])); }
    for i in (0..n - 1).rev() { q[i] = merge(single(&ns[r[i]]), dist(&ns[r[i]], &ns[r[i + 1]]), q[i + 1]); }
    (p, q)
}

// O(1): can u go between positions i and i+1?
fn insert_ok(r: &[usize], p: &[Seg], q: &[Seg], ns: &[Node], i: usize, u: usize) -> bool {
    let a = merge(p[i], dist(&ns[r[i]], &ns[u]), single(&ns[u]));
    merge(a, dist(&ns[u], &ns[r[i + 1]]), q[i + 1]).tw == 0
}

// O(n) reference: leave the depot at its earliest time, wait when early, fail when late.
fn simulate(r: &[usize], ns: &[Node]) -> bool {
    let mut t = ns[r[0]].a;
    for k in 1..r.len() {
        t += ns[r[k - 1]].s + dist(&ns[r[k - 1]], &ns[r[k]]);
        t = t.max(ns[r[k]].a);
        if t > ns[r[k]].b { return false; }
    }
    true
}

fn main() {
    let mut seed = 12345u64;
    let mut rnd = |m: i64| { seed ^= seed << 13; seed ^= seed >> 7; seed ^= seed << 17; (seed % m as u64) as i64 };
    let (mut checks, mut feas) = (0u64, 0u64);
    for _ in 0..2000 {
        let n = 30;
        let mut ns: Vec<Node> = (0..n).map(|_| {
            let a = rnd(400);
            Node { x: rnd(50), y: rnd(50), a, b: a + 20 + rnd(150), s: rnd(8) }
        }).collect();
        ns[0] = Node { x: 25, y: 25, a: 0, b: 100_000, s: 0 }; // depot
        let mut r = vec![0usize, 0];
        for u in 1..n { r.insert(r.len() - 1, u); if !simulate(&r, &ns) { r.remove(r.len() - 2); } }
        let (p, q) = build(&r, &ns);
        for u in 1..n {
            if r.contains(&u) { continue; }
            for i in 0..r.len() - 1 {
                let fast = insert_ok(&r, &p, &q, &ns, i, u);
                let mut r2 = r.clone(); r2.insert(i + 1, u);
                assert_eq!(fast, simulate(&r2, &ns));
                checks += 1; feas += fast as u64;
            }
        }
    }
    println!("{checks} insertions agree with the simulation ({feas} feasible)");
    // long route, wide windows: one timed batch each, no per-call timers
    let ns: Vec<Node> = (0..1002).map(|k| Node { x: k as i64 % 50, y: k as i64 / 50, a: 0, b: 1_000_000, s: 1 }).collect();
    let r: Vec<usize> = (0..1001).chain([0]).collect();
    let (p, q) = build(&r, &ns);
    let (t0, mut c) = (Instant::now(), 0);
    for i in 0..1000 { c += insert_ok(&r, &p, &q, &ns, i, 1001) as usize; }
    let o1 = t0.elapsed();
    let t0 = Instant::now();
    for i in 0..1000 { let mut r2 = r.clone(); r2.insert(i + 1, 1001); c += simulate(&r2, &ns) as usize; }
    println!("n=1000, 1000 checks ({c} ok): O(1) {:?}, O(n) {:?}", o1, t0.elapsed());
}

Run (release, std only): 308,776 seeded random insertions (2,000 instances of 30 nodes, 57,141 feasible) all agree. At n = 1000, 1,000 checks took about 3-9 µs with the O(1) test and 1.5 ms with clone-and-simulate (two runs).

Complexity and constants

• Check O(1): a dozen i64 max/min operations on three segments of 32 B. Refresh O(n) per accepted move. A neighbourhood of O(n^2) candidates costs O(n^2) instead of O(n^3).
• Cost drivers: cache misses on segment arrays of long routes, and refresh frequency. Keep segments contiguous by position.

Efficiency

• Cost: a merge chain is a handful of integer max/min ops, measured here at a few ns per check; bound is compute and first-touch cache misses, not bandwidth.
• Levers:
  • Prefix/suffix segments — O(n) per candidate becomes O(1) (benchmark above) — many candidates per accepted move.
  • Cheap necessary test first (E_u <= b_u from the forward pass) — prunes without the suffix — large neighbourhoods.
  • Hard check before cost — skips distance and penalty arithmetic for the infeasible majority (here 81% infeasible) — tight windows.
  • Refresh only touched routes — work scales with the change, not the solution — many short routes.
• Naive → standard → state of the art: re-simulate per candidate · O(n) · forward-slack check · O(1) for insertion · segment concatenation · O(1) for any rearrangement into few pieces, with warp and duration for penalties.

Implementation notes

• Integer time. Wide windows like [0, i64::MAX/4] are fine; i64::MAX overflows in early + at.
• Depot is a node with window [0, horizon] at both ends; a shift limit is the end depot's b.

Pitfalls

• Using only the next stop's latest time: slack is a minimum over the whole tail.
• Ignoring waiting in the push test rejects feasible moves.
• Reversed segments (2-opt, or-opt with reversal) need separately built data; merge is not symmetric.

Variants and alternatives

In production

• Routing solvers using local search, vehicle routing heuristics and large neighbourhood search; savings merges check the same windows.
• Slot assignment for arrivals (arrival sequencing) and machine schedules with release dates (job shop).

Implementations

Sources

• Savelsbergh, Local search in routing problems with time windows, Annals of Operations Research 4, 1985, 285-305. paper
• Savelsbergh, The vehicle routing problem with time windows: minimizing route duration, ORSA Journal on Computing 4(2), 1992, 146-154. paper
• Vidal, Crainic, Gendreau, Prins, Timing problems and algorithms: Time decisions for sequences of activities, Networks 65(2), 2015, 102-128. paper
• Vidal, Crainic, Gendreau, Prins, A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows, Computers & Operations Research 40(1), 2013, 475-489. paper