route-planning

Route Planning Skill

Overview

Plan efficient multi-city road trips with constraints like starting point, number of days, and no-fly requirements.

Core Strategy

Distance-Based Route Optimization

• Use distance matrix to calculate travel times/distances
• Minimize backtracking between cities
• Allocate days based on travel time and activities per city

Day Allocation Strategy

• 1 day for initial travel to first city
• Remaining days distributed across 3 Ohio cities
• Typical allocation: 2-2-2 days or 2-2-3 depending on distances
• Last day may include return travel (not full return in this case)

Python Code Example

from typing import List, Dict, Tuple
from itertools import permutations

def find_best_route(
    start_city: str,
    num_cities: int,
    available_cities: List[str],
    distance_matrix: Dict[str, Dict[str, float]]
) -> Tuple[List[str], float]:
    """
    Find optimal route visiting num_cities starting from start_city.
    Returns (route, total_distance)
    """
    best_route = None
    best_distance = float('inf')

    # Try all permutations of available cities
    for perm in permutations(available_cities[:num_cities]):
        route = [start_city] + list(perm)
        total_distance = calculate_route_distance(route, distance_matrix)

        if total_distance < best_distance:
            best_distance = total_distance
            best_route = route

    return best_route, best_distance

def calculate_route_distance(route: List[str], distance_matrix: Dict) -> float:
    """Calculate total distance for a route"""
    total = 0
    for i in range(len(route) - 1):
        from_city = route[i]
        to_city = route[i + 1]

        if from_city in distance_matrix and to_city in distance_matrix[from_city]:
            total += float(distance_matrix[from_city][to_city])
        else:
            return float('inf')  # Invalid route

    return total

def allocate_days_to_cities(
    num_days: int,
    num_cities: int
) -> List[int]:
    """
    Allocate days across cities.
    First city gets 1 day (travel day), remaining split among other cities.
    """
    # First city gets 1 day for arrival/travel
    remaining_days = num_days - 1
    remaining_cities = num_cities

    days_per_city = [1]  # First city

    # Distribute remaining days
    base_days = remaining_days // remaining_cities
    extra_days = remaining_days % remaining_cities

    for i in range(remaining_cities):
        days = base_days + (1 if i < extra_days else 0)
        days_per_city.append(days)

    return days_per_city

def estimate_travel_time(distance: float, mph: float = 60) -> float:
    """Estimate driving time in hours"""
    return distance / mph