Estudo Geralhttps://estudogeral.sib.uc.ptThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Wed, 28 Jul 2021 19:34:01 GMT2021-07-28T19:34:01Z50231- An automated reference point-like approach for multicriteria shortest path problemshttp://hdl.handle.net/10316/7920Title: An automated reference point-like approach for multicriteria shortest path problems
Authors: Clímaco, João; Craveirinha, José; Pascoal, Marta
Abstract: Abstract In this paper we introduce a method of analysis for the automated ordering and selection of solutions of a multicriteria shortest path model. The method is based on a reference point approach, where the paths in a specific priority region are ranked by non-decreasing order of a Chebyshev metric. In order to list paths according with this objective function a labelling algorithm is proposed. The developed method is applied in a video-traffic routing context. Computational results are presented and analysed, for randomly generated networks of significant dimension.
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/10316/79202006-01-01T00:00:00Z
- A bicriterion approach for routing problems in multimedia networkshttp://hdl.handle.net/10316/8351Title: A bicriterion approach for routing problems in multimedia networks
Authors: Clímaco, João C. N.; Craveirinha, José M. F.; Pascoal, Marta M. B.
Abstract: Routing problems in communication networks supporting multiple services, namely, multimedia applications, involve the selection of paths satisfying multiple constraints (of a technical nature) and seeking simultaneously to ldquooptimizerdquo the associated metrics. Although traditional models in this area are single-objective, in many situations, it is important to consider different, eventually conflicting, objectives. In this paper, we consider a bicriterion model dedicated to calculating nondominated paths for specific traffic flows (associated with video services) in multiservice high-speed networks. The mathematical formulation of the problem and the bicriterion algorithmic approach developed for its resolution are presented together with computational tests regarding an application to video-traffic routing in a high-speed network. The algorithmic approach is an adaptation of recent work by Ernesto Martins and his collaborators, namely, the MPS algorithm. © 2003 Wiley Periodicals, Inc.
Wed, 01 Jan 2003 00:00:00 GMThttp://hdl.handle.net/10316/83512003-01-01T00:00:00Z
- Finding non-dominated bicriteria shortest pairs of disjoint simple pathshttp://hdl.handle.net/10316/10091Title: Finding non-dominated bicriteria shortest pairs of disjoint simple paths
Authors: Clímaco, João C. N.; Pascoal, Marta M. B.
Thu, 30 Apr 2009 13:58:20 GMThttp://hdl.handle.net/10316/100912009-04-30T13:58:20Z
- Internet packet routing: Application of a K-quickest path algorithmhttp://hdl.handle.net/10316/5485Title: Internet packet routing: Application of a K-quickest path algorithm
Authors: Clímaco, João C. N.; Pascoal, Marta M. B.; Craveirinha, José M. F.; Captivo, M. Eugénia V.
Abstract: This paper describes a study on the application of an algorithm to rank the K-quickest paths to the routing of data packets in Internet networks. For this purpose an experimental framework was developed by considering two types of random generated networks. To simulate values of the IP packet sizes, a truncated Pareto distribution was defined, having in mind to reflect a key feature of Internet traffic, namely its self-similar stochastic nature. Results concerning the average CPU times of the algorithm for the different sets of experiments will be presented and discussed.
Mon, 01 Jan 2007 00:00:00 GMThttp://hdl.handle.net/10316/54852007-01-01T00:00:00Z
- Enumeração de soluções em problemas de optimização em redeshttp://hdl.handle.net/10316/1930Title: Enumeração de soluções em problemas de optimização em redes
Authors: Pascoal, Marta Margarida Braz
Abstract: A enumeração de K soluções de um dado problema combinatório é uma generalização, natural, desse problema combinatório, em que, em vez de se procurar uma única solução óptima, se pretende listar, por ordem não decrescente de um determinado custo, as K melhores soluções do problema. Este trabalho debruça-se sobre alguns problemas de determinação ordenada de soluções em Optimização em Redes, começando por analisar dois dos problemas clássicos, a enumeração de trajectos e a enumeração de caminhos, do ponto de vista mais habitual em que a função objectivo é aditiva, e para uma função objectivo genérica. Desenvolvem-se vários algoritmos para enumeração de trajectos e de caminhos que melhoram outros já conhecidos, incluindo processos para listar trajectos e caminhos relativamente a problemas que não verificam o Princípio de Optimalidade. Na sequência do estudo daqueles problemas analisa-se a enumeração de trajectos e caminhos óptimos segundo uma função objectivo concreta, conhecida como tempo total de transmissão e com aplicação nas áreas de redes de transportes e redes de telecomunicações. Introduzem-se dois algoritmos para enumerar caminhos segundo essa função objectivo e adaptam-se algoritmos de enumeração de caminhos e trajectos óptimos a esta função objectivo concreta. Aborda-se a determinação ordenada de soluções de problemas combinatórios na generalidade, com especial ênfase para a enumeração de afectações. Propõe-se um algoritmo para este último problema, donde resulta também uma rotina para determinar a segunda melhor afectação. Por fim, apresentam-se duas aplicações de algoritmos de enumeração a problemas de telecomunicações, nomeadamente um problema de encaminhamento de video-tráfego e um problema de encaminhamento de informação na internet.
Description: Tese de doutoramento em Matemática (Matemática Aplicada) apresentada à Fac. de Ciências e Tecnologia de Coimbra
Fri, 01 Apr 2005 00:00:00 GMThttp://hdl.handle.net/10316/19302005-04-01T00:00:00Z
- Algorithms for determining a node-disjoint path pair visiting specified nodeshttp://hdl.handle.net/10316/48006Title: Algorithms for determining a node-disjoint path pair visiting specified nodes
Authors: Gomes, Teresa; Martins, Lúcia; Ferreira, Sofia; Pascoal, Marta; Tipper, David
Abstract: The problem of calculating the shortest path that visits a given set of nodes is at least as difficult as the traveling salesman problem, and it has not received much attention. Nevertheless an efficient integer linear programming (ILP) formulation has been recently proposed for this problem. That ILP formulation is firstly adapted to include the constraint that the obtained path can be protected by a node-disjoint path, and secondly to obtain a pair of node disjoint paths, of minimal total additive cost, each having to visit a given set of specified nodes. Computational experiments show that these approaches, namely in large networks, may fail to obtain solutions in a reasonable amount of time. Therefore heuristics are proposed for solving those problems, that may arise due to network management constraints. Extensive computational results show that they are capable of finding a solution in most cases, and that the calculated solutions present an acceptable relative error regarding the cost of the obtained path or pair of paths. Further the CPU time required by the heuristics is significantly smaller than the required by the used ILP solver.
Description: Algorithms for determining a node-disjoint path pair visiting specified nodes
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/10316/480062017-01-01T00:00:00Z
- Constructing minimal cost/minimal SRLG spanning trees Over optical networks - An exact approachhttp://hdl.handle.net/10316/45083Title: Constructing minimal cost/minimal SRLG spanning trees Over optical networks - An exact approach
Authors: Craveirinha, José; Clímaco, João; Martins, Lúcia; Pascoal, Marta
Abstract: The construction of overlay or broadcast networks, based on spanning trees, over WDM optical networks with SRLG information has important applications in telecommunications. In this paper we propose a bicriteria optimisation model for calculating communication spanning trees over WDM
networks the objectives of which are the minimisation of the total number of different SRLGs of the tree links (seeking to maximise reliability) and the minimisation of the total bandwidth usage cost. An exact algorithm for generating the whole set of non-dominated solutions and methods for selecting a final solution in various decision environments, are put forward. An extensive experimental study on the application of the model, including two sets of experiments based on reference transport network topologies, with random link bandwidth occupations and with random SRLG assignments
to the links, is also presented, together with a discussion on potential advantages of the model.
Tue, 01 Jan 2013 00:00:00 GMThttp://hdl.handle.net/10316/450832013-01-01T00:00:00Z
- A comprehensive survey on the quickest path problemhttp://hdl.handle.net/10316/7731Title: A comprehensive survey on the quickest path problem
Authors: Pascoal, Marta; Captivo, M.; Clímaco, João
Abstract: Abstract This work is a survey on a special minsum-maxmin bicriteria problem, known as the quickest path problem, that can model the transmission of data between two nodes of a network. Moreover, the authors review the problems of ranking the K quickest paths, and the K quickest loopless paths, and compare them in terms of the worst-case complexity order. The classification presented led to the proposal of a new variant of a known K quickest loopless paths algorithm. Finally, applications of quickest path algorithms are mentioned, as well as some comparative empirical results.
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/10316/77312006-01-01T00:00:00Z
- A note on a new variant of Murty’s ranking assignments algorithmhttp://hdl.handle.net/10316/7762Title: A note on a new variant of Murty’s ranking assignments algorithm
Authors: Pascoal, Marta; Captivo, M. Eugénia; Clímaco, João
Abstract: In this paper a variant of Murty’s algorithm for ranking assignments according to cost is presented. It is shown that the worst-case computational complexity is better in this variant than in the original form of the algorithm. Computational results comparing three methods for ranking assignments are reported. They show that the behaviour of the new variant is also better in practice.
Wed, 01 Jan 2003 00:00:00 GMThttp://hdl.handle.net/10316/77622003-01-01T00:00:00Z
- A new improvement for a K shortest paths algorithmhttp://hdl.handle.net/10316/14424Title: A new improvement for a K shortest paths algorithm
Authors: Martins, Ernesto de Queirós Vieira; Pascoal, Marta Margarida Braz; Santos, José Luís Esteves
Mon, 01 Jan 2001 00:00:00 GMThttp://hdl.handle.net/10316/144242001-01-01T00:00:00Z
- Optimizing the proﬁt from a complex cascade of hydroelectric stations with recirculating waterhttp://hdl.handle.net/10316/14423Title: Optimizing the proﬁt from a complex cascade of hydroelectric stations with recirculating water
Authors: Korobeinikov, Andrei; Kovacec, Alexander; McGuinness, Mark; Pascoal, Marta; Pereira, Ana; Vilela, Sónia
Abstract: In modern reversible hydroelectric power stations it is possible to
reverse the turbine and pump water up from a downstream reservoir
to an upstream one. This allows the use of the same volume of water
repeatedly and was speciﬁcally developed for hydro-electric stations
operating with insuﬃcient water supply. Pumping water upstream
is usually done at times of low demand for electricity, to build up
reserves in order to be able to produce energy during peak hours, thus
balancing the load and making a proﬁt on the price diﬀerence.
In this paper, we consider a branched model for hydroelectric
power stations interacting in a complex cascade arrangement. The
goal of this study is to provide guidance in decision-making aimed
at maximizing the proﬁt. A detailed analysis is made of a simpler
reservoir conﬁguration, which indicates that even though the problem
is nonlinear, a bang-bang type of control is optimal, where the power
stations are operated at maximum rates of ﬂow. Some simple relation-
ships between price and timing of decisions are calculated directly. A
numerical algorithm is also developed.
Fri, 01 Jan 2010 00:00:00 GMThttp://hdl.handle.net/10316/144232010-01-01T00:00:00Z
- An algorithm for ranking quickest simple pathshttp://hdl.handle.net/10316/4102Title: An algorithm for ranking quickest simple paths
Authors: Pascoal, Marta M. B.; Captivo, M. Eugénia V.; Clímaco, João C. N.
Abstract: In this paper, an algorithm for ranking loopless paths in undirected networks, according to the transmission time, is presented. It is shown that the worst-case computational time complexity of the algorithm presented is , which is also the best-known complexity to solve this problem. The worst-case memory complexity is , which improves the existing algorithms. Finally, comparative computational results, with other algorithms for the same problem, are reported.
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/10316/41022005-01-01T00:00:00Z
- A new implementation of Yen’s ranking loopless paths algorithmhttp://hdl.handle.net/10316/7763Title: A new implementation of Yen’s ranking loopless paths algorithm
Authors: Martins, Ernesto Q. V.; Pascoal, Marta M. B.
Abstract: Yen’s algorithm is a classical algorithm for ranking the K shortest loopless paths between a pair of nodes in a network. In this paper an implementation of Yen’s algorithm is presented. Both the original algorithm and this implementation present ${\cal O}(Kn(m + n\log n))$ computational complexity order when considering a worst-case analysis. However, computational experiments are reported, which allow to conclude that in practice this new implementation outperforms two other, Perko’s implementation and a straightforward one.
Wed, 01 Jan 2003 00:00:00 GMThttp://hdl.handle.net/10316/77632003-01-01T00:00:00Z
- Algoritmos para a enumeração dos K trajectos mais curtoshttp://hdl.handle.net/10316/14415Title: Algoritmos para a enumeração dos K trajectos mais curtos
Authors: Pascoal, Marta Margarida Braz
Description: Dissertação de mestrado em Matemática apresentada à Faculdade de Ciências e Tecnologia da Universidade de Coimbra
Wed, 01 Jan 1997 00:00:00 GMThttp://hdl.handle.net/10316/144151997-01-01T00:00:00Z
- On a relaxed maximally disjoint path pair problem: A bicriteria approachhttp://hdl.handle.net/10316/90443Title: On a relaxed maximally disjoint path pair problem: A bicriteria approach
Authors: Pascoal, Marta; Clímaco, João
Abstract: In some application areas in telecommunication and transportation networks, there are problems requiring the determination of pairs of paths, aiming at minimizing the number of links, or link groups that they share, and their total cost. In this paper, a new bicriteria algorithm is proposed to deal with this problem. The algorithm is based on ranking pairs of paths by order of the total cost, using an adaptation of a path-ranking algorithm, after a suitable modiﬁcation of the network topology. Nondominated solutions are then ﬁltered by means of a dominance test. First, computational experiments are reported in order to assess the efﬁciency of the algorithm to calculate the whole set of nondominated pairs of paths. Second, we present computational results focused on the nondominated solutions close to the maximal disjoint pair (i.e., quasi-disjoint pairs only, for a predeﬁned admissible relaxation value) because in some application problems, such as shared risk link group pairs of paths, only those solutions have practical relevance.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/10316/904432020-01-01T00:00:00Z
- Bicriteria path problem minimizing the cost and minimizing the number of labelshttp://hdl.handle.net/10316/44383Title: Bicriteria path problem minimizing the cost and minimizing the number of labels
Authors: Pascoal, Marta; Captivo, M. Eugénia; Clímaco, João; Laranjeira, Ana
Abstract: We address a bicriterion path problem where each arc is assigned with a cost value and a label (such as a color). The first criterion intends to minimize the total cost of the path (the summation of its arc costs), while the second intends to get the solution with a minimal number of different labels. Since these criteria, in general, are conflicting criteria we develop an algorithm to generate the set of non-dominated paths. Computational experiments are presented and results are discussed.
Tue, 01 Jan 2013 00:00:00 GMThttp://hdl.handle.net/10316/443832013-01-01T00:00:00Z
- The minmax regret robust shortest path problem in a finite multi-scenario modelhttp://hdl.handle.net/10316/44387Title: The minmax regret robust shortest path problem in a finite multi-scenario model
Authors: Pascoal, Marta; Resende, Marisa
Abstract: The robust shortest path problem is a network optimization problem that can be defined to deal with uncertainty of costs associated with the arcs of a network. Two models have been considered for the robust shortest path problem: interval data and discrete data sets. This work addresses the robust shortest path problem with a minmax regret objective function on a finite multi-scenario model. This problem consists in finding an optimal path in the sense that it has the minimum maximum deviation from the shortest one over all scenarios. With this goal some properties of the problem and of its optimal solutions are derived. These results allow to introduce three approaches, a labeling algorithm, an algorithm based on ranking loopless paths, and a hybrid algorithm which ranks loopless paths in a suitable way to apply the early elimination of useless solutions. The algorithms are tested on random networks and compared with a previous method for the same problem. The obtained computational results are reported and discussed. They show that the labeling and the hybrid approaches outperform the others.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/10316/443872014-01-01T00:00:00Z
- An exact method for constructing minimal cost/minimal SRLG spanning trees over optical networkshttp://hdl.handle.net/10316/44523Title: An exact method for constructing minimal cost/minimal SRLG spanning trees over optical networks
Authors: Craveirinha, José M. F.; Clímaco, João C. N.; Martins, Lúcia M. R. A.; Pascoal, Marta
Abstract: The construction of overlay or broadcast networks, based on spanning trees, over WDM optical networks with SRLG information, has important applications in telecommunications. In this paper we propose a bicriteria optimization model for calculating communication spanning trees over WDM networks the objectives of which are the minimization of the total number of different SRLGs of the tree links (seeking to maximise reliability) and the minimization of the total bandwidth usage cost. An exact algorithm for generating the whole set of non-dominated solutions and methods for selecting a final solution in various decision environments are put forward. An extensive experimental study on the application of the model, including two sets of experiments based on reference transport network topologies, with random link bandwidth occupations and with random SRLG assignments to the links, is also presented, together with a discussion on potential advantages of the model.
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/10316/445232015-01-01T00:00:00Z
- Dynamic preprocessing for the minmax regret robust shortest path problem with finite multi-scenarioshttp://hdl.handle.net/10316/44390Title: Dynamic preprocessing for the minmax regret robust shortest path problem with finite multi-scenarios
Authors: Pascoal, Marta; Resende, Marisa
Abstract: The minmax regret robust shortest path problem aims at finding a path that minimizes the maximum deviation from the shortest paths over all scenarios. It is assumed that different arc costs are associated with different scenarios. This paper introduces a technique to reduce the network, before a minmax regret robust shortest path algorithm is applied. The preprocessing method enhances others explored in previous research. The introduced method acts dynamically and allows to update the conditions to be checked as new network nodes that can be discarded are identified. Computational results on random and Karasan networks are reported, which compare the dynamic preprocessing algorithm and its former static version. Two robust shortest path algorithms as well as the resolution of a mixed integer linear formulation by a solver are tested with and without these preprocessing rules.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/10316/443902016-01-01T00:00:00Z
- Path based algorithms for metro network designhttp://hdl.handle.net/10316/44388Title: Path based algorithms for metro network design
Authors: Laporte, Gilbert; Pascoal, Marta
Abstract: This paper proposes a practical methodology for the problem of designing a metro configuration under two criteria: population coverage and construction cost. It is assumed that a set of corridors defining a rough a priori geometric configuration is provided by the planners. The proposed algorithm consists of fine tuning the location of single alignments within each corridor. This is achieved by means of a bicriteria methodology that generates sets of non-dominated paths. These alignments are then combined to form a metro network by solving a bicriteria integer linear program. Extensive computational experiments confirm the efficiency of the proposed methodology.
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/10316/443882015-01-01T00:00:00Z
- Combining multicriteria analysis and tabu search for dial-a-ride problemshttp://hdl.handle.net/10316/44391Title: Combining multicriteria analysis and tabu search for dial-a-ride problems
Authors: Paquette, Julie; Cordeau, Jean-François; Laporte, Gilbert; Pascoal, Marta
Abstract: In the Dial-a-Ride Problem (DARP) the aim is to design vehicle routes for a set of users who must be transported between given origin and destination pairs, subject to a variety of side constraints. The standard DARP objective is cost minimization. In addition to cost, the objectives considered in this paper include three terms related to quality of service. This gives rise to a multicriteria problem. The problem is solved by means of a flexible and simple metaheuristic which efficiently integrates the reference point method for multicriteria optimization within a tabu search mechanism. Extensive tests were performed on randomly generated data and on real-life data provided by a major transporter in the Montreal area. Results indicate that the algorithm can yield a rich set of non-dominated solutions. It can also be employed to determine good trade-offs between cost and quality of service.
Tue, 01 Jan 2013 00:00:00 GMThttp://hdl.handle.net/10316/443912013-01-01T00:00:00Z
- An approach to determine unsupported non-dominated solutions in bicriteria integer linear programshttp://hdl.handle.net/10316/44522Title: An approach to determine unsupported non-dominated solutions in bicriteria integer linear programs
Authors: Clímaco, João C. N.; Pascoal, Marta
Abstract: In this paper, we introduce a method for finding both supported and unsupported non-dominated solutions of a bicriteria integer linear program (BCILP). One-phase and two-phase implementations of the method are described, and their interactive versions are outlined. The one-phase method and the second phase of the other are based on the minimization of weighted Chebyshev distances to well-chosen reference points. The dynamic change of reference point proposed here makes this method particularly suitable for interactive approaches. Computational experiments on random instances of three classes of BCILP are reported and discussed. The implementation of the proposed method as a method to approximate the set of non-dominated solutions is described and evaluated in computational terms.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/10316/445222016-01-01T00:00:00Z
- Bimaterial 3D printing using galvanometer scannershttp://hdl.handle.net/10316/90444Title: Bimaterial 3D printing using galvanometer scanners
Authors: Bandeira, Daniel; Pascoal, Marta; Santos, Beatriz
Abstract: In this work a 3D printing system based on the use of stereolithography and able to print parts made of two materials is studied. The 3D printing problem is divided into two subproblems. First, the problem of locating UV light emitters capable of reaching all areas of the polymer that constitutes the part to be printed is analyzed with the goal of minimizing the number of used emitters. Next, for each layer of the part the selected emitters are assigned to the areas of the polymer to be reached, with the goals of maximizing the angle of incidence of the UV light on the printing plane and minimizing the number of emitters that need to be activated. Integer linear formulations were introduced in an earlier work for both problems. Here these models are revisited and heuristic and exact methods are developed. Finally, the formulations and methods are analyzed for a case study. The results of the computational experiments are presented and discussed.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/10316/904442020-01-01T00:00:00Z