I am trying to solve the following problem:

I have a set of $N$ requests that must be processed by vehicles. I do not know the locations of these requests. Requests can be processed by a same vehicle, and this vehicle can perform multiple trips, subject to capacity and time constraints which I will detail below. Also, the number of requests that are processed together (in one trip) must always be the same (and this number does not have to be an integer). I need to minimize the number of vehicles required to process all requests.

Here is a more formal description of the problem.

  • Let $x$ ($1 \le x\le N$) denote the number of requests that are processed in one trip
  • Let $y_i \in \{0,1\}$ be a binary variable that takes value $1$ if and only if vehicle $i \in V$ is used. $|V|$ is assumed to be large enough.
  • Let $n_i \in \mathbb{N}$ be the number of trips performed by vehicle $i \in V$

The number of used vehicles is minimized: $$ \min \; \sum_{i \in V} y_i $$ subject to:

  • Capacity constraints: each request has a unit demand of $q$, and the total demand in a vehicle must not exceed the vehicles capacity $Q$: $$ qx \le Q $$
  • Time constraints: it takes $(ax+b)$ units of time to perform one trip ($a$ and $b$ are constants), and the total duration (including all trips) must not exceed some constant $T$: $$ n_i (ax+b) \le T y_i \quad \forall i \in V $$
  • All requests must be processed: $$ x \sum_{i \in V} n_i = N $$

For some reason, I think the problem is not well posed, and I am looking for ways to improve it. For starters, it is not linear (and not trivial (?)) to linearize. I could solve it as a real routing problem with random positions of the $N$ points, but I don't think this is a good approach either, as $|N|$ can be very large. I would like to keep it "high level" if possible.

I am hoping that I am missing something obvious. Does the above formulation make sense ? And is there anyway to improve it, or linearize it? Any other approach is welcome.

Thanks for any help !

An example to make things as clear as possible: $N=\{u,v,w\}$, $q=Q=1$, $a=1$, $b=0$, $T=2$. In this case, $x=1$, one vehicle can process $u$ and $v$ in two trips. Another can process $w$ in one trip.

Time constraints have been partially linearized based on @RobPratt's answer.


1 Answer 1


As an approximation, suppose that the number $x$ of requests per trip does need to be an integer. Then $x$ needs to be at most $Q/q$ and divide $N$. For each fixed $$x\in\{1,\dots,\min(N,\lfloor Q/q \rfloor): x \mid N\},$$ minimize $\sum_{i\in V} y_i$ subject to linear constraints \begin{align} (ax+b)n_i &\le T y_i &&\text{for $i\in V$} \\ x \sum_{i\in V} n_i &= N \end{align} Keep whichever $x$ yields the best objective value.

  • $\begingroup$ Thanks Rob, this is very helpful, as always. $\endgroup$
    – Kuifje
    Jul 30, 2021 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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