EU/ME - the metaheuristics community

  • Increase font size
  • Default font size
  • Decrease font size
Home Metaheuristics articles

Journal of Heuristics 17(5), 2011

E-mail Print PDF

Biased random-key genetic algorithms for combinatorial optimization

by José Fernando Gonçalves and Mauricio G. C. Resende


Random-key genetic algorithms were introduced by Bean (ORSA J. Comput. 6:154–160, 1994) for solving sequencing problems in combinatorial optimization. Since then, they have been extended to handle a wide class of combinatorial optimization problems. This paper presents a tutorial on the implementation and use of biased random-key genetic algorithms for solving combinatorial optimization problems. Biased random-key genetic algorithms are a variant of random-key genetic algorithms, where one of the parents used for mating is biased to be of higher fitness than the other parent. After introducing the basics of biased random-key genetic algorithms, the paper discusses in some detail implementation issues, illustrating the ease in which sequential and parallel heuristics based on biased random-key genetic algorithms can be developed. A survey of applications that have recently appeared in the literature is also given.

Last Updated on Monday, 26 September 2011 05:59

Newsflash: Odysseus 2012

E-mail Print PDF
Odysseus 2012, Extended deadline, October 31, 2011.

Newsflash: EA 2011

E-mail Print PDF
EA 2011, Programme is now available. List of accepted papers. Registration is open.
Last Updated on Thursday, 15 September 2011 13:09

LION 2012 - Newsflash

E-mail Print PDF
LION 2012, Call for special sessions is online. Deadline Oct. 14, 2011.
Last Updated on Tuesday, 30 August 2011 07:13

Journal of Heuristics 17(4), 2011

E-mail Print PDF

A Bus Driver Scheduling Problem: a new mathematical model and a GRASP approximate solution

by Renato De Leone, Paola Festa and Emilia Marchitto


This paper addresses the problem of determining the best scheduling for Bus Drivers, a NP-hard problem consisting of finding the minimum number of drivers to cover a set of Pieces-Of-Work (POWs) subject to a variety of rules and regulations that must be enforced such as spreadover and working time. This problem is known in literature as Crew Scheduling Problem and, in particular in public transportation, it is designated as Bus Driver Scheduling Problem. We propose a new mathematical formulation of a Bus Driver Scheduling Problem under special constraints imposed by Italian transportation rules. Unfortunately, this model can only be usefully applied to small or medium size problem instances. For large instances, a Greedy Randomized Adaptive Search Procedure (GRASP) is proposed. Results are reported for a set of real-word problems and comparison is made with an exact method. Moreover, we report a comparison of the computational results obtained with our GRASP procedure with the results obtained by Huisman et al. (Transp. Sci. 39(4):491–502, 2005).

4OR: A Quarterly Journal of Operations Research

E-mail Print PDF

A large neighbourhood search heuristic for the aircraft and passenger recovery problem

by Serge Bisaillon, Jean-François Cordeau, Gilbert Laporte and Federico Pasin


This paper introduces a large neighbourhood search heuristic for an airline recovery problem combining fleet assignment, aircraft routing and passenger assignment. Given an initial schedule, a list of disruptions, and a recovery period, the problem consists in constructing aircraft routes and passenger itineraries for the recovery period that allow the resumption of regular operations and minimize operating costs and impacts on passengers. The heuristic alternates between construction, repair and improvement phases, which iteratively destroy and repair parts of the solution. The aim of the first two phases is to produce an initial solution that satisfies a set of operational and functional constraints. The third phase then attempts to identify an improved solution by considering large schedule changes while retaining feasibility. The whole process is iterated by including some randomness in the construction phase so as to diversify the search. This work was initiated in the context of the 2009 ROADEF Challenge, a competition organized jointly by the French Operational Research and Decision Analysis Society and the Spanish firm Amadeus S.A.S., in which our team won the first prize.


European Journal of Operational Research

E-mail Print PDF

A tabu search heuristic for the dynamic transportation of patients between care units

by Y. Kergosien, Ch. Lenté, D. Piton and J.-C. Billaut


The problem studied in this paper stems from a real application to the transportation of patients in the Hospital Complex of Tours (France). The ambulance central station of the Hospital Complex has to plan the transportation demands between care units which require a vehicle. Some demands are known in advance and the others arise dynamically. Each demand requires a specific type of vehicle and a vehicle can transport only one person at a time. The demands can be subcontracted to a private company which implies high cost. Moreover, transportations are subject to particular constraints, among them priority of urgent demands, disinfection of a vehicle after the transportation of a patient with contagious disease and respect of the type of vehicle needed. These characteristics involve a distinction between the vehicles and the crews during the modeling phase. We propose a modeling for solving this difficult problem and a tabu search algorithm inspired by Gendreau et al. (1999). This method supports an adaptive memory and a tabu search procedure. Computational experiments on a real-life instance and on randomly generated instances show that the method can provide high-quality solutions for this dynamic problem with a short computation time.


Page 7 of 12


EU/ME 2017

Submit now your abstract.

Metaheuristics Events

<<  October 2018  >>
 Mo  Tu  We  Th  Fr  Sa  Su 
  1  2  3  4  5  6  7
  8  91011121314

Who's Online

We have 161 guests online