Development of the computerized system of optimum allocation and delivery of medical products
Paper objectives and tasks
Purpose of creation system being developed is to improve the economic efficiency of freight transport in a warehouse of a pharmaceutical company by: increase in the average load of a flight, increasing traffic volumes, determining the order of loading the goods into the truck, increasing the number of points of delivery and speed of delivery, as well as minimizing the number of vehicles for transportation. Also, if you use this system will accelerate the process of route compilation by manager.
Next problems have been formulated:
· To characterize the object and to assess the requirements for the developed system
· Analyze the methods, models, algorithms and tools to build and optimize routes goods delivery
· Make a choice and justification of the method to accomplish the objective
· Develop and implement a software algorithm for building optimal route of drug delivery
Justification of paper topicality
Nowadays cargo transportation is an integral part of society. Cargo can be transported to any location, regardless of their size and dimensions.
Automating the building routes is a necessity for the company during its growth. Implementing such a system is cost-effective solution, as it accelerates the process of the controller, minimizes the influence of human factors ,leads to a reduction in idle cars for loading and unloading ,the efficient use of rolling stock . The result is a decrease in the time storing goods in regard with planning of replenishment stock.
Thus the formation of optimal routes and vehicle load schemes helps synchronize the warehouse, retail outlets and vendors, which ensures continuity of the delivery process.
Ant algorithm
The idea of the ant algorithm - modeling of the ants behavior associated with their ability to quickly find the shortest path from the nest to a food source and to adapt to changing conditions, finding a new shortest path. This is an elementary rule the ants behavior and determine the ability to find a new path, if the old is not available.
Picture 1 - Scheme of the ant algorithm
The problem is formulated as a problem of finding a minimum cost closed path for all tops without repetitions in a complete weighted graph with n vertices. Informally vertices are points that should visit the car, and weights of the edges reflect the distance of travel. This problem is NP-hard, and precise search algorithms for its solution has factorial complexity.
Taking into account of the problem selection rules the way by ant are described as follows:
1.1. The ants have their own "memory ". Because each city can be visited only once, then each ant has a list of already visited cities - a list of bans. Denote by Jik list of cities to be visited ant k, located in the city i.
2. 2. Ants have the "vision" - the visibility is heuristic desire to visit the city j, if the ant is in city i. We assume that the visibility is inversely proportional to the distance between cities ηij=1/Dij.
3. 3. Ants have the "smell" - they can catch the trail pheromone, which confirming the desire to visit the city j from the city i based on the experience of other . Amount of pheromone on edge (i, j) at time t is denoted byτij(t) .
4. 4. On this basis we can formulate a probability-proportional rule that determines the transition probability k-th ant from city i to city j:
, (1)
Where α, β-parameters for specifying the weight of pheromone trail. When α = 0, the algorithm degenerates to the greedy algorithm (to be selected the nearest town). Note that the choice of a probabilistic, rule (1) only determines the width of the zone of the city j; the total area of all cities Jik throws a random number that determines the choice of an ant. Rule (1) does not change during the algorithm, but in two different ants value of the transition probability will be different because they have a different list of acceptable cities
5. 5. Having an edge (i, j), an ant lays on him a certain amount of pheromone, which should be associated with the optimal choices made. Let Tk(t) the route taken by the ant k at time t; Lk(t) – the length of this route, and Q - order of the optimal path. Then deferrable amount of pheromone can be defined as:
, (2)
The rules of the environment determine the evaporation of pheromone. Let p = [0,1] the coefficient of evaporation, while evaporation rule has the form:
,(3)
where m – ant count.
At the beginning of the algorithm the number of pheromone on the edges is assumed to be a small positive number. The total number of ants is constant and equal to the number of cities, each ant starts the route from your city.
Conclusion
As a result of this work have been collected and studied materials on cargo routing problem. Were tested methods and algorithms for optimizing the routing of vehicles, as well as works of companies, offering comprehensive and software tools for the integration and optimization of their basic functionality.