The Traveling Salesdog Problem

A Julia + JuMP mixed-integer linear program plans an aging greyhound’s weekly walks, making distance/novelty tradeoffs explicit across 22.8 trillion possible schedules.

What Matters

• Model uses binary matrix x[day, walk_time, activity] plus used_activity[a] to maximize variety and off-leash runs while capping daily mileage.
• Consecutive-day constraint blocks any activity from repeating within a 2-day window; morning/night walks within the same day must also differ.
• Optimal solution from 460,800 tied schedules yields 9.4 miles/week, 9 unique activities, 8 run/play walks across 7 days.
• Lincoln Park (0.2 mi) dominates the schedule; Harvard (0.8 mi) appears once Sunday morning — distance penalty working as intended.
• Excluded stochastic factors: weather, baseball games, kite-flyers, enemy dogs, and Bebop’s veto on going home.
• [HN: @jdw64] Key modeling question is what to exclude; veto behavior was dropped because it would require tracking prior-day plan execution to satisfy novelty constraints.
• [HN: @wespiser_2018] Vetos occur mostly going home, not departing; a plan-with-options variant could handle it but complicates the novelty constraint across days.

Original | Discuss on HN