# Vehicle passenger assignment with capacity constraint

## Problem Summary

To match passengers (the number of passengers) to capacitated vehicles such that the profit is increased. All the vehicles have the same capacity $$c$$. It is not important to track which passenger is matched to which vehicle.

## Problem Background

I'm trying to find a solution to the following passenger matching problem:

The network is represented by graph $$G=(V,E)$$. $$V$$ is the set of nodes/stations. $$p_{ij}$$ is the profit of traveling through an edge $$(i,j)$$. Let $$N$$ be the number of vehicles, all the vehicles have the same capacity $$c$$.

At each (discreet) time step, the passengers arrive at their origin station and need to be transported to their destination station. $$d^t_{ij}$$ is the demand. $$f^t_{ij} \le d^t_{ij}$$ is the passenger flow, i.e., the number of passengers that are traveling from $$i$$ to $$j$$ at time $$t$$ and are successfully matched to a vehicle. The unmatched passers will leave the system. $$X^t_i$$ is the total number of available vehicles at station $$i$$ at time $$t$$.

### Objective

The objective is to maximize profit.

Problem formulation for single occupancy vehicle

I read a few resources and found the following formulation. However, this formulation assumes that the vehicles are single occupancy.

$$max \sum_{i,j \in V} f^t_{ij}p^t_{ij}$$ $$0 \le f^t_{ij} \le d^t_{ij} \quad i,j \in V \quad (1)$$ $$\sum_{j\in V} f^t_{ij} \le X^t_i \quad i \in V \quad \quad (2)$$

The constraint $$(1)$$ ensures that the passenger flow doesn't exceed the demand and is non-negative.

The constraint $$(2)$$ ensures that the number of vehicles doesn't exceed the number of available vehicles $$X^t_i$$ at time $$t$$ at station $$i$$.

As long as the demand is integral, this formulation results in integral passenger flow.

## Question

I'd like to extend the above single occupancy formulation to multi-passenger vehicles. I explored some resources online but the methods focused on individual vehicles instead of stations and were using ILP.

# Update

I modified the problem formulation to set an upper bound to the vehicle count.

$$max \sum_{i,j \in V} f_{ij}p_{ij}$$ $$0 \le c.x_{i,j} \le d_{ij}+c \quad i,j \in V \quad (1)$$ $$\sum_{j \in V} x_{ij} \le X_i \quad \forall i \in V \quad \quad (2)$$ $$f_{i,j} \le c.x_{ij} \quad \forall i,j \in V \quad \quad (3)$$

• Are you assuming that vehicles always deliver their passengers and return to their starting points within one time unit?
– prubin
Jan 31 at 16:43
• @Corey, The problem sounds like 1) The multi-vehicle pickup and delivery problem or 2) The Multiple Vehicle DIAL-A-RIDE Problem. Do you search for those? Feb 1 at 7:34
• @prubin yes, I haven't thought about it but I think for simplicity we can assume that we are solving the problem only once, i.e., removing the $t$. Feb 1 at 11:40
• Thank you @A.Omidi Feb 1 at 11:40

If, per a comment, we ignore questions of how time periods link together, whether vehicles return to their starting points etc., and if we assume that a vehicle makes at most one trip per time period (stopping at a single destination), then to allow up to $$c$$ passengers per vehicle you can introduce nonnegative integer variables $$x_{ij}^t$$ representing the number of vehicle trips from $$i$$ to $$j$$ at time $$t$$ and replace (2) with $$\sum_{j\in V} x_{ij}^t \le X_i^t\quad \forall i\in V,\,\forall t$$ and $$f_{ij}^t \le c\cdot x_{ij}^t\quad \forall i,j\in V,\,\forall t.$$

• Thank you so much @prubin. To make sure I have understood you correctly, $x^t_{ij}$ is a decision variable and we don't need to include it in the objective function right? Feb 3 at 10:30
• Correct on both counts.
– prubin
Feb 3 at 16:29
• Dear Prubin, the formulation was working fine, however, it was assigning a random vehicle count. For example, it matched 1 passenger for trip i,j however it selected 14 vehicles for this trip. So, I modified the constraint (1) i.e, $0 \le f^t_{ij} \le d^t_{ij} \quad i,j \in V$ with $0 \le c.x_{i,j} \le d_{ij}+c \quad i,j \in V$. Now, it seems it calculats correctly. I showed this update in my question post. Can you please let me know what do you think and whether there is a better way to do this? Mar 2 at 14:32
• Assuming that there is no need for vehicles to "deadhead" (meaning the $x$ variables only count vehicles carrying passengers), I would just add a constraint $x_{i,j}^t \le f_{i,j}^t.$
– prubin
Mar 2 at 16:53

Say you have total $$V=\sum_i X_{i}$$ vehicles so if $$z_{v,i}^t$$ represents number of passengers vehicle $$z_v$$ carries from node $$i$$ at time $$t$$.
Define vars $$z_{v,i }^t$$ over Set S = {1,2...V}, time $$T$$ and nodes $$i$$
$$\sum_j f_{i,j}^t \le c\sum_v z_{v,i}^t \le \sum_j d_{i,j}^t$$
$$\sum_j f_{i,j}^t \le cX_{i}^t$$
You can you replace $$f_{i,j}^t$$ with $$z_{v,i,j}^t$$ if you want
• Okay, but now you are have a fixed $i$ on the left and a sum over $i$ on the right.