EU/ME - the metaheuristics community

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

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

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

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

Abstract

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.

Read more...
 

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

Abstract

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.

Read more...
 

European Journal of Operational Research

E-mail Print PDF

A reduced variable neighborhood search algorithm for uncapacitated multilevel lot-sizing problem

by Yiyong Xiao, Ikou Kaku, Qiuhong Zhao and Renqian Zhang

Abstract

Multilevel lot-sizing (MLLS) problems, which involve complicated product structures with interdependence among the items, play an important role in the material requirement planning (MRP) system of modern manufacturing/assembling lines. In this paper, we present a reduced variable neighborhood search (RVNS) algorithm and several implemental techniques for solving uncapacitated MLLS problems. Computational experiments are carried out on three classes of benchmark instances under different scales (small, medium, and large). Compared with the existing literature, RVNS shows good performance and robustness on a total of 176 tested instances. For the 96 small-sized instances, the RVNS algorithm can find 100% of the optimal solutions in less computational time; for the 40 medium-sized and the 40 large-sized instances, the RVNS algorithm is competitive against other methods, enjoying good effectiveness as well as high computational efficiency. In the calculations, RVNS updated 7 (17.5%) best known solutions for the medium-sized instances and 16 (40%) best known solutions for the large-sized instances.

Read more...
 

Journal of heuristics

E-mail Print PDF

Quantum-inspired evolutionary algorithms: a survey and empirical study

by  Gexiang Zhang

Abstract

 Quantum-inspired evolutionary algorithms, one of the three main research areas related to the complex interaction between quantum computing and evolutionary algorithms, are receiving renewed attention. A quantum-inspired evolutionary algorithm is a new evolutionary algorithm for a classical computer rather than for quantum mechanical hardware. This paper provides a unified framework and a comprehensive survey of recent work in this rapidly growing field. After introducing of the main concepts behind quantum-inspired evolutionary algorithms, we present the key ideas related to the multitude of quantum-inspired evolutionary algorithms, sketch the differences between them, survey theoretical developments and applications that range from combinatorial optimizations to numerical optimizations, and compare the advantages and limitations of these various methods. Finally, a small comparative study is conducted to evaluate the performances of different types of quantum-inspired evolutionary algorithms and conclusions are drawn about some of the most promising future research developments in this area.

Read more...
 


Page 7 of 11

Newsflash

EU/ME 2017

Submit now your abstract.

Metaheuristics Events

<<  May 2017  >>
 Mo  Tu  We  Th  Fr  Sa  Su 
  1  2  3  4  5  6  7
  8  91011121314
152021
25262728
293031    

Who's Online

We have 121 guests online