How to compute the minimum number of vehicles required

Question

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.

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.