Vehicle passenger assignment with capacity constraint

Question

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)$$

Answer 1

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.$$

Answer 2

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$
Additional constraints
$\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$
Or
You can you replace $f_{i,j}^t$ with $z_{v,i,j}^t$ if you want