Christian Blum Gabriela Ochoa (Eds.) 0 0 6 8 Evolutionary Computation S C in Combinatorial Optimization N L 14th European Conference, EvoCOP 2014 Granada, Spain, April 23–25, 2014 Revised Selected Papers 123 Lecture Notes in Computer Science 8600 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen TUDortmundUniversity,Germany DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum MaxPlanckInstituteforInformatics,Saarbruecken,Germany Christian Blum Gabriela Ochoa (Eds.) Evolutionary Computation in Combinatorial Optimization 14th European Conference, EvoCOP 2014 Granada, Spain, April 23-25, 2014 Revised Selected Papers 1 3 VolumeEditors ChristianBlum IKERBASQUE,BasqueFoundationforScience UniversityoftheBasqueCountry DepartmentofComputerScienceandArtificialIntelligence PaseoManuelLardizabal1,20018SanSebastian,Spain E-mail:[email protected] GabrielaOchoa UniversityofStirling,SchoolofNaturalSciences DepartmentofComputingScienceandMathematics CottrellBuilding,StirlingFK94LA,UK E-mail:[email protected] CoverillustrationdesignedbyLauraPirovano. ISSN0302-9743 e-ISSN1611-3349 ISBN978-3-662-44319-4 e-ISBN978-3-662-44320-0 DOI10.1007/978-3-662-44320-0 SpringerHeidelbergNewYorkDordrechtLondon LibraryofCongressControlNumber:2014944311 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ©Springer-VerlagBerlinHeidelberg2014 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection withreviewsorscholarlyanalysisormaterialsuppliedspecificallyforthepurposeofbeingenteredand executedonacomputersystem,forexclusiveusebythepurchaserofthework.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheCopyrightLawofthePublisher’slocation, inistcurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Permissionsforuse maybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violationsareliabletoprosecution undertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Whiletheadviceandinformationinthisbookarebelievedtobetrueandaccurateatthedateofpublication, neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityforanyerrorsor omissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,withrespecttothe materialcontainedherein. Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface During past decades, metaheuristic algorithms have been shown to be provenly effective for a wide range of hard combinatorial optimization problems arising in a variety of industrial, economic, and scientific settings. Well-known exam- ples of metaheuristics include, but are not limited to, ant colony optimization, evolutionary algorithms, greedy randomized adaptive search procedures, iter- ated local search, simulated annealing, tabu search and variable neighborhood search.Metaheuristicshavebeenappliedtomanydifferenttypesofoptimization problems,includingscheduling,timetabling,networkdesign,transportationand distribution,vehiclerouting,packingandcutting, satisfiabilityandgeneralinte- ger linear programing. The series of EvoCOP events is dedicated, in particular, to algorithmic advances in this field of research. The firsteditionofEvoCOPwasheldin 2001.Since then the eventhasbeen heldannually.Noteably,EvoCOPwasthefirsteventspecificallydedicatedtothe application of evolutionary computation and related methods to combinatorial optimization problems. Originally held as a workshop, EvoCOP eventually be- cameaconferencein2004.Pasteventsgaveresearchersanexcellentopportunity to present their latest research and to discuss current developments and appli- cations.Followingthe generaltrendofthe disappearanceofboundariesbetween different metaheuristics, EvoCOP has broadened its scope in recent years and hassolicitedpapersonanykindofmetaheuristicforcombinatorialoptimization. This volume contains the proceedings of EvoCOP 2014, the 14th European ConferenceonEvolutionaryComputationinCombinatorialOptimization.Itwas heldinGranada,Spain,duringApril23–25,2014,jointlywithEuroGP2014,the 17thEuropeanConferenceonGeneticProgramming,EvoBIO2014,the12thEu- ropean Conference on Evolutionary Computation, Machine Learning and Data Mining in Computational Biology, EvoMUSART 2014, the Third International Conference on Evolutionary and Biologically Inspired Music, Sound, Art and Design,andEvoApplications2014(formerlyEvoWorkshops),whichconsistedof 13individualtracksrangingfromcomplexsystemsoverevolutionaryalgorithms in energy applications to evolutionary robotics. Since 2007, all these events are grouped under the collective name EvoStar, and constitute Europe’s premier co-located event on evolutionary computation and metaheuristics. Accepted papers of previous EvoCOP editions were published by Springer in the series Lecture Notes in Computer Science (LNCS – Volumes 2037, 2279, 2611, 3004, 3448, 3906, 4446, 4972, 5482, 6022, 6622, 7245, 7832). Below we report statistics for each conference. VI Preface EvoCOP submitted accepted acceptanceratio 2001 31 23 74.2% 2002 32 18 56.3% 2003 39 19 48.7% 2004 86 23 26.7% 2005 66 24 36.4% 2006 77 24 31.2% 2007 81 21 25.9% 2008 69 24 34.8% 2009 53 21 39.6% 2010 69 24 34.8% 2011 42 22 52.4% 2012 48 22 45.8% 2013 50 23 46.0% 2014 42 20 47.6% The rigorous, double-blind reviewing process of EvoCOP 2014 resulted in the selection of 20 out of 42 submitted papers; the acceptance rate was 47.6%. Eventhoughslightlylower,the numberofsubmissionswasinline withprevious years, which is–given the current times of crisis and limited funding–a rather remarkable achievement. At this point we would like to emphasize the work of theProgramCommittee.Infact,thededicatedworkofourProgramCommittee membersisessentialforthecontinuingsuccessofEvoCOP.Wewouldalsoliketo mentionthatacceptance/rejectiondecisionswerenotonlybasedonthereceived referee reports but also on a personal evaluation of the program chairs. There are various persons and institutions that contributed to the success of the conference and to whom we would like to express our appreciation. First of all, we thank the local organizers of EvoStar 2014, J.J. Merelo and his team, from the University of Granada. They did an extraordinary job. Furthermore, we would like to thank Marc Schoenauer from Inria (France) for his continu- ing support concerning the MyReview conference management system. We also thank Kevin Sim from Edinburgh Napier University, Mauro Castelli from the Universidade Nova de Lisboa and Pablo Garc´ıa S´anchez from the University of Granada for an excellent web site and publicity material. Thanks are also due to Jennifer Willies and the Institute for Informatics and Digital Innovation at Napier Universityin Edinburgh, Scotland, for administrative supportandevent coordination. Finally, we gratefully acknowledge the University of Granada for its support to EvoStar. Last, but not least, we would like to thank Carlos Cotta, Peter Cowling, Jens Gottlieb, Jin-KaoHao, Jano van Hemert, Peter Merz, Martin Middendorf, and Gu¨nther R. Raidl for their hard work and dedication at past editions of EvoCOP,whichcontributedtomakingthisconferenceoneofthereferenceevents in evolutionary computation and metaheuristics. May 2014 Christian Blum Gabriela Ochoa Organization EvoCOP 2014 was organized jointly with EuroGP 2014, EvoBIO 2014, EvoMUSART 2014, and EvoApplications 2014. Organizing Committee PC Chairs Christian Blum IKERBASQUE University of the Basque Country, Spain Gabriela Ochoa University of Stirling, UK Local Organization Juan J. Merelo University of Granada, Spain The whole organizer team of the University of Granada Publicity Chairs Kevin Sim University of Edinburgh, UK Mauro Castelli Universidade Nova de Lisboa, Portugal Pablo Garc´ıa S´anchez University of Granada, Spain EvoCOP Steering Committee Carlos Cotta Universidad de Ma´laga, Spain Peter Cowling University of York, UK Jens Gottlieb SAP AG, Germany Jin-Kao Hao University of Angers, France Jano van Hemert University of Edinburgh, UK Peter Merz Hannover University of Applied Sciences and Arts, Germany Martin Middendorf University of Leipzig, Germany Gu¨nther Raidl Vienna University of Technology, Austria Program Committee Adnan Acan Eastern Mediterranean University, Turkey Hern´an Aguirre Shinshu University, Japan Enrique Alba Universidad de Ma´laga, Spain VIII Organization Mehmet Emin Aydin University of Bedfordshire, UK Ruibin Bai University of Nottingham, UK Thomas Bartz-Beielstein Cologne University of Applied Sciences, Germany Maria Blesa Universitat Polit`ecnica de Catalunya, Spain Christian Blum IKERBASQUE and University of the Basque Country, Spain Sandy Brownlee University of Stirling, UK Rafael Caballero University of M´alaga, Spain Alexandre Caminada UTBM, France Pedro Castillo Universidad de Granada, Spain Jos´e Francisco Chicano Garcia Universidad de M´alaga, Spain Carlos Coello Coello CINVESTAV-IPN, Mexico Peter Cowling University of York, UK Keshav Dahal University of the West of Scotland, UK Karl Doerner Johannes Kepler University Linz, Austria Benjamin Doerr LIX, Ecole Polytechnique, France Anton V. Eremeev Omsk Branch of Sobolev Institute of Mathematics, Russia Francisco Fern´andez de Vega University of Extremadura, Spain Bernd Freisleben University of Marburg, Germany Philippe Galinier Ecole Polytechnique de Montreal, Canada Adrien Goeffon University of Angers, France Jens Gottlieb SAP, Germany Walter Gutjahr University of Vienna, Austria Jin-Kao Hao University of Angers, France Richard F. Hartl University of Vienna, Austria Emma Hart Edinburgh Napier University, UK Geir Hasle SINTEF Applied Mathematics, Norway Istva´n Juhos University of Szeged, Hungary Graham Kendall University of Nottingham, UK Joshua Knowles University of Manchester, UK Mario K¨oppen Kyushu Institute of Technology, Japan Jozef Kratica University of Belgrade, Serbia Fr´ed´eric Lardeux University of Angers, France Rhyd Lewis Cardiff University, UK Arnaud Liefooghe Universit´edesSciencesetTechnologiesdeLille, France Jos´e Antonio Lozano University of the Basque Country, Spain Zhipeng Lu HUST, China Penousal Machado University of Coimbra, Portugal Dirk C. Mattfeld University of Braunschweig, Germany Barry McCollum Queen’s University Belfast, UK Juan Julia´n Merelo University of Granada, Spain Organization IX Peter Merz Hannover University of Applied Sciences and Arts, Germany Martin Middendorf Universit¨at Leipzig, Germany Julian Molina University of M´alaga, Spain Antonio Mora University of Granada, Spain Pablo Moscato The University of Newcastle, Australia Christine L. Mumford Cardiff University, UK Nysret Musliu Vienna University of Technology, Austria Yuichi Nagata Tokyo Institute of Technology, Japan Giuseppe Nicosia University of Catania, Italy Gabriela Ochoa University of Stirling, UK Beatrice Ombuki-Berman Brock University, Canada Mario Pavone University of Catania, Italy Francisco J.B. Pereira Universidade de Coimbra, Portugal Daniel Cosmin Porumbel University of Artois, France Jakob Puchinger Austrian Institute of Technology, Austria Gu¨nther Raidl Vienna University of Technology, Austria Marcus Randall Bond University, Queensland, Australia Marc Reimann Warwick Business School, UK Eduardo Rodriguez-Tello Civerstav - Tamaulipas, Mexico Andrea Roli Universita` degli Studi di Bologna, Italy Fr´ed´eric Saubion University of Angers, France Marc Schoenauer Inria, France Patrick Siarry Universit´e Paris-EstCr´eteil Val-de-Marne, France Kevin Sim Edinburgh Napier University, UK Jim Smith University of the West of England, UK Giovanni Squillero Politecnico di Torino, Italy Thomas Stu¨tzle Universit´e Libre de Bruxelles, Belgium El-ghazali Talbi Universit´edesSciencesetTechnologiesdeLille, France Kay Chen Tan National University of Singapore, Singapore Jorge Tavares Microsoft, Germany Jano van Hemert University of Edinburgh, UK Nadarajen Veerapen University of Stirling, UK Sebastien Verel Universit´e de Nice Sophia Antipolis, France Takeshi Yamada NTT Communication Science Laboratories, Japan Shengxiang Yang De Montfort University, UK Table of Contents A Hybrid Ant Colony Optimization Algorithm for the Far From Most String Problem .................................................. 1 Christian Blum and Paola Festa A Parametric Framework for Cooperative Parallel Local Search........ 13 Danny Munera, Daniel Diaz, Salvador Abreu, and Philippe Codognet A Survey of Meta-heuristics Used for Computing Maximin Latin Hypercube ...................................................... 25 Arpad Rimmel and Fabien Teytaud An Analysis of Parameters of irace ............................... 37 Leslie P´erez C´aceres, Manuel L´opez-Ib´an˜ez, and Thomas Stu¨tzle An Improved Multi-objective Algorithm for the Urban Transit Routing Problem ........................................................ 49 Matthew P. John, Christine L. Mumford, and Rhyd Lewis An Iterated Greedy Heuristic for Simultaneous Lot-Sizing and Scheduling Problem in Production Flow Shop Environments........... 61 Harlem M.M. Villadiego, Jos´e El´ıas C. Arroyo, and Andr´e Gustavo dos Santos Balancing Bicycle Sharing Systems: An Approach for the Dynamic Case ........................................................... 73 Christian Kloimu¨llner, Petrina Papazek, Bin Hu, and Gu¨nther R. Raidl Cooperative Selection: Improving Tournament Selection via Altruism... 85 Juan Luis Jim´enez Laredo, Sune S. Nielsen, Gr´egoire Danoy, Pascal Bouvry, and Carlos M. Fernandes Diversity-Driven Selection of Multiple Crossover Operators for the Capacitated Arc Routing Problem........................... 97 Pietro Consoli and Xin Yao Dynamic Period Routing for a Complex Real-World System: A Case Study in Storm Drain Maintenance.......................... 109 Yujie Chen, Peter Cowling, and Stephen Remde Elementary Landscape Decomposition of the Hamiltonian Path Optimization Problem............................................ 121 Darrell Whitley and Francisco Chicano