1
$\begingroup$

I am dealing with a multi-travelling passenger problem.

  • $x_{i,j}$ is a binary variable that allocate a passenger $i$ to a vehicle $j$, every vehicle can carry only $n_{pv}$ passenger where $i \in \{1,2,\dots,n\}$ and $j \in \{1,2,\cdots,n_v\}$, $(n_v = n/n_{pv})$

where $n$ is the number of passengers, $n_v$ is the number of vehicles and $n_{pv}$ is the number of passenger per vehicle.

The mathematical model to allocate each passenger to a vehicle to minimize the total cost. The decision variable is $x_{i,j}$ where \begin{align}x_{i,j}=\begin{cases} 1 &&\text{if passenger $i$ is allocated to vehicle $j$}\\0 &&\text{otherwise.}\end{cases}\end{align}

The objective is \begin{align}\min&\quad\sum_i \sum_j c_{i,j}\cdot x_{i,j} &&\text{$c_{i,j}$ is the cost of travelling passenger $i$ by vehicle $j$}\\\text{s.t.}&\quad\sum_j x_{i,j}= 1 &&\text{for each $i$}\\&\quad\sum_i x_{i,j} = n_{pv} &&\text{for each $j$}.\end{align}

The passengers are allocated by the order of $i$; i.e. $i = 1$ will be allocated before $i = 2$ and so on.

I want to formulate a decision variable indicating the order of passengers in each vehicle denoted by $y_i$; i.e. $y_i = 1$ if he is the first passenger assigned to his vehicle, $y_i = 2$ if he is the second assigned to his vehicle and so on.

For example if we have $n = 9$ passengers and $n_{pv} = 3$, if the values of the decision variables were \begin{align} x_{1,1} = 1, &&x_{1,2} = 0, &&x_{1,3} = 0 \\ x_{2,1} = 1, &&x_{2,2} = 0, &&x_{2,3} = 0 \\ x_{3,1} = 0, &&x_{3,2} = 1, &&x_{3,3} = 0 \\ x_{4,1} = 0, &&x_{4,2} = 0, &&x_{4,3} = 1 \\ x_{5,1} = 1, &&x_{5,2} = 0, &&x_{5,3} = 0 \\ x_{6,1} = 0, &&x_{6,2} = 0, &&x_{6,3} = 1 \\ x_{7,1} = 0, &&x_{7,2} = 1, &&x_{7,3} = 0 \\ x_{8,1} = 0, &&x_{8,2} = 0, &&x_{8,3} = 1 \\ x_{9,1} = 0, &&x_{9,2} = 1, &&x_{9,3} = 0 \end{align} then the values of $y_i$s will be \begin{align} y_1 &= 1\\ y_2 &= 2\\ y_3 &= 1\\ y_4 &= 1\\ y_5 &= 3\\ y_6 &= 2\\ y_7 &= 2\\ y_8 &= 3\\ y_9 &= 3. \end{align}

How can I derive the values of $y_i$s through linear equations? I have a previous generous answer for another model, I used the same concept to derive the vehicle number for each passenger $v_i$ using \begin{align}\sum_j j\cdot x_{i,j} = v_i\quad\forall i\end{align} where $v_i \in \{1,2,\dots,n_v\}$ but I don't know if that is the right way to derive $y_i$ or not.

I appreciate your help.

$\endgroup$
2
  • $\begingroup$ Dr @RobPratt, I appreciate always your answers to my question .. and the generous answer I talked in my post was yours of course, ... I can link $v$ to $x$ .. but I can't find a way to link $y$ to $v$ or link $y$ to $x$ directly .. I really appreciate your help $\endgroup$
    – OR Junior
    May 8, 2020 at 21:37
  • $\begingroup$ Sorry that I misunderstood at first. I have now posted an answer. $\endgroup$
    – RobPratt
    May 8, 2020 at 22:19

1 Answer 1

3
$\begingroup$

You want to enforce $x_{i,j}=1 \implies y_i=\sum_{k \le i} x_{k,j}$. One way to do that is as follows: $$-\min(n_{pv},i)(1-x_{i,j}) \le y_i - \sum_{k \le i} x_{k,j} \le \min(n_{pv},i)(1-x_{i,j})$$ for all $i$ and $j$. Here, we have used big-M values based on $0 \le y_i \le \min(n_{pv},i)$ and $0 \le \sum_{k \le i} x_{k,j}\le \min(n_{pv},i)$.

$\endgroup$
2
  • $\begingroup$ Dr @RobPratt ... WoW .. I really appreciate your help, Dr .. could you suggest me a good book to study this art of mathematical modelling .. I really want to thank you again.. Thank you for your help and time $\endgroup$
    – OR Junior
    May 8, 2020 at 22:42
  • 2
    $\begingroup$ H. Paul Williams, Model Building in Mathematical Programming $\endgroup$
    – RobPratt
    May 8, 2020 at 23:13

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.