The Use of Heuristic Algorithms to Optimize the Transport Issues on the Example of Municipal Services Companies

Mariusz Izdebski

doi:10.5604/08669546.1146961

Authors

Mariusz Izdebski Warsaw University of Technology Faculty of Transport, Warsaw, Poland Author

DOI:

https://doi.org/10.5604/08669546.1146961

Keywords:

municipal services companies, transport, optimization, genetic algorithm, ant algorithm

Abstract

In this article the main optimization problems in the municipal services companies were presented. These problems concern the issue of vehicle routing. The mathematical models of these problems were described. The function of criterion and the conditions on designating the vehicle routing were defined. In this paper the hybrid algorithm solving the presented problems was proposed. The hybrid algorithm consists of two heuristic algorithms: the ant and the genetic algorithm. In this paper the stages of constructing of the hybrid algorithm were presented. A structure of the data processed by the algorithm, a function of adaptation, a selection of chromosomes, a crossover, a mutation and an inversion were characterized. A structure of the data was presented as string of natural numbers. In selection process the roulette method was used and in the crossover process the operator PMX was presented. This algorithm was verified in programming language C #. The process of verification was divided into two stages. In the first stage the best parameters of the hybrid algorithm were designated. In the second stage the algorithm was started with these parameters and the result was compared with the random search algorithm. The random search algorithm generates 2000 routes and the best result is compared with the hybrid algorithm.

References

Atkin J., Burke Edmund K., Greenwood John S., Reeson D., Hybrid Metaheuristics to Aid Runway Scheduling at London Heathrow Airport. Transportation Science, Institute for Operations Research and the Management Sciences (INFORMS), Volume 41 Issue 1, pp. 90-106, USA 2007.

Abdoun O., Abouchabaka J., A Comparative Study of Adaptive Crossover Operators for Genetic Algorithms to Resolve the Traveling Salesman Problem. International Journal of Computer Applications, Foundation of Computer Science, Volume 31 - No. II, pp. 49-57, New York, USA , October 2011.

Bautista J., Fernandez E., Pereira J., Solving an urban waste collection problem using ants heuristics. Computers & Operations Research, Elsevier. Volume 35, Issue 9, pp. 3020-3033, USA 2008.

Bautista J., Pereira J., (2004) Ant algorithms for urban waste collection algorithms. Lecture Notes in Computer Science 3172: 302-309.

Belien J., Boeck L., Municipal Solid Waste Collection and Management Problems: A Literature Review, Transportation Science, Institute for Operations Research and the Management Sciences (INFORMS) Volume 48 Issue I, pp. 78-102, USA 2014.

Benjamin A.M, Beasley J.E, (2010) Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities. Comput. Oper. Res. 37:2270-2280.

Bräysy O., Gendreau M., Vehicle Routing Problem with Time Windows, Part II: Metaheuristics, Transportation Science, Institute for Operations Research and the Management Sciences (INFORMS). Volume 39 Issue 1, pp. 119-139, USA 2005.

Colomi A., Dorigo M., Manezzo V., Genetic Algorithms and Highly Constrained Problems: The Time-Table Case, Proceedings of the First International Conference on Parallel Problem Solving from Nature. Lecture Notes in Computer Science, Vol.496,Verlag,1991s. 55-59.

Dorigo M., Gambardela L.M., Ant Colony System: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, Vol.1(1) ( 1997), 53 - 66.

Dorigo M., Gambardela L.M., Ant Colonies for the Travelling Salesman Problem. BioSystems. Vol. 43 (1997). 73-81.

Dorigo M., Stutzle T., Ant Colony Optimization, Bradford Books, USA, 2004.

Goldberg D. E., Lingle R., Alleles Loci, and the TSP, Proceedings of the First International Conference on Genetic Algorithms, Lawrence Erlbaum Associates, Hillsdale, pp. 154-159, NJ 1985.

Goldberg D. E., Algorytmy genetyczne i ich zastosowanie. Wydawnictwo Naukowo - Techniczne. Warszawa 1995.

Grefenstette J., Gopal R., Rosmaita B., Van Gucht D., Genetic Algorithm for the TPS, Proceedings of the First International Conference on Genetic Algorithms, Lawrence Erlbaum Associates. Hillsdale, pp. 160-168. NJ 1985.

Grzymkowski R., Kaczmarek K., Kieltyka S., Nowak I., Wykłady z modelowania matematycznego. Wydawnictwo Pracowni Komputerowej Jacka Skalmierskiego, Gliwice 2008.

Izdebski M., Jacyna M., Some Aspects of the Application of Genetic Algorithm for Solving the Assignment Problem of Tasks to Resources in a Transport Company, Logistic and Transport, Vol. 21, No 1. pp. 13-20. Wrocław 2014.

Izdebski M., Jacyna M., The algorithm solving the problem of allocation of tasks to resources in the transport company. Conference Proceedings Carpathian Logistics Congres. (CD-ROM), Kraków 2013.

Jacyna, M., Modelowanie i ocena systemów transportowych. Oficyna Wydawnicza Politechniki Warszawskiej. Warszawa 2009.

Nagata Y., Kobayashi S., A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem, Transportation Science, Institute for Operations Research and the Management Sciences (INFORMS) Volume 25 Issue 2, pp. 346-363, USA 2013.

Ombuki-Berman B.M., Runka A., Hanshar F.T., (2007). Waste collection vehicle routing problem with time windows using multi¬objective genetic algorithms. Internat. Assoc. Sci. Tech. Development Proc. Third IASTED Internat. Conf. Computational Intelligence. Evolutionary Comput. (ACTA Press, Anaheim, CA), 91-97.

Płaczek E., Szołtysek J., Wybrane metody optymalizacji systemu transportu odpadów komunalnych w Katowicach, LogForum, Wyższa Szkoła Logistyki, Vol. 4, pp. 1-10, Poznań 2008.

Viotti P., Polettini A., Pomi R., Innocenti C., (2003), Genetic algorithms as a promising tool for optimisation of the MSW collection routes. Waste Management Res. 21:292- 298, 2014.

Michalewicz Z., Algorytmy genetyczne + struktury danych = programy ewolucyjne, Wydawnictwo Naukowo - Techniczne, Warszawa 1996.