Time Windows

Handle time window constraints for routing and scheduling optimization.

Installation

pip install numpy

Quick Start

from datetime import datetime, timedelta
from typing import Tuple, List

def check_time_window(arrival_time: datetime, window: Tuple[datetime, datetime]) -> dict:
    """
    Check if an arrival time fits within a time window.
    Returns timing details including wait time if early.
    """
    start, end = window

    if arrival_time < start:
        return {
            'feasible': True,
            'early': True,
            'wait_time': (start - arrival_time).total_seconds() / 60,
            'service_start': start
        }
    elif arrival_time <= end:
        return {
            'feasible': True,
            'early': False,
            'wait_time': 0,
            'service_start': arrival_time
        }
    else:
        return {
            'feasible': False,
            'late_by': (arrival_time - end).total_seconds() / 60
        }

Common Patterns

Time Window Representation

class TimeWindow:
    """Represent a time window with optional flexibility."""

    def __init__(self, start: datetime, end: datetime,
                 soft_start: datetime = None, soft_end: datetime = None):
        self.hard_start = start
        self.hard_end = end
        self.soft_start = soft_start or start
        self.soft_end = soft_end or end

    def check_arrival(self, arrival: datetime) -> dict:
        """Check arrival against time window."""
        result = {
            'hard_feasible': self.hard_start <= arrival <= self.hard_end,
            'soft_feasible': self.soft_start <= arrival <= self.soft_end,
            'wait_time': 0,
            'penalty': 0
        }

        if arrival < self.hard_start:
            result['wait_time'] = (self.hard_start - arrival).total_seconds()
        elif arrival > self.hard_end:
            result['hard_feasible'] = False

        # Calculate soft penalty
        if arrival < self.soft_start:
            result['penalty'] = (self.soft_start - arrival).total_seconds()
        elif arrival > self.soft_end:
            result['penalty'] = (arrival - self.soft_end).total_seconds()

        return result

    def overlaps(self, other: 'TimeWindow') -> bool:
        """Check if this window overlaps with another."""
        return (self.hard_start <= other.hard_end and
                self.hard_end >= other.hard_start)

    def duration_minutes(self) -> float:
        """Get window duration in minutes."""
        return (self.hard_end - self.hard_start).total_seconds() / 60

Route Time Window Feasibility

def check_route_feasibility(route: List[dict], travel_times: dict) -> dict:
    """
    Check if a route respects all time windows.
    route: list of {'location': str, 'window': (start, end), 'service_time': int}
    travel_times: dict of (from, to) -> minutes
    """
    current_time = route[0].get('departure_time', datetime.now())
    schedule = []
    violations = []

    for i, stop in enumerate(route):
        if i > 0:
            travel = travel_times.get((route[i-1]['location'], stop['location']), 0)
            current_time += timedelta(minutes=travel)

        window_start, window_end = stop['window']

        if current_time < window_start:
            wait = (window_start - current_time).total_seconds() / 60
            current_time = window_start
        elif current_time > window_end:
            violations.append({
                'stop': i,
                'location': stop['location'],
                'late_by': (current_time - window_end).total_seconds() / 60
            })
            wait = 0
        else:
            wait = 0

        schedule.append({
            'location': stop['location'],
            'arrival': current_time,
            'wait_time': wait,
            'departure': current_time + timedelta(minutes=stop.get('service_time', 0))
        })

        current_time += timedelta(minutes=stop.get('service_time', 0))

    return {
        'feasible': len(violations) == 0,
        'violations': violations,
        'schedule': schedule,
        'total_time': (current_time - route[0].get('departure_time', datetime.now())).total_seconds() / 60
    }

Time Window Clustering

def cluster_by_time_window(stops: List[dict], max_gap_minutes: int = 60) -> List[List[dict]]:
    """
    Cluster stops by overlapping or close time windows.
    """
    if not stops:
        return []

    # Sort by window start
    sorted_stops = sorted(stops, key=lambda x: x['window'][0])

    clusters = [[sorted_stops[0]]]

    for stop in sorted_stops[1:]:
        current_cluster = clusters[-1]
        last_stop = current_cluster[-1]

        # Check if windows are close enough
        gap = (stop['window'][0] - last_stop['window'][1]).total_seconds() / 60

        if gap <= max_gap_minutes:
            current_cluster.append(stop)
        else:
            clusters.append([stop])

    return clusters

Time Window Relaxation

def relax_time_windows(stops: List[dict], max_relaxation_minutes: int = 30) -> List[dict]:
    """
    Relax time windows to improve routing flexibility.
    """
    relaxed = []

    for stop in stops:
        window_start, window_end = stop['window']

        # Expand window
        new_start = window_start - timedelta(minutes=max_relaxation_minutes)
        new_end = window_end + timedelta(minutes=max_relaxation_minutes)

        relaxed.append({
            **stop,
            'original_window': stop['window'],
            'window': (new_start, new_end),
            'relaxation': max_relaxation_minutes
        })

    return relaxed

Minimize Waiting Time

def optimize_departure_time(route: List[dict], travel_times: dict) -> datetime:
    """
    Find optimal departure time to minimize total waiting time.
    """
    # Calculate earliest feasible departure
    min_departure = None

    for i, stop in enumerate(route):
        if i == 0:
            continue

        # Calculate time needed to reach this stop
        cumulative_travel = 0
        cumulative_service = 0
        for j in range(i):
            if j > 0:
                cumulative_travel += travel_times.get(
                    (route[j-1]['location'], route[j]['location']), 0
                )
            cumulative_service += route[j].get('service_time', 0)

        # Latest departure to arrive at window end
        window_end = stop['window'][1]
        latest_departure = window_end - timedelta(
            minutes=cumulative_travel + cumulative_service
        )

        if min_departure is None or latest_departure < min_departure:
            min_departure = latest_departure

    # Adjust for first stop's window
    if route:
        travel_to_first = travel_times.get(('depot', route[0]['location']), 0)
        first_window_start = route[0]['window'][0]
        earliest_useful = first_window_start - timedelta(minutes=travel_to_first)

        if min_departure and min_departure < earliest_useful:
            min_departure = earliest_useful

    return min_departure

Time Window Statistics

def analyze_time_windows(stops: List[dict]) -> dict:
    """
    Generate statistics about time windows.
    """
    if not stops:
        return {}

    durations = []
    start_times = []
    end_times = []

    for stop in stops:
        start, end = stop['window']
        durations.append((end - start).total_seconds() / 60)
        start_times.append(start)
        end_times.append(end)

    return {
        'count': len(stops),
        'avg_duration_minutes': sum(durations) / len(durations),
        'min_duration': min(durations),
        'max_duration': max(durations),
        'earliest_start': min(start_times),
        'latest_end': max(end_times),
        'span': (max(end_times) - min(start_times)).total_seconds() / 3600,
        'tight_windows': sum(1 for d in durations if d < 60)
    }