DonNTU
Masters' portal

Abstract

The subsystem optimization transport timetables, depending on the traffic flow

Contents

1. Introduction
2. Actuality of theme and planed practical results
3. Aim and research tasks
4. Analysis of existing methods of modeling
5. Mathematical formulation of the problem
6. Queuing systems with heterogeneous flows and specialized channels
7. Experimental studies
8. Conclusion
9. List of sources
10. Notes

Introduction

With the development of computer science and information technology, they began to penetrate and expand into all the interests of the wider area of human activity. Opportunities were limited to the development and application of computer modeling techniques in solving problems of various types.

Mathematical modeling and computer experiment are indispensable in cases where it is impossible to carry out the actual simulation, or unreasonable. However, such cases may be on the computer simulation, pre-built mathematical models of the studied processes.

Currently, the majority resorts to modeling, tons of the primary method of research in all areas of knowledge and science-based method of assessment of characteristics of complex systems used for decision making in various fields.

Existing or projected system can be effectively investigated using mathematical models (analytical and simulation), implemented on modern computers.

The research hypotheses play an important role, ie, certain predictions based on a small number of experimental data, observations and conjectures. Rapid and complete verification of the hypotheses put forward can be made in the course of the experiment.

Actuality of theme and planed practical results

Recently in various areas of practice was necessary to solve various problems of probability. Examples of such problems include: passenger transport, repair shops, ticket offices, taxis, hairdressers, etc.

Due to the large number of passengers there is a problem of calculating the optimal scheduling of traffic on the route to resolve it is proposed to simulate the transport of passengers.

Relevance of this work is to use the algorithm without performing a complete listing of model parameters, but returns one of the best results.

As a result of an optimal schedule is planned to receive traffic.

Aim and research tasks

Aim of this work is to create a subsystem for modeling the transport of passengers and of optimal scheduling of traffic using this model.

To achieve this goal it is necessary to solve the basic problem:

  1. investigate to determine the ridership modeling method.
  2. conduct a comparative analysis of modeling techniques.
  3. develop an algorithm.
  4. develop subsystem allows to simulate the transport of passengers.
  5. conduct performance testing developed subsystems.

Analysis of existing methods of modeling

Modeling process a process of transition from real to virtual, through the formalization of further modeling is itself, after this interpretation, m e the reverse transition from the virtual to the real field.

In the simplest case, the modeling process is as follows:

Figure 1 – The modeling process

Each method has its own characteristics, so they can be divided in many ways.

One of the first signs of the classification, you can choose the degree of completeness of the model and the model divided into:

Depending on the nature of the studied system processes all types of modeling can be divided into:

Depending on the object representation can distinguish these types of modeling:

Among the possible models is most appropriate simulation, namely the modeling of queuing systems (QS).

In queuing theory study of the system, the input of which receives a random stream of requests (demands), falling in the general case, the random times. Received applications served by the system through the provision of some resources for some time, and being in some degree of handled, leaving the system. The most salient point operation of queuing systems is the presence of queues in which requests are waiting for the liberation of resources used by other service applications. In the simplest case, the queuing system is determined by the flow of applications, and the length of the queue service discipline (order of selection of applications from the queue), the number of channels (instruments) service, the service time distribution. In more complex cases, the reliability of the instrument is considered maintenance.

Existing methods of modeling the QS can be divided according to several criteria:

  1. The structure:

    • single channel – called single-channel system, which has a place, as well as a channel to serve only one, so is suitable only if the passenger uses a unit of transport;

    • multi – multi-channel system is a system that has one common queue, and multiple channels to service, so this type of model is most suitable for implementation, tons of pieces of equipment serving the passengers in most cases more than one. If it is used only one unit of transport, it is enough to set the necessary parameters of the model;

    • multiphase – a system in which the service channels are consistently and perform various maintenance operations. Not suitable for implementation of the model, tons of orders are processed only once on one of the channels;

    • single phase – homogeneous systems that perform the same operation of the service, the type most suitable for the implementation of the QS, t to the model performs the same operation, t e the carriage of passengers;

    • closed – queuing system in which requirements can be served back in and re-enter the service;

    • open – this is where the QS flow characteristics of applications do not depend on the condition of the QS itself.

  2. Acceptable waiting time for requests in the queue:
    • system without failure;
    • system with limited expectations;
    • system without delay.

    Can use all types of applications in the queue, but you should implement the transfer of the model parameters to specify which types of applications you can use and which not.

  3. In the discipline select the queue:
    • applications are selected from the queue in order of receipt;

      Parameters of applications in the queue are shifted display on fig. 3.

    • applications are selected from the queue in a random order. If all bids are equal, then the probability of selecting any one of them will be equal to 1/k The choice a simulation of the complete group of events. Removing applications from the queue parameters can be carried out in the second case, maybe in the basic algorithm;
    • applications are selected for the minimum waiting time. Necessary in the formulation of the application in a queue to remember the moment of possible failure, and when you select an application from the queue to find the appropriate time with a minimum value. Removing the application and the shift parameters are similar to the previous item, but the cycle starts with a selected number of the application.
    • selection of priority. In setting the application must be in line for a given condition in the rule to form the priority of applications received and remember it. When selecting an application can be seen an array of priorities and select the bid with the highest priority. Removal of the parameters of the application from a queue in the second case.

    Can use all the methods for selecting the application from the queue, but to implement the transfer of the model parameters, indicating what type of selection can be used, and what not, to T in some situations, you can use only one type, but sometimes more, te combine them.

  4. By the method of selecting a channel:
    • the minimum time of release;
    • in random order;
    • by priority.
    To implement the model passengers queuing is most suitable way to select a channel by priority.

Figure 3 – Select the application in order of receipt

Mathematical formulation of the problem

Table 1. Description of the subsystem

Subsystem Applications Channels
Passenger Passengers Transport (buses)

In modeling the transport of passengers can be arranged algorithm, which is an enlarged view is shown below.

Figure 4 – Block diagram of the algorithm

Model should take the following parameters:

Model is developed and implemented to assess the specific quality indicators, they are the output values of the model.

Output value model are as follows:

Queuing systems with heterogeneous flows and specialized channels

Uniform flow in a general sense, is characterized by having a joint, ie, multi-step distribution function of the probability density. Simulate such a flow is difficult, therefore, find ways to simplify the description of the flow. For example, consider the points of receipt of applications as a uniform flow, and after the moment of receipt of an application referred to a particular class and define its parameters. There is another approach: different types of applications are treated as separate independent threads. For each type is determined by the time of receipt of the application once, and in the survey that is sent to the application, which has a minimum time of admission.

To simulate heterogeneous flow systems can be divided into three classes.

  1. System has one or more channels and all channels can be evaluated any type of application display on fig. 5. Modeling of such systems does not cause difficulties and performed as a single or multi-channel system, taking into account the various parameters of the application served;
  2. The system for each type of application there is a single channel (single or multiple) display on fig. 6. Modeling of such systems is the same as for homogeneous flows, but first, a separator must be provided in accordance with the application type, and provide that these claims can be tested as each of its channel;
  3. Systems, in which types of applications and number of channels intertwined. When modeling such systems is necessary to provide distribution of the flow of applications through the appropriate channels. One option provides for the distribution of these flows to create an array of relevant parameters.

Figure 5 – In each application a separate channel

Figure 6 – Types of applications and number of channels intertwined

(animation: 5 frames, 6 cycles of repeating, 35 kilobytes)

In implementing the QS passengers the most suitable class is the second, where T e for each type of application has a separate channel.

Experimental studies

Subsystem is implemented in the Microsoft Visual Studio 2010 on in C#. In the experiments showed subsystem permissible deviation from the actual data that is sufficient to solve the problem.

Conclusions

Was the analysis of various modeling techniques. The main drawbacks of most methods is:

  1. restriction algorithm model leads to incomplete modeling of the transport of passengers.
  2. inability to simulate the task.

Algorithm with non-uniform flow and the specialized channels devoid of these shortcomings and is fully suited for the task.

To find the optimum solution used genetic algorithms in the selection of model parameters, but it increases the resources expended in the simulation, since the selection of parameters depends on the capacity of the hardware and the optimization algorithm, it may take a long time.

Currently, there are several implementations of this method, however, the subsystems include a variety of methods of modeling because of what the cost increases, or the software can not adapt to the task.

List of sources

  1. Светличная В.А. Моделирование систем. [Текст] В.А. Светличная 2009. – 36 c.
  2. Stratum. Моделируй свою реальность. – 1998–2011. – [Электронный ресурс]. – Режим доступа: http://stratum.ac.ru/textbooks/modelir/lection30.html.
  3. Элементы теории массового обслуживания. – 1998–2011. – [Электронный ресурс]. – Режим доступа: http://edu.dvgups.ru/METDOC/EKMEN/ETR/WEBUMK/frame/4.htm.
  4. Советов Б.Я.. Яковлев С.А. «Моделирование систем» [Текст] Б.Я. Советов, С.А. Яковлев. Учебное пособие 3-е юд., перераб. и доп. 2001.
  5. Бусленко Н. П.. Моделирование сложных систем. М.: Наука, 1978, 400 с.
  6. Лоу Аверил М., Кельтн В. Девид «Имитационное моделирование» [Текст] М. Лоу Аверил, В. Девид Кельтн. Питер, Издат.группа BHV 2004 – 848 с.
  7. Поляк, Ю. Г. Вероятностное моделирование на ЭВМ [Текст] / Ю.Г. Поляк. – М. : Сов. Радио, 1971. – 400 с.
  8. Лекции по моделированию систем – 2009–2011. – [Электронный ресурс]. – Режим доступа: http://www.studfiles.ru/dir/cat32/subj1235/file11058/view112484/page1.html.
  9. Математические методы моделирования экономических систем [Текст] Бережная Е.В., Бережной В.И. 2-е изд., перераб. и доп. – М.: Финансы и статистика, 2006. – 432 с.
  10. Методы математического моделирования: Учебное пособие [Текст] Умнов А.Е. 3-е издание, испр. и доп – М.: МФТИ, 2012 – 295 с.

Notes

When writing this master of the abstract work is not yet complete. Final completion: December 1, 2012 Full text of the work and materials on the subject may be obtained from the author or his head after that date.