1
$\begingroup$

I have cars and persons and I want each persons to be in a car. Moreover, each person has a number of persons they can share a car with.

I have implemented a model (with binary variables and constant objective) which works well for small instances. However for larger ones the solver takes ages and I have to interupt it.

What would be a good approach to takle this issue (I'm thinking branch-and-bound, metaheuristics, etc. But I don't really have a clear idea).

$\endgroup$
6
  • $\begingroup$ Is $M_i$ the maximum number of persons with whom $i$ can share a car (as opposed to minimum or exact number), and does it include $i$ or not (i.e., if $M_i=3$ is that $i$ and two others or $i$ and three others)? Also, do cars have capacity limits separate from $M_i$? $\endgroup$
    – prubin
    Mar 15, 2023 at 15:43
  • $\begingroup$ Are the $n$ cars identical? $\endgroup$
    – RobPratt
    Mar 15, 2023 at 15:55
  • $\begingroup$ @RobPratt Yes the cars are identical $\endgroup$
    – Meth
    Mar 15, 2023 at 17:22
  • $\begingroup$ Column generation might work well here. Are you able to share data for a larger instance? $\endgroup$
    – RobPratt
    Mar 15, 2023 at 17:27
  • 1
    $\begingroup$ @Meth what's the objective here? If it's to accommodate all m passengers & if n cars are identical then heuristic involving sorting will do the job. $\endgroup$ Mar 15, 2023 at 18:12

2 Answers 2

2
$\begingroup$

The following solves quickly with at least one commercial solver. Let binary decision variable $x_{ij}$ indicate whether person $i$ rides in car $j$. The constraints are: \begin{align} \sum_j x_{ij} &= 1 &&\text{for all $i$} \tag1\label1 \\ \sum_{k\not= i} x_{kj} + (m - 1 - M_i) x_{ij} &\le m - 1 &&\text{for all $i$ and $j$} \tag2\label2 \end{align} Constraint \eqref{1} assigns each person to exactly one car. Constraint \eqref{2} enforces the logical implication $$x_{ij} = 1 \implies \sum_{k\not= i} x_{kj} \le M_i,$$ which you could instead enforce via an indicator constraint.

An interesting variant would be to minimize the number of cars used. In that case, introduce a binary variable $y_j$ to indicate whether car $j$ is used, change the RHS of \eqref{2} to $(m-1)y_j$, and minimize $\sum_j y_j$.

This formulation lends itself to column generation with a set partitioning master problem, and Ryan-Foster branching can perform well. That approach is automated in SAS if you specify to use the Dantzig-Wolfe decomposition algorithm with METHOD=SET or explicitly identify the block structure via the .BLOCK constraint suffix. If you are using a different solver, you can try implementing column generation yourself. The corresponding formulation has a binary decision variable $z_S$ for each feasible subset $S$ of (at most $4$) people. The constraints are then: \begin{align} \sum_{S: i \in S} z_S &= 1 && \text{for all $i$} \tag3\label3 \\ \sum_{S} z_S &\le n \tag4\label4 \end{align} Constraint \eqref{3} assigns each person to exactly one car. Constraint \eqref{4} enforces using at most $n$ cars. For static column generation, you would generate all feasible $S$ a priori and solve one MILP. For dynamic column generation, you would need to iterate between a master LP problem and a MILP subproblem.

$\endgroup$
1
  • $\begingroup$ Are you minimizing the number of cars used or just trying to find a feasible solution? $\endgroup$
    – RobPratt
    Mar 15, 2023 at 18:59
1
$\begingroup$

You can try the following algorithm:

  1. Sort passengers in descending order of number of co-passengers, $M_i$.Output sets $S_4 = \{i\in P: M_i \gt 3\}$. Similarly sets $ S_3, S_2, S_1, S_0$. P is set of $m$ passengers\
  2. Loop through each of the sets in the cardinal number $ 4,3,2,1$ like
    initialize $ C_1 = 0$
    $ C_{n} = C_{n} + i: i \in S_{k+1|k\lt 4} \land m_i \lt C_{j} $
    $C_{n} = k \quad \forall n \le {\vert S_k\vert\over k}$
    You can allocate/track individual allocation as well
    $ C_{n}= \{i: i \in S_k\}: C_n \lt k \quad \forall n \le {\vert S_k\vert\over k}$
    $ C_{n+1} = {\vert S_{k} \vert \mod k} $
    $\forall n \in$ cars:
    $ \forall k \in \{4,3,2,1,0\}$ (Nested loop, $n$ is the inner loop)

$ C_j =$ number of passengers in car $ j$

$\endgroup$
1
  • $\begingroup$ Basically you collect members who say are ok to travel in group of 4, in a set $S_4$. Suppose its 7 people. So you would need 1 car (4)+1car(3). Allocate 4 people to first car, then 3 to next car. Then move to next set $S_3$. If $S_4$ has 9 people, you'd need 2 cars and 1 car to get 9th passenger from $S_4$ and then 2 more to same car from $S_3$. Since cars are identical and different solutions as only constraint is how many co-passengers each passenger is ok with, you may not need a solver. $\endgroup$ Mar 16, 2023 at 17:42

Your Answer

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

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