Crossposted at Operations Research SE
The objective is to load as many passenger vehicles as possible on an auto-train. The train has two levels and both are constrained in terms of length (sum of length of vehicles <= available length).
I currently model the problem as an assignment problem due to the complex precedence constraints. So the train has a certain number of slots on both levels. Due to additional weight constraints for each wagon, some of these platforms can remain empty. $p \in W_{1}$ are the slots on the top level and $p \in W_{0}$ the slots on the bottom level $v \in V$ are the vehicles.
I have successfully implemented the constraints in case there is only a single row:
- 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$.
The two constraints I use that work are:
- $\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 \forall (v,u) \in A:W_{l\in 0/1}$
- $\sum\limits_{p\in P}x_{pv} \geq \sum\limits_{p\in P}x_{p(v+1)} \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: [0, 4, 6, 5]
Bot level: [1, 2, 7, 3, 8]
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]
Bot level: [1, 2, 7, 4, 8]
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.
i.g.: If I want to avoid the example above: $v = 4$, $v' = 7$
if $\sum\limits_{p\in W_0}px_{pv'} \leq \sum\limits_{p\in W_0}px_{p(v-1)} \forall v,v' \in V$
then $\sum\limits_{p\in W_1}px_{p(v'-1)} \leq \sum\limits_{p\in W_1}px_{p} \forall v,v' \in V$
This is not working at all so far. I would greatly appreciate any help! Sadly I have so far also not found a paper that deals with a similar problem.