Vehicle Route assignment with capacity constraint

Question

Problem Background

I'm trying to find a solution/model to the following problem:

Let's consider a cellular network (mobile network, ie., hexagonal cells) denoted $N$ composed of $|N|$ cells. Each cell $i \in N$ has a resources capacity $R_i$.

Let $D_{i,j}$ denote the distance between the centers of two adjacent cells $i \in N$ and $j \in N$.

Also, let $V$ be a set of vehicles composed of $|V|$ vehicles. Each vehicle $v \in V$ has a resources demand $r_v$. Furthermore, at the beginning, each vehicle $v \in V$ is located in a starting cell $S_v \in N$ and has a mission to complete, i.e., traveling to a destination cell $D_v \in N$ via some intermediate cells.

The mission of the vehicle $v \in V$ must start at a predefined time denoted $T^v_S$ and must end no later than the mission complete time denoted $T^v_E$.

When a vehicle $v \in V$ passes through a cell $i \in N$, $r_v$ resources will be reserved from the $R_i$ resources of that cell.

When a vehicle $v \in V$ leaves a cell $i \in N$, the $r_v$ resources will be released.

Assumptions

• We assume that the vehicles travel between the centers of the adjacent cells.
• We assume that at the beginning, the vehicles are located in cells with sufficient resources.
• We assume that each vehicle has a maximum speed of $S^v_{max}$

Objective

The objective is to find the shortest path from the cell $S_v$ to the cell $D_v$ for all the vehicles while respecting the time and resources constraints.

Question

I was exploring some vehicles routing LP models and Dynamic flow network, but none of them seems to be suitable for my problem. If anyone can help me with some related problems, models, techniques or hints to solve this problem I would be very gratefull.

Answer 1

I assume that the variables $D_{i, j}, T^v_E, S^v_{max} \in \mathbb{R}_{>0}$. Here are my pointers for modeling this problem in discrete time steps,

Define a binary variable $y_{vi} (t) \in \{0, 1\}$: Vehicle $v$ is in space $i$ at time $t$. Then, the resource constraint can be expressed as $\sum_{v \in V} y_{vi} (t) \leq R_i, \, \forall i \in N, \forall t \geq 0$. The time constraint can be expressed as,

$$y_{v i} (t = T^v_E) = \begin{cases} 1 &\quad\text{if } i = D_v\\ 0 &\quad\text{otherwise.} \\ \end{cases}$$

Define $Y(t) = [y_{v i} (t)]_{v \in V, i \in N} \in \{0, 1\}^{|V|\times |N|}$ and $T = \max_{v\in V} T^v_E$. Since the maximum speed is fixed, the problem can be modeled as distance minimization. In this case, the objective function is, $$\min_{Y} \sum_{t=2}^T \sum_{v=1}^V \left(D_{\arg_{i}(y_{v i} (t-1) == 1), \arg_{j}(y_{v j} (t) == 1)} \right)$$

If you assume discrete time formulation, then we can use these definitions for a solution. We further need to add constraints on the reachable nodes in each time step for every vehicle.

The question needs more structure about the types of variables, specifically the space in which they live. For example, is the time discrete or continuous? Is $D_{i, j}$ defined only on neighboring nodes in $N$? Can this be represented as a graph? If it is defined for all nodes, what is the meaning of vehicle path intersecting another node space.