DonNTU   Masters' portal

Abstract

Content

Introduction

Support of clients is currently the highest position among corporate purposes, including to attract new customers. Modern technologies allow to increase the efficiency of solving this problem. At present, it is possible to communicate with customers means not only voice but also video-telephony (Skype, Google Talk, QIP, etc.). Despite this, there are problems to solve which can only exit the employee organization to the customer. An example of the service organization will serve as a corporation "Parus-Donetsk". Core business: development, promotion and implementation of software (software) to automate the management of the enterprise. Parus-Donetsk – a representation of the corporation Parus in the Donbass. "Parus-Donetsk" customers are more than 400 organizations in Donetsk and more than 1100 in the area. The state enterprise has only 46 employees. To provide support to organizations which exceed 1500 employees "Parus-Donetsk" to optimally allocate their time and choose the best route for productive work.

1. Description of the object of research

The object of research in this paper is to serve. Support of clients can be implemented in two ways:

Way to solve the problem the client is dependent not only on the complexity of the issue, but also on knowledge of the client in the computer field. For example, about 70% of clients do not cope with the simplest tasks, like updating the software or forms. With the system basically works as an accountant. Updating is carried out in three stages:

  1. setup file is sent to the customer e-mail;
  2. employee (accountant) of the organization-customer loads on your computer setup file;
  3. accountant runs the installer on your PC.

Basically, there are difficulties in the second stage. Not all accountants can use e-mail. It does not always depend on the availability of Internet. Typically, these difficulties arise in ignorance of the specialist. A good accountant is not always a good PC user.

2. Justification of the relevance of the problem

Each month comes an updated installer. To update the software, ideally, the client does not need help Parus`s employees, but in fact we obtain the following statistics: 70% of client organizations are not in place to upgrade themselves and seek help in the Parus. 70% of organizations in 1570 – about 1100 firms. Given the state office in Donetsk, we obtain the relation "employee organizations": 1100/43≈26. Each employee Paruss, one organization spends on average about 2–3 hours (excluding time on the road). If we talk about organizations that are in the city, the time spent on the road about 2 times smaller. If you need to support the client resides outside of Donetsk, on a road worker spends as much time as to the actual service.

In addition to monthly updates, a quarterly update. Every 3 months to update product needs "Parus-Consolidation" The process of updating the system should not last more than a week. It turns out that organizations need to update the 1100 employees of 43 "Parus-Donetsk" 5 working days. For a clearer picture, count the number of organizations that cater to every employee Paruss. Given the fact that the employee has 26 organizations, we get: 26/5≈5 (organizations per day). To update the software must be less than the time, but at the same time spent on the road. That is, one organization should be an average of 1 hour, while on the road all the same 2–3 hours (in the region). If you calculate the amount of time spent by an employee at the Paruss in an organization, we get 1+3=4 (h) maximum). In sum: 4*5=20 (hours) for 5 organizations – the rate for the employee "Parus-Donetsk"). Given that the working day is 8 hours, face the problem of lack of time, to be exact – the employee does not have time to serve half of the organizations at maximum load.

3. Review of the chosen method of distribution in terms of the task

The algorithm is based ant colony behavior – marking more successful ways of a large number of pheromone [10]. The work begins with the placement of ants in the vertices (cities), then begins the ants – the direction is determined by the probabilistic method, based on the formulas of the form:

The formula of probability

(3.1)

where: Pi transition probability on the path i, li the reciprocal of the weight (length) i-th transition, ƒi amount of pheromone on the i-th transition, q value, which determines the "greedy" algorithm, p value, which determines the "herd instinct" of the algorithm and q+p=1.

The solution is not exact and may even be one of the worst, however, due to the probabilistic solutions, the repetition of the algorithm can produce (enough) the exact result.

The original idea comes from the observation of ants in the process of finding the shortest path from the colony to the power source.

In Fig. 3.1 shows the algorithm:

  1. The first ant finds a food source (F) by any method, and then returned to the nest (N), leaving behind a trail of pheromones.
  2. Then the ants choose one of four possible ways, and then strengthen it and make attractive.
  3. The ants choose the shortest route, because the longer stronger pheromones have evaporated.
Behavior of Ants

Figure 3.1 – Behavior of Ants
(animation: 7 frames, 8 cycles of repeating, 26 kilobytes)

Among the experiments on the choice between two paths of unequal length, leading from the colony to a power source, biologists have noticed that, as a rule, the ants use the shortest route. The model for this behavior is as follows:

Ants use the environment as a means of communication. They exchange information indirectly through pheromones, in the course of their "work". Exchange of information is local, only the ants that are in close proximity, where they remained pheromones – can learn about them. Such a system is called "Stigmergy" and is valid for many social animals. This mechanism for solving the problem is very complex and is a good example of self-organizing system. This system is based on the positive and negative feedback. Theoretically, if the amount of pheromone will remain unchanged over time on all routes, it would be impossible to choose a path. However, due to feedback, small vibrations lead to a strengthening of one of the routes and the system stabilizes to the shortest path [11].

Conclusion

The analysis in the research work has shown that the problem of the distribution depends on the problem of route optimization, which can be formalized as a special case of the traveling salesman problem with additional constraints on time. Computerization has been studied object, the ways of his automation and the necessity of developing a new system, analyzed the methods for finding optimal routes, formulated a mathematical model. Eventually, after studying one of the most popular algorithms for optimization of different processes, namely, the ant algorithm, we can conclude that this algorithm will allow us to solve the problem. A method for solving the problem using the ant algorithm. Future work will focus on the implementation of this method and its experimental study for the task.

This master's work is not completed yet. Final completion: December 2012. The full text of the work and materials on the topic can be obtained from the author or his head after this date.

References

  1. Лорьер Ж.-Л., Системы искусственного интеллекта / Пер. с фр. и ред. В. Л. Стефанюка. – М.: Мир, 1991. – С. 238–244.
  2. Рассел С. Дж., Норвиг, П. Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach / Пер. с англ. и ред. К. А. Птицына. – 2-е изд. – М.: Вильямс, 2006. – С. 157–162.
  3. Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. – Addison-Wesley, 1984.
  4. R. Bellman: On a Routing Problem // Quarterly of Applied Mathematics. 1958. Vol 16, No. 1. C. 87–90, 1958.
  5. L. R. Ford, Jr., D. R. Fulkerson. Flows in Networks, Princeton University Press, 1962.
  6. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн, Алгоритмы: построение и анализ = Introduction to Algorithms. – 2-е изд. – М.: «Вильямс», 2006. – С. 1296.
  7. Ананий В. Левитин Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. – М.: «Вильямс», 2006. – С. 189–195.
  8. M. Dorigo & T. Stutzle, 2004. Ant Colony Optimization, MIT Press.
  9. M. Dorigo, G. Di Caro & L. M. Gambardella, 1999. "Ant Algorithms for Discrete Optimization". Artificial Life, 5 (2): 137–172.
  10. M. Dorigo, V. Maniezzo & A. Colorni, 1996. "Ant System: Optimization by a Colony of Cooperating Agents", IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26 (1): 29–41.
  11. C. Blum, 2005 "Ant colony optimization: Introduction and recent trends". Physics of Life Reviews, 2: 353–373.
  12. T. Stutzle et H.H. Hoos, MAX-MIN Ant System, Future Generation Computer Systems, volume 16, pages 889–914, 2000.
  13. L. M. Gambardella, M. Dorigo, "Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem" // Twelfth International Conference on Machine Learning, Morgan Kaufmann, p. 252–260, 1995.
  14. M. Dorigo, L. M. Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation Vol. 1, 1, p. 53–66, 1997.
  15. T. Stutzle, H. Hoos, "MAX-MIN Ant System and local search for the traveling salesman problem" // IEEE International Conference on Evolutionary Computation, p. 309–314, 1997.
  16. Bernd Bullnheimer, Richard F. Hartl, Christine Strau?, "A new rank based version of the Ant System. A computational study" // Adaptive Information Systems and Modelling in Economics and Management Science, 1, 1997.