# How to compute the minimum number of vehicles required

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.

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.