Lötschberg-base line

The Lötschberg base tunnel is a component of the AlpTransit concept. It leads from Frutigen in the Kander valley to Raron in the Rhone valley. Access from the north will be provided by large new sections of Rail 2000: Basel-Liestal and Olten-Bern. In the south, it will connect to the existing Simplon base tunnel, whose access lines are currently being extended by our Italian neighbours.

Project overview

The Lötschberg base tunnel is designed as a tunnel system with two separated single-track tubes, one in each direction. However, in order to reduce costs, only one tunnel tube will be built between the north portal in Fru-tigen and the service station envisaged in Mitholz. This is possible since the Kandertal exploration tunnel which has already been completed runs parallel and will act as a rescue and safety gallery in the operational phase. South of Mitholz, as far as the south portal in Raron, two tunnel tubes are envisaged; in an initial phase the railway infrastructure of the western tubes is envisaged only between Ferden and Raron. The total length of the base tunnel is 34.6 km. The distance between the two tubes is generally 40 m. The two tunnel tubes will be linked every 333 m by cross-ways. The lateral tunnel to Steg will have the same profile as the tunnel tubes, so that infrastructure can be installed for rail traffic at a later date, allowing a subsequent direct link to be constructed towards central Valais.

For further information, see the reference of this text : http://www.blsalptransit.ch/

[Top] 

Probabilistic Aspects of Constraint Satisfaction

Michael Kupper, ETH Zurich

Constraint satisfaction problems deal with decision variables having to be assigned values in order to satisfy a set of logical constraints (so called clauses).

Certain problems of this type (G-Sat, the "Generalised" or "non-boolean" satisfiability problem) can be expressed as questions about related hypergraphs. Actually, these questions naturally generalise classical problems of graph theory (in particular, determining the stability and chromatic number).

The main issues considered (from a probabilistic viewpoint) are the determination of

• the stability number of a G-sat instance, that is the maximal cardinality of a subset of variables inducing a satisfiable subinstance.
• the stable cover number of a G-sat instance, that is the minimal cardinality of a partition of the instance into satisfiable subinstances.
• the satisfiability threshold for G-sat instances, that is the ratio clauses/variables below which almost every instance is satisfiable, and above which almost every instance is not satisfiable.

A probabilistic analysis of these issues is relevant for the sake of heuristics testing: Heuristics are developed to deal with instances of hard problems for which no exact (or even approximate) algorithm can be applied, and for which often not even a reasonable bound for the optimum can be obtained (see a) and b) above). How can we then test the quality of a heuristic on large instances? A first possibility consists in constructing instances with known optimum (such instances being unfortunately atypical), a second one is to generate at random instances according to a given probabilistic model, and to deduce from theoretical consideration a small range where the optimum is likely to be located with high probability. The probabilistic analysis of the behaviour of the optimum for such instances can sometimes deliver amazingly sharp results, as illustrated in this diploma. The main probabilistic model considered here is H(n,r,k,p), the probability space of instances on n variables having r possible values, and with clauses of cardinality k occurring independently with probability 0<p<1.

This diploma contains (new) results about the concentration of the stability number and the asymptotic behaviour of the stable cover number. Moreover it gives an analytic characterisation of some upper and lower bounds for the satisfiability threshold of G-k-Sat. Finally, the report contains a rather self-contained account, explaining the methods applied (first and second moment, Martingales, deferred decision,...) and illustrating their applications. In particular, the author gives a detailed reconstruction of the kernel of the Frieze & Suen's paper: "Analysis of two simple heuristics on random instances of k-SAT".

For further information , please contact Dr. Maurice Cochand (cochand@ifor.math.ethz.ch).

Essential attributes for software transferability and end-user adoption of vehicle routing heuristics

Alain Hertz, Ecole Polytechnique de Montréal - GERAD

The vehicle routing problem (VRP) holds a central place in distribution management and has become one of the most widely studied problems in combinatorial optimization. Only relatively small instances can be solved to optimality, no exact algorithm being capable of consistently solving instances in excess of 50 customers. This explains why heuristics are commonly used in practice.

There has been a steady evolution, over the past forty years, in the development of VRP heuristics. In the early classical heuristics, much of the emphasis was put on quickly obtaining a feasible solution and possibly applying to it a post-optimization procedure. This class of methods includes the well-known savings algorithm and the sweep algorithm. Over the last en years, much of the effort has concentrated on the development of algorithms based on meta-heuristics using mainly two principles: local search and population search. In local search methods, an intensive exploration of the solution space is performed by moving step by step from the current solution to another promising solution in its neighbourhood. Tabu search is an example of this principle. Population search consists of maintaining a pool of good parent solutions and recombining them to produce offspring. A classical example is genetic search. While more time consuming than the early heuristics, meta-heuristics are capable of consistently producing high quality solutions.

Yet most commercial software and several in-house computer programs used by companies are based on unsophisticated methodologies dating sometimes back to the 1960s. There are several reasons for this state of affairs. One is that the optimization component of a VRP software is only a small part of the product, most of the effort being expanded on data management and sophisticated user interfaces. Another reason is that company analysts and software developers are simply unaware of the latest algorithmic developments.

We believe the main hindrance to technology transfer may be more deep-rooted. In our opinion, most of the available VRP heuristics lack some of the necessary attributes to ensure their adoption by practitioners. We describe what we believe are four essential attributes for software transferability and end-user adoption. We then provide an appraisal of some of the best known heuristic with respect to these criteria.

Professor Alain Hertz
alain.hertz@gerad.ca