Graphs and networks are collections of nodes and arcs. The nodes are used to represent cities, major intersections, or individual customer locations. The arcs are used to represent the linkages between nodes. The linkages could be telecommunication lines or roads. The links can be one-way or bi-directional. Numeric values on the links can represent the actual length of the link, the distance as the crow flies, or the time to traverse the link. In routing applications, it is important to use travel times and not just distances. Two miles on the open road are traversed much faster than two miles through city streets. In addition, these data will often need to be adjusted by time of day.
The field of graph theory dates back more than two hundreds years with mathematicians such as Euler actively involved in its theoretical analysis. Graph theorists were primarily interested in understanding the properties of different graph structures without numeric values attached to the arcs. With the growth of computers, the study of networks moved into a new phase in the 1950s and 60s that focused on the development of efficient algorithms to solve optimization problems in routing. Networks were no longer just a collection of nodes and arcs; arcs now included numeric values which could represent either distance or time. One of the first class of problems that was solved related to finding the shortest path between two points (nodes) on a network. A computer scientist named Dijkstra developed one of the first efficient algorithms for solving this problem. Dijkstra's algorithm is the basis for widely available software that responds to requests for finding the shortest or fastest route to a specific location. In addition, this algorithm is an important element of the management of information traveling through a telecommunications network.
In the 1970s operations researchers began to study two classes of vehicle routing problems, the traveling salesman problem and the Chinese postman problem. One class of problems involves an individual or vehicle traveling along the shortest route from node to node, visiting every node in the network and then returning home to its base. (The 19th century mathematician William Hamilton first posed the question of the existence of a circuit that visited each node once and only once.) This problem is called the traveling salesman problem (TSP), as it represents the challenge facing a salesman who must travel from city to city and return home. It is part of a broad class of problems for which we know it is NOT possible to develop algorithms that are guaranteed to find the absolute optimal solution in a reasonable period of time. Instead, operations researchers work on developing heuristic algorithms that search for good or near optimal solutions. These algorithms generally have two phases. The first phase attempts to find a good initial solution. The second phase involves minor modifications to the best solution found so far in order to create better and better routes.
In practical applications, the transportation manager rarely deals with routing just one vehicle. Instead, he has a whole fleet of vehicles. In this case the algorithms must divide the set of nodes (pick-up or delivery points) into separate routes, with each route assigned to a vehicle. Companies such as Federal Express have large internal operations research groups working on a wide range of issues related to the routing of vehicles and the overall management of the truck fleet. In contrast, a bank such as Wells Fargo or Bank of America might commission a consulting firm to design the routes for a fleet of trucks. These trucks pick up cancelled checks several times a day at the bank branch offices and then deliver them to a check clearing house for posting with the Federal Reserve for collection of funds. School bus routing also involves applying algorithms used to solve TSP.
In the not so good old days, routing software ran in batch mode on a mainframe computer. The solution was printed out as a sequential list of stops. To see the route, an individual would take a piece of see-through vellum, lay it over a big map and trace the route by hand. If a mistake had been made in the input data or new stops had to be added, the process would have to start all over again and the original piece of vellum tossed out. In the 1980s, the personal computer revolutionized this process. Not only could the algorithms be run almost instantaneously on the manager's desk, more importantly the solutions could be linked to widely available geographic information systems (GIS). As a result the routes could be shown on the computer screen overlaid on the actual street network. This new capability motivated a change in the design of routing packages to enable the experienced manager to contribute to the design and modification of the final routes. No mathematical model can capture all aspects of a complex problem. Thus, the need to tweak a solution to account for something not explicitly included in the model is not uncommon. PC based systems have enabled managers to easily adjust the final routes.
The Chinese Postman Problem (CPP) is a close cousin to TSP. In this routing problem the traveler must traverse every arc (i.e. road link) in the network. The name comes from the fact that a Chinese mathematician, Mei-Ko Kwan (1962), developed the first algorithm to solve this problem for a rural postman. It is an extension to one of the earliest graph theory questions, the Königsberg Bridge Problem, which was studied by Euler (1736). The Pregel River runs through the city of Königsberg in Germany. In a city park seven bridges cross branches of the river and connect two islands with each other and with opposite banks of the river. For many years the citizens of Königsberg tried to take walks that took them over each bridge once without retracing any part of their path. Euler was able to prove that such a walk is impossible. In general, graph theorists are interested in understanding whether or not a circuit exists that does not require traversing the same arc twice. Operations researchers are interested in finding the shortest route in any type of network.
The Chinese Postman class of problems is relevant to a number of other services. Garbage collection, street sweeping, salting or gritting of icy roads, and snow plowing are some of the other services for which vehicle routing algorithms have been applied. Meter readers also must travel up and down every street. Checking roads for potholes or serious deterioration or checking pipelines for weak spots also fall into this class of problems.
In the ever complex real-world additional constraints can arise that complicate the search for efficient routes. Labor contracts may require that the routes of different drivers must be approximately of equal length. There may be significant time restrictions or time windows on when a vehicle must visit a specific location to make a delivery or pick-up. The vehicle making pick-ups may also have capacity limitations such as a garbage truck which would restrict the maximum length of a route. Uncertainty can also complicate route planning. Trucks that deliver gasoline or oil, can't be sure when they set out as to how much they will have to pump into each of the tanks on their route.
Planning routes is just one piece of the decision making puzzle that a transportation manager must put together. The manager must also make decisions as to the size of the fleet, the location of depots or landfills, the size and type of vehicles. There are dozens of commercial software packages to aid in routing and scheduling vehicles. A generic website that can lead the reader to many packages for solving such problems can be found at http://www.transportweb.com/. Examples of specific software packages can be found at:
http://www.optrak.co.uk/ and http://www.navesinklogistics.com/.