Re: [tablix-list] optimizations based on room-distances possible?

From: Tomaž Šolc <tomaz.solc_at_tablix.org>
Date: Thu, 21 Aug 2008 10:47:43 +0200

Hi Max

> I was thinking if it was possible to do some extension to the walk
> module that would consider more than just the fact that somebody
> needs to change rooms. To avoid walking is a very important feature,
> but it's not always possible.
>
> In my particular case I have three separate 11-story buildings and
> each of them has just 3 elevators. So it makes a huge difference if a
> tiny class of 10 students has to move 7 floors (by elevator) or if a
> big class of 50 students needs to move 1 floor (taking the stairs). A
> switch of buildings for a big class is something to avoid totally if
> possible.
>
> I thought about it like some GPS-routing software where there are
> different routes with different speeds, capacities, etc. to the same
> places. One would lay out the buildings flat on paper and connect the
> rooms with corridors, staircases, elevators and a sidewalk in between
> buildings. Each of the connections has a distance, speed, maximum
> capacity, etc.

This sounds like an interesting idea. The timetables I worked with
didn't involve such bottlenecks - changing classrooms was merely
inconvenient for the students.

The minimum information you would need to provide to Tablix is the
weight for movements between all pairs of classrooms. The walk module
would then calculate its fitness value by adding weights of all
movements needed for the current timetable (and possibly taking into
account the number of students in classes).

Now you can complicate the way you calculate these weights as much as
you wish :) The simplest version of such a walk module would leave this
calculation to some external software and just read the movement weights
from module options.

On the other hand, you could also do it in the walk module itself. For
example you could assign some "location" to each room and then specify
the properties of connections between these locations in options to the
walk module. You could then use some algorithm to find the cheapest
paths between all pairs of points on such a graph. You could also
specify how paths scale with the number of people (e.g. staircases are
better at moving lots of people at once than elevators).

> Admittedly, this sounds like overkill and not at all related to
> timetabling. So the first step would be to just have a dynamic weight
> for walk that uses the number of students in the class. I'm not sure,
> but I believe this is possible with just tiny modifications to the
> DTD (a size attribute for classes). If the DTD would also allow a
> location attribute for the rooms one could start from there. The
> actual distance calculation could even be external then.

There's no need to modify the XML schema. The "restriction" tags can be
used to apply arbitrary attributes to resources.

See for example "placecapability" module that uses restriction tags to
assign various capabilities to classrooms.

> Maybe I'm just dreaming, but I believe Tablix is generally capable of
> solving a "travelling salesman". Please bring me back to reality
> showing me how wrong I am or help me getting my idea laid out
> straight.

You're not dreaming :) This idea is not that far fetched.

It would need some experimenting though to see how well the genetic
algorithm would optimize such a constraint. It's hard to predict this in
  advance.

As I see it, the basic routing problem would be solved separately from
the main genetic algorithm, so the performance probably wouldn't be much
worse than the current walk module.

Best regards
Tomaž
Received on Thu Aug 21 2008 - 10:43:37 CEST

This archive was generated by hypermail 2.2.0 : Fri Aug 22 2008 - 06:30:08 CEST