Metaheuristics for Logistics

2A Review of Logistic Problems

After quickly presenting some historical (section 2.1) and polynomial (section 2.2) problems, we will describe over the following sections (2.3 to 2.7) some ten non-polynomial problems that represent the richness and variety of the problems we may be faced with in logistics. We will talk about packing and routing problems, production scheduling and planning, and the location of sites.

2.1. Some history

Logistics is a field that abounds with optimization problems and is, from a historical point of view, at the base of some of the best Operations Research problems. We will mention four examples that prove this point: the Fermat–Torricelli point, the Monge problem, the problem of the Seven Bridges of Königsberg and the Icosian Game.

2.1.1. The Fermat–Torricelli point

Pierre de Fermat formulated the following problem in 1636: “given three points, find a fourth one such that the total distance from the three given points is the minimum possible”. The direct logistic application of this problem consists of determining the best location of a depot that should supply three cities. Popular belief is often obstinate and even today many consider the center of gravity of the triangle as the solution to this problem (is the so-called barycenter method not regularly employed to determine the location of a logistic site?). However, in 1640, Evangelista Torricelli proposed a geometrical solution to this problem (Figure 2.1). If the three angles do not exceed ...