Information Technology Reference
In-Depth Information
•
Computer aided design (CAD): design of complex materials, e.g. optical
filters or composite materials [Boudet et al. 1996]; shape and structure
optimization.
•
Telecommunications: deflection routing of packets in ultra high speed net-
works [Herault 1997b], code optimization in broadband wireless systems
(CDMA), and optimization of the radiation pattern of antenna arrays.
•
Nuclear: stock management of perishable material [Privault et al. 1998a,b].
•
Spatial: scheduling; mission planning, resource allocation, etc.
•
Human resources: management optimization, allocation of persons to po-
sitions, optimization of timetables.
•
Signal and image processing: particle tracking [Derou et al. 1996], pattern
recognition [Herault et al. 1993].
•
Industry: job shop scheduling, packaging and routing problems.
Many other applications are described in [Takefuji 1992; Cichocki et al. 1993;
Dagli 1994; Takefuji et al. 1996].
Those problems can often be encoded as mathematical problems of graph
theory, such as graph colouring, graph partitioning, graph matching, as well
as extraction of sub-graphs with specific properties like cliques, paths, cycles,
etc. [Gondran et al. 1995]. As a consequence, it is important to study, jointly
with the applications, how to solve those families of generic problems. The
travelling salesman problem is one of those archetypal hard combinatorial
problems; we describe it in the following section.
8.1.2 The Travelling Salesman Problem (TSP)
Throughout this chapter, the graph theory problem named travelling sales-
man problem, which is a reference among the combinatorial problems, will be
frequently used as a problem example.
Reminder of the TSP
This is a tour optimisation problem: a travelling salesman has to visit some
towns with known geographic coordinates. To reduce its costs, he looks for a
tour that is as short as possible in terms of distance, and which goes through
each town exactly once.
Many algorithms have been proposed in the literature to solve this prob-
lem [Reinelt 1994; Gondran et al. 1995].
An example of problem with 101 towns is illustrated by Figs. 8.1 and 8.2.
Many applications can be modelled as this type of combinatorial problem:
such is the case, for instance, for the problem of finding the shortest path of
an industrial tool that has to machine some parts of an object (e.g., drill holes
in a printed circuit board).
Search WWH ::
Custom Search