Railway Quota Allotment Problem

I describe the following problem and in future posts will try to find optimal solutions to the problem. The problem statement is as follows:

The Indian Railway maintains a quota based system where each station is given some number of seats. These seats are located in different kinds of classes, say sleeper, 3-tier AC and 2-tier AC. Every train has different number of compartments and so the length of the trains differ. Every stations has one entry point where passengers come on the platform and they walk to the compartment where quota is allotted for that particular station and then take the seat. Our aim is to minimize the distance passengers have to walk.

To simplify the problem we will assume following:

1. There is only one class of compartment in each train. So all the passengers travel to that compartment only.
2. Length of each train is same, i.e. $l$.
3. There are $N$ stations with entry points $e_i, 1 \le i \le N $ such that $ 0 \le e_i \le l $. You can see that $e_i$ is expressed as a distance from the start of the train.
4. Every station occupies $x_i$ length of the train such that $ 0 < x_i <= l, 1 <= i <= N$. It is easy to see that $ \displaystyle\sum\limits_{i=1}^N x_i = l $. If station $i$ is allotted quota at distance $d_i$ from start of the train, the next quota allotment can happen only at distance $d_i + x_i$.
5. The quota allotted to each station is at $q_i$ distance from the start of the train such that $0 <= q_i < l, 1 <= i <= N$. The problem is to find $q_i$ for each station such as to optimize $ \displaystyle\sum\limits_{i=1}^{N} | e_i - q_i | $. See that not all the passengers at station $s_i$ has to travel till $q_i$ but to simplify the things, we assume so.

The image on the left shows a sample problem for two stations and a probable solution. The total distance travelled by passengers on both the stations is $e_1 + e_2 - x_1$.

There are several methods that I will try to focus on including greedy method and dynamic programming since the problem is to find an optimal solution. I will focus on finding whether the solution has an optimal sub-structure. The number of different possible solutions depend on the permutations of stations and so is of the order of $N!$. The problem becomes more complicated by usage of absolute value of $ e_i - q_i $. I haven't seen this kind of problem in literature so I don't think this will be solved easily by me.