Routing problems: a historical perspective

Abstract

This paper presents an historical perspective on routing problems. Today a well-established class of optimization problems, routing problems have played a pivotal role in the development of Logistics as a discipline, even influencing other sectors not directly connected to management studies. The aim of this paper is to provide an overview of the evolution of this topic, starting from seminal contributions by Euler and Hamilton, and illustrating the most recent applications. This article is based on a longer article originally published in Italian (Bruno et al. 2010).

Notes

¹ Some details about Königsberg city life during the eighteenth century can be found in the novel Critica della Ragion Criminale, by Michael Gregorio (alias Michael Jacob and Daniela De Gregorio), Einaudi, 2006. One of the main characters of the novel is the philosopher Immanuel Kant.

² If the graph that represents the problem is connected and all the vertices have even degree, an Eulerian circuit exists. Euler also showed that a path exists if the graph has only two vertices with odd degree, in which case the path must depart from one of these two vertices.

³ Also sometimes known as the Route Inspection Problem (RIP). Goldman affirms, in a personal note dated 14 December 2003, that he was influenced in selecting the name of the problem by the title of a noir novel by Ellery Quen, The Chinese orange mystery (1934).

⁴ According to the original rules, up to 15 different games could be implemented. Hamilton's idea was that two people could compete against each other, the first by selecting the version of the game and setting up the rules, the second by solving it. Hamilton (1856, 1858) also developed a discipline that he named Icosian Calculus, which he utilized to investigate closed paths on dodecahedrons

⁵ When a Hamiltonian path has an arc that connects the last vertex to the first one, it is called a Hamiltonian Circuit.

⁶ Morton and Land (1955) state that the TSP was originally named the Laundry Van Problem.