DM -Artigos em Revistas Internacionais / Articles in International Journals
Permanent URI for this collection
Browse
Recent Submissions
- A structural Lagrangean relaxation for two-duty period bus driver scheduling problemsPublication . Pinto, José Pinto; Pato, Margarida VazThe two-duty period bus driver scheduling problem is a particular case of the generalized set covering problem, min {cTx : Ax ⩾ b, 0 ⩽ x ⩽h and integer) where, each column of the boolean matrix A consists of at most two strings of consecutive ones. Such a denomination for the problem is due to several real life applications, in particular for bus crew scheduling. In this paper, we present a 'structural' lagrangean relaxation and penalties for improving the bounds on the optimum for the problem. Two other lagrangean relaxation approaches, previously reported in the literature, are considered too. A computational study relative to these relaxations was carried out with both randomly generated test problems and real life cases from Rodoviária Nacional, a large mass transport operator in Portugal. The results reported in the paper evidence a better performance for the lagrangean relation approach wich combined with greedy heuristics, yeld a reasonably good and fast procedure for tackling real life problems
- Search strategies for the feeder bus network design problemPublication . Martins, Carlos Lúcio; Pato, Margarida VazThis paper reports on computing solutions for a specific problem arising in public transport systems - the Feeder Bus Network Design Problem (FBDP). The problem requires the design of a set of feeder bus routes and the definition of their service frequencies to satisfy both the resource constraints and the demand for transportation: passengers located at any of the bus stops wish to go to any of the stations of a rail transit line in order to access a common destination identified as the central station. The objective is to minimize a cost function, where both passenger and operator interests are considered. This problem may be formulated as a difficult, nonlinear and nonconvex mixed integer problem, classified as NP-hard. The study focuses on a combined building plus improving heuristic procedure, partially taken from literature. The starting module builds up a solution through a sequential savings or a two-phase method, and for the last module the method includes local search, as well as tabu search heuristics with different strategies. Additionally, computational results from a set of problems simulating real life situations are given. Through this experiment the authors conclude that the simplest short-term version of tabu search is one of most promising heuristics.
- A three-phase procedure for designing an irrigation system’s water distribution networkPublication . Gonçalves, Graça Marques; Pato, Margarida VazThis paper focuses on the design of an irrigation network included in a public project to build a distributing water system for agricultural purposes. We begin by outlining the issue. We then present a procedure composed of three sequential modules to tackle this complex problem. The first module provides the design of the network links by heuristically constructing a short length Steiner forest. In the second module, the flows for every arc of this network are calculated. The last one determines the size of the pipes and pumps by solving a mixed binary linear programming problem. A real experiment is reported. Although further improvements are required, the results confirm the adaptability of the overall procedure to assist agricultural engineers in preparing their projects.
- An integer multicommodity flow model applied to the rerostering of nurse schedulesPublication . Moz, Margarida; Pato, Margarida VazThe problem of rerostering service schedules is very common in organizations that work shifts around the clock every day of the year with a set number of employees. Whenever one or more workers announce that they will not be able to attend to tasks previously assigned in their schedule, those tasks must be performed at the expense of alterations in the schedules of other workers. These changes should not conflict with the rules laid down by the administration and employment contracts and should affect the previous schedules as little as possible. This is a difficult real problem calling for a computational tool to cope with it easily. In the paper the issue is described in detail in the context of nurse scheduling and formulated as an integer multicommodity flow problem with additional constraints, in a multi-level acyclical network. A heuristic was implemented as a first approach to solving the problem. Subsequently the integer linear programming formulation of the multicommodity flow model and two linear relaxations were tested using CPLEX [2] optimizers. The computational results reported regard real instances from a Lisbon state hospital. Satisfactory rosters were obtained within acceptable computational times in all instances tested, either with the integer optimizer, or with the heuristic. This being so, refinements will be undertaken to embed these methodologies in a decision support system that may assist the head nurse in her daily rerostering activities.
- A comparison of discrete and continuous neural network approaches to solve the class/teacher timetabling problemPublication . Carrasco, Marco Paulo; Margarida Vaz Pato, Margarida Vaz PatoThis study explores the application of neural network-based heuristics to the class/teacher timetabling problem (CTTP). The paper begins by presenting the problem characteristics in terms of hard and soft constraints and proposing a formulation for the energy function required to map the issue within the artificial neural network model. There follow two distinct approaches to simulating neural network evolution. The first uses a Potts mean-field annealing simulation based on continuous Potts neurons, which has obtained favorable results in various combinatorial optimization problems. Afterwards, a discrete neural network simulation, with discrete winner-takes-all neurons, is proposed. The paper concludes with a comparison of the computational results taken from the application of both heuristics to hard hypothetical and real CTTP instances. This experiment demonstrates that the discrete approach performs better, in terms of solution quality as well as execution time. By extending the comparison, the neural discrete solutions are also compared with those obtained from a multiobjective genetic algorithm, which is already being successfully used for this problem within a timetabling software application
- Solving the problem of rerostering nurse schedules with hard constraints : new multicommodity flow modelsPublication . Moz, Margarida; Pato, Margarida VazThe problem of rerostering nurse schedules arises in hospitals when at least one nurse informs that she will be unable to perform the shifts assigned to her on one or more future work days. As a result, the current roster must be rebuilt in accordance with labour contract rules and institutional requirements. All such restraints are regarded as hard constraints. However, major alterations in the previously assigned nurse schedules must be avoided. This paper is based on a case study of a public hospital in Portugal. It presents two new integer multicommodity flow formulations for the rerostering problem, besides a computational experiment performed using real data. The first model is based on a directed multilevel acyclic network. The aggregation of nodes in this network led to the second model. The results obtained show that the second integer multicommodity flow formulation outperforms the first, both in terms of solution quality, as well as in computational time.
- An improved genetic heuristic to support the design of flexible manufacturing systemsPublication . Lourenço, Lídia Lampreia; Pato, Margarida VazIn industry, when flexible manufacturing systems are designed within a group technology approach, numerous decision-taking processes emerge requiring control of the multiple characteristics of the system. In this context, several grouping problems are identified within the scope of combinatorial optimisation. Such is the case of the part families with precedence constraints problem, which is defined in order to set up families where the total dissimilarity among the parts placed in the same family is minimal and precedence constraints, as well as capacity constraints arise when grouping parts. The present paper describes the use of an improved genetic heuristic to tackle this problem. It comprises a standard genetic heuristic with appropriate operators, improved through specific local search. In order to study the performance of the improved genetic approach, a special purpose constructive heuristic plus an earlier version of the genetic heuristic were implemented. CPLEX software was used from a binary linear formulation for this problem. Computational results are given from the experiment performed using test instances partly taken from the literature while others were semi-randomly generated. The improved genetic heuristic produced optimal solutions for most of the shortest dimension test instances and acted positively in relation to the constructive heuristic results, over almost all the instances. As for the CPLEX it found optimal solutions only for the small instances, besides which for the higher dimensioned instances CPLEX failed to obtain any integer solutions at all, in 10h running time. Therefore, these experiments demonstrate that the improved genetic is a good tool to tackle high dimensioned test instances, when one does not expect an exact method to find an optimal solution in reasonable computing time.
- A genetic algorithm approach to a nurse rerostering problemPublication . Margarida Moz, Margarida Moz; Pato, Margarida VazThe nurse rerostering problem ccurs when one or mor enurses cannot work in shifts that were previously assigned to her or them. If no pool of reserve nurses exists to replace those absent, then the current roster must be rebuilt. This new roster must comply with the labour rules and institutional constraints. Moreover, it must be as similar as possible to the current one. The present paper describes constructive heuristics, besides several versions of genetic algorithms based on specific encoding and operators for sequencing problems applied to the nurse rerostering problem, defined with hard constraints. In the genetic algorithms described, each individual in the population is associated with a pair of chromosomes, representing permutations of tasks and nurses. Those permutations are used as input to a procedure that generates rosters. The fitness of individuals is given by the similarity between the roster generated from the permutations and the current one. The authors developed several versions of the genetic algorithm, whose difference lay in the encoding of permutations and in the genetic operators used for each encoding. These heuristics were tested with real data from a Lisbon hospital and yielded good quality solutions. Scope and purpose the research reported is part of a project designed to develop a system for the management of nurse schedules for implementation in Portuguese public hospitals. The specific problem of rebuilding nurse schedules is addressed when unexpected staff absences arise. The complexity of the problem led the authors to design heuristic procedures. The tests performed so far with real data have shown that the algorithms attain good quality solutions at a computing time within the bounds stipulated by the hospital.
- The effect of strengthened linear formulations on improving the lower bounds for the part families with precedence constraints problemPublication . Lourenço, Lídia Lampreia; Pato, Margarida VazThe part families with precedence constraints problem (PFP) arises in industry, when flexible manufacturing systems are designed within a group technology approach. The aim of this problem is to arrange parts into families by imposing capacity constraints, concerning both the number of parts and processing times, besides precedence constraints in the building of families. Mixed binary linear programming formulations for the PFP are presented. In endeavoring to strengthen the linear relaxations for the formulations, and hence generate better lower bounds for the optimal value of PFP, some valid inequalities, based on the properties of the problem, were deduced. The lower bounds obtained significantly improved through the very weak, frequently null, bounds resulting from the original linear relaxation. Moreover, it may be concluded that these models can be a useful methodology to enforce the performance of any branch-and-bound for this very important problem in flexible manufacturing systems.
- Solving a bi-objective nurse rerostering problem by using a utopic Pareto genetic heuristicPublication . Pato, Margarida Vaz; Moz, MargaridaNurse rerostering arises when at least one nurse announces that she will be unable to undertake the tasks previously assigned to her. The problem amounts to building a new roster that satisfies the hard constraints already met by the current one and, as much as possible, fulfils two groups of soft constraints which define the two objectives to be attained. A bi-objective genetic heuristic was designed on the basis of a population of individuals characterised by pairs of chromosomes, whose fitness complies with the Pareto ranking of the respective decoded solution. It includes an elitist policy, as well as a new utopic strategy, introduced for purposes of diversification. The computational experiments produced promising results for the practical application of this approach to real life instances arising from a public hospital in Lisbon.