Ant Colonies As Logistic Processes Optimizers Carlos A

1、Ant Colonies As Logistic Processes OptimizersOutlineAbstractIntroductionThe Logistic ProcessScheduling Using Ant ColonyStimulation Results and AnalysisReal work ExampleConclusionReferencesAbstractThe optimization of logistic processes using ant colonies. The analysis of the algorithm parameters is d

2、one in a simulation.It was applied to a real logistic process at Fujitsu-Siemens Computers.The results show that the ant colonies provide a better solution to logistic processes.Introduction What is Logistics? Planning, handling, and control of the storage of goods between the manufacturing point an

3、d the consumption point. cross-docking centers instead of stocks.The key issue is to deliver the goods in time by minimizing the stocks. The scheduling algorithm has to decide which goods are delivered to which customers.Centralized static scheduling vs. dynamic distributed scheduling The Logistic P

4、rocess Fig. 1. General representation of the logistic process The Logistic ProcessThe birth process (arrival of new orders). Poison distribution of the birth process:x : the random variable number of orderslambdaT : the probability of this event occur on a certain time T. The Logistic ProcessThe dea

5、th process (delivery of orders) is modeled by the exponential distribution.T: the random variable : the death rate.Process Description Order arrival. - order is a set of components ci and contain a desired delivery dateComponent request.- Each component has quantity.Component arrival. - supplier del

6、ay: time to be delivered to the logistic system. Process Description Component assignment. The focus of this paper -A component stock contains the available components and their quantity.-A order stock is waiting listOrder delivery -delay d is difference between the delivery date and the desired dat

7、e. Scheduling Policies Pre-assignment vs. dynamic decentralized approachPre-assignment (p.a.). Components are assigned to specific orders. Not efficientlyDistributed approach. The agents associated with orders and components exchange information between each other. More flexible than pre-assignmentS

8、cheduling Using Ant Colonies The optimization of the scheduling process is a NP-hard problem.The problems information can be translated into the pheromones, and used by all the interacting agents in order to achieve a good global solution. Scheduling Using Ant ColoniesTwo different set of entities:c

9、omponent food source order nest.m ants, one per food source, distribute the food to the n nests.In every iteration t of the algorithm, the ants have to choose with some probability p which is the nest to visit first. Then, they deposit a pheromone in the path from the food source to the nest. Schedu

10、ling Using Ant ColoniesEach ant delivers an amount qij from the total amount qi of component i 1, . . . , m to an order j 1, . . . , n. Since there are several nests to visit, the ant k chooses the path to a particular nest with a probability pScheduling Using Ant Colonies ij is the amount of pherom

11、one connecting i to j, nij is a visibility function Tk is the tabu list of the kth ant. This list contains all of the visited orders + the orders dont need component type. and express the relative importance of trail pheromone (experience) with visibility (knowledge)Scheduling Using Ant Coloniesdj i

12、s the delay of order j We try to have nij = 1.The local update of the pheromone concentration is then given bywhere c is small constant. Scheduling Using Ant ColoniesAt the end of a complete tour the change of pheromones in all paths is given bythe solution can be evaluated using a performance measu

13、ren is the number of orders and dj is the delay of order j. Scheduling Using Ant ColoniesFig. 2. Example of an ant colony applied to the logistic process with pheromone concentration level on the trails: High (), Medium (- -) and Low ()Scheduling Using Ant ColoniesAt each tour N of the algorithm (wh

14、ere each tour has n m iterations t), a z is computed and stored in the set Z = z(1), , z(N)If z(N) is higher than the previous z Z, then the actual solution has improved and the used pheromones should be increased. If it is worse, they should be reduced. Scheduling Using Ant ColoniesThis is done by

15、the global pheromone updateAlgorithmFig. 3. Ant colonies optimization algorithm for logistic processes Simulation Results Let lambdaT = 10;each order can have at the most 7 different types of components ci; the quantity for each component varies randomly between 1 and 20;each type of component has a

16、 constant supplier delay, which are 1, 3, 2, 3, 1, 2, 6 days for components type c1, , c7 respectively. For each order a desired date is generated using an exponential distribution with = 7. The simulation refers to an interval of 6 months. Simulation ResultsThe results are presented with the parame

17、ters = 1, = 10, p = 0.9 and Nmax = 20.Table 1. Comparison between the scheduling methods in number of ordersSimulation ResultsFig. 4. Histograms of the order delay d. Pre-assignment method (left) vs. the results for the ants (right). Ants:higher number of delivery on time (d=0)lower spread between m

18、ax and min delayTuning the Parameters The parameters and which are coupled between each other are changed at the same time, while others decoupled parameters remain constant. Varying and , using a fixed value p = 0.9. Tuning the ParametersFig. 5. Number of orders delivered for a fixed and varying an

19、d . Tuning the ParametersNumber of orders delivered on the correct date is high, if is small. It has an optimal value for = 1We can conclude that the parameter tunes the number of orders in the right dayand controls the spread around that value Tuning the ParametersEvaporation coefficient (1-p) p 0:

20、 the increment received by the new ants it will influence greatly the paths of the next antsp 1 the solution can rapidly stagnate. As it can be seen, the value of evaporation should be around 0.1 (p = 0.9), in order to achieve a good solutionFig. 6. Number of orders in the right day, for different s

21、ets of fixed and and varying pTuning the ParametersNumber of colonies per day Nmax. Fig. 7. Evolution of the solution for different number of coloniestoo few : not have enough iterations to find a good solutiontoo many: increased severely the computational cost.Real World Example The analysis presen

22、ted an optimized solution with = 1, = 0.5, p = 0.9, and Nmax = 20. In small data set of the dataFig. 8. Histograms of the orders delay d for the scheduling methodsReal World ExampleAnts: More orders are delivered on time. Less orders are delayedGood alternative to pre-assignment scheduling method !C

23、onclusionsTo apply in the ant colonies optimization algorithm to the optimization of logistic processes. Its explored the correlations between the parameters and their role in the algorithm. The results show how the analysis is able to improve the algorithm performance, and explain the reasons for that improvement. Finally, the algorithm was applied to a real data set, and the ant algorithm proved to be a better scheduling method than the pre-assignment.ConclusionsFuture work: The use of a different cost function z, The incorporation in the ants wit