Optimizing Christmas Lights Driving Routes

2025-12-05 2 min read

Every Christmas my family drives around to see neighborhood light displays. For the 2025 Viera Bright Lights Battle, families registered their decorated homes, and I wanted to have a list we could use for an optimal route to visit them all starting at our home. So I built a system to generate one.

The problem

Given a list of home addresses and a starting point, find the fastest driving order to visit all of them. This is the Traveling Salesman Problem - finding the shortest Hamiltonian path through a set of nodes. It’s NP-hard in the general case, but for the size of this dataset (tens of homes), good approximate solutions are fast enough.

Getting real travel times

Straight-line distance between addresses doesn’t reflect actual driving time (obviously). Roads exist, traffic lights exist, some routes are faster even if they’re longer. I decided to use OSRM - an open-source routing engine - to compute a matrix of real road travel times between every pair of addresses:

script.pyPython
matrix = fetch_duration_matrix(coordinates, osrm_url)

This gives an N×N matrix where matrix[i][j] is the driving time in seconds from address i to address j. OSRM handles the actual routing; I just need the durations.

Solving the TSP

Google OR-Tools has a vehicle routing solver that handles TSP variants well. I set it up to minimize total travel time (not distance), with the starting address fixed as the depot:

script-2.pyPython
manager = pywrapcp.RoutingIndexManager(len(addresses), 1, depot_index)
routing = pywrapcp.RoutingModel(manager)
routing.SetArcCostEvaluatorOfAllVehicles(time_callback_index)

OR-Tools finds a good solution in typically under 30 seconds for typical input sizes. The result is an ordered list of stops.

Output

The final output is a navigation JSON with:

  • Ordered list of stops with addresses and coordinates
  • Total estimated driving time
  • Route geometry (polyline) for map display
  • Turn-by-turn directions fetched from OSRM for each leg

The route geometry renders directly onto a map so drivers can follow along without manually entering each address into navigation.

Result

The generated route cut driving time by 37% compared to visiting homes in submission order. My family used it on Christmas Eve and it worked exactly as expected.

Source Code

You can find the full source code for this project on GitHub: viera-christmas-lights

Back to top