Operational Research

Frontmatter

Performance Evaluation of Parfois Retailing Stores

Abstract

This study describes a method for the assessment of retail store performance using Data Envelopment Analysis (DEA). The method is applied to the Portuguese company, Parfois, operating in retail fashion accessories, where we analyze the efficiency of 63 stores operating in Portugal. Firstly, we present a literature review on the subject, followed by a description of the company and the DEA method applied to the Parfois stores. Then, some of the factors potentially affecting the efficiency of Parfois stores are also analyzed, and the implications of using this method are discussed. The main intention of the study is to show how DEA can be used as a support tool to the management of Parfois stores at a national level and to help the company, through the identification of areas of potential growth, to define objectives, to increase its performance and achieve excellence.

Maria Emília Dias Alves, Maria C. A. Silva Portela

Optimization Clustering Techniques on Register Unemployment Data

Abstract

An important strategy for data classification consists in organising data points in clusters. The k-means is a traditional optimisation method applied to cluster data points. Using a labour market database, aiming the segmentation of this market taking into account the heterogeneity resulting from different unemployment characteristics observed along the Portuguese geographical space, we suggest the application of an alternative method based on the computation of the dominant eigenvalue of a matrix related with the distance among data points. This approach presents results consistent with the results obtained by the k-means.

Carlos Balsa, Alcina Nunes, Elisa Barros

Web Based Application for Home Care Visits’ Optimization of Health Professionals’ Teams of Health Centers

Abstract

Health Centers have among one of their many tasks the provision of health care at home. This service is provided by teams of health professionals, usually composed of physicians and nurses belonging to the Health Centers. The scheduling of the visits is made by a health professional that groups one or more routes in order to minimize the time of team’s visits. However, as there is no technical or computer application to plan and optimize the visits in a systematic way, the obtained solutions are rarely the best ones. To improve this situation we were challenged by a Health Center to create an application to optimize the visits of health care professionals. This paper presents the solution developed involving a web application called “Health at Home”, which uses the heuristic of Clarke and Wright. The main novelty of this work is the inclusion of priority and non-priority patients, according to their degree of aseptic, within the routes optimization of the health professionals’ teams.

Bruno Bastos, Tiago Heleno, António Trigo, Pedro Martins

Cell-Free Layer Measurements in a Network with Bifurcating Microchannels Using a Global Approach

Abstract

One of the most interesting hemodynamic phenomenon observed in microchannels is the existence of a marginal cell-free layer (CFL) at regions adjacent to the wall. This is a well known phenomenon that occurs in simple glass capillaries and in vivo microvessels, but has never been investigated in detail in biomedical microdevices containing complex geometries. In the present chapter, in vitro blood flowing through bifurcating microchannels was studied, with the aim of characterizing the cell-free layer (CFL). For that three different videos with different hematocrit and flow rates were considered. All images were obtained by means of a high-speed video microscopy system and then processed in MatLab using the Image Processing toolbox. The numerical data was obtained automatically and analyzed by optimization techniques using the genetic algorithm approach. The results suggest that the CFL were formed in a similar way at the upper and lower regions in all bifurcations.

David Bento, Diana Pinho, Ana I. Pereira, Rui Lima

Computational Comparison of Algorithms for a Generalization of the Node-Weighted Steiner Tree and Forest Problems

Abstract

Habitat fragmentation is a serious threat for the sustainability of species. Thus, the identification of effective linkages to connect valuable ecological units is an important issue in conservation biology. The design of effective linkages should take into account that areas which are adequately permeable for some species’ dispersal may act as obstructions for other species. The determination of minimum cost effective linkages is a generalization of both node-weighted Steiner tree and node-weighted Steiner forest problems. We compare the performance of different procedures for this problem using large real and simulated instances.

Raul Brás, J. Orestes Cerdeira

Development of a Numerically Efficient Biodiesel Decanter Simulator

Abstract

This chapter deals with the modelling, simulation, and control of a separator unit used in the biodiesel industry. While mechanistic modelling provides an accurate way to describe the system dynamics, it is an iterative and computationally burdensome process that arises from the need to determine the liquid-liquid equilibria via the flash calculation. These disadvantages would preclude the use of mechanistic models for process optimization or model based control. In order to overcome this problem, an alternative strategy is here suggested. It consists of maintaining the mechanistic model structure and to approximate the iterative calculations with an artificial neural network. The general approach for dataset consideration and neural network training and validation are presented. The quality of the resulting neural network is demonstrated to be high while the computation burden is significantly reduced. Finally, the obtained grey-box model is used in order to carry out dynamic simulation and control tests of the unit.

Ana S. R. Brásio, Andrey Romanenko, Natércia C. P. Fernandes

Determination of (0, 2)-Regular Sets in Graphs and Applications

Abstract

In this paper, relevant results about the determination of (κ, τ)-regular sets, using the main eigenvalues of a graph, are reviewed and some results about the determination of (0, 2)-regular sets are introduced. An algorithm for that purpose is also described. As an illustration, this algorithm is applied to the determination of maximum matchings in arbitrary graphs.

Domingos M. Cardoso, Carlos J. Luz, Maria F. Pacheco

A Multiobjective Electromagnetism-Like Algorithm with Improved Local Search

Abstract

The Multiobjective Electromagnetism-like Mechanism (MOEM) is a relatively new technique for solving continuous multiobjective optimization problems. In this work, an enhanced MOEM algorithm (EMOEM) with a modified local search phase is presented. This algorithm derives from the modification of some key components of MOEM including a novel local search strategy, which are relevant for improving its performance. To assess the new EMOEM algorithm, a comparison with an original MOEM algorithm and other three multiobjective optimization state-of-the-art approaches, OMOPSO (a multiobjective particle swarm optimization algorithm), MOSADE (a multiobjective differential evolution algorithm) and NSGA-II (a multiobjective evolutionary algorithm), is presented. Our aim is to assess the ability of these algorithms to solve continuous problems including benchmark problems and an inventory control problem. Experiments show that EMOEM performs better in terms of convergence and diversity when compared with the original MOEM algorithm. EMOEM is also competitive in comparison with the other state-of-art algorithms.

Pedro Carrasqueira, Maria João Alves, Carlos Henggeler Antunes

A Routing/Assignment Problem in Garden Maintenance Services

Abstract

We address a routing/assignment problem posed by Neoturf, which is a Portuguese company working in the area of project, building and garden’s maintenance. The aim is to define a procedure for scheduling and routing efficiently its clients of garden maintenance services. The company has two teams available throughout the year to handle all the maintenance jobs. Each team consists of two or three employees with a fully-equipped vehicle capable of carrying out every kind of maintenance service. At the beginning of each year, the number and frequency of maintenance interventions to conduct during the year, for each client, are agreed. Time windows are established so that visits to the client should occur only within these periods. There are clients that are supposed to be always served by the same team, but other clients can be served indifferently by any of the two teams. Since clients are geographically spread over a wide region, the total distance traveled while visiting clients is a factor that weighs heavily on the company costs. Neoturf is concerned with reducing these costs, while satisfying agreements with its clients. We give a mixed integer linear programming formulation for the problem, discuss limitations on the size of instances that can be solved to guarantee optimality, present a modification of the Clarke and Wright heuristic for the vehicle routing with time windows, and report preliminary computational results obtained with Neoturf data.

J. Orestes Cerdeira, Manuel Cruz, Ana Moura

A Column Generation Approach to the Discrete Lot Sizing and Scheduling Problem on Parallel Machines

Abstract

In this work, we study the discrete lot sizing and scheduling problem (DSLP) in identical parallel resources with (sequence-independent) setup costs and inventory holding costs. We propose a Dantzig-Wolfe decomposition of a known formulation and describe a branch-and-price and column generation procedure to solve the problem to optimality. The results show that the lower bounds provided by the reformulated model are stronger than the lower bounds provided by the linear programming (LP) relaxation of the original model.

António J. S. T. Duarte, J. M. V. Valério de Carvalho

A Tool to Manage Tasks of R&D Projects

Abstract

We propose a tool for managing tasks of Research and Development (R&D) projects. We define an R&D project as a network of tasks and we assume that different amounts of resources may be allocated to a task, leading to different costs and different average execution times. The advancement of a task is stochastic, and the management may reallocate resources while the task is being performed, according to its progress. We consider that a strategy for completing a task is a set of rules that define the level of resources to be allocated to the task at each moment. We discuss the evaluation of strategies for completing a task, and we address the problem of finding the optimal strategy. The model herein presented uses real options theory, taking into account operational flexibility, uncertain factors and the task progression. The evaluation procedure should maximize the financial value for the task and give the correspondent strategy to execute it. The procedure and model developed are general enough to apply to a generic task of an R&D project. It is simple and the input parameters can be inferred through company and/or project information.

Joana Fialho, Pedro Godinho, João Paulo Costa

An Exact and a Hybrid Approach for a Machine Scheduling Problem with Job Splitting

Abstract

The unrelated parallel machine scheduling problem with job splitting and setup times is addressed in this paper.

A time-indexed integer programming formulation of the problem to minimize a weighted function of the processing occurring both before and after jobs’ due dates is proposed. Moreover, we apply to a suitable decomposition of the integer programming model a recently proposed framework for decomposable integer programming/combinatorial optimization problems (SearchCol, meta-heuristic search by column generation) based on the combination of column generation and meta-heuristics.

A problem specific heuristic to use in the column generation component of the SearchCol is developed. To evaluate the effectiveness of the models and the proposed algorithms, computational tests are performed.

Luís Florêncio, Carina Pimentel, Filipe Alvelos

Testing Regularity on Linear Semidefinite Optimization Problems

Abstract

This paper presents a study of regularity of Semidefinite Programming (SDP) problems. Current methods for SDP rely on assumptions of regularity such as constraint qualifications (CQ) and well-posedness. In the absence of regularity, the characterization of optimality may fail and the convergence of algorithms is not guaranteed. Therefore, it is important to have procedures that verify the regularity of a given problem before applying any (standard) SDP solver. We suggest a simple numerical procedure to test within a desired accuracy if a given SDP problem is regular in terms of the fulfilment of the Slater CQ. Our procedure is based on the recently proposed DIIS algorithm that determines the immobile index subspace for SDP. We use this algorithm in a framework of an interactive decision support system. Numerical results using SDP problems from the literature and instances from the SDPLIB suite are presented, and a comparative analysis with other results on regularity available in the literature is made.

Eloísa Macedo

Decompositions and a Matheuristic for a Forest Harvest Scheduling Problem

Abstract

In this paper, we describe four decomposition models and a matheuristic based on column generation for the forest harvest scheduling problems subject to maximum area restrictions. Each of the four decomposition models can be seen as a Dantzig-Wolfe decomposition of the so-called bucket formulation (compact mixed integer program), in two cases with additional constraints on the connectivity of the buckets. The matheuristic is based on one of the decomposition models (the \(\mathcal{S}\)-knapsack-and-clique decomposition) and relies on the interaction of column generation with a general purpose mixed integer programming solver. We compare the quality of the solutions obtained for benchmark instances with the bucket formulation and with applying column generation and solving the integer restricted master problem (MipHeur) for the same time limit. We concluded that the proposed matheuristic provides, in general, better solutions than both the other approaches for small and medium instances, while, for large instances, the MipHeur approach outperformed the other two.

Isabel Martins, Filipe Alvelos, Miguel Constantino

A Routing and Waste Collection Case-Study

Abstract

Waste collection systems are among the main concerns of municipalities due to the resources involved. In this paper we present a hybrid heuristic to find the vehicle routes that should be performed to collect the household waste along the streets of a network. The solution method hybridizes the resolution of ILP based models with some simple heuristic ideas to assign services (collecting streets) to the vehicles. The Seixal case study, in the Lisbon Metropolitan Area, is tackled and some encouraging results are reported.

Karine Martins, Maria Cândida Mourão, Leonor Santiago Pinto

Exact Solutions to the Short Sea Shipping Distribution Problem

Abstract

Short sea shipping has several advantages over other means of transportation, recognized by EU members. The maritime transportation could be dealt like a combination of two well-known problems: the container stowage problem and routing planning problem. The integration of these two well-known problems results in a new problem CSSRP (Container stowage and ship routing problem) that is also an hard combinatorial optimization problem. The aim of this work is to solve the CSSRP using a mixed integer programming model. It is proved that regardless the complexity of this problem, optimal solutions could be achieved in a reduced computational time. For testing the mathematical model some problems based on real data were generated and a sensibility analysis was performed.

Ana Moura, Jorge Oliveira

A Consumption-Investment Problem with a Diminishing Basket of Goods

Abstract

We consider the problem faced by an economic agent trying to find the optimal strategies for the joint management of her consumption from a basket of K goods that may become unavailable for consumption from some random time τ _i onwards, and her investment portfolio in a financial market model comprised of one risk-free security and an arbitrary number of risky securities driven by a multi-dimensional Brownian motion. We apply previous abstract results on stochastic optimal control problem with multiple random time horizons to obtain a sequence of dynamic programming principles and the corresponding Hamilton-Jacobi-Bellman equations. We then proceed with a numerical study of the value function and corresponding optimal strategies for the problem under consideration in the case of discounted constant relative risk aversion utility functions (CRRA).

Abdelrahim S. Mousa, Diogo Pinheiro, Alberto A. Pinto

Assessing Technical and Economic Efficiency of the Artisanal Dredge Fleet in the Portuguese West Coast

Abstract

The bivalve dredge fleet is by far the most extensively studied fleet among the Portuguese artisanal segment. It is considered one of the most important artisanal fisheries, essentially due to the number of fishermen and vessels involved and to the high volume and value of the catches. The present study aimed to explore the efficiency of the dredge fleets that operated in the west coast of Portugal between 2006 and 2012. The methodology was based on the use of data envelopment analysis to assess vessels’ efficiency. The inputs considered included the number of days at sea, a biomass stock indicator, and the characteristics of the vessels (power, length and tonnage). The annual fishing quota per vessel was also included in the model as a contextual factor. In the technical efficiency analysis, the outputs were defined by the weight of captures for three different bivalve species. Using data on the prices of each species in the wholesale market, revenue efficiency was also estimated to complement the technical efficiency analysis. The results allowed to gain insights concerning the performance of both Northwest and Southwest fleets, considering both technical and economic aspects of the fishery. It was also possible to identify the benchmark vessels, whose practices should be followed by the other vessels of the fleet.

M. M. Oliveira, A. S. Camanho, M. B. Gaspar

Production Planning of Perishable Food Products by Mixed-Integer Programming

Abstract

In this paper, the main complexities related to the modeling of production planning problems of food products are addressed. We start with a deterministic base model and build a road-map on how to incorporate key features of food production planning. The different “ingredients” are organized around the model components to be extended: constraints, objective functions and parameters. We cover issues such as expiry dates, customers’ behavior, discarding costs, value of freshness and age-dependent demand. To understand the impact of these “ingredients”, we solve an illustrative example with each corresponding model and analyze the changes on the solution structure of the production plan. The differences across the solutions show the importance of choosing a model suitable to the particular business setting, in order to accommodate the multiple challenges present in these industries. Moreover, acknowledging the perishable nature of the products and evaluating the amount and quality of information at hands may be crucial in lowering overall costs and achieving higher service levels. Afterwards, the deterministic base model is extended to deal with an uncertain demand parameter and risk management issues are discussed using a similar illustrative example. Results indicate the increased importance of risk-management in the production planning of perishable food goods.

Maria João Pires, Pedro Amorim, Sara Martins, Bernardo Almada-Lobo

Sectors and Routes in Solid Waste Collection

Abstract

Collecting and transporting solid waste is a constant problem for municipalities and populations in general. Waste management should take into account the preservation of the environment and the reduction of costs. The goal with this paper is to address a real-life solid waste problem. The case reveals some general and specific characteristics which are not rare, but are not widely addressed in the literature. Furthermore, new methods and models to deal with sectorization and routing are introduced, which can be extended to other applications. Sectorization and routing are tackled following a two-phase approach. In the first phase, a new method is described for sectorization based on electromagnetism and Coulomb’s Law. The second phase addresses the routing problems in each sector. The paper addresses not only territorial division, but also the frequency with which waste is collected, which is a critical issue in these types of applications. Special characteristics related to the number and type of deposition points were also a motivation for this work. A new model for a Mixed Capacitated Arc Routing Problem with Limited Multi-Landfills is proposed and tested in real instances. The computational results achieved confirm the effectiveness of the entire approach.

Ana M. Rodrigues, J. Soeiro Ferreira

Solving Multilocal Optimization Problems with Parallel Stretched Simulated Annealing

Abstract

This work explores the use of parallel computing to solve multilocal optimization problems with Stretched Simulated Annealing (SSA), a method that combines simulated annealing with a stretching function technique. Several approaches to the parallelization of SSA are explored, based on different strategies for the refinement of the initial feasible region in subregions and its allocation to the processors involved. The parallel approaches, collectively named as PSSA (Parallel SSA), make viable what would otherwise be unfeasible with traditional sequential computing: an efficient search of the subregions that allows to find many more optima in a reasonable amount of time. To prove the merits of PSSA, several experimental metrics and numerical results are presented for a set of benchmark problems.

José Rufino, Ana I. Pereira

Efficiency and Productivity Assessment of Wind Farms

Abstract

This study develops a framework to provide insights regarding the performance of the farms of an energy player in the Portuguese wind sector. The focus of the wind farm performance assessment is on the operating stage which corresponds to the electrical energy generation process, during 2010 and 2011. In a first stage, Data Envelopment Analysis is used to measure the efficiency of wind farms in generating electrical energy from the resources available and non-discretionary variables. This analysis enables the identification of the best practices of the efficient farms which can be emulated by inefficient ones. In a second stage, changes in wind farms productivity are investigated using Malmquist index. Bootstrap procedures are applied to obtain statistical inference on the efficiency estimates. We conclude that almost all farms decreased overall productivity levels, mainly due to the decline in the productivity levels of the frontier, which is in accordance with the decrease in wind availability observed in 2011.

Clara Bento Vaz, Ângela Paula Ferreira

Multi-period and Multi-product Inventory Management Model with Lateral Transshipments

Abstract

Inventory management plays an important role in supply chains. Through a correct inventory management policy, supply chains can close the gap created by the imbalance between supply and demand, eliminating costly supply chains. This paper aims to contribute to this goal and presents an Inventory Management (IM) policy implemented on a Mixed Integer Linear Programming (MILP) model that optimizes the flow of products through a multi-period and multi-product supply chain. Normally distributed demands are received at the retailers who replenish their stock from the regional warehouses, which, in turn, are supplied by a central warehouse. Lateral transshipment is allowed among regional warehouses and among retailers. In order to validate and compare the proposed policy against commonly used policies, the Continuous Review and the Periodic Review policies are modeled using the same approach and acting over the same system. The comparison of inventory management policies shows that the IM policy outperforms the classical policies in terms of material availability leading to an overall reduction of operational costs.

Joaquim Jorge Vicente, Susana Relvas, Ana Paula Barbosa Póvoa

Periodic Versus Non-periodic Multipurpose Batch Plant Scheduling: A Paint Industry Case Study

Abstract

In order to guarantee the correct plant resources allocation, an efficient and uniform methodology is required to address the wide diversity of operational problems. The high flexibility requirement in the process industry, to be able to satisfy the market demand and service level, triggered the development of optimal scheduling methodologies in industrial management. In this work, a case study of a chemical process in the paint industry is presented, where the complexity of resource allocation and schedule optimisation is addressed through the use of the Resource Task Network (RTN) methodology. Two scheduling models are compared, considering a non-periodic and periodic operation mode. Mixed Integer Linear Programming (MILP) formulation are implemented where profit is maximized. The results of each formulation applied to a real case study are compared and discussed based in plant schedule resources allocation and required manpower.

Miguel Vieira, Tânia Pinto-Varela, Ana Paula Barbosa-Póvoa