2014
The 14th European Conference on Evolutionary Computation in Combinatorial Optimisation
April 23-25, 2014
Granada, Spain
Part of Evo* 2014 (http://www.evostar.org)
including: EuroGP, EvoCOP,
EvoBIO, EvoMUSART and
EvoApplications
The 14th European Conference on Evolutionary Computation in Combinatorial Optimisation is a multidisciplinary conference that brings together researchers working on metaheuristics for solving difficult combinatorial optimization problems appearing in various industrial, economic, and scientific domains. Prominent examples of metaheuristics include: evolutionary algorithms, simulated annealing, tabu search, scatter search and path relinking, memetic algorithms, ant colony and bee colony optimization, particle swarm optimization, variable neighbourhood search, iterated local search, greedy randomized adaptive search procedures, estimation of distribution algorithms, and hyperheuristics. Successfully solved problems include scheduling, timetabling, network design, transportation and distribution problems, vehicle routing, travelling salesman, graph problems, satisfiability, energy optimization problems, packing problems, planning problems, and general mixed integer programming.
The EvoCOP 2014 conference will be held in the city of Granada located in the south of Spain. It will be held in conjunction with EuroGP (the 17th European Conference on Genetic Programming), EvoBIO (the 12th European Conference on Evolutionary Computation, Machine Learning and Data Mining in Computational Biology), , EvoMUSART (12th European conference on evolutionary and biologically inspired music, sound, art and design) and EvoApplications (specialist events on a range of evolutionary computation topics and applications), in a joint event collectively known as Evo*.
For more information see the EvoCOP 2014 webpage
http://www.evostar.org/
Areas of Interest and Contributions
Topics of interest include, but are not limited to:
Applications of metaheuristics to combinatorial optimization problems
Novel application domains for metaheuristic optimisation methods
Representation techniques
Neighborhoods and efficient algorithms for searching them
Variation operators for stochastic search methods
Constraint-handling techniques
Hybrid methods and hybridization techniques
Parallelization
Theoretical developments
Search space and landscape analyses
Comparisons between different (also exact) techniques
Metaheuristics and machine learning
Ant colony optimisation
Artificial immune systems
Bee colony optimization
Genetic programming and Genetic algorithms
(Meta-)heuristics
Scatter search
Particle swarm optimisation
Tabu search, iterated local search and variable neighborhood search
Memetic algorithms and hyperheuristics
Estimation of distribution algorithms
String processing
Scheduling and timetabling
Network design
Vehicle routing
Graph problems
Satisfiability
Packing and cutting problems
Energy optimization problems
Practical solving of NP-hard problems
Mixed integer programming
Multi-objective optimisation
Grid computing
Combinatorial optimisation
Nature and Bio-inspired methods
Quantum computing and quantum annealing
Optimization in Cloud computing
Search-based software engineering
Publication Details
All accepted papers will be presented orally at the conference and printed in the proceedings published by Springer in the LNCS series (see LNCS volumes 2037, 2279, 2611, 3004, 3448, 3906, 4446, 4972, 5482, 6022, 6622, 7245 and 7832 for the previous proceedings).
Submission Details
Submissions must be original and not published elsewhere. The submissions will be peer reviewed by members of the program committee. The authors of accepted papers will have to improve their paper on the basis of the reviewers comments and will be asked to send a camera ready version of their manuscripts. At least one author of each accepted work has to register for the conference, attend the conference and present the work.
The reviewing process will be double-blind, please omit information about the authors in the submitted paper. Submit your manuscript in Springer LNCS format.
Submission link: http://myreview.csregistry.org/evocop14/
Page limit: 12 pages
Important Dates
Submission deadline: 1 November 2013 11 November 2013
Notification: 06 January 2014
Camera ready: 01 February 2014
Evo* event: April 23-25, 2014
EvoCOP Programme Chairs
- Christian Blum
IKERBASQUE, Basque Foundation for Science, Spain
christian.c.blum(at)gmail.com
- Gabriela Ochoa
University of Stirling, Scotland, UK
gabriela.ochoa(at)cs.stir.ac.uk
Programme Committee
adnan.acan(at)emu.edu.tr
Acan Adnan, Eastern Mediterranean University, Turkey
adrien.goeffon@univ-angers.fr
Goëffon Adrien, University of Angers, France
alexandre.caminada(at)utbm.fr
Caminada Alexandre, UTBM, France
andrea.roli(at)unibo.it
Roli Andrea, Università di Bologna, Italy
arnaud.liefooghe(at)univ-lille1.fr
Liefooghe Arnaud, Université Lille 1, France
b.mccollum(at)qub.ac.uk
McCollum Barry, Queen's University Belfast, UK
bombuki@brocku.ca
Ombuki-Berman Beatrice, Brock University, Canada
C.L.Mumford(at)cs.cardiff.ac.uk
Mumford Christine L., Cardiff University, UK
ccoello(at)cs.cinvestav.mx
Coello Coello Carlos, CINVESTAV-IPN, Mexico
chicano@lcc.uma.es
Chicano Francisco, Universidad de Málaga, Spain
christian.c.blum(at)gmail.com
Blum Christian, IKERBASQUE, Basque Foundation for Science, Spain
d.mattfeld(at)tu-bs.de
Mattfeld Dirk C., Technische Universität Braunschweig, Germany
daniel.porumbel(at)univ-artois.fr
Porumbel Daniel Cosmin, University of Artois, France
doerr(at)mpi-inf.mpg.de
Doerr Benjamin LIX, Ecole Polytechnique, France
eat(at)lcc.uma.es
Alba Enrique, Universidad de Málaga, Spain
E.Hart(at)napier.ac.uk
Emma Hart, Edinburgh Napier University, Scotland, UK
eletankc(at)nus.edu.sg
Tan Kay Chen, National University of Singapore, Singapore
ertello(at)tamps.cinvestav.mx
Rodriguez-Tello Eduardo, Civerstav - Tamaulipas, Mexico
fcofdez(at)unex.es
Fernández de Vega, Francisco, University of Extremadura, Spain
freisleb(at)informatik.uni-marburg.de
Freisleben Bernd, University of Marburg, Germany
Geir.Hasle(at)sintef.no
Hasle Geir, SINTEF Applied Mathematics, Norway
giovanni.squillero(at)polito.it
Squillero Giovanni, Politecnico di Torino, Italy
goc@cs.stir.ac.uk
Ochoa Gabriela, University of Stirling, Scotland, UK
gxk(at)cs.nott.ac.uk
Kendall Graham, University of Nottingham, UK
hao(at)info.univ-angers.fr
Hao Jin-Kao, Université d'Angers, Fance
j.knowles(at)manchester.ac.uk
Knowles Joshua, University of Manchester, UK
ja.lozano(at)ehu.es
Lozano José Antonio, University of the Basque Country, Spain
jakob.puchinger(at)arsenal.ac.at
Puchinger Jakob, Austrian Institute of Technology, Austria
James.Smith(at)uwe.ac.uk
Smith Jim, University of the West of England, UK
jano(at)vanhemert.co.uk
van Hemert Jano, University of Edinburgh, UK
jast(at)dei.uc.pt
Tavares Jorge, University of Coimbra, Portugal
jens.gottlieb(at)sap.com
Gottlieb Jens, SAP, Germany
jj(at)merelo.net
Merelo Juan Julián, University of Granada, Spain
jkratica(at)mi.sanu.ac.rs
Kratica Jozef, Serbian Academy of Sciences and Arts, Serbia
jorge.maturana(at)inf.uach.cl
Jorge Maturana, Universidad Austral de Chile, Chile
julian.molina(at)uma.es
Molina Julian, University of Málaga, Spain
keshav.dahal@uws.ac.uk
Dahal Keshav, University of the West of Scotland, UK
k.sim(at)napier.ac.uk
Sim Kevin, Edinburgh Napier University, UK
karl.doerner(at)univie.ac.at
Doerner Karl, Johannes Kepler University Linz, Austria
lardeux@info.univ-angers.fr
Lardeux Frédéric, University of Angers, France
lewisr9(at)Cardiff.ac.uk
Lewis Rhyd, Cardiff University, UK
machado(at)dei.uc.pt
Machado Penousal, University of Coimbra, Portugal
marc.reimann(at)uni-graz.at
Reimann Marc, University of Graz, Austria
Marc.Schoenauer(at)inria.fr
Schoenauer Marc, INRIA, France
mehmet.aydin(at)beds.ac.uk
Aydin Mehmet Emin, University of Bedfordshire, UK
meignan.david(at)gmail.com
David Meignan, University of Osnabruck, Germany
middendorf(at)informatik.uni-leipzig.de
Middendorf Martin, Universität Leipzig, Germany
mjblesa(at)lsi.upc.edu
Blesa Maria J., Technical University of Catalonia, Spain
mkoeppen(at)ieee.org
Köppen Mario, Kyushu Institute of Technology, Japan
mpavone(at)dmi.unict.it
Pavone Mario, University of Catania, Italy
mrandall(at)staff.bond.edu.au
Randall Marcus, Bond University, Queensland, Australia
musliu(at)dbai.tuwien.ac.at
Musliu Nysret, Vienna University of Technology, Austria
nagatay(at)jaist.ac.jp
Nagata Yuichi, Tokyo Institute of Technology, Japan
nicosia(at)dmi.unict.it
Nicosia Giuseppe, University of Catania, Italy
nve@cs.stir.ac.uk
Veerapen Nadarajen, University of Stirling, Scotland, UK
pedro(at)atc.ugr.es
Castillo Pedro, Universidad de Granada, Spain
peter.cowling(at)york.ac.uk
Cowling, Peter, University of York, UK
peter.merz(at)fh-hannover.de
Merz Peter, University of Applied Sciences and Arts Hannover, Germany
philippe-2.galinier(at)polymtl.ca
Galinier Philippe, Ecole Polytechnique de Montreal, Canada
pross(at)blueyonder.co.uk
Peter Ross, Edinburgh Napier University, UK
raidl(at)ads.tuwien.ac.at
Raidl Günther, Vienna University of Technology, Austria
research(at)juhos.info
Juhos István, University of Szeged, Hungary
Richard.Hartl(at)UniVie.ac.at
F. Hartl Richard, University of Vienna, Austria
rzb(at)cs.nott.ac.uk
Bai Ruibin, University of Nottingham, UK
saubion(at)info.univ-angers.fr
Frederic Saubion, University of Angers, France
sbr@cs.stir.ac.uk
Brownlee Sandy, University of Stirling, Scotland, UK
sebastien.verel(at)inria.fr
Verel Sebastien, Université du Littoral Côte d'Opale, France
syang(at)dmu.ac.uk
Yang Shengxiang, De Montfort University, UK
siarry(at)univ-paris12.fr
Siarry Patrick, University of Paris 12, France
stuetzle(at)ulb.ac.be
Stuetzle Thomas, Université Libre de Bruxelles, Belgium
talbi(at)lifl.fr
Talbi El-ghazali, Université des Sciences et Technologies de Lille, France
thomas.bartz-beielstein(at)fh-koeln.de
Bartz-Beielstein Thomas, Cologne University of Applied Sciences, Germany
walter.gutjahr(at)univie.ac.at
Gutjahr Walter, University of Vienna, Austria
xico(at)dei.uc.pt
Pereira Francisco J. B., Universidade de Coimbra, Portugal
yamada.tak(at)lab.ntt.co.jp
Yamada Takeshi, NTT Communication Science Laboratories, Kyoto, Japan
zhipeng.lui(at)gmail.com
Lu Zhipeng, HUST, Wuhan, China
Thursday 24 April 2014
0930-1110
Session 1: Swarm Intelligence Algorithms (Chair: Christian Blum)
The Influence of Correlated Objectives on Different Types of P-ACO Algorithms
Ruby L. V. Moritz, Enrico Reich, Matthias Bernt and Martin Middendorf
The influence of correlated objectives on different types of P-ACO algorithms for solutions of multi objective optimization problems is investigated. Therefore, a simple method to create multi objective optimization problems with correlated objectives is proposed. Theoretical results show how certain correlations between the objectives can be obtained. The method is applied to the Traveling Salesperson problem. The influence of the correlation type and strength on the optimization behavior of different P-ACO algorithms is analyzed empirically. A particular focus is given on P-ACOs with ranking methods.
Gaussian Based Particle Swarm Optimisation and Statistical Clustering for Feature Selection
Mitchell C. Lane, Bing Xue, Ivy Liu and Mengjie Zhang
Feature selection is an important but difficult task in classification, which aims to reduce the number of features and maintain or even increase the classification accuracy. This paper proposes a new particle swarm optimisation (PSO) algorithm using statistical clustering information to solve feature selection problems. Based on Gaussian distribution, a new updating mechanism is developed to allow the use of the clustering information during the evolutionary process of PSO based on which a new algorithm (GPSO) is developed. The proposed algorithm is examined and compared with two traditional algorithms and a PSO based algorithm which does not use clustering information on eight benchmark datasets of varying difficulty. The results show that GPSO can be successfully used for feature selection to reduce the number of features and achieve similar or even better classification performance than using all features. Meanwhile, it achieves better performance than the two traditional feature selection algorithms. It maintains the classification performance achieved by the standard PSO for feature selection algorithm, but significantly reduces the number of features and the computational cost.
Modeling an Artificial Bee Colony with inspector for clustering tasks
Cosimo Birtolo, Giovanni Capasso, Davide Ronca and Gennaro Sorrentino
Artificial Bee Colony (ABC) is a recent meta-heuristic approach. In this paper we face the problem of clustering by ABC and we model a further bee role in the colony, performed by inspector bee. This model conforms with real honey bee colony, indeed, in nature some bees among the foraging ones are called inspectors because they preserve the colony's history and historical information related to food sources. We experiment inspector behavior in ABC and compare the solution to traditional clustering algorithm. Finally, the effect of colony size is investigated and experimental results are discussed.
The Firefighter Problem: Application of Hybrid Ant Colony Optimization Algorithms
Christian Blum, Maria J. Blesa, Carlos García-Martínez, Francisco J Rodríguez and Manuel Lozano
The firefigther problem is a deterministic discrete-time model for the spread (and the containment) of fire on an undirected graph. Assuming that the fire breaks out at a predefined set of vertices, the goal is to save as many vertices as possible from burning. The same model has also been used in the literature for the simulation of the spreading of deseases. In this work we present, to our knowledge, the first metaheuristics for tackling this problem. In particular, a pure ant colony optimization approach and a hybrid variant of this algorithm are proposed. The results show that the hybrid ant colony optimization variant is superior to the pure ant colony optimization version and to a mathematical programming solver, especially when the graph size and density grows.
1135-1315
Session 2: Fitness Landscapes and Adaptive Algorithms (Chair: Francisco Chicano)
Phase Transition and Landscape Properties of the Number Partitioning Problem
Khulood Alyahya and Jonathan E. Rowe
This paper empirically studies basic properties of the fitness landscape of random instances of number partitioning problem, with a focus on how these properties change with the phase transition. The properties include number of local and global optima, number of plateaus, basin size and its correlation with fitness. The only two properties that were found to change when the problem crosses the phase transition are the number of global optima and the number of plateaus, the rest of the properties remained oblivious to the phase transition. This paper, also, studies the effect of different distributions of the weights and different neighbourhood operators on the problem landscape.
Global Optimization of Multimodal Deceptive Functions
David Iclanzan
Local search algorithms operating in high-dimensional and multimodal search spaces often suffer from getting trapped in a local optima, therefore requiring many restarts. Even with multiple restarts, their search efficiency critically depends on the choice of the neighborhood structure. In this paper we propose an approach in which the need for the restarts is exploited to improve the neighborhood definitions. Namely, a graph clustering based linkage detection method is used to mine the information from several runs, in order to extract variable dependencies and update the neighborhood structure, variation operators accordingly. We show that the adaptive neighborhood structure approach enables the efficient solving of challenging global optimization problems that are both deceptive and multimodal.
An Analysis of Parameters of irace
Leslie Pérez Cáceres, Manuel López-Ibáñez and Thomas Stützle
The irace package implements a flexible tool for the automatic configuration of algorithms. However, irace itself has specific parameters to customize the search process according to the tuning scenario. In this paper, we analyze five parameters of irace: the number of iterations, the number of instances seen before the first elimination test, the maximum number of elite configurations, the statistical test and the confidence level of the statistical test. These parameters define some key aspects of the way irace identifies good configurations. Originally, their values have been set based on rules of thumb and an intuitive understanding of the configuration process. This work aims at giving insights about the sensitivity of irace to these parameters in order to guide their setting and further improvement of irace.
Elementary Landscape Decomposition of the Hamiltonian Path Optimization Problem
Darrell Whitley and Francisco Chicano
There exist local search landscapes where the evaluation function is an eigen function of the graph Laplacian that corresponds to the neighborhood structure of the search space. Problems that display this structure are called Elementary Landscapes and they have a number of special mathematical properties. The problems that are not elementary landscapes can be decomposed in a sum of elementary ones. This sum is called the elementary landscape decomposition of the problem. In this paper, we provide the elementary landscape decomposition for the Hamiltonian Path Optimization Problem under two different neighborhoods.
1430-1610
Session 3: Real World and Routing Problems (Chair: Bin Hu)
Personalized Multi-Day Trips to Touristic Regions: A hybrid GA-VND approach
Ali Divsalar, Pieter Vansteenwegen, Masoud Chitsaz, Kenneth Sörensen and Dirk Cattrysse
When a tourist is visiting a large region with many attractions, frequently there is not enough time to reach all of them. Moreover when the journey takes more than a day, at the end of each day an accomodation place should be selected to continue the trip the next day. In this research, we introduce the Orienteering Problem with Hotel Selection and Time Windows (OPHS-TW) in order to model this real application. A set of 395 benchmark instances with known optimal solution are created and a hybrid Genetic Algorithm with a Variable Neighborhood Descent (GA-VND) phase is developed to efficiently solve the instances in a reasonable time.
An Improved Multi-Objective Algorithm for the Urban Transit Routing Problem
Matthew P. John, Christine L. Mumford and Rhyd Lewis
The determination of efficient routes and schedules in public transport systems is complex due to the vast search space and multiple constraints involved. In this paper we focus on the Urban Transit Routing Problem concerned with the physical network design of public transport systems. Historically, route planners have used their local knowledge coupled with simple guidelines to produce network designs. Several major studies have identified the need for automated tools to aid in the design and evaluation of public transport networks. We propose a new construction heuristic used to seed a multi-objective evolutionary algorithm. Several problem specific mutation operators are then combined with an NSGAII framework leading to improvements upon previously published results.
Dynamic Period Routing for a Complex Real-World System: A Case Study in Storm Drain Maintenance
Yujie Chen, Peter Cowling and Stephen Remde
This paper presents a case study of a real world storm drain maintenance problem where we must construct daily routes for a maintenance vehicle while considering the dynamic condition and social value of drains. To represent our problem, a dynamic period vehicle routing problem with profit (DPVRPP) model is proposed. This differs from the classical period routing problem in a number of ways. Firstly, it is dynamic: during the planning horizon, the demands from damaged drains and residents reports arrive continuously. In addition, the drains condition is changing over time. Secondly, our objective is maximizing the profit, defined here as the drains condition with respect to its social value. This study is based on large-scale data provided by Gaist Solutions Ltd. and the council of a UK town (Blackpool). We propose an adaptive planning heuristic (APH) that produces daily routes based on our model and an estimation of changing drain condition in the future. Computational results show that the APH approach can, within reasonable CPU time, produce much higher quality solutions than the scheduling strategy currently implemented by Blackpool council.
Metaheuristics for the Pick-up and Delivery Problem with Contracted Orders
Philip Mourdjis, Peter Cowling and Martin Robinson
Contracted orders represent a novel extension to the Pick-up and Delivery Problem (PDP) with soft time windows. This extension to the multiple depot problem has depots managed by separate, competing haulage companies ``carriers''. Orders may be assigned to a specific carrier ``contracted'', ``allocated'' to a specific carrier but allowed to swap if this improves the solution or free to use any carrier ``spot hired''. Soft time windows lead to a multi-objective problem of minimising distance travelled and delay incurred. In this paper we use real order data supplied by 3 large distributors and 220 carriers. Additional, randomised, orders are generated to match the distributions observed in this data, representing backhaul orders for which no data is available. We compare a manual scheduling technique based on discussions with industry partners to popular metaheuristics for similar problems namely Tabu Search (TS), Variable Neighbourhood Search (VNS) and Hybrid Variable Neighbourhood Tabu Search (HVNTS), using our modified local search operators. Results show that VNS and HVNTS produce results which are 50% shorter than greedy approaches across test instances of 300 orders in a one week period.
1630-1810
Session 4: Cooperative and Metaheuristic Search (Chair: Darrell Whitley)
A Survey of Meta-Heuristics used for Computing Maximin Latin Hypercube
Arpad Rimmel and Fabien Teytaud
Finding maximin latin hypercube is a discrete optimization problem believed to be NP-hard. In this paper, we compare different meta-heuristics used to tackle this problem: genetic algorithm, simulated annealing and iterated local search. We also measure the importance of the choice of the mutation operator and the evaluation function. All the experiments are done using a fixed number of evaluations to allow future comparisons. Simulated annealing is the algorithm that performed the best. By using it, we obtained new highscores for a very large number of latin hypercubes.
Cooperative Selection: Improving Tournament Selection via Altruism
Juan Luis Giménez Laredo, Sune S. Nielsen, Grégoire Danoy, Pascal Bouvry and Carlos M. Fernandes
This paper analyzes the dynamics of a new selection scheme based on altruistic cooperation between individuals. The scheme, which we refer to as cooperative selection, extends from tournament selection and imposes a stringent restriction on the mating chances of an individual during its lifespan: winning a tournament entails a depreciation of its fitness value. We show that altruism minimizes the loss of genetic diversity while increasing the selection frequency of the fittest individuals. An additional contribution of this paper is the formulation of a new combinatorial problem for maximizing the similarity of proteins based on their secondary structure. We conduct experiments on this problem in order to validate cooperative selection. The new selection scheme outperforms tournament selection for any setting of the parameters and is the best trade-off, maximizing genetic diversity and minimizing computational efforts.
An Iterated Greedy heuristic for simultaneous lot-sizing and scheduling problem in production flow shop environments
Harlem M. M. Villadiego, José Elias C. Arroyo, and André Gustavo dos Santos
In this work, we consider the integrated lot-sizing and sequencing problem in a permutation flow shop with machine sequence-dependent setups. The problem is to determine the lot sizes and the production sequence in each period of a planning horizon such that the customer demands must be met and the capacity of the machines must be respected. The objective is to determine the sum of the setup costs, the production costs and the inventory costs over the planning horizon. Due to the complexity of the problem, we propose a heuristic based on Iterated Greedy metaheuristic which uses sequencing and lot-sizing decisions. The proposed method is compared against the best heuristics available in the literature in a large set of problem instances. Comprehensive computational and statistical analyses are carried out in order to validate the performance of the proposed heuristic.
A Parametric Framework for Cooperative Parallel Local Search
Danny Munera, Daniel Diaz, Salvador Abreu, and Philippe Codognet
In this paper we address the problem of parallelizing local search. We propose a general framework where different local search engines cooperate (through communication) in the quest for a solution. Several parameters allow the user to instantiate and customize the framework, like the degree of intensification and diversification. We implemented a prototype in the X10 programming language based on the adaptive search method. We decided to use X10 in order to benefit from its ease of use and the architectural independence from parallel resources which it offers. Initial experiments prove the approach to be successful, as it outperforms previous systems as the number of processes increases.
Friday 25 April
0930-1110
Session 5: EvoCOP Best-paper Nominations (Chair: Gabriela Ochoa)
Diversity-Driven Selection of Multiple Crossover Operators for the Capacitated Arc Routing Problem
Pietro Consoli and Xin Yao
The Capacitated Arc Routing Problem (CARP) is a NP-Hard routing problem with strong connections with real world problems. In this work we aim to enhance the performance of MAENS, a state-of-the-art algorithm, through a self-adaptive scheme to choose the most suitable operator and a diversity-driven ranking operator. Experimental results on 181 problem instances show how these techniques can both improve the results of the current state-of-the-art algorithms and provide good directions to develop EAs with a more robust approximation ratio.
Learning Inherent Networks from Stochastic Search Methods
David Iclanzan, Fabio Daolio and Marco Tomassini
Analysis and modeling of search heuristics operating on complex problems is a difficult albeit important research area. Inherent networks, i.e. the graphs whose vertices represent local optima and the edges describe the weighted transition probabilities between them, enable a network characterization of combinatorial fitness landscapes. Methods revealing such inherent structures of the search spaces in relation to deterministic move operators, have been recently developed for small problem instances. This work proposes a more general, scalable, data-driven approach, that extracts the transition probabilities from actual runs of metaheuristics, capturing the effect and interplay of a broader spectrum of factors. Using the case of NK landscapes, we show that such an unsupervised learning approach is successful in quickly providing a coherent view of the inherent network of a problem instance.
Balancing Bicycle Sharing Systems: An Approach for the Dynamic Case
Christian Kloimüllner, Petrina Papazek, Bin Hu and Günther R. Raidl
Operators of public bicycle sharing systems (BSSs) have to regularly redistribute bikes across their stations in order to avoid them getting overly full or empty. We consider the dynamic case where this is done while the system is in use. There are two main objectives: On the one hand it is desirable to reach particular target fill levels at the end of the process so that the stations are likely to meet user demands for the upcoming day(s). On the other hand operators also want to prevent stations from running empty or full during the rebalancing process which would lead to unsatisfied customers. We extend our previous work on the static variant of the problem by introducing an efficient way to model the dynamic case as well as adapting our previous greedy and PILOT construction heuristic, variable neighborhood search and GRASP. Computational experiments are performed on instances based on real-world data from Citybike Wien, a BSS operator in Vienna, where the model for user demands is derived from historical data.
A Hybrid Ant Colony Optimization Algorithm for the Far From Most String Problem
Christian Blum and Paola Festa
The far from most string problem belongs to the family of string selection and comparison problems known as sequence consensus problems, where a finite set of sequences is given and one is interested in finding their consensus, that is, a new sequence that represents as much as possible all the given sequences. Among the consensus problems, the far from most string problem is computationally one of the hardest ones with applications in several fields, including molecular biology where one is interested in creating diagnostic probes for bacterial infections or in discovering potential drug targets. This paper comes with several contributions. On one side, the first linear integer programming formulation for the considered problem is introduced. On the other side, a hybrid ant colony optimization approach for finding good approximate solution to the problem is proposed. Both approaches are compared to the current state of the art, which is a recently proposed hybrid GRASP with path-relinking. Computational results on a large set of randomly generated test instances indicate that the hybrid ACO is very competitive.