GRADUATION DISSERTATION

Subject : Methods and algorithms for finding optimal pathways agents geographically distributed outlets

Content

RELEVANCE

Today, there are two types of systems to optimize traffic - desktop-oriented access over the WAN.

The main and decisive difference in these types of systems is a source of information for the route. Desktop systems take information from databases on their own servers, or receiving data on the local network. Of the advantages worth noting control over access to information, besides the speed of applications built on a desktop client - server architecture many times can exceed the speed of the web - oriented subsystem. The disadvantage of these systems is the need for continuous updating of data, and complement them with new, which makes such systems are dependent on the frequency of updates. This is reflected on the relevance of the information needed to perform the ultimate task - finding the optimal route.

The main purpose of this subsystem is to make optimal route agent, compiled on the basis of various criteria: the distance between outlets, the time spent on the trip, type of terrain, fuel consumption, the direction of movement on the roads (unidirectional, bidirectional).

The main tasks are:

  • visualization of data on the routes on a map, view the finding separately Interso waypoints;
  • display detailed information on outlets (its performance).
There will also be organized by the information output from the processing subsystem and user parameters that influenced the outcome.

PURPOSE AND TASKS OF DESIGH AND RESEARCH

Today's market offers solutions for every taste and color, for any budget, trying to cover all proizvodstvennnye needs. And tomorrow the needs and requirements will undoubtedly ambitious and more severe. This fact poses the question of the developers looking for new ways of solving tasks, taking into account the need to constantly update their products. This directly relates to the theme of my research, as cards become obsolete over time, new buildings, driving directions. Thus there is need for a reliable source of map data with which to obtain relevant geographic data and a system that would be based on these data, helped to choose the shortest and cheapest route for the movement.

SCIENTIFIC NOVELTY

Centralization of geographic information in one source, and scalability of the system will make that the base on which to build a highly accurate and effective solution for various logistics organizations in the future to help save on the planning and the cost of travel.

PRACTICAL SIGNIFICANCE OF RESULTS

With the help of this system is supposed to get funds to:

  • analysis of the effectiveness of movement of commercial agents;
  • geographic visualization of routes;
  • regulation of movement of agents outlets.

Improving the effectiveness of visiting the outlets will be received by:

  • control of movement of agents;
  • optimize the time - more than visited the outlet for the same time.

REVIEW

There are two types of systems to optimize traffic - desktop-oriented access over the WAN. The main and decisive difference in these types of systems is a source of information for the route. Desktop systems take information from databases on their own servers. obtaining data on the LAN. Of the advantages worth noting control over access to information, besides the speed of applications built on the client - server architecture many times can exceed the speed of the web – oriented subsystem. The disadvantage of these systems is the need for continuous updating of data, and add new ones, which makes such systems are dependent on the frequency of updates that affect the relevance of the information necessary to fulfill the ultimate task - finding the optimal route.

Web – based systems are, in my opinion, more effective means of solving the problem. Despite the lower-speed access to data, they provide the greatest urgency, flexibility and expandability, the ability to access necessary information from anywhere, and if appropriate provision - mobile access with PDA or phone.

Structurally, these systems represent a set of two parts - a database and the client side. The database contains geographical data to coordinates, address, a set of streets, roads and buildings to determine the location, a route, find the map of any object.

The main specific differences of distributed systems is the presence of its database, aimed at controlling traffic or agents, and the impossibility of integrating corporate data to the data card. According to the specifics of the problem, it would be impossible to reflect on the map data on retail outlets and information about them.

The client side consists of two parts - the logic and user interface. The application logic assumes the availability of means for communicating with the server that contains the map data, a server with enterprise data, classes that implement the optimization techniques for finding the shortest route to follow for routing; means to display the results of the user.

MATH METHODS

As the input data according to the schedule problem is seen by agents of outlets - routing, location of outlets, in some cases their precise geographic coordinates (latitude, longitude). Need to get the route built according to different criteria:

  • the distance between outlets;
  • the time spent on the trip;
  • type of terrain;
  • fuel consumption.

After receiving the route is necessary to put it on a map, showing you visit outlets as stopping points agent. To solve this problem it is necessary to obtain geographical coordinates of the paths between outlets, ie the coordinates of highways, streets, houses that the agent is obliged to visit. Upon receipt of such data can be connected algorithms search for optimal routes on existing coordinates. Mathematically, the city can be represented as a graph, that is an ordered pair G: = (V, E), for which the following conditions:

  • V is the set of vertices or nodes,
  • E is the set of pairs (in the case of an undirected graph - unordered) vertices, called edges.

In fact, the vertex V is a crossroads, junctions, edges E - unite their stretches of road. This scheme is applicable not only in the scale of the city, but in fact the road network of the country. Thus, to solve the problem, use algorithms on graphs, allowing to find the optimal path through a set of vertices.

The figure shows a schematic view of an undirected graph with six vertices, which are mainly junctions and seven ribs, which are mainly roads connecting the intersections (Figure 1).


Figure 1. Undirected graph with six vertices and nine edges.

Work system has the provider of geographic information, such as Google Maps, which provide the system with information about roads, intersections, alternatives to arrive at the destination. The system, based on this information, comparing it with information on the schedule visiting the outlets, create a route visiting the outlets, to calculate the indices of selection of the route. Access to analytical information will be provided to analysts, to view the routes on a map with a precise description of the route of travel - agents.

The scheme of the system (in other words, architecture) is shown in Figure 2.

Иллюстрация работы подсистемы
Figure 2. The functioning process of the subsystem, illustrating the receipt and processing of information. Animation consists of 4 frames with a delay of 50ms between frames, the delay for the replay is 250ms, the number of cycles of reproduction is not limited to, the volume 87kB.

To find the shortest path in graphs is well known a large number of algorithms that take into account the conditions of the problem. This algorithms on weighted graphs with weights inherent edges. These algorithms include:

  • search algorithm A *;
  • Dijkstra's algorithm;
  • shortest paths algorithm of Floyd;
  • genetic algorithm;
  • ant algorithm;
  • Hopfield neural network model.

SUMMARY

Developments in this area do not lose relevance for the current day, since new tools and technologies to expand the scale and scope of problem solving to deliver a new level of efficiency results.

REFERENCES

  • Laurière J.-L. Artificial Intelligence ed. with CHF. and ed. VL Stefanyuk. - M.: Mir, 1991. - S. 238-244. - 20 000 copies. ind. - ISBN 5-03-001408-X
  • Russell SJ., Norvig, P. Artificial Intelligence: A Modern Approach = Artificial Intelligence: A Modern Approach / Per. from English. and ed. KA Ptitsyn. - 2 ed .. - M.: Williams, 2006. - S. 157-162. - 3000 copies. ind. - ISBN 5-8459-0887-6
  • Nilsson N. Artificial Intelligence: Methods solutions = Problem-solving Methods in Artificial Intelligence / Per. from English. VL Stefanyuk, ed. Fomin. - M.: Mir, 1973. - S. 70 - 80.
  • Dechter, R., Pearl, J. Generalized best-first search strategies and the optimality of A* // Journal of the ACM. — 1985. — Т. 32. — № 3. — С. 505 — 536.
  • Hart P. E., Nilsson, N. J., Raphael, B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths // IEEE Transactions on Systems Science and Cybernetics SSC4. — 1968. — № 2. — С. 100 — 107.
  • Hart P. E., Nilsson, N. J., Raphael, B. Correction to «A Formal Basis for the Heuristic Determination of Minimum Cost Paths» // SIGART Newsletter. — 1972. — Т. 37. — С. 28 — 29.
  • Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. — Addison-Wesley, 1984. — ISBN 0-201-05594-5
  • Hanani B. Levitin, Chapter 3. Brute force: The traveling salesman problem / / Algorithms: An Introduction to the design and analysis = Introduction to The Design and Analysis of Algorithms. - M.: "Williams", 2006. - S. 159-160. - ISBN 0-201-74395-7
  • Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein Algorithms: construction and analysis = Introduction to Algorithms. - 2 ed. - M.: "Williams", 2006. - S. 1296. - ISBN 0-07-013151-1 VI
  • Mudrov traveling salesman problem. - M.: "Knowledge", 1969. - S. 62.

When writing this Autosummary master work was not yet completed. Date of final completion: Dec. 1, 2010 Full text of the work and materials on the topic can be obtained from the author or his supervisor after that date.