|
One of the areas of research and development of the project will be the multi-criteria optimization of routes in a network. Problems involving routing optimization are actually topics of great interest in the field of combinatorial optimization. The most common which appears in day-to-day is the shortest path problem. Roughly speaking, the problem consists in determining the path of least cost (distance, time, money, effort) between two points of a network. This type of problem can be applied to areas as vast as genetics, sociology or linguistics, but in the field of transport and logistics that the problem is of particular relevance with regard to geographic information systems. Other routing problem with great for transportation companies is the traveling salesman problem. In this problem, one is aimed to find the best route that passes at each city only once.
Although issue like the shortest path problem has begun to be investigated in the late 50, this topic has gained, a special interest in recent years due to the evolution of computing power and consequent improvement of the algorithms to deal with huge networks.
The use of efficient routing algorithms designed for specific variants of the problem has defined the quality of applications in the competitive market of geographic information systems. Proof of this is the existence of routing extensions in the main commercial products such as:
• Network Analyst;
• ArcLogistics;
• ArcGIS for Transportation Analytics;
• Telogis Route - Saas. In general, the algorithms developed by different companies are not public and, consequently, it is not known which formulation and implementation were used. This happens precisely due the competitive nature that exists in this type of applications. Under the SGP-GIMS project, SmartGeo want, in collaboration with the University of Coimbra, developing a particular type of routing algorithm - A multi-criteria optimization algorithm - which has little or no expression in commercial software, including the most popular in market above.
|
