Hard combinatorial optimization (CO) problems pose challenges to traditional algorithmic solutions. The search space usually contains a large number of local optimal points and the computational cost to reach a global optimum may be too high for practical use. In this work, we conduct a comparative study of several state-of-the-art metaheuristic algorithms for hard CO problems solving. Our study is motivated by an industrial application called the Fertilizer Blends Optimization. We focus our study on a number of local search metaheuristics and analyze their performance in terms of both runtime efficiency and solution quality. We show that local search granularity (move step size) and the downhill move probability are two major factors that affect algorithm performance, and we demonstrate how experimental tuning work can be applied to obtain good performance of the algorithms. <p>Our empirical result suggests that the well-known Simulated Annealing (SA) algorithm showed the best performance on the fertilizer problem. The simple Iterated Improvement Algorithm (IIA) also performed surprisingly well by combining strict uphill move and random neighborhood selection. A novel approach, called Delivery Network Model (DNM) algorithm, was also shown to be competitive, but it has the disadvantage of being very sensitive to local search granularity. The constructive local search method (GRASP), which combines heuristic space sampling and local search, outperformed IIA without a construction phase; however, the improvement in performance is limited and generally speaking, local search performance is not sensitive to initial search positions in our studied fertilizer problem.

Hard combinatorial optimization (CO) problems pose challenges to traditional algorithmic solutions. The search space usually contains a large number of local optimal points and the computational cost to reach a global optimum may be too high for practical use. In this work, we conduct a comparative study of several state-of-the-art metaheuristic algorithms for hard CO problems solving. Our study is motivated by an industrial application called the Fertilizer Blends Optimization. We focus our study on a number of local search metaheuristics and analyze their performance in terms of both runtime efficiency and solution quality. We show that local search granularity (move step size) and the downhill move probability are two major factors that affect algorithm performance, and we demonstrate how experimental tuning work can be applied to obtain good performance of the algorithms. <p>Our empirical result suggests that the well-known Simulated Annealing (SA) algorithm showed the best performance on the fertilizer problem. The simple Iterated Improvement Algorithm (IIA) also performed surprisingly well by combining strict uphill move and random neighborhood selection. A novel approach, called Delivery Network Model (DNM) algorithm, was also shown to be competitive, but it has the disadvantage of being very sensitive to local search granularity. The constructive local search method (GRASP), which combines heuristic space sampling and local search, outperformed IIA without a construction phase; however, the improvement in performance is limited and generally speaking, local search performance is not sensitive to initial search positions in our studied fertilizer problem.

presente trabalho consolida um estudo para o planejamento de trajetória livre de colisão para um robô pneumático com 5 graus de liberdade aplicando três algoritmos metaheurísticos: algoritmos metaheurísticos por vagalumes, algoritmos metaheurísticos por enxames de partículas e algoritmos genéticos. No que se refere à aplicação de algoritmos metaheurísticos ao estudo de planejamento de trajetória de robôs manipuladores na presença de obstáculos, existem diferentes tipos de técnicas para evitar colisões que consideram os efeitos cinemáticos e dinâmicos na obtenção de trajetórias com o menor tempo, torque, etc. Neste estudo, são propostas contribuições à aplicação dessas técnicas especificamente a robôs manipuladores pneumáticos, sobretudo, no que diz respeito às características específicas dos servoposicionadores pneumáticos, como, por exemplo, a modelagem do atrito desses sistemas, o cálculo da massa equivalente, etc. A metodologia utilizada é definida em duas etapas. A primeira delas consiste na obtenção de pontos intermediários, adquiridos considerando a menor distância entre os mesmos e o ponto final, gerados considerando a presença de obstáculos (cilindros, cubos e esferas) Esses obstáculos são mapeados em regiões de colisão, que constituem restrições para o problema de otimização. A segunda etapa baseia-se no estudo do planejamento de trajetórias: aplicam-se b-splines de 5º e 7º grau na interpolação dos pontos intermediários, com vistas à obtenção de trajetórias que considerem, de um lado, a menor força dos atuadores associada à dinâmica do manipulador em estudo e, de outro, restrições cinemáticas e dinâmicas, determinadas por meio das características operacionais dos servoposicionadores pneumáticos. Os resultados mostram que a metodologia proposta é adequada para tarefas de manipulação de peças na presença de obstáculos, uma vez que os pontos intermediários situam-se fora da região de colisão nos três casos aqui apresentados. Além disso, quanto à segunda etapa, observou-se que as trajetórias de 5º e 7º grau apresentaram resultados similares, de maneira que os erros obtidos poderiam ser melhorados analisando aspectos associados ao controlador do robô em estudo. / The thesis presents a study for collision-free trajectory planning for a pneumatic robot with 5 degrees of freedom applying three metaheuristic algorithms: firefly metaheuristic algorithm, particle swarm optimization and genetic algorithms. As regards the application of metaheuristic algorithms to the study of the trajectory planning of manipulating robots in the presence of obstacles, there are different types of techniques to avoid collisions that consider the kinematic and dynamic effects, obtaining trajectories with the optimal time, torque, etc. In this study, contributions are made to the application of these techniques specifically to pneumatic manipulator robots, particularly with regard to the specific characteristics of pneumatic servo-actuators, such as friction modeling of these systems, calculation of equivalent mass, etc. The methodology used is defined in two steps. The first one consists of obtaining intermediate points, acquired considering the smallest distance between the intermediate points and the final point, generated considering the presence of obstacles (cylinders, cubes and spheres) These obstacles are mapped in collision regions, which are constraints to the optimization problem. The second step is based on the study of the trajectory planning: 5th and 7th degree b-splines are applied in the interpolation of the intermediate points, in order to obtain trajectories that consider the smallest actuator force associated to the dynamics of the manipulator and the kinematic and dynamic constraints, determined by the operational characteristics of pneumatic servo-positioners. The results show that the proposed methodology is suitable for tasks of manipulating parts in the presence of obstacles because the intermediate points are outside the collision region in the three cases presented here. In addition, it was observed that the trajectories of 5th and 7th degree presented similar results, so that the errors obtained could be improved by analyzing aspects associated to the controller of the robot.

presente trabalho consolida um estudo para o planejamento de trajetória livre de colisão para um robô pneumático com 5 graus de liberdade aplicando três algoritmos metaheurísticos: algoritmos metaheurísticos por vagalumes, algoritmos metaheurísticos por enxames de partículas e algoritmos genéticos. No que se refere à aplicação de algoritmos metaheurísticos ao estudo de planejamento de trajetória de robôs manipuladores na presença de obstáculos, existem diferentes tipos de técnicas para evitar colisões que consideram os efeitos cinemáticos e dinâmicos na obtenção de trajetórias com o menor tempo, torque, etc. Neste estudo, são propostas contribuições à aplicação dessas técnicas especificamente a robôs manipuladores pneumáticos, sobretudo, no que diz respeito às características específicas dos servoposicionadores pneumáticos, como, por exemplo, a modelagem do atrito desses sistemas, o cálculo da massa equivalente, etc. A metodologia utilizada é definida em duas etapas. A primeira delas consiste na obtenção de pontos intermediários, adquiridos considerando a menor distância entre os mesmos e o ponto final, gerados considerando a presença de obstáculos (cilindros, cubos e esferas) Esses obstáculos são mapeados em regiões de colisão, que constituem restrições para o problema de otimização. A segunda etapa baseia-se no estudo do planejamento de trajetórias: aplicam-se b-splines de 5º e 7º grau na interpolação dos pontos intermediários, com vistas à obtenção de trajetórias que considerem, de um lado, a menor força dos atuadores associada à dinâmica do manipulador em estudo e, de outro, restrições cinemáticas e dinâmicas, determinadas por meio das características operacionais dos servoposicionadores pneumáticos. Os resultados mostram que a metodologia proposta é adequada para tarefas de manipulação de peças na presença de obstáculos, uma vez que os pontos intermediários situam-se fora da região de colisão nos três casos aqui apresentados. Além disso, quanto à segunda etapa, observou-se que as trajetórias de 5º e 7º grau apresentaram resultados similares, de maneira que os erros obtidos poderiam ser melhorados analisando aspectos associados ao controlador do robô em estudo. / The thesis presents a study for collision-free trajectory planning for a pneumatic robot with 5 degrees of freedom applying three metaheuristic algorithms: firefly metaheuristic algorithm, particle swarm optimization and genetic algorithms. As regards the application of metaheuristic algorithms to the study of the trajectory planning of manipulating robots in the presence of obstacles, there are different types of techniques to avoid collisions that consider the kinematic and dynamic effects, obtaining trajectories with the optimal time, torque, etc. In this study, contributions are made to the application of these techniques specifically to pneumatic manipulator robots, particularly with regard to the specific characteristics of pneumatic servo-actuators, such as friction modeling of these systems, calculation of equivalent mass, etc. The methodology used is defined in two steps. The first one consists of obtaining intermediate points, acquired considering the smallest distance between the intermediate points and the final point, generated considering the presence of obstacles (cylinders, cubes and spheres) These obstacles are mapped in collision regions, which are constraints to the optimization problem. The second step is based on the study of the trajectory planning: 5th and 7th degree b-splines are applied in the interpolation of the intermediate points, in order to obtain trajectories that consider the smallest actuator force associated to the dynamics of the manipulator and the kinematic and dynamic constraints, determined by the operational characteristics of pneumatic servo-positioners. The results show that the proposed methodology is suitable for tasks of manipulating parts in the presence of obstacles because the intermediate points are outside the collision region in the three cases presented here. In addition, it was observed that the trajectories of 5th and 7th degree presented similar results, so that the errors obtained could be improved by analyzing aspects associated to the controller of the robot.

presente trabalho consolida um estudo para o planejamento de trajetória livre de colisão para um robô pneumático com 5 graus de liberdade aplicando três algoritmos metaheurísticos: algoritmos metaheurísticos por vagalumes, algoritmos metaheurísticos por enxames de partículas e algoritmos genéticos. No que se refere à aplicação de algoritmos metaheurísticos ao estudo de planejamento de trajetória de robôs manipuladores na presença de obstáculos, existem diferentes tipos de técnicas para evitar colisões que consideram os efeitos cinemáticos e dinâmicos na obtenção de trajetórias com o menor tempo, torque, etc. Neste estudo, são propostas contribuições à aplicação dessas técnicas especificamente a robôs manipuladores pneumáticos, sobretudo, no que diz respeito às características específicas dos servoposicionadores pneumáticos, como, por exemplo, a modelagem do atrito desses sistemas, o cálculo da massa equivalente, etc. A metodologia utilizada é definida em duas etapas. A primeira delas consiste na obtenção de pontos intermediários, adquiridos considerando a menor distância entre os mesmos e o ponto final, gerados considerando a presença de obstáculos (cilindros, cubos e esferas) Esses obstáculos são mapeados em regiões de colisão, que constituem restrições para o problema de otimização. A segunda etapa baseia-se no estudo do planejamento de trajetórias: aplicam-se b-splines de 5º e 7º grau na interpolação dos pontos intermediários, com vistas à obtenção de trajetórias que considerem, de um lado, a menor força dos atuadores associada à dinâmica do manipulador em estudo e, de outro, restrições cinemáticas e dinâmicas, determinadas por meio das características operacionais dos servoposicionadores pneumáticos. Os resultados mostram que a metodologia proposta é adequada para tarefas de manipulação de peças na presença de obstáculos, uma vez que os pontos intermediários situam-se fora da região de colisão nos três casos aqui apresentados. Além disso, quanto à segunda etapa, observou-se que as trajetórias de 5º e 7º grau apresentaram resultados similares, de maneira que os erros obtidos poderiam ser melhorados analisando aspectos associados ao controlador do robô em estudo. / The thesis presents a study for collision-free trajectory planning for a pneumatic robot with 5 degrees of freedom applying three metaheuristic algorithms: firefly metaheuristic algorithm, particle swarm optimization and genetic algorithms. As regards the application of metaheuristic algorithms to the study of the trajectory planning of manipulating robots in the presence of obstacles, there are different types of techniques to avoid collisions that consider the kinematic and dynamic effects, obtaining trajectories with the optimal time, torque, etc. In this study, contributions are made to the application of these techniques specifically to pneumatic manipulator robots, particularly with regard to the specific characteristics of pneumatic servo-actuators, such as friction modeling of these systems, calculation of equivalent mass, etc. The methodology used is defined in two steps. The first one consists of obtaining intermediate points, acquired considering the smallest distance between the intermediate points and the final point, generated considering the presence of obstacles (cylinders, cubes and spheres) These obstacles are mapped in collision regions, which are constraints to the optimization problem. The second step is based on the study of the trajectory planning: 5th and 7th degree b-splines are applied in the interpolation of the intermediate points, in order to obtain trajectories that consider the smallest actuator force associated to the dynamics of the manipulator and the kinematic and dynamic constraints, determined by the operational characteristics of pneumatic servo-positioners. The results show that the proposed methodology is suitable for tasks of manipulating parts in the presence of obstacles because the intermediate points are outside the collision region in the three cases presented here. In addition, it was observed that the trajectories of 5th and 7th degree presented similar results, so that the errors obtained could be improved by analyzing aspects associated to the controller of the robot.

The design of public transportation networks includes the problem of finding efficient transit routes. This problem is called the Urban Transit Routing Problem (UTRP) and it is a highly complex combinatorial optimization problem. Solving the UTRP and finding more efficient transit routes may lead to large cost savings as well as shorter average travel times for the passengers. The most common approach to solving it, in the literature, is with the usage of a metaheuristic algorithm. The purpose of this thesis is to solve the UTRP with such an algorithm, and to make the algorithm efficient. To this end, the multi-objective Discrete Cuckoo Search (MODCS) algorithm is introduced and it solves the UTRP with respect to both passenger and operator objectives. Two network instances are solved for: the common benchmark network of Mandl's network, and the Södertälje bus network. For Mandl's network, the results were compared to other algorithms in the literature. The results showed great performance of the MODCS algorithm with respect to the passenger objective, and not as good with respect to the operator objective. The computation times of the MODCS were higher than those of the other algorithms. For the Södertälje bus network, the MODCS algorithm found route sets with significantly better objective values than those of a previous master thesis algorithm. Furthermore, the average computation times of the MODCS algorithm were much less than those of the previous master thesis algorithm. / Att designa kollektivtrafiknät inkluderar problemet av att hitta effektiva kollektivtrafiklinjer. Detta problem kallas för Urban Transit Routing Problem (UTRP) och det är ett mycket komplext kombinatoriskt optimeringsproblem. Att lösa UTRP och hitta effektivare kollektivtrafiklinjer kan leda till stora besparingar samt lägre genomsnittliga restider för passagerare. Den vanligaste metoden för att lösa problemet, inom litteraturen, är med en metaheuristisk algoritm. Syftet med detta examensarbete är att lösa UTRP med en sådan algoritm samt att göra algoritmen effektiv. Den multiobjektiva diskreta Cuckoo Search (MODCS) algoritmen blev introducerad för att uppnå syftet, och den löste UTRP med avseende på både passagerar- och operatörintressen. Två olika nätverk har lösts: Mandls nätverk som är det vanligaste att jämföra med, och Södertäljes bussnätverk. Resultaten för Mandls nätverk blev jämförda med resultaten av andra algoritmer i litteraturen. MODCS algoritmen hittade linjenät med mycket bra värden för passagerarintresset, men inte lika bra för operatörintresset. Beräkningstiden för MODCS var högre än för de andra algoritmerna. För Södertäljes bussnätverk så hittade MODCS algoritmen linjenät som hade mycket bättre objektiva värden än en algoritm från ett tidigare examensarbete. De genomsnittliga beräkningstiderna var dessutom mycket lägre för MODCS än för algoritmen från det tidigare examensarbetet.

[ES] Un aprovechamiento racional y ajustado de los recursos hídricos disponibles en el regadío implica la necesidad de disponer de infraestructuras que mediante conducciones a presión permitan llevar desde captación hasta la planta los volúmenes requeridos. Los sistemas de riego a presión, tanto a nivel colectivo como en parcela, permiten un alto control sobre el agua aplicada y garantizan una alta eficiencia de aplicación. La adopción de estos sistemas de riego ha llevado en los últimos 30 años a la construcción y puesta en marcha de numerosas redes colectivas de riego a presión. En el marco mediterráneo donde el modelo productivo se basa en una agricultura intensiva de parcelas de tamaño pequeño y medio (superficies medias no superiores a 0,5 ha), el sistema de distribución del agua desde la red a la parcela se realiza normalmente a través de hidrantes denominados multiusuario. La localización y capacidad hidráulica de estos elementos es un tema poco estudiado hasta la fecha. Tradicionalmente su localización y definición de los elementos que lo componen ha corrido a cargo de la propia experiencia en estos campos de los ingenieros, desconociendo en muchos casos como afectan estos parámetros al funcionamiento final de la instalación y a los costes que supone dicha inversión. Esta Tesis aborda el estudio de estos aspectos con el objetivo de obtener una metodología de cálculo basada en la utilización de los SIG que optimice tanto la ubicación de los hidrantes como el trazado de conducciones entre los mismos desde el punto de alimentación. Como punto de partida, se definió la capacidad hidráulica de los mismos en cuanto a caudal y número de tomas que pueden abastecer, dando unas recomendaciones basadas en estudios hidráulicos de las características finales que deben tener los mismos en cada caso y de las tomas individuales a parcela. Seguidamente, se abordó la problemática de la localización, relacionada directamente con el anterior punto. En este caso, mediante la utilización de distintas herramientas de geoprocesos que ofrecen los softwares basados en SIG, se obtuvieron las localizaciones que minimizan tanto los costes energéticos como los de inversión. Finalmente, obtenida la ubicación, se estableció el trazado de las conducciones desde la toma hasta cada uno de los hidrantes. En este caso, los criterios a tener en cuenta fueron función del tipo de vía por el que se pretenden trazar (camino rural, carretera, cauce, etc) llevándose a cabo mediante la elaboración de un mapa ráster de resistencias donde la solución óptima fue aquella que menos resistencia acumulada ofrecía. Para su elaboración se requirió del apoyo de metodologías de análisis Multicriterio como AHP. Toda la metodología de trabajo fue aplicada sobre doce casos de estudio reales y se comparará con el diseño de ingenieros proyectistas especialistas en el campo de la modernización de regadíos. Los resultados obtenidos mediante el uso de la metodología planteada arrojaron unos ahorros en los costes totales de hasta el 15 % respecto al dimensionado externo. En todos ellos se obtuvo la misma tendencia, pese a obtener mayor número de hidrantes multiusuario, se redujeron los costes totales de instalación de la red. Como conclusión puede decirse que la metodología aportada redujo considerablemente los costes y planteó unos criterios objetivos a la hora del diseño y dimensionado de las redes. De este modo se redujo la subjetividad aportada por el proyectista. / [CAT] Un aprofitament racional i ajustat dels recursos hídrics disponibles en el regadiu implica la necessitat de disposar d'infraestructures que mitjançant conduccions a pressió permeten portar des de captació fins a la planta els volums requerits. Els sistemes de reg a pressió, tant a nivell col·lectiu com en parcel·la, permeten un alt control sobre l'aigua aplicada i garanteixen una alta eficiència d'aplicació. L'adopció d'aquests sistemes de reg ha portat en els últims 30 anys la construcció i posada en marxa de nombroses xarxes col·lectives de reg a pressió. En el marc mediterrani on el model productiu es basa en una agricultura intensiva de parcel·les de grandària petita i mitjana (superfícies mitjanes no superiors a 0,5 ha), el sistema de distribució de l'aigua des de la xarxa a la parcel·la es realitza normalment a través d'hidrants denominats multiusuari. La localització i capacitat hidràulica d'aquests elements és un tema poc estudiat fins hui. Tradicionalment la seua localització i definició dels elements que ho componen ha sigut a càrrec de la pròpia experiència en aquests camps dels enginyers, desconeixent en molts casos com afecten aquests paràmetres al funcionament final de la instal·lació i als costos que suposa aquesta inversió. Aquesta Tesi aborda l'estudi d'aquests aspectes amb l'objectiu d'obtindre una metodologia de càlcul basada en la utilització dels SIG que optimitze tant la ubicació dels hidrants com el traçat de conduccions entre els mateixos des del punt d'alimentació. Com a punt de partida, es va definir la capacitat hidràulica dels mateixos quant a cabal i nombre de tomes que poden proveir, donant unes recomanacions basades en estudis hidràulics de les característiques finals que han de tindre els mateixos en cada cas i de les preses individuals a parcel·la. Seguidament, es va abordar la problemàtica de la localització, relacionada directament amb l'anterior punt. En aquest cas, mitjançant la utilització de diferents eines de geoprocesos que ofereixen els softwares basats en SIG, es van obtindre les localitzacions que minimitzen tant els costos energètics com els d'inversió. Finalment, obtinguda la ubicació, es va establir el traçat de les conduccions des de la presa fins cadascun dels hidrants. En aquest cas, els criteris a tindre en compte van ser funció del tipus de via pel qual es pretenen traçar (camí rural, carretera, llit, etc) duent-se a terme mitjançant l'elaboració d'un mapa ráster de resistències on la solució òptima va ser aquella que menys resistència acumulada oferia. Per a la seua elaboració es va requerir del suport de metodologies d'anàlisi Multicriteri com AHP. Tota la metodologia de treball va ser aplicada sobre dotze casos d'estudi reals i va comparar amb el disseny d'enginyers projectistes especialistes en el camp de la modernització de regadius. Els resultats obtinguts mitjançant l'ús de la metodologia plantejada van llançar uns estalvis en els costos totals de fins al 15% respecte al dimensionament extern. En tots ells es va obtindre la mateixa tendència, malgrat obtindre major nombre d'hidrants multiusuari, es van reduir els costos totals d'instal·lació de la xarxa. Com a conclusió pot dir-se que la metodologia aportada va reduir considerablement els costos i va plantejar uns criteris objectius a l'hora del disseny i dimensionament de les xarxes. D'aquesta manera es va reduir la subjectivitat aportada pel projectista. / [EN] Rational and adjusted use of the water resources available in irrigation implies the need to have infrastructures that, by means of pressure pipes, can carry out the required volumes from the catchment to the plant. Pressurized irrigation systems, both at the collective level and on the plot, allow high control over the water applied and guarantee high application efficiency. The adoption of these irrigation systems has led in the last 30 years to the construction and start-up of numerous collective pressurized irrigation networks. In the Mediterranean framework, where the production model is based on intensive agriculture of small and medium-sized plots (average surfaces not exceeding 0.5 ha), the water distribution system from the network to the plot is normally carried out through of -called multi-user hydrants. The location and hydraulic capacity of these elements is a subject little studied to date. Traditionally, its location and definition of the elements that compose it have been carried out by the engineers' own experience in these fields, in many cases unaware of how these parameters affect the final operation of the installation and the costs involved in said investment. This thesis deals with the study of these aspects to obtain a calculation methodology based on the use of GIS that optimizes both the location of the hydrants and the layout of the pipes between them from the point of supply. As a starting point, their hydraulic capacity was defined in terms of flow rate and number of intakes they can supply, giving recommendations based on hydraulic studies of the final characteristics that they should have in each case and of the individual intakes on a plot. Next, the problem of location, directly related to the previous point, was addressed. In this case, by using different geoprocessing tools offered by GIS-based software, locations that minimize both energy and investment costs were obtained. Finally, once the location was obtained, the layout of the pipes from the intake to each of the hydrants was established. In this case, the criteria to be taken into account were a function of the type of road along which it is intended to be traced (rural road, highway, riverbed, etc.) carried out by preparing a raster map of resistances where the optimal solution was that that offered less accumulated resistance. For its elaboration, the support of Multicriteria analysis methodologies such as AHP was required. The entire work methodology was applied to twelve real case studies and will be compared with the design of specialist project engineers in the field of irrigation modernization. The results obtained through the use of the proposed methodology showed savings in total costs of up to 15% compared to external dimensioning. The same trend was obtained in all of them, despite obtaining a greater number of multi-user hydrants, the total costs of installing the network were reduced. In conclusion, it can be said that the methodology provided considerably reduced costs and proposed objective criteria when designing and sizing the networks. In this way, the subjectivity provided by the designer was reduced. / González Pavón, C. (2023). Optimización de la localización de hidrantes multiusuario y trazado de redes de riego a presión mediante la utilización de SIG [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/192926