After solving the challenges of planning her trip and packing her suitcase, Sofia has finally arrived in Paris. Sofia is faced with an exciting, yet overwhelming decision: how to visit the best Paris has to offer in just three days. From the Eiffel Tower to the Musée d'Orsay, and the streets of Montmartre to the banks of the Seine, there’s just too much to do in too little time.

This is where Sofia’s travel planning becomes another optimization problem—specifically, the Orienteering Problem (OP).

What is the Orienteering Problem?

The Orienteering Problem asks: Given a time or distance constraint, how can you maximize the value of the places you visit?

Unlike the Traveling Salesman Problem, where you have to visit every location, the Orienteering Problem allows you to choose a subset of locations based on their value and proximity, while adhering to a time limit.

In Sofia’s case, she needs to select the landmarks that will give her the best experience during her limited time in Paris. While the Eiffel Tower might be a must-see, some lesser-known locations might hold personal value for her, and balancing these preferences with logistical constraints like opening hours and travel distances becomes key.

Extending to the Team Orienteering Problem

However, Sofia is staying in Paris for multiple days—not just one—so we need to extend the problem to account for this. The Team Orienteering Problem (TOP) is an extension of the Orienteering Problem. The standard Orienteering Problem helps solve for one day of sightseeing, where Sofia would choose the best landmarks to visit given the time constraints.

Instead of just planning a single route for one day, Sofia needs to plan multiple routes—one for each day of her 3-day trip. Each day can be thought of as its own "team," with its own time limit and set of landmarks to visit. The goal remains the same: to maximize the total value of the landmarks she visits. But now, she also has to decide how to split the visits across the three days, making sure she uses her time effectively each day while not visiting the same landmark twice.

To handle this complexity, Sofia will model her trip using a Mixed-Integer Linear Program (MILP), which will help her balance her time, travel, and preferences over multiple days.

What is a MILP?

A Mixed-Integer Linear Program (MILP) is a mathematical model used to optimize decisions while respecting a set of constraints. In Sofia’s case, she has to decide whether or not to visit certain landmarks (binary decisions), and for each day, how much time she spends traveling and visiting (continuous decisions). The "mixed" part refers to the fact that some decisions are binary (yes/no), while others involve real numbers (time spent).

Let’s break down Sofia’s decision-making process by explaining how the MILP works in four parts: the data, the decision variables, the objective function, and the constraints.

1. The Data

First, we need to define the data that Sofia uses for decision-making. This includes:

• Landmark Values: Each landmark has a value based on its significance to Sofia. The Eiffel Tower, for example, might have a high value, while a cozy café might have a lower but still meaningful value.

• Minimum Time Spent at Each Landmark: Each landmark requires a minimum amount of time to visit. For example, the Louvre might require several hours, while a bookstore might require only a short visit. Sofia must spend at least this minimum amount of time at every location she chooses to visit.

• Travel Times: The time it takes to move between landmarks, such as 20 minutes from the Eiffel Tower to the Musée d'Orsay.

• Available Time per Day: Each day, Sofia has a set number of hours to explore Paris. For example, she might have 9.5 hours per day, including travel and visits. This leaves her some time in the day for meals and resting.

• Starting Location: Sofia’s hotel near the Louvre is her starting point each day.

Below is a map of Paris highlighting the landmarks Sofia is considering. Each location is marked with its value to Sofia and the estimated time required to visit. This will serve as the foundation for the optimization model.

The base map used in the visuals was adapted from Paris City Vision. The nodes, edges, and all edits were added to illustrate Sofia’s travel itinerary optimization.

2. The Decision Variables

The decision variables represent the choices Sofia needs to make during her trip. For each landmark, she needs to answer:

• Will I visit this landmark?

• If I do, on which day will I visit it—Day 1, Day 2, or Day 3?

These are binary choices—yes or no. For each landmark, Sofia will decide whether to visit it on a particular day or not. The model will use these variables to help Sofia build her itinerary.

3. The Objective Function

Sofia’s goal is to maximize the total value of her trip. The objective function sums up the value of all the landmarks Sofia chooses to visit over the three days.

For example, if Sofia visits high-value landmarks like the Eiffel Tower on Day 1 and the Catacombes on Day 2, the objective function will sum their values. The MILP will ensure that Sofia’s decisions result in the highest possible total value for her 3-day trip.

4. The Constraints

The constraints are the rules that Sofia’s itinerary must follow to be realistic and manageable:

• Daily Time Limits: Each day has a set time limit (e.g., 9.5 hours), which includes the time spent visiting landmarks and the travel time between them. The model ensures that Sofia doesn’t exceed this total time limit on any given day.

• Minimum Time at Each Landmark: For every landmark Sofia chooses to visit, she must spend at least the minimum required time at that location. This ensures that she gets the most out of each visit and doesn’t rush through key experiences.

• Non-Overlapping Visits: Sofia can visit each landmark only once during the entire trip. If she visits the Eiffel Tower on Day 1, she cannot visit it again on Day 2 or 3. This ensures that she maximizes the number of unique landmarks visited.

• Starting and Ending at Her Hotel: Every route begins and ends at Sofia's hotel near the Louvre. The total travel time must include the journey from and back to her hotel.

• Travel Constraints: Sofia can only travel between landmarks she has chosen to visit on a specific day. The time spent traveling must fit within that day’s time limit.

These constraints ensure that Sofia’s itinerary is practical, making the most of her time while avoiding repetitive visits.

Below is an example of Sofia’s potential itinerary, with color-coded routes for each day’s plan.

The base map used in the visuals was adapted from Paris City Vision. The nodes, edges, and all edits were added to illustrate Sofia’s travel itinerary optimization.

Want to Try This Yourself?

If you’re interested in solving optimization problems like Sofia’s itinerary, here are some widely-used solvers and tools specifically for mixed-integer linear programming (MILP) that you can explore:

• Gurobi – A top solver for mixed-integer programming problems. It offers free academic licenses and comprehensive guides on how to solve MILP problems. Check out their MIP overview to get started.

• Google OR-Tools – A free and user-friendly library for solving optimization problems, including MILP. Their guide provides step-by-step instructions on how to implement MILP models.

• PuLP – A Python library that simplifies modeling MILP problems. This guide walks you through setting up a basic MILP model and connecting it to solvers like CBC and Gurobi.

If you’re new to modeling and have questions, feel free to reach out—I’d be happy to discuss ideas or guide you through getting started! And if you're feeling ambitious, try implementing the MILP model provided below using one of the solvers mentioned above.

MILP Model for Sofia's 3-Day Itinerary

Conclusion

With optimization on her side, Sofia turned what could have been a whirlwind tour of Paris into a perfectly paced, memorable itinerary. By strategically choosing her routes and landmarks, she experienced the city her way, making time for both the iconic and the personal.

Optimization wasn’t just about efficiency—it allowed Sofia to fully enjoy her journey, creating space for both structure and spontaneity. Whether it’s solving logistical challenges or planning your dream trip, tools like Gurobi, Google OR-Tools, and PuLP show that smart decision-making can turn complexity into clarity.

Sofia’s journey is far from over. Next, she’ll face an entirely new challenge: planning a trip for her friends, each with their own unique preferences. Will she manage to satisfy everyone? Stay tuned as we dive into the Assignment Problem in the next article.