Combining Simulation with Heuristics to solve Stochastic Routing and Scheduling Problems

Many real-world problems in the production and logistics business are NP-hard even in their deterministic representation, and actually also show stochastic behaviour, where even the mathematical description of the -frequently empirical - distributions is difficult or even impossible. Therefore, an approach is acquired that enables the search for valid and reasonably good solutions under representation of the stochastic system behaviour. A suitable approach is to combine heuristic optimization with simulation techniques. This paper discusses how Monte-Carlo simulation can be combined with heuristics and meta-heuristics in order to efficiently solve such stochastic combinatorial optimization problems. The application is illustrated with examples in two different fields, including logistics and transportation - e.g. vehicle routing problems and inventory problems - as well as manufacturing and production - e.g. scheduling problems.