3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You don't seem to have actually stated the actual problem in sufficient detail to determine what a correct formulation might be. Given the zillions of variations of VRP out there, simply calling it "VRP without time and cost constraints, whose objective is to maximize revenue" is not enough information to provide any useful answer. $\endgroup$ – mhum Nov 1 '17 at 23:54
  • $\begingroup$ @mhum I apologize for the lack of precision, but I realized I've made some errors in my formulation above. I have made some edits to narrow down the scope as well. $\endgroup$ – Stoner Nov 2 '17 at 9:15
  • $\begingroup$ I still don't think this description is sufficient. You still have not stated what the problem actually is; a formulation is how you would solve a problem. Furthermore, even in the given formulation(s), there are strange things like the fact that you have not specified any intra-stop distances, only distances between stops and the depot. Is this problem one-dimensional (i.e.: do all the stops lie on a line)? $\endgroup$ – mhum Nov 2 '17 at 16:54
  • $\begingroup$ @mhum in my perspective, the intra-stop distances will be the differences between any $2$ stops, given by $d_i−d_j(>0)$ for $i≠j,i>j$. In particular, I've stated that in the question, and also in the second constraint. As for the next point you have raised, yes, the problem is one-dimensional as the goal is to find a path or route (which is essentially a line) that generates the greatest revenue. Note that only a subset of stops can be visited - for e.g. stops $1,3,5$ (since $L=3$ implies that the distance between any $2$ stops $d_i−d_j$ must be strictly greater than $3$). $\endgroup$ – Stoner Nov 2 '17 at 19:51
  • 1
    $\begingroup$ @hongsy If you are speaking about the objective value, then no. Note that the revenues $r_i$ are each way larger than 42, and that each $x_i \in \{0,1 \}$. $\endgroup$ – Stoner Nov 7 '17 at 17:36
2
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your formulation! The constraint $x_i +x_j \leq 1$ is just what I needed! :) It all makes sense now. Just a question though - shouldn't we include also the constraint $\sum\limits_{i=1}^n x_i \leq n-1$ to ensure that a subset of stops will be visited instead of all $n$ stops? $\endgroup$ – Stoner Nov 7 '17 at 18:50
  • $\begingroup$ Sure, you can add that constraint if you want. I didn't see where in the problem statement that you are prohibited from visiting all sites. $\endgroup$ – mhum Nov 7 '17 at 20:42
  • $\begingroup$ Thank you for the clarification. Since no one else gave an answer, I'll grant you the bounty then. :) $\endgroup$ – Stoner Nov 7 '17 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.