MIP constraints with chronological ordering

Question

I am using a MIP formulation to decide which dates and locations (i.e. stops) should be chosen for a route that maximizes the total revenue over all chosen stops. My decision variable $X$ is the permutation of all possible locations $L$ and all possible dates $T$, where $X[l,t]$ represents the binary choice of a location $l \in L$ and date $t \in T$.

I have a revenue matrix $R$, where $R[l,t]$ represents the revenue estimate for a given location-date pair. I also have a distance matrix $D_l$ which gives the distance between any two locations, as well as a time distance matrix $D_t$ which gives the number of days between any two dates. I am also operating with the constraints:

• The route has at most $N$ stops: $\sum X[l, t] \leq N$
• Each date may be chosen at most once: $\sum_{l \in L} X[l, t] \leq 1 \space \forall \space t \in T$
• Each location may be chosen once: $\sum_{t \in T} X[l, t] \leq 1 \space \forall \space l \in L$

A requirement of the problem is that each stop on the route has to be within $d$ miles of the previous stop, and between $t_1$ and $t_2$ days of the previous stop. For example, this could mean that any two stops on the route must be within 250 miles of each other and between 5 and 7 days apart from each other.

My first attempt was to find the set of "invalid" choices for each choice in my decision variable. This means for each choice $X[l,t]$, I found the set of other choices $Y$ that satisfy the conditions:

• $D_l[l, l'] > d \space \forall \space l' \in L$
• $D_t[t, t'] < t_1 \space \forall \space t' \in T$
• $D_t[t, t'] > t_2 \space \forall \space t' \in T$

Then, when building the constraints, requiring $\sum Y \le 1 - X[l, t]$ for each location date pair in my decision variable. Efficiency of this approach aside, it doesn't work as it is naive to any ordering of stops on the route and ultimately restricts my solution space down to a single valid location date pair.

I also attempted the "inverse" formulation, where for each choice I found all "valid" choices (essentially flipping the equalities of the previous conditions), $Y'$, and building the constraints $\sum Y \ge X[l,t]$. This also doesn't work as it is just not restrictive enough to prevent invalid routes.

I'm at an impasse at this point and could use help from the community on my formulation of these constraints. I believe that if I could encode the ordering of stops into the constraints, i.e. that the distance and time conditions only apply to the next stop on my route and not all stops, I would have a working solution.

Any and all help is much appreciated!

Answer 1

I recommend a network-based formulation in a directed acyclic network with a node for each location-date pair $(l,t)$ and an arc from $(l,t)$ to $(l',t')$ if $t < t'$ and the time and distance restrictions are satisfied. Also introduce a source node $(l_S,t_S)$ and a sink node $(l_T,t_T)$ to represent the start and end of the route, respectively. Let binary decision variable $x_{l,t,l',t'}$ indicate whether arc $(l,t,l',t')\in A$ is traversed. The problem is to maximize the total revenue $$\sum_{(l,t,l',t')\in A} R[l',t'] x_{l,t,l',t'}$$ subject to \begin{align} \sum_{(l,t,l',t')\in A} x_{l,t,l',t'} - \sum_{(l',t',l,t)\in A} x_{l',t',l,t} &= \begin{cases} 1 & \text{if $(l,t)=(l_S,t_S)$} \\ -1 & \text{if $(l,t)=(l_T,t_T)$} \\ 0 & \text{otherwise} \end{cases} &\text{for all nodes $(l,t)$} \tag1\label1\\ \sum_{(l,t,l',t')\in A} x_{l,t,l',t'} &\le N+1 \tag2\label2\\ \sum_{(l,t,l',t')\in A} x_{l,t,l',t'} &\le 1 &&\text{for all $t'$} \tag3\label3\\ \sum_{(l,t,l',t')\in A} x_{l,t,l',t'} &\le 1 &&\text{for all $l'$} \tag4\label4\\ \end{align} Constraint \eqref{1} yields a path from source to sink. Constraint \eqref{2} enforces at most $N$ stops. Constraint \eqref{3} chooses each date at most once. Constraint \eqref{4} chooses each location at most once.

See the following blog post of mine for a very similar problem and the resulting network-based formulation: https://blogs.sas.com/content/operations/2015/04/03/the-traveling-baseball-fan-problem/

Answer 2

You may need to define a set of binary variables $y_{l,l'}$ for arcs/routes from $l$ to $l'$ in a set $E$ and say $T$ is set of dates in chronological order.
Also define a constant $\tau_{t,t'} : t'= T_t +1$ where $\tau_{t,t'} = 1: t+5 \le t' \le t+7 $, else $0$ with additional constraints like

$ y_{l,l'}=0 \quad \forall (l,l'): D_{l,l'} \gt 250$

$ x_{l,t}+ x_{l',t'} \le \tau_{t,t'}y_{l,l'}+1 : \ \ t' = T_t +1 \ \ \forall t$

The edge/arc variable $y_{l,l'} $ will provide the constraint on visiting 2 stops within the given time frame.

If there are dates when there's possibility no location is visited then define $ \tau_{t,t'}= 1$ for all $ (t,t')$ pairs of $T$ as a parameter in $ t\times t$ matrix Then the 2nd set of constraints can be modified as

$x_{l,t}+ x_{l',t'} \le \tau_{t,t'}y_{l,l'}+1 + \sum_{m \in V - \{l,l' \}}x_{m,t''} \ \ \forall (l,l') \in V \ \ \forall t \lt t'' \lt t'$

Answer 3

As is often the case, @RobPratt's answer is probably the best way to approach this, but if you don't like the edge-based formulation and insist on the same $x_{\ell t}$ variables you started with, I think the following formulation will work:

In addition to the $x_{\ell t}\in\{0,1\}$ variables, you also introduce $y_{\ell t}\in\{0,1\}$ and $z_{\ell t}\in\{0,1\}$, which are variables that indicate if $(\ell,t)$ is the start or end of your schedule respectively. Naturally you'll have $$\sum_{\ell,t}y_{\ell t}=\sum_{\ell,t}z_{\ell t}=1~.$$Next, the role that $D_\ell$ and $D_t$ serve is that for each $(\ell,t)$, you have a set of "successors" $S(\ell,t)$ and "predecessors" $P(\ell,t)$. A successor of $\ell,t$ is an assignment $(\ell',t')$ such that $(\ell,t)\to(\ell',t')$ is a valid consecutive pair, and a predecessor has $(\ell',t')\to(\ell,t)$ as a valid consecutive pair. You have a constraint that says that if you're using $(\ell,t)$, then either you're using a successor of $(\ell,t)$, or that's the end of your schedule, which you can do with these constraints: $$x_{\ell t} \leq z_{\ell,t} + \sum_{(\ell',t')\in S(\ell,t)}x_{\ell't'}~\forall(\ell,t)$$ $$z_{\ell,t}+x_{\ell't'}\leq 1~\forall(\ell,t),\forall(\ell',t')\in S(\ell,t)$$ The second of those two constraints says that you can't use any successors of $(\ell,t)$ if it's designated as the end of the schedule. You do the same thing for predecessors:$$x_{\ell t} \leq y_{\ell,t} + \sum_{(\ell',t')\in P(\ell,t)}x_{\ell't'}~\forall(\ell,t)$$ $$y_{\ell,t}+x_{\ell't'}\leq 1~\forall(\ell,t),\forall(\ell',t')\in P(\ell,t)$$

The other role that $D_\ell$ and $D_t$ serve is that they give "forbidden pairs", i.e. there exist pairs of assignments $(\ell,t)$ and $(\ell',t')$ that are mutually incompatible and cannot possibly coexist on the schedule together (e.g. $|t-t'|\leq t_{min}$, which you called $t_1$ in your post). Let $F(\ell,t)$ be the set of all assignments $(\ell',t')$ that are forbidden as a result of using $(\ell,t)$, so you'd write a constraint that $$x_{\ell t} + x_{\ell' t'} \leq 1~\forall (\ell,t),\forall(\ell',t')\in F(\ell,t)~.$$

I think that covers it, in addition to the constraints you already have that $$\sum_{\ell,t} x_{\ell t} \leq N$$ $$\sum_\ell x_{\ell t} \leq 1 ~\forall t$$ $$\sum_t x_{\ell t} \leq 1 ~\forall \ell~.$$