Journal of Heuristics 17(5), 2011
Monday, 26 September 2011 05:59
Marc Sevaux
Biased random-key genetic algorithms for combinatorial optimizationby José Fernando Gonçalves and Mauricio G. C. Resende AbstractRandom-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
Read more...
Newsflash: Odysseus 2012
Tuesday, 20 September 2011 06:36
Marc Sevaux
Odysseus 2012, Extended deadline, October 31, 2011.
Newsflash: EA 2011
Thursday, 15 September 2011 13:07
Marc Sevaux
Last Updated on Thursday, 15 September 2011 13:09
|
LION 2012 - Newsflash
Thursday, 25 August 2011 07:10
Marc Sevaux
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
Monday, 18 July 2011 06:35
Marc Sevaux
A Bus Driver Scheduling Problem: a new mathematical model and a GRASP approximate solutionby Renato De Leone, Paola Festa and Emilia Marchitto Abstract 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).
Read more...
|
4OR: A Quarterly Journal of Operations Research
Tuesday, 28 June 2011 09:38
Marc Sevaux
A large neighbourhood search heuristic for the aircraft and passenger recovery problemby Serge Bisaillon, Jean-François Cordeau, Gilbert Laporte and Federico Pasin AbstractThis 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.
Read more...
European Journal of Operational Research
Monday, 27 June 2011 06:56
Marc Sevaux
A tabu search heuristic for the dynamic transportation of patients between care units This article is not included in your organization's subscription. However, you may be able to access this article under your organization's agreement with Elsevier. by Y. Kergosien, Ch. Lenté, D. Piton and J.-C. Billaut AbstractThe 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.
Read more...
|
|
|
|
Page 7 of 12 |