Cost-optimization Algorithm Comparison for Fresh Crop Transportation in Sri Lanka

Cost-optimization Algorithm Comparison for Fresh Crop Transportation in Sri Lanka. Considered Genetic Algorithm,
Ant Colony Optimization and Simulated Annealing.

1. Cost-optimization Algorithm Comparison for Fresh Crop Transportation in Sri Lanka

2. Outline Introduction Objectives Methodology Results Conclusion

3. Introduction Final Year Project : Digital Agricultural Marketplace between farmers, large scale buyers and transportation providers Transportation optimization is needed to overcome issues such as time waste, waste of product due to transportation problems and the cost.

4. Objectives Identify the best optimization method for minimizing the transportation cost We have compared three optimization algorithms through out our research, which are listed below. Genetic Algorithm Ant Colony Optimization Simulated Annealing

5. Methodology Selecting the Algorithms 1 Creating a Model 2 Selecting Test Instance 3 Running each Algorithm 4 Evaluating Results 5 Selecting the best possible algorithm 6

6. Methodology This is a Capacitated Vehicle Routing Problem (CVRP) A fleet of vehicles with known capacity should deliver items to customers with known demand.

7. Model Methodology

8. Genetic Algorithm One of the most applied methods in the optimization field. The genetic algorithm has based on the mechanics of natural selection and genetics. There are 5 main steps

9. Ant Colony Optimization Ant colony optimization is developed by observing the behavioral characteristics of ant colonies. Three main steps are identified in ACO. A B wikipedia.org Adaptation Cooperation Daemon actions (Optional)

10. If we consider an ant on one node, probability of the ant visiting the next node depends on two factors. Ant Colony Optimization A B wikipedia.org Attractiveness of the edge Pheromone level of the edge

11. Simulated Annealing A probabilistic technique for approximating the global optimum of a given function. Name comes from annealing in metallurgy A technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects.

12. We have found solutions to benchmark CVRP instance E-n33-k4, where 33 nodes (1st one is the depot) are present and 4 vehicles are used to deliver to customers with various demands. Capacity of a vehicle is considered to be fixed. Test Instance

13. Test Instance 1 2 700 3 400 4 400 5 1200 6 40 7 80 8 2000 9 900 10 600 11 750 12 1500 13 150 14 250 15 1600 16 450 17 700 18 550 19 650 20 200 21 400 22 300 23 1300 24 700 25 750 26 1400 27 4000 28 600 29 1000 30 500 31 2500 32 1700 33 1100 Demands

14. Genetic Algorithm Results

15. Genetic Algorithm 116 → 27 → 25 → 24 → 21 → 22 → 19 → 14 55 → 11 → 20 → 23 → 26 → 18 → 15 → 2 44 → 6 → 7 → 8 → 10 → 9 → 33 → 12 → 13 → 3 331 → 30 → 29 → 17 → 28 → 32 Results

16. Results Ant Colony Optimization

17. Results 19 → 20 → 22 → 21 → 23 → 25 → 24 → 26 → 18 → 16 4 → 3 → 13 → 12 → 33 → 9 → 10 → 11 → 7 → 8 → 6 17 → 28 → 27 → 29 → 30 31 → 32 → 15 → 2 → 14 → 5 Ant Colony Optimization

18. Results Simulated Annealing

19. Results Simulated Annealing 31 → 27 → 2 3 → 13 → 19 → 22 → 23 → 21 → 24 → 25 → 28 → 17 → 29 → 30 4 → 12 → 33 → 11 → 9 → 8 → 5 32 → 15 → 16 → 18 → 26 → 20 → 14 → 10 → 7 → 6

20. Simulated Annealing Genetic Algorithm Ant Colony Optimization Algorithm Total Distance Computational time(s) Ant Colony Optimization 885.74 34.850 Genetic Algorithm 897.50 34.523 Simulated Annealing 890.00 11.710 Results

21. Conclusion As our main objective we have focused on the minimizing the transportation cost by optimizing the route selection. After the implementations we have got results as the lowest total distance is given by Ant Colony optimization with a value of 885.74

22. Conclusion When considering the computational cost Simulated Annealing has the lowest value. But compared to the computational cost, total distance is more significant as the cost for a unit increase causes a higher increase in transportation cost. According to the results, we can conclude that Ant Colony Optimization is the most suitable algorithm from these three algorithms.

23. Thank You