As the title states, I am curious as to whether there is a simple formulation to such a vehicle routing problem in integer programming. To be more precise, the formulation consists of the following variables:
a binary variable $x_i \in \{0,1\}$ for each potential stop $i$ that indicates whether the vehicle will travel past that stop, a revenue $r_i \gt 0$ for each stop $i$, and distance $d_i \geq 0$ from the starting depot, where the starting depot is denoted $0$ and final depot denoted $n+1$ for $n$ such stops.
In particular, the distance between any two chosen stops is strictly greater than $L$ kilometers, and the problem is defined by a route of $M$ kilometers, and that includes the $\textbf{starting and ending depots}$. For clarity, we assume that $d_1<d_2<\dots <d_n$ such that the stops are in order.
Some comments and suggestions are deeply appreciated. I apologize if there already exists such a formulation in a textbook or research article, but I just can't seem to find it.
$\textbf{Addition (since this post was unanswered for 3 days):}$
Over the 3 days, while thinking of such a formulation, I came up with the following formulation and also tried solving it by $\color{red}{branch-and-bound}$ and also by deriving a $\color{red}{dynamic}$ $\color{red}{programming} $ $\color{red}{solution}$ for the possible formulation. The model which I came up with is as follows (adapted from the TSP problem - without including $M$ since logically a constraint that restricts each stop $i$ to be visited at most once means that no matter what, the length of the route will be at most $M$):
$$\begin{equation*} \begin{aligned} & \text{maximize} & & \sum\limits_{i=1}^n r_i x_i\\ & \text{s.t.} & & \sum\limits_{i=1}^n x_i \leq n-1 \hspace{15mm} (\text{since a subset of stops are visited}) \\ &&& d_i - d_j > L \hspace{22mm} \forall i>j, i=1,\dots,n,j=1,\dots,n\\ &&& x_i \in \{0,1\} \hspace{24mm} i=1,\dots,n \end{aligned} \end{equation*}$$
So I thought of experimenting with some values, say
$\mathbf{d}=(d_1,d_2,d_3,d_4,d_5,d_6)=(3,5,10,11,13,15), \textbf{r}=(r_1,r_2,r_3,r_4,r_5,r_6)=(110,80,150,115,200,110), M=25, L=3$
Are any of my formulations correct (do let me know if it is and if there are other possible formulations)? And how should I proceed by branch-and-bound (say using depth-first-search), and also solve it by dynamic programming?
I will outline a problem that I believe is equivalent to the problem that the asker has asked.
We are given $n$ sites sitting on a line. For the sake of concreteness, let's say that they sit on the x-axis with co-ordinates $(d_i, 0)$ for $i=1,2,\ldots n$. We associate with each site $i$ a reward $r_i$. We would like to select a subset of these $n$ sites with maximum total reward such that no two selected sites are within distance $L$ of each other.
We formulate an integer linear program as follows: $$\begin{equation*} \begin{aligned} & \text{maximize} & & \sum\limits_{i=1}^n r_i x_i\\ & \text{subject to} & & x_i \in \{0,1\} \hspace{24mm} i=1,\dots,n \\ &&& x_i + x_j \leq 1 \hspace{22mm} \forall i,j \text{ s.t. } 0 <d_i -d_j \leq L\\ &&& \end{aligned} \end{equation*}$$ This is sufficient to solve the problem.