The Traveling Salesdog Problem

How I used numerical optimization to plan my greyhound’s week

Posted on by Adam Wespiser

Bebop at the beach

Bebop, my Greyhound, is a big dog. 85lbs, and starting to slow down. Tall enough to sneak a bite of Easter ham off the counter from behind the island, and cute enough to get away with it. Greyhounds might look weird, yet their form strictly follows function. Track movement in an open field, chase it, and entertain the people watching.

As a puppy, he never stopped. Yet, the moment came when I noticed him take the first step slower, become more selective about play, and take longer to recover.

In light of this, I’ve started thinking about what the perfect routine would be: two walks a day, one run, minimal time over hard surfaces. He loves novelty, so different activities every day, and never the same activity two days in a row.

In other words, maximum variety and enrichment while minimizing the distance traveled from home.

Julia + JuMP

This task, how do we pick the best of several choices under constraint, is an optimization problem. Taking the activities we can do and their qualities into consideration, the question of dog enrichment can be solved with a mixed-integer linear program: a set of binary decisions (what we do and when) with an objective to minimize distance.

To solve this, I reached for Julia’s JuMP library. I’ve always liked Julia for its ergonomics and performance, and JuMP lets you write a model that looks almost exactly like the math.

We can skip the mathematical formalisms, and JuMP will take us from mental model to executable code.

Project Setup

The project is available on github and has two main files. The optimizer defines the model, reads in data, and prints the results, while a csv file defines each activity and its attributes as a row. The goal of this project is to reason about the tradeoffs by comparing optimal solutions to our actual schedule, not find a magical perfect solution. In other words, I’ll be able to take our existing schedule, and compare it to the optimal schedule to see which constraints are respected, and where I could do better.

I recorded 9 possible activities, estimated their distance from my home, and noted if they have an off leash area. For distance, I’m using “door to door” distance from my house, where each activity starts and stops from my front door. Fortunately, we only do one activity per walk so we can avoid modelling the distance between activities.

activity_id distance_miles area has_run_area
R1 0.2 Lincoln Park Yes
R2 0.3 Perry Park Yes
R3 0.6 AAAS Woods Yes
R4 0.4 CHA Park No
R5 0.3 Community Plaza No
R6 0.2 Neighbors House No
R7 0.8 Harvard No
R8 0.3 Union Square No
R9 0.4 Martha Perry Lowe Park No

Variables

For the model, I set up two variables, x and used_activity to keep track of the activities assigned to walks, and which activities are used.

x is a binary matrix which designates the weekly schedule. It’s indexed by day, walk time (morning or night), and activity with the value set to 0 or 1. For instance, x[monday, morning, lincoln park] equals 1 if we go to Lincoln Park for the Monday morning walk, and 0 otherwise.

used_activity records which activities are performed during the week. For instance, used_activity[a] == 1 means the activity appears once in the weekly schedule.

Maximizing used_activity increases the coverage of unique activities each week. Besides counting activities, we can restrict the activities to only appear once per day and prevent the same activity appearing in consecutive days. There are better psychological measures of novelty, like optimizing days since doing the activity last, or exponential time decay, but I wanted to keep the model simple.

Here’s the definition of the variables in JuMP:

@variable(model, x[day_indexes, walk_indexes, activity_indexes], Bin)
@variable(model, used_activity[activity_indexes], Bin)

Constraints

There are three constraint families:

First, we’ll set up constraints to uphold a daily structure of one walk in the morning and evening. We want one activity per walk, at least one run per day, and put a distance cap on all activities in a day.

The expression @constraint(m, [range], condition) means for all [range], condition must hold. To put a cap on distance traveled, max_daily_distance is a constant based on my smartphone activity data, and we use round_trip_distance to account for distance as “travel under paw” or two times distance from home.

# assign one activity per walk
@constraint(model, [d in day_indexes, w in walk_indexes],
    sum(x[d, w, a] for a in activity_indexes) == 1)

# daily distance cap
@constraint(model, [d in day_indexes],
    sum(round_trip_distance[a] * x[d, w, a]
        for w in walk_indexes, a in activity_indexes) <= max_daily_distance)

# at least one run per day
@constraint(model, [d in day_indexes],
    sum(activities.has_run_area[a] * x[d, w, a]
        for w in walk_indexes, a in activity_indexes) >= 1)

For novelty, the first constraint ensures morning and night walks have different activities, and the second ensures activities from two subsequent days must be different.

# morning and night activities are unique
@constraint(model, [d in day_indexes, a in activity_indexes],
    sum(x[d, w, a] for w in walk_indexes) <= 1)

# activities from subsequent days are different
@constraint(model, [d in 2:day_count, a in activity_indexes],
    sum(x[d, w, a] for w in walk_indexes) +
    sum(x[d - 1, w, a] for w in walk_indexes) <= 1)

For weekly variety, we add two small bookkeeping constraints that link used_activity[a] to the actual schedule. Since used_activity is derived from the schedule decisions in x, we need to force it to turn on when an activity is selected, and keep it off if an activity is never selected.

# if used_activity[a] is 1, activity a must be assigned at least once.
@constraint(model, [a in activity_indexes],
    used_activity[a] <= sum(x[d, w, a]
        for d in day_indexes, w in walk_indexes))

# if activity a is assigned to any walk, used_activity[a] must turn on.
@constraint(model, [d in day_indexes, w in walk_indexes, a in activity_indexes],
    used_activity[a] >= x[d, w, a])

This gives us a derived value that simplifies our optimization.

Objective Function

Now, we can implement the objective: find the weekly schedule that gives Bebop the most variety and daily enrichment while keeping the pavement mileage low. For each of the three terms, we have a model weight, weight.{X}, which is a pre-defined constant to balance the terms.

The first expression of the objective rewards variety, where used_activity[a] is 1 if activity a appears at least once during the week. weights.area controls how much the model values adding one more distinct activity.

weights.area * sum(used_activity[a] for a in activity_indexes)

Next, we want to reward activities where Bebop can run off leash. activities.has_run_area[a] is 1 if an activity has a run/play opportunity, so x[d, w, a] is 1 if an activity a is chosen for that walk. Multiplying them means that we count this walk only if the chosen activity has a run/play area, so this term rewards schedules with more run/play walks. Additionally, we have weights.run which is a constant model weight.

weights.run * sum(activities.has_run_area[a] * x[d, w, a]
    for d in day_indexes, w in walk_indexes, a in activity_indexes)

Finally, a term to penalize extra miles by counting the total mileage under foot across the week. We subtract the model weight, - weights.distance * ..., so the optimization will favor closer activities, all else being equal.

- weights.distance * sum(round_trip_distance[a] * x[d, w, a]
      for d in day_indexes, w in walk_indexes, a in activity_indexes)

Putting it together, we get an objective that rewards variety and runs, while penalizing travel further away from home.

@objective(model, Max,
  weights.area * sum(used_activity[a] for a in activity_indexes)
  + weights.run * sum(activities.has_run_area[a] * x[d, w, a]
      for d in day_indexes, w in walk_indexes, a in activity_indexes)
  - weights.distance * sum(round_trip_distance[a] * x[d, w, a]
      for d in day_indexes, w in walk_indexes, a in activity_indexes))

That’s it!

Modeling choices

To get the distances, I eyeballed the distance in Google Maps, and applied a fudge factor based on how much of the distance was on hard surfaces, what Bebop doesn’t like. Walks are not a straight line anyway, so similar to setting daily maximum distance based off my smartphone’s health tracker, this gets us close.

Several factors are not included in the model, like weather, construction, picnics, enemy dogs, or Bebop deciding to veto my selection. Sometimes Bebop just freezes if we aren’t going to the nearest park, so a more accurate model would need to account a probability that we aren’t going to the closest park. Additionally, Bebop can’t run on a field if there are children playing, or a family having a picnic. We’ve tried that, it doesn’t work out, and he also doesn’t like people flying kites. I’m not sure why. Between May and October there are often baseball or softball games on the fields, which happens only at night. All of these exceptions could be accounted for, but each one greatly increases the complexity of the model.

We are also modelling novelty as weekly activity coverage and avoid assigning an activity more than once per 2 day period— not true psychological novelty. For picking walks day to day, I solve this problem by choosing the activity we have least recently done, but using exponential time decay function could work better. This simplified constraints are enough for this application, but one notable edge case is that running the schedule week over week might result in repeated activities on the first day of the week.

Results

Taking a look at the results, we get a diverse schedule, and a few things stand out:

Here’s a pretty print of the results:

Weekly dog-walking schedule
===========================
Monday:
  morning: R2 (perry park, run/play, 0.6 mi under foot)
  night:   R1 (lincoln park, run/play, 0.4 mi under foot)
Tuesday:
  morning: R6 (neighbors house, sniff walk, 0.4 mi under foot)
  night:   R3 (aaas woods, run/play, 1.2 mi under foot)
Wednesday:
  morning: R9 (martha perry lowe park, sniff walk, 0.8 mi under foot)
  night:   R1 (lincoln park, run/play, 0.4 mi under foot)
Thursday:
  morning: R2 (perry park, run/play, 0.6 mi under foot)
  night:   R5 (community plaza, sniff walk, 0.6 mi under foot)
Friday:
  morning: R8 (union sq, sniff walk, 0.6 mi under foot)
  night:   R1 (lincoln park, run/play, 0.4 mi under foot)
Saturday:
  morning: R2 (perry park, run/play, 0.6 mi under foot)
  night:   R4 (cha park, sniff walk, 0.8 mi under foot)
Sunday:
  morning: R7 (harvard, sniff walk, 1.6 mi under foot)
  night:   R1 (lincoln park, run/play, 0.4 mi under foot)

Summary
=======
objective value:      29.2
mileage under foot:   9.4 miles
unique activities:    9
run/play walks:       8
instances at optimum: 460800
raw search space:     22876792454961 schedules

There are 460,800 different optimal solutions, out of 22,876,792,454,961 possible schedules, so the model highly discriminating within a very large sample space.

The model found a good schedule, but not a perfect one. Once you define the constraints clearly, the model collapses to an intuitive solution: use the parks close to home most often, incorporate nearby sniff walks, and only rarely pick farther-away spots to add variation. There’s still a gap between this model and something I could put into practice, but it’s helpful to see what an alternative schedule that reflects a simplified assumptions looks like.

The optimization didn’t replace human thinking, it just made the tradeoffs explicit.

Resources

Source code available on Github