Scheduling trains with cross entropy optimisation

Abstract

The logistics of moving grain from silos to ports is constrained by the number of trains available and the capacity of loading and unloading facilities. We aim to schedule the available trains to move grain from silos to the port as quickly as possible. The sequence of trips that minimises the time required to complete all trips is a permutation of a basic sequence that has the required number of trips to each silo. We use the Cross Entropy Optimisation method to search for a permutation that minimises span. For small problems, where the optimal solution can be found by enumeration, the Cross Entropy Optimisation method achieves solutions within 5% of the optimum. It can also find good solutions for large problems. References

• Unveren A. and A. Acan. Multi-objective optimisation with cross entropy method: Stochastic learning with clustered Pareto fronts. IEEE Congress on Evolutionary Computations, pages 3065--3071, 2007.
• Boer P. T., Kroese D. P., Mannor S., and Rubinstein R. Y. A tutorial on the cross-entropy method. http://www.springerlink.com/index/KPW596202975755N.pdf.
• Rubinstein R. Y. and D. P. Kroese. The cross entropy method: A unified approach to combinatorial optimization, monte-carlo simulation, and machine learning. Springer--Verlag, New York, 2004.