A physical packing sequence algorithm for the container loading problem with static mechanical equilibrium conditions

The container loading problem (CLP) is a combinatorial optimization problem for the spatial arrangement of cargo inside containers so as to maximize the usage of space. The algorithms for this problem are of limited practical applicability if real-world constraints are not considered, one of the most important of which is deemed to be stability. This paper addresses static stability, as opposed to dynamic stability, looking at the stability of the cargo during container loading. This paper proposes two algorithms. The first is a static stability algorithm based on static mechanical equilibrium conditions that can be used as a stability evaluation function embedded in CLP algorithms (e.g. constructive heuristics, metaheuristics). The second proposed algorithm is a physical packing sequence algorithm that, given a container loading arrangement, generates the actual sequence by which each box is placed inside the container, considering static stability and loading operation efficiency constraints.

Dynamic stability metrics for the container loading problem

The Container Loading Problem (CLP) literature has traditionally evaluated the dynamic stability of cargo by applying two metrics to box arrangements: the mean number of boxes supporting the items excluding those placed directly on the floor (M1) and the percentage of boxes with insufficient lateral support (M2). However, these metrics, that aim to be proxies for cargo stability during transportation, fail to translate real-world cargo conditions of dynamic stability. In this paper two new performance indicators are proposed to evaluate the dynamic stability of cargo arrangements: the number of fallen boxes (NFB) and the number of boxes within the Damage Boundary Curve fragility test (NB_DBC). Using 1500 solutions for well-known problem instances found in the literature, these new performance indicators are evaluated using a physics simulation tool (StableCargo), replacing the real-world transportation by a truck with a simulation of the dynamic behaviour of container loading arrangements. Two new dynamic stability metrics that can be integrated within any container loading algorithm are also proposed. The metrics are analytical models of the proposed stability performance indicators, computed by multiple linear regression. Pearson’s r correlation coefficient was used as an evaluation parameter for the performance of the models. The extensive computational results show that the proposed metrics are better proxies for dynamic stability in the CLP than the previous widely used metrics.

Algoritmo genético para empacotamento de contentores

No âmbito da investigação operacional o problema de empacotamento de contentores é conhecido por procurar definir uma configuração de carga, de forma a otimizar a utilização de um espaço disponível para efetuar o empacotamento. Este problema pode ser apresentado em diversas formas, formas estas que variam em função das características de cada empacotamento. Estas características podem ser: o tipo de carga que se pretende carregar (homogénea ou heterogénea), a possibilidade de a carga poder sofrer rotações em todas as suas dimensões ou apenas em algumas, o lucro que está associado a cada caixa carregada ou restrições inerentes ao contentor como por exemplo dimensões. O interesse pelo estudo de problemas de empacotamento de contentores tem vindo a receber cada vez mais ênfase por várias razões, uma delas é o interesse financeiro dado que o transporte é uma prática que representa custos, sendo importante diminuir estes custos aproveitando o volume do contentor da melhor forma. Outra preocupação que motiva o estudo deste problema prende-se com fatores ambientes, onde se procura racionalizar os recursos naturais estando esta também ligada a questões financeiras. Na literatura podem ser encontradas varias propostas para solucionar este problema, cada uma destas dirigidas a uma variante do problema, estas propostas podem ser determinísticas ou não determinísticas onde utilizam heurísticas ou metaheurísticas. O estudo realizado nesta dissertação descreve algumas destas propostas, nomeadamente as metaheurísticas que são utilizadas na resolução deste problema. O trabalho aqui apresentado traz também uma nova metaheurísticas, mais precisamente um algoritmo genético que terá como objetivo, apresentar uma configuração de carga para um problema de empacotamento de um contentor. O algoritmo genético tem como objetivo a resolução do seguinte problema: empacotar várias caixas retangulares com diversos tamanhos num contentor. Este problema é conhecido como Bin-Packing. A novidade que este algoritmo genético vai introduzir nas diversas soluções apresentadas até à data, é uma nova forma de criar padrões iniciais, ou seja, é utilizada a heurística HSSI (Heurística de Suavização de Superfícies Irregulares) que tem como objetivo criar uma população inicial de forma a otimizar o algoritmo genético. A heurística HSSI tenta resolver problemas de empacotamento simulando, o comportamento da maioria das pessoas ao fazer este processo na vida real, contudo, tem um campo de busca reduzido entre as soluções possíveis e será então utilizado um algoritmo genético para ampliar este campo de busca e explorar novas soluções. No final pretende-se obter um software onde será possível configurar um dado problema de empacotamento de um contentor e obter, a solução do mesmo através do algoritmo genético. Assim sendo, o estudo realizado tem como principal objetivo contribuir com pesquisas e conclusões, sobre este problema e trazer uma nova proposta de solução para o problema de empacotamento de contentores.

A user-centered interface for scheduling problem definition

In this paper we present a user-centered interface for a scheduling system. The purpose of this interface is to provide graphical and interactive ways of defining a scheduling problem. To create such user interface an evaluation-centered user interaction development method was adopted: the star life cycle. The created prototype comprises the Task Module and the Scheduling Problem Module. The first one allows users to define a sequence of operations, i.e., a task. The second one enables a scheduling problem definition, which consists in a set of tasks. Both modules are equipped with a set of real time validations to assure the correct definition of the necessary data input for the scheduling module of the system. The usability evaluation allowed us to measure the ease of interaction and observe the different forms of interaction provided by each participant, namely the reactions to the real time validation mechanism.

Addressing the facilities layout design problem through constraint logic programming

One of the most difficult problems that face researchers experimenting with complex systems in real world applications is the Facility Layout Design Problem. It relies with the design and location of production lines, machinery and equipment, inventory storage and shipping facilities. In this work it is intended to address this problem through the use of Constraint Logic Programming (CLP) technology. The use of Genetic Algorithms (GA) as optimisation technique in CLP environment is also an issue addressed. The approach aims the implementation of genetic algorithm operators following the CLP paradigm.

An optimal scheduling problem in distribution networks considering V2G

This paper addresses the problem of energy resource scheduling. An aggregator will manage all distributed resources connected to its distribution network, including distributed generation based on renewable energy resources, demand response, storage systems, and electrical gridable vehicles. The use of gridable vehicles will have a significant impact on power systems management, especially in distribution networks. Therefore, the inclusion of vehicles in the optimal scheduling problem will be very important in future network management. The proposed particle swarm optimization approach is compared with a reference methodology based on mixed integer non-linear programming, implemented in GAMS, to evaluate the effectiveness of the proposed methodology. The paper includes a case study that consider a 32 bus distribution network with 66 distributed generators, 32 loads and 50 electric vehicles.

Ant colony search algorithm for the optimal power flow problem

To maintain a power system within operation limits, a level ahead planning it is necessary to apply competitive techniques to solve the optimal power flow (OPF). OPF is a non-linear and a large combinatorial problem. The Ant Colony Search (ACS) optimization algorithm is inspired by the organized natural movement of real ants and has been successfully applied to different large combinatorial optimization problems. This paper presents an implementation of Ant Colony optimization to solve the OPF in an economic dispatch context. The proposed methodology has been developed to be used for maintenance and repairing planning with 48 to 24 hours antecipation. The main advantage of this method is its low execution time that allows the use of OPF when a large set of scenarios has to be analyzed. The paper includes a case study using the IEEE 30 bus network. The results are compared with other well-known methodologies presented in the literature.

Problem-Based Learning e suas implicações: breve revisão teórica

A ESTSP-IPP implementou em 2008-2009 um novo modelo pedagógico, o PBL, em três licenciaturas. Este modelo tem sido considerado capaz de promover a aquisição de conhecimentos mas também o desenvolvimento de competências transversais valorizadas no mercado de trabalho; orienta-se em torno de problemas significativos da realidade profissional, trabalhados segundo a metodologia dos sete passos, destacando-se a aprendizagem através de pesquisa individual e trabalho de grupo; e visa ainda desenvolver processos cognitivos e metacognitivos como levantar hipóteses, comparar, analisar, interpretar e avaliar. Neste artigo, caracterizamos brevemente o modelo e respectivas implicações, justificando o interesse em investigar as repercussões da sua implementação.

Ant colony system based approach to single machine scheduling problems: weighted tardiness scheduling problem

The paper introduces an approach to solve the problem of generating a sequence of jobs that minimizes the total weighted tardiness for a set of jobs to be processed in a single machine. An Ant Colony System based algorithm is validated with benchmark problems available in the OR library. The obtained results were compared with the best available results and were found to be nearer to the optimal. The obtained computational results allowed concluding on their efficiency and effectiveness.

Solving MPCC problem with the hyperbolic penalty function

The main goal of this work is to solve mathematical program with complementarity constraints (MPCC) using nonlinear programming techniques (NLP). An hyperbolic penalty function is used to solve MPCC problems by including the complementarity constraints in the penalty term. This penalty function [1] is twice continuously differentiable and combines features of both exterior and interior penalty methods. A set of AMPL problems from MacMPEC [2] are tested and a comparative study is performed.

Solving a signalized traffic intersection problem with an hyperbolic penalty function

Mathematical Program with Complementarity Constraints (MPCC) finds many applications in fields such as engineering design, economic equilibrium and mathematical programming theory itself. A queueing system model resulting from a single signalized intersection regulated by pre-timed control in traffic network is considered. The model is formulated as an MPCC problem. A MATLAB implementation based on an hyperbolic penalty function is used to solve this practical problem, computing the total average waiting time of the vehicles in all queues and the green split allocation. The problem was codified in AMPL.

Caracterização de águas do processo e optimização dos consumos de água nos vários circuitos da Petibol, S.A. – Embalagens de Plástico

A empresa Petibol, S.A. – Embalagens de plástico centra-se na produção de embalagens de plástico a partir da matéria-prima Poliestireno Expandido (EPS) e Polipropileno Expandido (EPP). A empresa possui uma preocupação ao nível da qualidade da água e do aproveitamento energético, tendo desta forma surgido a realização do estudo na unidade industrial, com o objectivo de anular e/ou diminuir as possíveis lacunas existentes na unidade industrial. Numa primeira etapa foi realizada uma caracterização global à qualidade da água e à empresa, actualizando-se os esquemas já existentes, contabilizando-se os custos actuais relativamente aos processos no circuito da água (arrefecimento, aquecimento e pressurização), e por fim, efectuou-se um levantamento in loco do circuito de água, relativamente à pressão, temperatura e caudal. Numa fase posterior, foram propostos equipamentos e processos, tendo em vista a colmatação dos problemas identificados, realizando-se um subsequente estudo relativamente aos custos inerentes a esses novos processos. A caracterização à água foi avaliada em diferentes pontos do circuito industrial, tendo-se determinado na Sala de Bombagem que o filtro de areia não possuía as dimensões mais apropriadas, existindo também um problema a nível mecânico associado ao processo de contra-lavagem. Tais factos podem ser a causa da ocorrência de um aumento do teor de sólidos após a passagem na camada filtrante. Relativamente ao amaciador, este deveria amaciar de forma completa a água para alimentação à caldeira, embora se tenha registado à saída do amaciador uma dureza de 21,3 mg/L, denunciando problemas na troca iónica. No que toca à água de alimentação à caldeira, verifica-se a existência de parâmetros que não se encontram de acordo com os critérios enunciados para uma óptima qualidade, sendo eles o pH (10,14), condutividade (363 μS/cm), teor de ferro (1,21 mg/L) e a dureza (16 mg/L). De salientar que somente o teor de cobre, que se encontra em quantidades vestigiais, apresenta-se de acordo com os valores impostos. No que respeita à água da caldeira, esta apresenta parâmetros incompatíveis com os recomendados, sendo eles a condutividade (7350 μS/cm), teor de sólidos dissolvidos (5248 mg/L) e alcalinidade total (780 mg/L). De referir que o valor de pH (11,8) não se encontra de acordo com a aplicação do tratamento “fosfato-pH coordenado”. Em relação aos parâmetros com valores que se encontram dentro dos limites, estes correspondem à dureza (0 mg/L), ao teor de fosfatos (45 mg/L) e teor de sílica (0 mg/L). A água do circuito de arrefecimento foi sujeita a uma análise microbiológica, que corroborou a presença de um biofilme. Um dos problemas enunciados pela empresa, prendia-se com a impossibilidade de descarga, no colector municipal, dos condensados dos compressores, visto apresentarem uma quantidade de óleo de cerca de 43,3 mg/L, equivalente a quatro vezes o valor limite de emissão, de acordo com a legislação municipal. Por fim, o efluente de descarga industrial apresenta um valor de pH (10,3) acima do intervalo permitido por lei (6,0 – 9,0), sendo que a corrente que mais contribui para este acréscimo de pH corresponde à corrente proveniente da água de purga, visto esta apresentar um valor de pH de 12,22. De maneira a contornar os parâmetros enunciados, é proposto a substituição do filtro de areia da Sala de Bombagem, assim como a inserção de um conjunto de medidas de remoção de ferro e desinfecção, sendo a conjugação de arejamento, coagulação, filtração e desinfecção, por parte do hipoclorito, a proposta apresentada. Aos condensados dos compressores é apresentado um sistema de separação, que possibilita a remoção do óleo da água, e uma consequente descarga da mesma. Actualmente, não existe qualquer filtro de areia no circuito de arrefecimento da água, sendo proposto assim esse equipamento, de forma a minorar o desenvolvimento da população microbiana, bem como a permitir uma maior eficiência na transferência de calor na torre de arrefecimento. Relativamente à descarga industrial, é recomendável a colocação de um sistema de regularização automática de pH. A inserção de uma válvula de três vias permite um aproveitamento energético e de água, a partir da confluência da água oriunda dos furos com a água do tanque de água fria, sendo posteriormente alimentada à central de vácuo. No estudo da recuperação energética, um outro equipamento avaliado correspondeu à serpentina, no entanto, verificou-se que a poupança no consumo de gás natural era de apenas 0,005%, o que não se mostrou uma proposta viável. O orçamento de todos os equipamentos é de 11.720,76 €, possibilitando não só um melhor funcionamento industrial, como um menor impacto a nível ambiental. Os custos futuros de funcionamento aumentam em 3,36%, tendo a pressurização um aumento do seu custo em 3,4% em relação ao custo actual, verificando-se um custo anual de 10.781,21€, em relação aos processos de arejamento, coagulação e desinfecção.

New insights on integer-programming models for the kidney exchange problem

In recent years several countries have set up policies that allow exchange of kidneys between two or more incompatible patient–donor pairs. These policies lead to what is commonly known as kidney exchange programs. The underlying optimization problems can be formulated as integer programming models. Previously proposed models for kidney exchange programs have exponential numbers of constraints or variables, which makes them fairly difficult to solve when the problem size is large. In this work we propose two compact formulations for the problem, explain how these formulations can be adapted to address some problem variants, and provide results on the dominance of some models over others. Finally we present a systematic comparison between our models and two previously proposed ones via thorough computational analysis. Results show that compact formulations have advantages over non-compact ones when the problem size is large.