0
$\begingroup$

Objective and short problem description

The objective is to load as many passenger vehicles as possible on an auto-train. The train consists of multiple wagons with two levels each. The wagons are connected to each other. Every vehicle has to enter the train from the rear on the upper or the lower level and drive all the way to its assigned position. Once it entered a level it can not be moved to the other level and once it is positioned the following vehicles cant be in front of the vehicle.

The vehicles are parked very close to each other in one (first problem instance) or multiple (second instance) rows. We have to load the first vehicle before we load the second vehicle before we load the third vehicle and so on. If there are multiple rows we can always choose the currently first vehicle of each row.

Multiple constraints limit the capacity of the train. Each wagon is constrained in terms of length. Both levels of a wagon are constrained in terms of weight and height. On the bottom level the entry and exit of the wagons are sloped. Because of that on the first and last position of each wagon the height is more limited than the height on the positions in between.

Modeling approach

I currently model the problem as an assignment problem due to the complex precedence constraints. The train has a number of Wagons and a number of positions $P$ both levels ($W_l$ are sub-sets of platforms that are on the lower (0) and upper level (1)). Each wagon has a maximum of 6 positions on both levels which I model by building multiple subsets $W \in P$. Any of the positions can remain empty.

Weight and length constraints are very easy to implement by summing up lengths & weights of the vehicles $v \in V$ on the positions $p \in W$ over all the wagons. I model the height constraints with the help of auxiliary variables. In case the sum of the lengths of the vehicles on the lower level of a wagon is above a certain threshold, we have to account for the extra height of vehicle on the first position on the lower level of this wagon (which is now standing on a slope). If the sum is above a second threshhold we also have to consider the extra height due to the slope of the last position on the lower level of this wagon.

Question / Problem

I have implemented all of these constraints and they are working fine. I have also successfully implemented the precedence constraints in case there is only a single row of vehicles:

  • For a single row for every vehicle $v$ we build a set of pairs that models the precedence requirements for every vehicle according to the order in the row: v < u: $(v, u) \in A$.

Decision variable $x_{pv}$ is equal to 1, if vehicle $v$ is on position $p$ and 0, otherwise

The two constraints I use that work are:

  1. $\sum\limits_{p\in W_l}px_{pv} \leq \sum\limits_{p\in W_l}px_{pu} + (1-\sum\limits_{p\in W_l}x_{pu})*M\quad \forall (v,u) \in A:W_{l\in 0/1}$
  2. $\sum\limits_{p\in P}x_{pv} \geq \sum\limits_{p\in P}x_{p(v+1)} \quad\forall v \in {0, ..., |V|-1}$

The precedence constraints I want to model are:

  • The train has to be loaded from the back to the front on both levels
  • The vehicles are now parked in multiple rows and I can always only access the currently first vehicle in each row.

For example there are three rows with vehicles: [0, 1, 2] [3, 4, 5] [6, 7, 8] . 0 has to be loaded before 1, 1 before 2, 3 before 4, ...

If I use the above constraints (1) and (2) I can only model the precedences within each single row. However, there is also a precedence that connects the different rows which is that I can always only load the currently first vehicle of each row.

This problem becomes more clear if I show the result for the small example above:

Top level Wagon 1: [0, 4, 6, 5], Wagon 2: [...], ...

Bot level Wagon 1: [1, 2, 7, 3, 8], Wagon 2: [...], ...

Vehicle 4 and 7 can not be loaded because neither 6 nor 3 are loaded. A correct result would be:

Top level: [0, 3, 6, 5], Wagon 2: [...], ...

Bot level: [1, 2, 7, 4, 8], Wagon 2: [...], ...

I am searching for multiple days straight but can not figure out the right way to do it. My guess is that I somehow have to relate the predecessors of the vehicles between the rows.

Improve this question
$\endgroup$
2
  • $\begingroup$ What is $P$ in your second constraint? $\endgroup$
    – prubin ♦
    Jun 13 at 16:01
  • $\begingroup$ Sorry I didn't clarify that. P includes all platforms on upper and lower level. I adjusted some of the constraints a bit to not make the post extra long. $\endgroup$
    – Christian
    Jun 13 at 19:15

2 Answers 2

Reset to default
1
$\begingroup$

The following assumes that the $(v,u)\in A$ precedence requirements have to do with the order cars are in a row and not something else (such as cars before trucks, heavy vehicles before light vehicles or whatever).

I suggest using three sets of binary variables:

  • $x_{w,v} \in \lbrace 0, 1 \rbrace$ (1 if vehicle $v$ is loaded onto wagon $w\in \lbrace 1, \dots, W \rbrace$);
  • $y_{\ell,v}$ (1 if vehicle $v$ is put on level $\ell \in \lbrace 0, 1 \rbrace$, 0 if not); and
  • $z_{n,v}$ (1 if vehicle $v$ is the $n$-th vehicle taken, 0 if not).

Assuming $(v,u)\in A$ signifies that $v$ is parked immediately behind $u$ in the same row (whatever row that may be) and that all cars that are moved are taken (so if 4 is taken then 0 must be taken, not just moved off to the side), you can use the following constraints.

  • Each vehicle is assigned at most one position: $\sum_n z_{n,v} \le 1.$
  • Each position is assigned at most once: $\sum_v z_{n,v}\le 1.$
  • Each vehicle is assigned to exactly one level if taken (and to neither level if not taken): $y_{0,v}+y_{1,v} = \sum_n z_{n,v}.$
  • The position in which a vehicle is taken is greater than the position in which the vehicle in front of it is taken: $\sum_n (N - n)\cdot z_{n,v} \le \sum_n (N - n) \cdot z_{n,u}\ \ \forall (v,u)\in A.$ ($N$ is the total number of vehicles. The somewhat indirect formulation is to allow for the possibility that $u$ is taken but $v$ is not.)
  • If two vehicles $v \neq v'$ are both loaded on the same level $\ell$ in wagons $w$ and $w'$ respectively, with $w < w'$, then $v$ must be taken before $v'$: $\sum_n n\cdot z_{n,v} - \sum_n n \cdot z_{n,v'} \le N(4 - y_{\ell,v} - y_{\ell,v'} - x_{w,v} - x_{w',v'}).$
Improve this answer
$\endgroup$
8
  • $\begingroup$ Thank you for your suggestion Prof. Rubin. It is a good but unfortunately does not completly solve the problem. As I hinted in the original question, the train consists of multiple wagons which have additional constraints (e.g. on weight). Since in your model the positions are not related to the levels, I don't see how I can include this. E.g. every wagon has 6 positions $p \in P$ of which some can remain empty. In my current model I can just build subsets of 6 positions each and sum over the positions in each sub-set to include weight constraints. This is not possible in your model, right? $\endgroup$
    – Christian
    Jun 14 at 12:14
  • $\begingroup$ I guess either $y_{l,v}$ or $z_{n,v}$ might need an extra index for that. I think if we add the index to $y$, we also need to introduce additional precedence rules. If we add it to $z$ then we need more advanced constraints that somehow cover both levels. $\endgroup$
    – Christian
    Jun 14 at 12:33
  • $\begingroup$ You can add an index to $y$ for which wagon the car loads on (so $y_{w,\ell,v}=1$ if car $v$ loads on level $\ell$ of wagon $w.$ With that you can constrain either the number of vehicles or the weight of vehicles on each level of each wagon. As far as which positions are left empty, you can either assume that they are the last positions in the level (so loading four cars on the upper level of wagon 3 means the last two positions of that level are empty) or, if you want to intersperse empty slots among occupied slots, you can do that outside the model. $\endgroup$
    – prubin ♦
    Jun 14 at 15:55
  • $\begingroup$ Thank you. I have tried that. The problem with just adding this index is that the model does not understand the order of the wagons. This means the precedence rules are only followed within the individual wagons but the wagons do not follow any order. Because of that the vehicles of a single row are scattered across multiple wagons. $\endgroup$
    – Christian
    Jun 14 at 17:16
  • $\begingroup$ It sounds as though you are changing the terms of the problem. I saw nothing saying that cars from a particular row need to go in the same wagon. $\endgroup$
    – prubin ♦
    Jun 14 at 18:29
0
$\begingroup$

Suppose vehicles $v$ are currently parked in known matrix parameter $ S_{r,c}$
You can try along with your constrs (1) & (2):

$\sum_{p \in W_l} x_{p,S_{r+1,c}} \le \sum_{p \in W_l}x_{p,S_{r,c}} \quad \forall r \in \{0,1,...r-1 \} \ \ \forall c $: Row $r$ is inner loop

If you define $ x_{p,v}$ over vehicle set $v$ and same are pre-defined for $ S_{r,c}$ there's wont be any issues.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for your comment. If I understand it right, doesn't this only make it so that all the vehicles in the preceding row have priority over the vehicles in the next row? It should be possible that later rows are emptied before earlier rows. If I did not understand it correctly please correct me. $\endgroup$
    – Christian
    Jun 14 at 12:04
  • $\begingroup$ @Christian, so you'd like to have algorithm choose col 1 (from say cols 1,2,3) from say rows 1,2,3. Then choose col 2 & col 3 from rows 3, then col 2, col 3 from row 2, then finally cols from row 1? $\endgroup$
    – Sutanu Majumdar
    Jun 14 at 14:54
  • $\begingroup$ I want to choose any vehicle that is currently accessible. Meaning vehicle 0 in row 1 col 1 has to be loaded before vehicle 1 in row 1 col 1 and vehicle 3 in row 2 col 1 has to be loaded before vehicle 4 in row 2 col 1. The problem lies in the interaction between the rows. See the two examples in the original post. The first one does not work, the second one works since you always have to empty the row from the front and can't access later vehicles. $\endgroup$
    – Christian
    Jun 14 at 17:21

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.