How do I use my PTO? Part 3 - Bundling Trips

In Part 1, we laid out the most basic optimization problem formulation for choosing which trips to take given a large set of trips. An implicit assumption in this problem formulation is that the trips we choose amongst are standalone. We don’t really account for the interaction between two different trips.

For example, let’s say we have two trip options in France we could choose from in our set of options:

Alsace Wine Tasting Tour, November 9 – 12
Cote d’Azure Surf Camp, November 14 – 16

It is entirely plausible to do both. We could fly to Alsace then fly home, just to fly back to France to do the surf camp. Alternatively, we could fly to Alsace then go straight to Cote d’Azure. While we’re going to both options with both approaches, they would have two different cost structures (and of course impact how much PTO we need to spend).

Our original optimization formulation really only would consider the first approach because it doesn’t really know about how two trip itineraries would interact. In this post, let’s investigate how we might update our problem formulation to be able to bundle trips together.

Revisiting the problem statement in plain language

Let’s first set our nomenclature:

An itinerary is a scheduled list of activities at a particular destination. For example, traveling to the Amalfi Coast and hiking from hut to hut for a week is an itinerary.
A trip is an itinerary with a definitive start and end date. One itinerary can lead to many different trip options. For example, hiking the Amalfi Coast between August 9, 2024 – August 16, 2024 is a trip while simply hiking the Amalfi Coast is the itinerary. An assumption that we’ll make explicitly is that we are coming from and going back to our homebase before and after the trip.
A trip bundle is a set of trips where we do not travel back to our homebase between the trips in the bundle but rather travel directly from one trip to the other. Recall the example with the two trip options we posited in the intro of this post.

We still have the problem of choosing which trips to take but with the concept of trip bundling, we have the added problem of choosing whether or not to bundle trips. The question now is how do we change our mathematical formulation from Part 1 to account for bundling.

Revisiting value

In Part 1, I briefly mention that our overall objective is to “maximize value”. I define value, $v$ , as the following:

(1) $\begin{equation*}v = \mathbf{v}^\text{T} \mathbf{x}\end{equation*}$

where $\mathbf{v}$ is a vector of individual values for each trip options and $\mathbf{x}$ is a vector of our decision variables. For instance, in the case of just two trip options, $i$ and $j$ , value is the following after some matrix multiplication:

(2) $\begin{equation*}v = v_i x_i + v_j x_j\end{equation*}$

When we explicitly consider the individual trip value terms, e.g. $v_i$ and $v_j$ , as the standalone values for their respective trips (which we will), Eq. 1 is our total value without bundling.

When we bundle trips $i$ and $j$ , let’s say there is some adjustment to value we need to make. In real world terms, this adjustment could be costs to get from one place to another, etc. We will denote this adjustment as $\delta_{ij}$ . So if we want to account for bunding of trips $i$ and $j$ , our total value becomes the following:

(3) $\begin{equation*}v=v_ix_i + v_jx_j + \delta_{ij}x_ix_j\end{equation*}$

Notice that we only add the adjustment $\delta_{ij}$ is we choose trip $i$ and trip $j$ , i.e. $x_i =1$ and $x_j=1$ .

We’re not quite there yet. With Eq. 3, if we choose to take both trips $i$ and $j$ we also are assuming they are bundled. I want to consider the possibility that we can choose to take both trips but not bundle them. Let’s define a new variable $y_{ij}$ that is $0$ if we decide not to bundle trips $i$ and $j$ but $1$ if we do.

(4) $\begin{equation*}v=v_ix_i + v_jx_j + \delta_{ij}y_{ij}\end{equation*}$

Now, even if we decide to take both trips ( $x_i=1$ and $x_j=1$ ), we can still set $y_{ij}=0$ indicating no bundle. However, if we do bundle ( $y_{ij}=1$ ), then we better have $x_i=1$ and $x_j=1$ also. We’ll have to address this with constraints.

Defining our new decision variables

Before I dive into the additional constraints we need, let’s explicitly define and characterize our new decision variables. We have $N$ trips and thus have $_NC_2$ possible bundles when we only let a bundle have 2 elements. This can be a large number of bundles to consider practically, but since we’re still living in the mathematical world, let’s ignore that for now.

Let $\mathbf{y}$ be a vector of $_NC_2$ elements. Element $ij$ in $\mathbf{y}$ is $1$ if we bundle trips $i$ and $j$ and $0$ if we do not bundle them:

(5) $\begin{equation*}y_{ij} \in \{ 0,1\} \forall i \in \{1,\dots,N\} \text{ and } j \in \{i,\dots,N \}\end{equation*}$

Therefore, we still have all of our decision variables as binary. The optimization problem remains an integer program.

Defining our new constraints

Constraint 1: PTO Day Limit

Since bundling trips together could cause us to spend more PTO days to fill in the gap between the end of one trip and the beginning of another, we need to update our PTO constraint. The original PTO constraint is the following:

(6) $\begin{equation*}\mathbf{w}^T \mathbf{A}\mathbf{x} \leq D_{PTO}\end{equation*}$

where…

$\mathbf{w}$ is a vector of 365 elements, one element for each day of the year. If the $i$ th element corresponds to a holiday or a weekend (or a day where we wouldn’t have to take a PTO day to use), that element’s value in $\mathbf{w}$ is 0, otherwise it is 1
$\mathbf{A}$ is a $365\times N$ matrix, where the element in row $i$ and column $j$ is 1 if trip $j$ occurs during day $i$ , otherwise the element is 0
$D_{PTO}$ is the total number of PTO days we have for the year

I add a new term to Eq. 6 to account for additional PTO takes taken when bundling:

(7) $\begin{equation*}\mathbf{w}^T \left( \mathbf{A}\mathbf{x} + \mathbf{\hat{A}}\mathbf{y} \right) \leq D_{PTO}\end{equation*}$

where $\mathbf{\hat{A}}$ is a $365\times (_NC_2)$ matrix in which the element in row $k$ and column $h$ is $1$ if the bundle in column $h$ requires day $k$ to be taking as PTO. Note that this would be an additional day off beyond what is already being captured by the trips in the bundle themselves.

Constraint 2: Only 1 Trip at a Time

We can’t be in two places at the same time. We need to adapt our original constraint that prevents this with our bundles. In the original constraint, I reuse $\mathbf{A}$ and define $\mathbf{1}_{365}$ as a vector of 365 elements, all of which are $1$ :

(8) $\begin{equation*}\mathbf{A} \mathbf{x} \leq \mathbf{1}_{365}\end{equation*}$

where the righthand side computes the number of trips chosen for a given day.

To update this constraint, we just concatenate $\mathbf{\hat{A}}$ and $\mathbf{A}$ as well as $\mathbf{x}$ and $\mathbf{y}$ to yield the following:

(9) $\begin{equation*}\left[ \mathbf{A} \quad \mathbf{\hat{A}} \right] \left[\mathbf{x}^\text{T} \quad \mathbf{y}^\text{T} \right]^\text{T} \leq \mathbf{1}_{365}\end{equation*}$

That’s it. This constraint keeps us from choosing two trips that would occur on the same day or choosing two different bundles that would occur on the same day.

Constraint 3: No Repeats

We don’t have to do anything to the third set of constraints I discuss in Part 1. Since these constraints prevent us from choosing two trips that have the same itinerary, it also prevents us from choosing bundles that have the same itineraries with no change.

Constraint 4: Bundle Rationality

Finally, a completely new set of constraints. If we choose to bundle trips $i$ and $j$ , then we also have to choose to take trips $i$ and $j$ . We can use the elemental constraint below:

(10) $\begin{equation*}y_{ij} - x_ix_j \leq 0 \forall i \in \{1,\dots,N\} \text{ and } j \in \{i,\dots,N \}\end{equation*}$

In this constraint, if we have $y_{ij}=1$ but either $x_i=0$ or $x_j=0$ (or both), then the constraint is violated.

This constraint changes our optimization problem a lot. We no longer have a linear problem since we are multiplying two decision variables together ( $x_i$ and $x_j$ ). This change will impact how we solve our optimization problem later.

Constructing our new decision problem

Our new decision problem objective is the following:

(11) $\begin{equation*}\underset{\mathbf{x}, \mathbf{y}}{\text{maximize}} \: \mathbf{v}^\text{T} \mathbf{x} + \mathbf{\delta}^\text{T} \mathbf{y}\end{equation*}$

which reflects that we want to choose trips and how to bundle them such that we maximize our value (still a very nebulous concept). However, we are beholden to the constraints in Eqs. 7, 9, and 10 as well as the no repeat constraint that I mention but skip repeating in this post.

Closing remarks

Our optimization problem expanded a lot with the introduction of a new set of decision variables. Not only do we have more constraints and variable to worry about, we also have nonlinearity due to the constraints in Eq. 10. This nonlinearity impacts how we can solve our new problem. The code that I wrote in Part 2 to solve our original problem formulation in Part 1 is no longer suitable. I’ll have to address this with exploring a different optimization algorithm.

Additionally, we can’t forget that we have the ever-looming issue of populating our optimizer with data. Scraping trip information from the internet is relatively straightforward, but defining trip value is the most thought intensive. Value can be defined differently for different people. We’ll have to dive more into this in the future.

How do I use my PTO? Part 3 – Bundling Trips