Top

Soft Computing

Published in:

18-03-2016 | Methodologies and Application

A discrete firefly algorithm to solve a rich vehicle routing problem modelling a newspaper distribution system with recycling policy

Authors: Eneko Osaba, Xin-She Yang, Fernando Diaz, Enrique Onieva, Antonio D. Masegosa, Asier Perallos

Published in: Soft Computing | Issue 18/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A real-world newspaper distribution problem with recycling policy is tackled in this work. To meet all the complex restrictions contained in such a problem, it has been modeled as a rich vehicle routing problem, which can be more specifically considered as an asymmetric and clustered vehicle routing problem with simultaneous pickup and deliveries, variable costs and forbidden paths (AC-VRP-SPDVCFP). This is the first study of such a problem in the literature. For this reason, a benchmark composed by 15 instances has been also proposed. In the design of this benchmark, real geographical positions have been used, located in the province of Bizkaia, Spain. For the proper treatment of this AC-VRP-SPDVCFP, a discrete firefly algorithm (DFA) has been developed. This application is the first application of the firefly algorithm to any rich vehicle routing problem. To prove that the proposed DFA is a promising technique, its performance has been compared with two other well-known techniques: an evolutionary algorithm and an evolutionary simulated annealing. Our results have shown that the DFA has outperformed these two classic meta-heuristics.

previous article Modeling and minimizing information distortion in information diffusion through a social network

next article Assessing users’ emotion at interaction time: a multimodal approach with multiple sensors

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

http://umap.openstreetmap.fr.

http://research.mobility.deustotech.eu/media/publication_resources/Instances_Osaba_AC-VRP-SPDVCFP.rar.

Amorim P, Parragh SN, Sperandio F, Almada-Lobo B (2014) A rich vehicle routing problem dealing with perishable food: a case study. Top 22(2):489–508MathSciNetCrossRefMATH

Archetti C, Doerner KF, Tricoire F (2013) A heuristic algorithm for the free newspaper delivery problem. Eur J Oper Res 230(2):245–257MathSciNetCrossRefMATH

Atashpaz-Gargari E, Lucas C (2007) Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. In: IEEE congress on evolutionary computation, pp 4661–4667

Battarra M, Erdogan G, Vigo D (2014) Exact algorithms for the clustered vehicle routing problem. Oper Res 62(1):58–71MathSciNetCrossRefMATH

Boonkleaw A, Suthikarnnarunai N, Srinon R (2009) Strategic planning and vehicle routing algorithm for newspaper delivery problem: case study of morning newspaper, Bangkok, Thailand. In: Proceedings of the world congress on engineering and computer science, 2:1067–1071

Bortfeldt A, Hahn T, Männel D, Mönch L (2015) Hybrid algorithms for the vehicle routing problem with clustered backhauls and 3d loading constraints. Eur J Oper Res 243(1):82–96MathSciNetCrossRefMATH

Caceres-Cruz J, Arias P, Guimarans D, Riera D, Juan AA (2014) Rich vehicle routing problem: survey. ACM Comput Surv (CSUR) 47(2):32CrossRef

Campbell A, Clarke L, Kleywegt A, Savelsbergh M (1998) The inventory routing problem. In: Fleet management and logistics. Springer, New York, pp 95–113

Cao B, Glover F, Rego C (2015) A tabu search algorithm for cohesive clustering problems. J Heurist 21(4):457–477CrossRef

Chisman JA (1975) The clustered traveling salesman problem. Comput Oper Res 2(2):115–119CrossRef

de Armas J, Melián-Batista B, Moreno-Pérez JA, Brito J (2015) Gvns for a real-world rich vehicle routing problem with time windows. Eng Appl Artif Intell 42:45–56CrossRef

De Jong K (1975) Analysis of the behavior of a class of genetic adaptive systems. PhD thesis, University of Michigan, Michigan

Derrac J, García S, Molina D, Herrera F (2011) A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evolut Comput 1(1):3–18CrossRef

Dorigo M, Blum C (2005) Ant colony optimization theory: a survey. Theor Comput Sci 344(2):243–278MathSciNetCrossRefMATH

Fister I, Fister I Jr, Yang XS, Brest J (2013) A comprehensive review of firefly algorithms. Swarm Evolut Comput 13:34–46CrossRef

Fister I, Yang XS, Fister D, Fister Jr. I (2014) Firefly algorithm: a brief review of the expanding literature. In: Cuckoo search and firefly algorithm. Springer, New York, pp 347–360

Geem ZW, Kim JH, Loganathan G (2001) A new heuristic optimization algorithm: harmony search. Simulation 76(2):60–68CrossRef

Glover F (1989) Tabu search, part i. ORSA J Comput 1(3):190–206CrossRefMATH

Goldberg D (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley Professional, BostonMATH

Golden BL, Wasil EA (1987) Or practice computerized vehicle routing in the soft drink industry. Oper Res 35(1):6–17CrossRef

Haghani A, Jung S (2005) A dynamic vehicle routing problem with time-dependent travel times. Comput Oper Res 32(11):2959–2986CrossRefMATH

Herrero R, Rodríguez A, Cáceres-Cruz J, Juan AA (2014) Solving vehicle routing problems with asymmetric costs and heterogeneous fleets. Int J Adv Oper Manag 6(1):58–80

Hurter AP, Van Buer MG (1996) The newspaper production/distribution problem. J Bus Log 17:85–107

İnkaya T, Kayalıgil S, Özdemirel NE (2015) Ant colony optimization based clustering methodology. Appl Soft Comput 28:301–311CrossRef

Jati GK et al (2011) Evolutionary discrete firefly algorithm for travelling salesman problem, Volume 6943. Springer, New York

Kallehauge B, Larsen J, Madsen OB, Solomon MM (2005) Vehicle routing problem with time windows. Springer, New YorkCrossRefMATH

Kennedy J, Eberhart R et al (1995) Particle swarm optimization. In: Proceedings of IEEE international conference on neural networks. Volume 4, Perth, pp 1942–1948

Kirkpatrick S, Gellat C, Vecchi M (1983) Optimization by simmulated annealing. Science 220(4598):671–680MathSciNetCrossRefMATH

Lahyani R, Khemakhem M, Semet F (2015) Rich vehicle routing problems: from a taxonomy to a definition. Eur J Oper Res 241(1):1–14MathSciNetCrossRefMATH

Lahyani R, Coelho LC, Khemakhem M, Laporte G, Semet F (2015) A multi-compartment vehicle routing problem arising in the collection of olive oil in tunisia. Omega 51:1–10CrossRef

Laporte G, Mercure H, Nobert Y (1986) An exact algorithm for the asymmetrical capacitated vehicle routing problem. Networks 16(1):33–46MathSciNetCrossRefMATH

Li J, Pardalos PM, Sun H, Pei J, Zhang Y (2015) Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups. Exp Syst Appl 42(7):3551–3561CrossRef

Liang RH, Wang JC, Chen YT, Tseng WT (2015) An enhanced firefly algorithm to multi-objective optimal active/reactive power dispatch with uncertainties consideration. Int J Electr Power Energy Syst 64:1088–1097CrossRef

Marinakis Y, Marinaki M, Spanou P (2015) A memetic differential evolution algorithm for the vehicle routing problem with stochastic demands. In: Adaptation and hybridization in computational intelligence. Springer, New York, pp 185–204

Ma Y, Zhao Y, Wu L, He Y, Yang XS (2015) Navigability analysis of magnetic map with projecting pursuit-based selection method by using firefly algorithm. Neurocomputing 159:288–297CrossRef

Montané FAT, Galvao RD (2006) A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Comput Oper Res 33(3):595–619MathSciNetCrossRefMATH

Moscato P, Cotta C (2003) A gentle introduction to memetic algorithms. In: Handbook of metaheuristics. Springer, New York, pp 105–144

Nagata Y, Bräysy O, Dullaert W (2010) A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Comput Oper Res 37(4):724–737CrossRefMATH

Nalepa J, Blocho M (2015a) Co-operation in the parallel memetic algorithm. Int J Parall Progr 43(5):812–839CrossRef

Nalepa J, BlochoM (2015b) Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows. Soft Comput. doi:10.1007/s00500-015-1642-4

Qi Y, Hou Z, Li H, Huang J, Li X (2015) A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows. Compute Oper Res 62:61–77MathSciNetCrossRefMATH

Ree S, Yoon BS (1996) A two-stage heuristic approach for the newspaper delivery problem. Comput Ind Eng 30(3):501–509CrossRef

Rodriguez A, Gutierrez A, Rivera L, Ramirez L (2015) Rwa: comparison of genetic algorithms and simulated annealing in dynamic traffic. In: Advanced computer and communication engineering technology. Springer, New York, pp 3–14

Toth P, Vigo D (1999) A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls. Eur J Oper Res 113(3):528–543CrossRefMATH

Toth P, Vigo D (2002) The vehicle routing problem. Society for Industrial and Applied Mathematics, PhiladelphiaCrossRefMATH

Van Buer MG, Woodruff DL, Olson RT (1999) Solving the medium newspaper production/distribution problem. Eur J Oper Res 115(2):237–253CrossRefMATH

Vidal T, Crainic TG, Gendreau M, Lahrichi N, Rei W (2012) A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Oper Res 60(3):611–624MathSciNetCrossRefMATH

Vidal T, Crainic TG, Gendreau M, Prins C (2013) Heuristics for multi-attribute vehicle routing problems: a survey and synthesis. Eur J Oper Res 231(1):1–21MathSciNetCrossRefMATH

Vidal T, Crainic TG, Gendreau M, Prins C (2013) A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Comput Oper Res 40(1):475–489MathSciNetCrossRefMATH

Vidal T, Battarra M, Subramanian A, Erdogan G (2014) Hybrid metaheuristics for the clustered vehicle routing problem. Comput Oper Res 58(1):87–99

Villeneuve D, Desaulniers G (2005) The shortest path problem with forbidden paths. Eur J Oper Res 165(1):97–107MathSciNetCrossRefMATH

Wang C, Mu D, Zhao F, Sutherland JW (2015) A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup-delivery and time windows. Comput Ind Eng 83:111–122CrossRef

Yang XS (2009) Firefly algorithms for multimodal optimization. In: Stochastic algorithms: foundations and applications. Springer, New York, pp 169–178

Yang XS (2010) A new metaheuristic bat-inspired algorithm. In: Nature inspired cooperative strategies for optimization. Springer, New York, pp 65–74

Yang XS (2008) Nature-inspired metaheuristic algorithms. Luniver press, London

Yip PP, Pao YH (1995) Combinatorial optimization with use of guided evolutionary simulated annealing. IEEE Trans Neural Netw 6(2):290–295CrossRef

Zhang Z, Che O, Cheang B, Lim A, Qin H (2013) A memetic algorithm for the multiperiod vehicle routing problem with profit. Eur J Oper Res 229(3):573–584CrossRefMATH

Zhou L, Ding L, Qiang X (2014) A multi-population discrete firefly algorithm to solve tsp. In: Bio-inspired computing-theories and applications. Springer, New York, pp 648–653

Zouache D, Nouioua F, Moussaoui A (2015) Quantum-inspired firefly algorithm with particle swarm optimization for discrete optimization problems. Soft Comput. doi:10.1007/s00500-015-1681-x

Title: A discrete firefly algorithm to solve a rich vehicle routing problem modelling a newspaper distribution system with recycling policy
Authors: Eneko Osaba
Xin-She Yang
Fernando Diaz
Enrique Onieva
Antonio D. Masegosa
Asier Perallos
Publication date: 18-03-2016
Publisher: Springer Berlin Heidelberg
Published in: Soft Computing / Issue 18/2017
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-016-2114-1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 18/2017

The Problem Aware Local Search algorithm: an efficient technique for permutation-based problems

Simulated annealing based GRASP for Pareto-optimal dissimilar paths problem

Randomly attracted firefly algorithm with neighborhood search and dynamic parameter adjustment mechanism

A robust algorithm of support vector regression with a trimmed Huber loss function in the primal

An approach for solving a fuzzy bilevel programming problem through nearest interval approximation approach and KKT optimality conditions

Special issue on “Innovative approaches of softcomputing to networking systems and applications”

Premium Partner