In this chapter, some applications of network flow problems are addressed based on each type of problem being discussed. For example, in the case of shortest path problems, their concept in facility layout, facility location, robotics, transportation, and very large-scale integration areas are pointed out in the first section. Furthermore, the second section deals with the implementation of the maximum flow problem in image segmentation, transportation, web communities, and wireless networks and telecommunication areas. Moreover, in the third section, the minimum-cost flow problem is discussed in fleeting and routing problems, petroleum, and scheduling areas. Meanwhile, a brief explanation about each application as well as some corresponding literature and research papers are presented in each section. In addition, based on available literature in each of these areas, some research gaps are identified, and future trends as well as chapter’s conclusion are pointed out in the fourth section.
TopApplications Of The Shortest Path Problem
Networks are considerably applicable and important in our business and personal lives. Networks can be applied for manufacturing, transportation, and distribution areas, in which necessary products and basic commodities are obtained for suppliers and customers. Furthermore, they can be considered for other applications such as telephone networks, by which we can communicate easily within domestic or international communities, or computer networks that facilitate broadband communications and internet services taking considerably less time than it took in the past.
Facility Location and Facility Layout
In the facility location problem, provided that several facilities are located (configured as the vertices of a network), the shortest path problem can be taken into account in order to obtain the shortest possible path between each pair of facilities. For example, in a supply chain network in which the location of supplier(s), manufacturer(s), and distributer(s) must be determined, one of the first priorities for decision makers is to minimize the distance between suppliers and manufacturers and between distributers and customers (end-users). As another similar application, layout problems can be referred in which internal operations are primarily considered, and the shortest paths (distances) between machines and equipment should be obtained. In other words, based on the operational importance and relationships between equipment, the position of this equipment can be adjusted with regard to the shortest paths.
Robotic Systems
As one of the novel and state-of-the-art applications, the problem of robotics path planning and mapping has recently put their emphasis on the shortest path problem. Without loss of generality, given an autonomous robot, the essence of the robotics path planning problem is to find a collision-free path from a particular point to another in shortest time (Priya et al., 2006; Sun et al., 2006). Therefore, the robot path planning problem can be defined in terms of the shortest path problem. As a matter of fact, the importance of the shortest path problem is due to its wide contribution to the application of robotics path planning problems exerted in industrial robotics, computer aided design (CAD), computer aided manufacturing (CAM), and virtual prototyping areas.
Transportation of Hazardous Materials
The most common application of the shortest path problem in transportation areas is the transportation of hazardous materials such as explosive materials, flammable materials, and some chemical materials. Since these materials are susceptible, they ought to be passed from a source vertex to a sink vertex through the shortest path. However, it should be noted that in order to decrease the underlying risk of this shipment, the best k-shortest paths are considered so that in case of emergency, the material can be shifted from one path to another (Dadkar et al., 2008). In other words, a path from the source to the sink might be the shortest path, but it passes through many residential areas. Hence, such path is preferably ignored, and other alternative routes will be taken into account.