An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling

Details An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling

2005-10-31

arxiv.org/abs/cs/0510091v1

Computer Science

Artificial Intelligence

Scientific paper

Train timetabling is a difficult and very tightly constrained combinatorial problem that deals with the construction of train schedules. We focus on the particular problem of local reconstruction of the schedule following a small perturbation, seeking minimisation of the total accumulated delay by adapting times of departure and arrival for each train and allocation of resources (tracks, routing nodes, etc.). We describe a permutation-based evolutionary algorithm that relies on a semi-greedy heuristic to gradually reconstruct the schedule by inserting trains one after the other following the permutation. This algorithm can be hybridised with ILOG commercial MIP programming tool CPLEX in a coarse-grained manner: the evolutionary part is used to quickly obtain a good but suboptimal solution and this intermediate solution is refined using CPLEX. Experimental results are presented on a large real-world case involving more than one million variables and 2 million constraints. Results are surprisingly good as the evolutionary algorithm, alone or hybridised, produces excellent solutions much faster than CPLEX alone.

Affiliated with

Also associated with

No associations

Rating

An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An efficient memetic, permutation-based evolutionary algorithm for real-world train timetabling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-292256