3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Are you assuming that vehicles always deliver their passengers and return to their starting points within one time unit? $\endgroup$
    – prubin
    Jan 31 at 16:43
  • $\begingroup$ @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? $\endgroup$
    – A.Omidi
    Feb 1 at 7:34
  • $\begingroup$ @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$. $\endgroup$
    – Corey
    Feb 1 at 11:40
  • $\begingroup$ Thank you @A.Omidi $\endgroup$
    – Corey
    Feb 1 at 11:40

2 Answers 2

3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Corey
    Feb 3 at 10:30
  • $\begingroup$ Correct on both counts. $\endgroup$
    – prubin
    Feb 3 at 16:29
  • $\begingroup$ 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? $\endgroup$
    – Corey
    Mar 2 at 14:32
  • $\begingroup$ 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.$ $\endgroup$
    – prubin
    Mar 2 at 16:53
3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Your last constraint counts passengers on the left and vehicles on the right, which does not make sense to me. $\endgroup$
    – prubin
    Jan 31 at 16:41
  • $\begingroup$ Thanks, corrected it. $\endgroup$ Jan 31 at 16:51
  • $\begingroup$ Okay, but now you are have a fixed $i$ on the left and a sum over $i$ on the right. $\endgroup$
    – prubin
    Jan 31 at 21:11
  • $\begingroup$ Thank you @Sutanu. Can you please help me understand your solution? I have difficulty understanding the 1st constraint $\endgroup$
    – Corey
    Feb 1 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.