We give a new full explanation of the Tacoma Narrows Bridge collapse, occurred on November 7, 1940. Our explanation involves both structural phenomena, such as parametric resonances, and sophisticated mathematical tools, such as the Floquet theory. Contrary to all previous attempts, our explanation perfectly fits, both qualitatively and quantitatively, with what was observed that day. With this explanation at hand, we set up and partially solve some optimal control and shape optimization problems (both analytically and numerically) aiming to improve the stability of bridges. The control parameter to be optimized is the strength of a partial damping term whose role is to decrease the energy within the deck. Shape optimization intends to give suggestions for the design of future bridges.
Citation: Filippo Gazzola, Mohamed Jleli, Bessem Samet. A new detailed explanation of the Tacoma collapse and some optimization problems to improve the stability of suspension bridges[J]. Mathematics in Engineering, 2023, 5(2): 1-35. doi: 10.3934/mine.2023045
Related Papers:
[1]
Kawkab Al Amri, Qamar J. A Khan, David Greenhalgh .
Combined impact of fear and Allee effect in predator-prey interaction models on their growth. Mathematical Biosciences and Engineering, 2024, 21(10): 7211-7252.
doi: 10.3934/mbe.2024319
[2]
Saheb Pal, Nikhil Pal, Sudip Samanta, Joydev Chattopadhyay .
Fear effect in prey and hunting cooperation among predators in a Leslie-Gower model. Mathematical Biosciences and Engineering, 2019, 16(5): 5146-5179.
doi: 10.3934/mbe.2019258
[3]
Dirk Stiefs, Ezio Venturino, Ulrike Feudel .
Evidence of chaos in eco-epidemic models. Mathematical Biosciences and Engineering, 2009, 6(4): 855-871.
doi: 10.3934/mbe.2009.6.855
[4]
Yuhong Huo, Gourav Mandal, Lakshmi Narayan Guin, Santabrata Chakravarty, Renji Han .
Allee effect-driven complexity in a spatiotemporal predator-prey system with fear factor. Mathematical Biosciences and Engineering, 2023, 20(10): 18820-18860.
doi: 10.3934/mbe.2023834
[5]
Yuanfu Shao .
Bifurcations of a delayed predator-prey system with fear, refuge for prey and additional food for predator. Mathematical Biosciences and Engineering, 2023, 20(4): 7429-7452.
doi: 10.3934/mbe.2023322
[6]
Hongqiuxue Wu, Zhong Li, Mengxin He .
Dynamic analysis of a Leslie-Gower predator-prey model with the fear effect and nonlinear harvesting. Mathematical Biosciences and Engineering, 2023, 20(10): 18592-18629.
doi: 10.3934/mbe.2023825
[7]
Ranjit Kumar Upadhyay, Swati Mishra .
Population dynamic consequences of fearful prey in a spatiotemporal predator-prey system. Mathematical Biosciences and Engineering, 2019, 16(1): 338-372.
doi: 10.3934/mbe.2019017
[8]
Shunyi Li .
Hopf bifurcation, stability switches and chaos in a prey-predator system with three stage structure and two time delays. Mathematical Biosciences and Engineering, 2019, 16(6): 6934-6961.
doi: 10.3934/mbe.2019348
[9]
Rongjie Yu, Hengguo Yu, Chuanjun Dai, Zengling Ma, Qi Wang, Min Zhao .
Bifurcation analysis of Leslie-Gower predator-prey system with harvesting and fear effect. Mathematical Biosciences and Engineering, 2023, 20(10): 18267-18300.
doi: 10.3934/mbe.2023812
[10]
Wanxiao Xu, Ping Jiang, Hongying Shu, Shanshan Tong .
Modeling the fear effect in the predator-prey dynamics with an age structure in the predators. Mathematical Biosciences and Engineering, 2023, 20(7): 12625-12648.
doi: 10.3934/mbe.2023562
Abstract
We give a new full explanation of the Tacoma Narrows Bridge collapse, occurred on November 7, 1940. Our explanation involves both structural phenomena, such as parametric resonances, and sophisticated mathematical tools, such as the Floquet theory. Contrary to all previous attempts, our explanation perfectly fits, both qualitatively and quantitatively, with what was observed that day. With this explanation at hand, we set up and partially solve some optimal control and shape optimization problems (both analytically and numerically) aiming to improve the stability of bridges. The control parameter to be optimized is the strength of a partial damping term whose role is to decrease the energy within the deck. Shape optimization intends to give suggestions for the design of future bridges.
1.
Introduction
The generation of municipal/urban solid waste (MSW) is an inalienable consequence of the development of modern cities. Likewise, its correct management is one of the key elements for the sustainable development of a city [1]. The stages in the reverse logistics chain of MSW are diverse. According to Tchobanoglous et al. [2], they can be classified into waste generation; handling, separation, accumulation and processing of waste at source; collection, transfer and transportation; separation, processing and transformation of solid waste; and finally, disposition. In these stages, there are many decisions to be made. For this reason, proposing computer-aided tools that allow assisting decision-making agents can contribute to a more efficient use of resources.
This work focuses on the collection, transfer and transportation stage of waste, which is known to be among the most expensive activities of MSW systems [3]. This activity comprises the design of the waste collection routes for the vehicles that collect the waste produced by households and other commercial and institutional urban activities. The correct performance of this task is critical for due quality of service provided to the citizens since when it is mishandled it can lead to waste bins overflow which is associated with environmental and social issues. In particular, a simulated annealing (SA) metaheuristic algorithm is proposed to solve this problem. The proposed algorithm is compared against other metaheuristic algorithms and CPLEX in order to study its performance. The experimentation is carried out on both a well-known benchmark of the literature and real instances of the city of Bahía Blanca, Argentina. This paper is a revised and expanded version of our conference work presented at The Xth international conference of production research-Americas 2020 [4].
This article is structured as follows. Section 2 presents the proposed model and resolution algorithms for the addressed problem and a literature review of the main related works. Section 3 describes the results of the computational experimentation performed on a well-known benchmark set of instances from the literature and a real-world case of study. Section 4 analyses and discusses the obtained results. Finally, Section 5 presents the main conclusion and future research work lines.
2.
Materials and methods
The waste collection problem can be addressed considering multiple features depending on the collection system and the real-world restrictions that are taken into account. The waste collection problem that is addressed in this work is based on a community bin system in which waste is carried by generators from their households to the collection points that are distributed throughout the city. A collection point is a place in the city specially conditioned for installing a (waste) bin or set of bins.
2.1. Mathematical formulation
This problem can be modelled either as a Capacitated Vehicle Routing Problem (CVRP) or a soft clustered-CVRP, in which the collection points are split into regions (clusters) and within a route a vehicle visiting a collection point in a cluster must visit all the remaining collection points therein before leaving it or to respect the soft-cluster constraint, i.e., all collection points of the same cluster must be served by the same vehicle [5]. In this work, the waste collection problem is modelled as a CVRP in which a fleet of homogeneous vehicles has to visit all the collection points considering capacity constraints. Given a set of collection points C and a superset C_=C∪c0, where c0 is the depot where the vehicles start and end their trips, the following variables and parameters are defined: binary variable xij that takes value 1 if a vehicle uses the path from collection point i∈C to collection point j∈C and 0 otherwise; the continuous non-negative auxiliary variable ui for sub-tour elimination indexed over collection points (i∈C); parameter Q is defined as the capacity of the vehicle; parameter dij as the distance between collection points i∈C and j∈C; and parameter qi as the amount of waste to be collected at collection point i∈C. In this way, the following model is proposed, using the two-index formulation developed by Miller et al. [6] in Eqs (1)–(6).
minD=∑i,j∈C_xijdij
(1)
Subject to:
∑j∈C_j≠ixij=1,∀i∈C
(2)
∑j∈C_j≠ixji=1,∀i∈C
(3)
ui−uj≤Q(1−xij)−qj,∀i,j∈C,i≠j
(4)
qi≤ui≤Q,∀i∈C
(5)
x∈{0,1}
(6)
The proposed objective is to minimize the total distance travelled expressed in Eq (1). Equations (2) and (3) guarantee that each collection point is visited only once, having a single successor collection point and a single predecessor collection point on the route. Equation (4) prevents the formation of subtours. Equation (5) ensures that the vehicle's capacity is not exceeded. Equation (6) establishes the binary nature of the corresponding variable.
2.2. Proposed resolution method: a simulated annealing algorithm
As it was previously said, the collection of MSW in bins constitutes an application case of the VRP (Vehicle Routing Problem) problem. In computational complexity theory, this type of problem is classified as NP-hard [7], that is, it is at most as difficult as problems for which efficient solving algorithms that run in polynomial time have not yet been developed, regarding the size of the problem [8]. In this type of problems, metaheuristic tools allow obtaining good solutions in reasonable computational times [9]. The proposed resolution algorithm is based on a simulated annealing (SA) method and was adapted from the previous algorithm developed in Toncovich et al. [10,11]. SA is a local search-based method that was developed from an analogy with the physical phenomenon of annealing [12] to solve complex optimization problems. Local search methods search for the solution with the best value of the chosen criteria in the current solution neighborhood, accept it as the current solution, and repeat this procedure until it is not possible to improve the solution in the explored neighborhood. By systematically applying this procedure, a local optimum for the problem is generally obtained. To avoid being trapped in a local optimum, a diversification mechanism must be incorporated in order to adequately explore the solutions space. In simulated annealing metaheuristics, the diversification strategy allows moves, with some probability, toward solutions that worsen the current value of the objective function.
To get a good approximation to the optimal solution of the problem during the search process, it is necessary to restart the search regularly from one of the solutions accepted during the search process selected at random. The SA algorithm incorporates the classic parameters of simulated annealing. The parameters and variables corresponding to the implemented SA algorithm are indicated below.
● t: current iteration.
● n: current step.
● S0: initial solution.
● SA: current solution.
● Sc: candidate solution.
● S∗: best solution found.
● V(S): neighborhood for solution S, given by the set of solutions that can be obtained from solution S through a basic perturbation. In our implementation the perturbation is generated by swapping two randomly selected elements (collection points) in S.
● T: control parameter. This variable simulates the temperature in the real annealing process. It is a positive real number that varies in the interval T∈ [Tf, T0] during the execution of the algorithm, where T0 is the initial temperature and T0 > Tf.
● NT: maximum number of iterations performed by the algorithm for a certain temperature value Tn, at step n.
● α(T): function that determines the cooling mechanism, i.e., how T varies during the search process. In this case, it is a geometric progression of the form Tn=α×Tn−1, with α∈[0,8;0,999].
● Ncnt: number of consecutive iterations without improvement in the objective function value at the iteration t.
● Nstop: maximum allowable number of iterations without improvement.
● time_elapsed: time that has passed since the algorithm started.
● time_limit: amount of time available for executing the algorithm on a given instance.
● pA: probability of accepting a solution that is worse than the current solution.
● ϵ: a uniformly distributed random number in the interval (0, 1).
The pseudo-code of the SA algorithm is presented in Algorithm 1.
Algorithm 1: Simulated annealing algorithm.
Inputs: data of the instance (dij, qi, Q) and parameters T0, Tf, α, NT, Nstop, time_limit Initialization time_elapsed←0; time←now() create S0 using a randomized greedy procedure evaluateS0, D(S0), using Equation (1) SA←S0; S∗←S0; t←1; n←1; Ncnt←0; T1←T0 repeat counter←0 repeat create a new solution Sc, Sc∈V(SA) evaluate Sc, D(Sc) Cost←D(Sc)−D(SA) if Cost≤0 then SA←Sc; ; Ncont←0 ifD(S∗)<D(SA)then S∗←SA endif else pA←e−CostTn; ϵ←rand(0,1) ifϵ≤pAthen SA←Sc; Ncnt←0 else Ncnt←Ncnt+1 endif endif t←t+1; time_elapsed←now()−time; counter←counter+1 untilcounter≥NT n←n+1; Tn←α×Tn−1 untilNcnt>Nstop OR Tn>Tf OR timeelapsed>time_limit return S∗
The proposed metaheuristic is compared with a commercial solver and other two metaheuristics, i.e., large neighborhood search (LNS) algorithm developed by Erdoğan [13] and a standard genetic algorithm.
2.3.1. Commercial solver based on MIP formulation
The solver that is used to solve the proposed mathematical formulation presented in Section 2.1 is CPLEX. In order to speed up the resolution process, the Eq (7) is added that sets the minimum number of trips required considering the overall waste to collect.
∑j∈Cxc0j≥∑j∈CqiQ
(7)
This Equation is a well-known valid inequality or cut in routing problems [14]. In preliminary tests, this cut was found to be competitive for reducing the computing times. This is generally associated to a better estimation of the lower bound due to a tighter approximation of the feasible region of the linear relaxation to the feasible region of the actual MIP model in resolution algorithms based on branch-and-cut [15] as CPLEX.
2.3.2. Large neighbourhood search
Erdoğan's metaheuristic was adapted from the adaptive LNS heuristic developed by Pisinger and Ropke [16], which extends Shaw's original heuristic [17]. A simplified explanation of its operation and pseudo-code is presented in Algorithm 2.
Algorithm 2: Pseudo-code of large neighborhood search [13].
Input: data of the instance (dij, qi, Q) and parameter Timelimit Initialization S0←InitialSol() S'←LocalSearch() BestSol←S' Timeelapsed←0 repeat time←now() S'←DestryAndRebuild(S') S'←LocalSearch(S') ifD(S')≤D(BestSol) BestSol←S' else ϵ←rand(0,1) If ϵ≤pvalue BestSol←S' end if end if Timeelapsed←now()−time untilTimeelapsed>Timelimit returnBestSol
The operation of the heuristic consists of two main stages. The first is the construction of an initial solution that is obtained by inserting clients into the available routes in accordance with the objective to be minimized (operator InitialSol()). Then, an enhancement is made using the LocalSearch() operator that applies four local search techniques. The first three are known as Exchange (two clients are exchanged), 1-OPT (a client is extracted from one route and reinserted into another) and 2-OPT (two route segments are exchanged). These operators are detailed in Groër et al. [18]. The fourth local search operator is Vehicle-Exchange. This operator tries to exchange the vehicles assigned to two routes, which is why it is useful when working with a heterogeneous fleet.
The second stage is where you try to get an improvement on the solution from the previous stage. The DestroyAndRebuild() operator is applied, which considerably alters the current solution to explore another region of the search space and thus be able to escape from local optimum. In particular, long sections of routes are extracted from the current solution and the extracted clients are reinserted in those positions that minimize the objective function (function D() defined in Eq (1)). A solution is accepted if it has a better cost than the best solution found so far or, if a solution does not have a better cost than the previous solution, it can even be accepted with a probability p-value. This process is repeated cyclically up to the time limit imposed by the user.
2.3.3. Genetic algorithm
The schema of the implemented genetic algorithm (GA) is presented in in Algorithm 3.
Algorithm 3: Pseudo-code of genetic algorithm [19].
Input: data of the instance (dij, qi, Q) and parameters pc, pm, #P, and Timelimit Initialization P←InitialPopulation() Timeelapsed←0 repeat time←now() evaluate(P) parents←selection(Pt) offspring←crossover(parents) offspring←mutation(offspring) P←variationoperations(parents) untilTimeelapsed>Timelimit returnbestindividualfound
The GA was developed using the Distributed Evolutionary Algorithms in Python (DEAP) framework [20] and has the following characteristics:
● Representation of solutions. Solutions are encoded as a permutation of integers of length equal to the number of containers n. Each index in the vector represents the visit order in the tour and the corresponding integer value represents one of the containers.
● Initialization. The population of size |P| is initialized by applying a random procedure to generate the permutations with a uniform distribution.
● Genetic operators. The recombination operator is the Partially Mapped Crossover (PMX) applied on two selected individuals with pc probability. The mutation operator is based on Swap Mutation and swaps two elements of the permutation. Both selected operators have been usually applied in CVRP problems [21]. The mutation applies to an individual with probability pm. The proposed operators guarantee the feasibility of the solution.
● Selection. The selection is made through a binary tournament, from which the one with the best fitness is selected.
● Replacement. In each iteration, the new population is made up of the best 10% (with better fitness) of the previous population and the rest of new individuals generated through genetic operators.
● Fitness assessment. The fitness function is decoded by reading alleles in the gen from left to right and inserting a depot visit when necessary due to the capacity constraint of the vehicle. An example of the decoding process is presented in Figure 1 for a representative gen considering a vehicle with a capacity of 7m3. The collection vehicle starts its route from the depot and collects the waste of GAPs 2, 1 and 5. However, collecting the waste of GAP 6 is not feasible since the amount of waste (1.5m3) exceeds the available remaining capacity of the vehicle, i.e., 7m3–2.3m3−2.3m3−2.1m3=0,3m3. Thus, a visit to the depot to unload the vehicle is inserted before visiting GAP 6, adding the distances d50 and d06 to the fitness. Then, the vehicle visits GAPs 4, 7 and 3 and, finally, it returns to the depot.
● Cut due to stagnation. A deadlock cut-off mechanism was incorporated. The algorithm stops when no improvement in the fitness of the best individual is obtained during a time interval equal to 50% of the maximum execution time of the instance. Otherwise, it continues until the generation—evaluation, selection, crossing, mutation and replacement cycle—which has exceeded the maximum execution time at the end.
2.4. Related works
The problem of collection of containerized waste in a city has been frequently addressed in the literature. In Beliën et al. [22] and Han and Ponce Cueto [23], extensive reviews of these works are developed.
Among the main works that applied heuristics in waste collection, it is the work of Kim et al. [24] who applied a clustering-based heuristic and an insertion heuristic on a set of real-world instances of the United States of America. Over the same dataset, Benjamin and Beasley [25] applied two advanced metaheuristics, i.e., a variable neighborhood search and a tabu search, improving the previous results of Kim et al. [24]. Nesmachnow et al. [9] proposed an evolutionary algorithm to optimized collection routes in Montevideo, Uruguay while considering priorities in collection points that are located near public institutions or busy places in which overflowing may have a large social impact.
Regarding SA algorithms in waste management, there is the work of Tirkolaee et al. [26]. The authors applied a metaheuristic based on SA improved with an efficient cooling equation to address the problem of waste collection considering uncertainty in waste generation that aims at minimizing the total distance and the usage cost of vehicles. The proposed algorithm obtained similar results than the exact solution for small instances. A comprehensive work was performed by Nowakowski et al. [27] who compared four different heuristics, i.e., simulated annealing, tabu search, greedy, and bee colony optimization, to solve case studies of three different cities in the context of electronic waste collection. The results showed that SA outperforms the rest of the proposed heuristics. A similar problem is addressed in Tirkolaee et al. [3] in which more priority is assigned to collect waste bins that are located near some special places, such as health centers that produce hazardous waste, than to household waste for addressing a case study in Sanandaj, Iran. The proposed SA-based algorithm was able to obtain near-optimal solutions in comparison with the CPLEX solver. Mekamcha et al. [28] proposed a SA to deal with a waste collection case study in the Algerian city of Tlemcen in which the collection is modelled as a Travelling Salesman Problem. The SA algorithm is compared with a Tabu Search obtaining better results regarding total distance minimization.
In the case of Argentina, some studies can be found on applications of VRP models to solve the problem of design of collection routes. For example, Bonomo et al. [29] implemented a solution strategy based on integer programming to schedule the collection routes for waste containers in the Southern area of the City of Buenos Aires. On the other hand, in Bonomo et al. [30] a different model is presented for this city, which aims at minimizing the travel distances simultaneously with minimizing wear and tear on vehicles. In the city of Concordia, Bertero [31] presents an application to design the city's collection routes, making an effort to minimize the number of turns to facilitate the implementation of the routes by the authorities. On the other hand, Bianchetti et al. [32] exhibits an algorithm to solve the zoning of the city of San Miguel de Tucumán in order to optimize the use of resources, reassigning trucks to the downtown area of the city. In Braier et al. [33], through mathematical programming models, the collection of recyclable waste is planned for the city of Morón. Delle Donne et al. [34] presented a solution strategy based on integer programming to scheduling of routes to collect waste produced by leaf sweeping of streets in the city of Trenque Lauquen.
From the analysis of the related literature, we consider that there is still room to propose efficient algorithms based on simulated annealing to design waste collection routes. Moreover, this work compares SA with other metaheuristic approaches and a commercial solver in order to assess the competitiveness of the simulated annealing procedure and addresses a real case study of the city of Bahía Blanca.
3.
Results of computational experimentation
This Section presents the set of benchmark instances from the literature, the real-world case from the city of Bahía Blanca, the implementation details for the solution algorithms, the obtained results and an analysis of these results.
3.1. Case study: Argentinean city of Bahía Blanca
Bahía Blanca is a medium-size city located in the South of Argentina: It is considered as a major industrial, logistic and university center from the southern part of the country. The management of urban solid waste in the city of Bahía Blanca is a crucial activity for local authorities, not only because of the broad environmental and social impact associated with its operation but also because it consumes a large part of the municipality's budgetary resources [35]. Therefore, approaches that allow the optimization of collection logistics may be relevant to achieve a more efficient service provision [8,36]. Nowadays, waste collection is performed in a door-to-door basis. However, there are initiatives and studies that aim at migrating to a community bins system [8,35–38]. This work uses a real dataset that was obtained in one of these projects carried out by the academic, municipality and private stakeholders of the city [35]. This dataset was built with the aim of migrating from the current door-to-door waste collection system to the community waste bins system and it corresponds to two neighborhoods of the downtown of Bahía Blanca. These neighborhoods can be depicted in Figure 2: The University neighborhood as sector A and the downtown as sector B.
One of the goals of the aforementioned project [35] was also to implement source classification of waste to increase the amount of waste that is recycled in the city and assess the impact of different collection frequencies in the number of collection points. Following these guidelines for this work, the real instances are defined as follows. Firstly, three different geographic areas are considered: Sector A, Sector B, and the overall Sector A + B. From each area, four different instances are constructed, which differ in the type of waste -humid or dry waste- and the collection frequency considered. The instances of humid waste are always collected six times per week since they cannot remain uncollected due to environmental reasons. However, dry waste can be collected either four times per week or three times per week. Thus, Cavallin et al. [35] proposed two systems based on collection frequency for the city: The F2 system in which humid waste is collected six times per week and dry waste is collected four times per week, and F3 system in which dry waste is collected six times per week and dry waste is collected three times per week. Considering the three factors, i.e., geographic sector, type of waste and collection frequency in the system, the twelve instances of Table 1 are defined11. Further details of the instances can be consulted in Cavallin et al. [35]. In regard to the present work, the collection frequency of the dry waste will affect the stored quantity of dry waste to be collected, and due to its influence on the required storage space in the collection point, it will also affect the quantity of humid waste to be collected.
The capacity of the truck was set in 21 m3 which is the common capacity in the trucks of the fleet of the collection company. The distances between collection points were estimated with Open Source Routing Machine22 using the approach proposed by Vázquez [39].
3.2. Benchmark instances
In regard to the CVRP benchmark instances, the well-known set E of 13 instances proposed in Christofides and Eilon [40] was used. Both the instances and the optimal solutions were retrieved from the VRP-REP digital repository [41].
3.3. Implementation details
For solving the MIP formulation of Eqs (1)–(7), the commercial solver IBM ILOG CPLEX 20.1 was used [42]. It was implemented using GAMS 35.1 [43] as a modelling language. The majority of the parameters were kept in their default values [42,43] except for the enlargement of the working memory from the default 2048 MB to 5000 MB. This parameter was changed since on preliminary experimentation the solver ran out of memory space using the default configuration. The model that was solved with CPLEX is the MIP model composed by Eqs (1)–(7), which includes the valid inequality of the minimum number of trips (Eq (7)) to accelerate convergence. A time limit of 15,000 seconds was set to CPLEX for each run. The exact resolution was only applied to the real-world scenarios since the optimal solution of the benchmark instances is already available.
The SA was programmed in Visual Basic for Applications (VBA), the same programming language used in the LNS implementation taken from the repository of the author33. The GA algorithm was implemented using the DEAP library as the programming language.
Regarding the calibration of the metaheuristics the LNS does not need calibration [13]. The SA algorithm was fine-tuned using a small number of test runs in order to establish the values for the parameters specified in Section 2.2.
The GA algorithm was calibrated with a parametric analysis. The parameters that were analyzed through a statistical analysis were the size of the population |P|—the values 100; 150; and 200 were considered, the probability of mutation pm—the values 0.05; 0.1; 0.15; 0.20; and 0.25 were considered and crossover pc—the values 0.5; 0.6; 0.7; 0.8; 0.9; and 1 were tested. For carrying out the parametric analysis the instances P-n16-k8, P-n19-k2 and P-n20-k2 proposed in [44] were used. For each instance and for each parametric configuration, 50 independent executions were carried out. The Shapiro-Wilk test was applied to study whether the fitness distribution had a normal distribution. Since many executions did not fit a normal distribution, the medians were evaluated with the Friedman test [45], selecting the configuration: |P| = 200, pc = 0.9 and pm = 0.25 as the most promising parametric configuration.
In order to provide a fair comparison between different metaheuristics the same computing time limits and implementation computer should be used [46]. In this case, the three metaheuristic were run in a personal computer with an Intel Core i5-3570k@3.40 GHz processor and 12 GB of RAM memory on a Windows 10 environment. For solving the instances, 30 runs were performed with each metaheuristic to obtain a more representative sample of the performance of the algorithms. Regarding execution times, Equation (8) was used to set the maximum execution time of each run in seconds (M) for the metaheuristics which is proportional to the number of collection points in the instance -excluding the depot-(N)
M=(N×10×60)50
(8)
It should be taken into account that both the SA and the GA described here have cut-off mechanisms due to stagnation that can lead to a real execution time that is less than the maximum. This is not the case for the LNS whose execution time will be equal to the maximum. In the case of CPLEX, a time limit of 15,000 seconds was given to the solver.
3.4. Computational experimentation
In this Section, we present the results of the computational experimentation. The experimentation was performed over two different datasets: the real world MSW instances of Bahía Blanca described in Section 3.1 and the benchmark instances described in Section 3.2, respectively.
Since the three metaheuristics involve probabilistic parameters, the results were statistically analyzed according to the following procedure. Each metaheuristic was run 30 times on each instance. Then, a two-stage statistical methodology is applied. First, the Shapiro-Wilk normality test [47] is used to determine whether the results follow a normal distribution. The null hypothesis of this test is that the data has a normal distribution and the alternative hypothesis is that the data cannot be assured to have a normal distribution. The test was applied with a statistical confidence level of 0.95.
After that, in case the results of the three metaheuristics for a specific instance follow a normal distribution, the mean value is used as estimator for the studied metric and the standard deviation (std) is used as a measure of statistical dispersion, and the parametric ANOVA statistical test is applied to analyze if there are significant differences on the mean values of the metaheuristics. Conversely, in case the results of any of the metaheuristics does not follow a normal distribution, the median value is used as estimator for the studied metric and the interquartile range (IQR) as a measure of statistical dispersion, and the non-parametric Kruskal-Wallis statistical test [48] is applied to analyze if there are significant differences on the median values of the metaheuristics. The null hypothesis of this test is that the medians are equal and the alternative hypothesis is that the medians are not equal. It was applied with a statistical confidence level of 0.95.
In both set of instances, at least the results of one of the metaheuristics rejected the hypothesis of normal distribution according to Shapiro Wilk test. Thus, medians and interquartile ranges are used to report the results and the Kruskal-Wallis test is used to analyze the differences among medians. The detailed results of the Shapiro Wilk and Kruskal-Wallis tests can be consulted in Appendix.
For the real instances Table 2 reports for each metaheuristic: the minimal value, the median value, the maximal value, and the interquartile range/standard deviation of the D values achieved by each metaheuristic. In the pairwise comparisons performed by Kruskal-Wallis statistical test all the medians where found to be statistically different except for those that have an asterisk*, which rejected this hypothesis.
Table 2.
Results of the real instances of the three metaheuristics.
In Table 3, the best distance—D according to Eq (1)—obtained for each real instance with CPLEX and each metaheuristic is reported. Besides, it is reported the gap estimated by CPLEX to the ideal solution calculated by the software and the percentage difference between the best solution obtained by each metaheuristic and the solution obtained by CPLEX according to Eq (9).
ΔMH=DMH−DCPLEXDCPLEX%
(9)
where DMH is the distance obtained by each metaheuristic and DCPLEX is the distance obtained with CPLEX. Thus, in Table 3 when ΔMH has a negative value it means that the metaheuristic obtained a better result than CPLEX. We compare the CPLEX solution with two distances of the metaheuristic: the best or minimal distance and the median distance.
Table 3.
Percentage difference of the solutions of each metaheuristic to the exact solution.
Instance
CPLEX
Comparison with minimal D
Comparison with median D
D
CPLEX gap %
ΔSA
ΔLNS
ΔGA
ΔSA
ΔLNS
ΔGA
A-F2HUM
25.49
*0.00%
1.96%
1.53%
28.63%
5.18%
5.41%
43.55%
A-F2DRY
47.18
10.73%
–2.23%
–1.63%
10.49%
–0.61%
–0.61%
17.99%
A-F3HUM
27.21
*0.00%
0.37%
1.91%
36.49%
2.72%
5.88%
49.73%
A-F3 DRY
67.42
13.76%
–1.77%
–2.18%
7.58%
–1.01%
–1.28%
11.77%
B-F2HUM
24.53
0.43%
0.12%
0.77%
27.49%
1.75%
3.14%
39.59%
B-F2 DRY
40.66
10.65%
–2.12%
–2.48%
12.37%
–0.61%
–0.74%
18.37%
B-F3HUM
28.54
0.10%
1.75%
2.66%
57.64%
3.50%
5.68%
66.74%
B-F3 DRY
63.46
26.30%
–9.63%
–9.61%
7.73%
–8.08%
–8.10%
14.50%
A + B-F2HUM
49.12
10.13%
–1.40%
2.08%
57.64%
0.37%
3.58%
68.80%
A + B-F2 DRY
96.09
31.47%
–7.39%
–7.86%
15.61%
–5.81%
–4.68%
20.03%
A + B-F3HUM
57.62
16.54%
–4.84%
–4.37%
98.53%
1.87%
–2.38%
120.59%
A + B-F3DRY
141.18
39.09%
–14.12%
–10.84%
23.84%
–13.08%
–8.84%
28.94%
Average
–3.27%
–2.50%
32.00%
–1.46%
–0.24%
41.72%
Note: *These solutions are proven optimal by CPLEX.
As aforementioned, to extend the metaheuristic comparison, the instances of the benchmark Set E [40] were solved. Table 5 shows the best results found in each instance by the algorithms under study, while Table 6 shows the performance of the metaheuristics in comparison to the BKS (Best Known Solution) of the instance using the percentage difference estimated with Eq (10).
Δ′MH=DMH−DBKSDBKS%
(10)
where DMH is the distance obtained by each metaheuristic and DBKS is the distance of the BKS of the instance. Again, we compare the BKS with two distances: the best (minimal) value and the median value achieved by each metaheuristic.
Table 5.
Results of the benchmark instances of the three metaheuristics.
Similarly, to the results of real-world instances, in Figure 4 we present a chart with the results of the best distance achieved by each metaheuristic and the BKS of each instance of the benchmark.
4.
Discussion
In this Section, we discuss the main results from the computational experimentation performed on real waste collection instances and on the benchmark set E. As a summary of the metaheuristics we present Table 7 in which we outlined the main features of the three metaheuristic.
Table 7.
Main features of each metaheuristic.
Feature
SA
LNS
GA
Type of algorithm
Local search
Neighborhood search
Evolutionary algorithm
Stopping criterion
Time limit/maximum allowable number of iterations without improvement
Time limit
Time limit/maximum time without improvement
Programming language
VBA
VBA
Python
Main parameters
Initial temperature/ function that determines the cooling mechanism
Auto-tuning by the author
Population size, crossover and mutation probability,
Concerning the real instances of the MSW system of Bahía Blanca, the results are presented in Tables 2–4. Table 2 shows that SA obtained the smallest minimal distance in nine out of 12 instances while LNS provided the smallest distance in the three remaining instances. Regarding the median distances, SA produced the smallest median in eight out of 12 instances (however, in two instances the medians are not found to be statistically different from the ones obtained by LNS). LNS obtained the best median distance in five instances (however, in four instances these medians were not statistically different from those of SA). In instance A-F2DRY both algorithms obtained the same median. Both the SA and the LNS procedures always outperform the GA in terms of minimal values and median values. Neither the GA nor the SA cut were stopped before the maximum allowable computing time due to stagnation.
The results of Table 3 show that CPLEX was able to obtain optimal solutions (with 0.00% CPLEX gap) in only two out of 12 instances, i.e., A-F2HUM and A-F3HUM. In the rest of the instances, the optimality CPLEX gap is larger than zero with the maximum gap in instance A + B-F3DRY (39.09%). Regarding the comparison between the metaheuristics and CPLEX, SA minimal distances are on average 3.27% better than CPLEX solutions, having the largest improvement in instance A + B-F3DRY (–14.12%). Regarding LNS, minimal solutions are on average 2.50% better than CPLEX, having the largest improvement also in instance A+B-F3DRY (–10.84%). The minimal solutions of the GA are on average 32.00% worse than the CPLEX solutions, having the smallest difference on instance A-F3 DRY (7.58%). When comparing the median distances of the metaheuristics with CPLEX solutions, the relationship is maintained, being SA the metaheuristic that obtains the best average difference (–1.46%) followed by the LNS (–0.24%). Results of Table 4 showed that in relation to the average number of iterations carried out, SA and GA reach a greater number of iterations as the number of nodes grows. Conversely, in the case of LNS the number of iterations decreases as number of nodes increases.
Another important feature to analyze is the variation of the results of the algorithms. Since instances were non-parametric, the interquartile range better represents these values. In order to better depict the differences between the algorithms, in Figure 3 we present the box plots of the four real-world representative instances. A box plot is a simple way of visualizing statistical data on a plot in which a rectangle is drawn to represent the second and third quartiles with a vertical line inside to indicate the median value. The lower and upper quartiles are shown as horizontal lines either side of the rectangle. If there are outliers (values that surpass the lower and upper quartiles) these are plotted as extra scatter dots outside of the main box. For the sake of comparison, we also present the unique value of CPLEX. From Figure 3 it can be depicted that the GA always obtains worse results than the other two metaheuristics and CPLEX. Moreover, the variability of the results also seems to be larger, especially in instance A + B-F2HUM (Figure 3(a)). LNS and SA are very competitive against CPLEX. Besides, the variability of these algorithms seems to be relatively small especially in instance A + B-F3DRY (Figure 3(c)).
Figure 3.
(a). Boxplot of instance A + B-F2HUM. (b). Boxplot of instance A + B-F2DRY. (c). Boxplot of instance A + B-F3HUM. (d). Boxplot of instance A + B-F3DRY. Distance of the best distances in kilometers obtained by each metaheuristic and of CPLEX solution for each real-world instance.
Another aspect that is relevant toanalyze in connection with the efficiency of the solution algorithms used to solve the real scenarios, is the impact of the partition of the overall area into two sectors. Partitioning complex problems into smaller (more tractable) parts is a normal procedure employed to address the complexity of NP-hard problems [49], as it is the case of the CVRP that is addressed in this work. In this case, the partition is performed at the level of the input instance dividing the overall area into two smaller Sectors (Sectors A and B). Although this allows the resolution algorithm to face a smaller problem, which might be easier to solve, it can also generate a certain loss of quality of the obtained solution since the algorithm do not take into account the overall scenario. The joint search space of the partitioned scenarios is smaller than the search space of the overall scenario since some possibilities are not feasible in the partitioned case (i.e., combining bins that belong to different sectors in the same route). For analyzing this behavior for the proposed algorithms, in Table 8 we report the percentage deviation between solving the two partitions separately and solving the global scenario computed according to Eq (11).
DA+B−(DA+DB)(DA+DB)
(11)
where DA, DB, DA+B are the best distance values for sectors A and B, and the overall area A + B, respectively. Thus, a negative difference determines that the resolution approach is able to improve the results when considering the overall instance in comparison to the partitions.
Table 8.
Analysis of performance partition of the real scenario.
From the results of Table 8, it can be seen that CPLEX is able to improve the solution only in instance of humid waste and collection frequency F2. SA is able to improve the solution when it considers the overall area in comparison to solving the partitions in three out of four cases, having the largest improvement in instances of dry waste and collection frequency F2 (4.19%). LNS improves the solution also in two out of four cases, having the largest improvement in humid waste and collection frequency F3 (3.38%). GA always provides a worse result when dealing with a larger scenario instead of the partitioned problem. Thus, the proposed SA was able to manage quite efficiently the increment in the collection area and take advantage of the enlargement of the search space, providing better solutions for the global scenario. On the other hand, GA could not take advantage of this possibility probably been more affected by the larger complexity of facing a larger scenario.
4.2. Benchmark set E
The results of the benchmark set E are reported in Tables 4 and 5. Results of Table 4 show that, regarding the minimal distances, the SA is able to obtain the best solution in 12 out of 13 instances while LNS in six instances out of 13. The relationship between both metaheuristics is reversed when comparing the median values that in this set of instances are all statistically different according to Kurskall-Wallis test. The medians of the results of LNS are better in 10 instances and those of SA are better in 7 instances. Although it is able to achieve the best minimal value in two instances, GA is usually outperformed by the other two metaheuristics in both minimal and median values.
Regarding Table 5, it is necessary to clarify that both SA and GA find a lower value than the optimal value reported in the literature for the E-n30-k3 instance given that, since they do not have a restriction indicating the number of routes, they report a solution with an additional route. Table 5 shows that the SA is able to obtain solutions that are on average (excluding instance E-n30-k3) only 0.16% worse in comparison to the value of 2.75% of LNS. The efficiency of SA is maintained when considering medians comparison, the solutions being around 0.86% distanced on average from the BKS while the LNS value is about 2.75%. As in the case of the real dataset, the GA provides worse results than those of the other two metaheuristics. Neither the GA nor the SA cut were stopped before the maximum allowable computing time due to stagnation.
Regarding benchmark instances, no boxplots are presented since the results of the metaheuristics have less variability in this set of instances and, thus, the box plots were less illustrative. From Table 6, it can be seen that the interquartile range for most of the results of the LNS and the SA is zero. Only the GA, keeps a certain variability in the results. Instead of box plots, in Figure 4 we present a chart with the results of the best distance achieved by each metaheuristic and the BKS of each instance of the benchmark. Once again, it is seen that the GA usually obtains worse solutions than the other two metaheuristics although there are two exceptions in instances E-n76-k7 and E-n23-k3 (in which GA obtain a better result than LNS). As aforementioned, in E-n30-k3 both SA and GA obtain a better solution but they use a larger number of routes.
Figure 4.
Distance of the best distance obtained by each metaheuristic and of CPLEX solution for each real-world instance.
Finding new tools to make municipal/urban solid waste (MSW) logistics more efficient is a pressing concern in today's societies. This work is focused on solving waste collection problems for the Bahía Blanca area. In particular, it addresses a problem found in previous works where the exact solution of waste collection problems was inefficient, because the partitioning of the scenarios into smaller portions was required to achieve convergence to an acceptable feasible solution using reasonable computational times.
Therefore, in this work a comparative study is presented between the exact resolution and three metaheuristic solution tools for the problem of MSW collection in Bahía Blanca. The exact solution is based on a linear programming formulation of the CVRP model using the CPLEX software. On the other hand, with respect to the metaheuristic resolution, a simulated annealing algorithm (SA) is proposed, which is compared with an algorithm taken from the literature based on large neighborhood search (LNS) and a standard genetic algorithm (GA). In addition, the comparison among of metaheuristics using some instances of a well-known benchmark from the literature is carried out. The proposed SA has a similar performance to the LNS algorithm of the literature -obtaining values close to the optimal solution on several occasions- and markedly exceeds the performance of the standard GA.
After analyzing the experimental work carried out, it can be affirmed that the application of these algorithms provides potentially acceptable and competent results, having the metaheuristics the advantage of the less computational effort required to reach the solution. The experience carried out on the benchmark problems and on the MSW instances of Bahía Blanca, marked a good performance of the proposed SA algorithm in comparison to other metaheuristics and CPLEX in both real MSW instances and benchmark instances. It showed to be particularly competitive when compared to a state-of-the-art LNS algorithm from the related literature. On the other hand, GA exhibited a poor performance compared to SA and LNS, possibly due to the use of a standard genetic algorithm with a simple decoding function taken from applications in unconstrained problems such as the Traveling Salesman Problem.
As research lines of work in the future, it is planned to experiment with larger scenarios of the city of Bahía Blanca, using the proposed metaheuristics, which were validated in the present work. It is also intended to incorporate other realistic features to the problem such as time limits for the routes or a finite size of the collection vehicles fleet. Furthermore, it is proposed to develop the coding function of the genetic algorithm with an approach that is better adapted to the type of CVRP problem addressed in this paper. Finally, it is expected to continue performing the comparison between the three metaheuristics with different set of instances and parametric configurations in order to expand the analysis.
Acknowledgments
This work was funded by the research projects PGI 24/J084 and PGI 24/ZJ35 of the Universidad Nacional del Sur. The authors of this work wish to thank V. Herrán Symonds for her assistance in gathering the real data of the MSW scenarios of the city of Bahía Blanca. The third author of this work was funded by the Consejo Interuniversitario Nacional of Argentina (CIN) under the grant Becas de Estímulo a las Vocaciones Científicas (Scholarship EVC-CIN Call 2018).
Conflict of interest
All authors declare no conflicts of interest in this paper.
References
[1]
B. Akesson, Understanding bridges collapses, London: CRC Press, Taylor & Francis Group, 2008.
[2]
O. H. Ammann, T. von Kármán, G. B. Woodruff, The failure of the Tacoma Narrows Bridge, Technical Report, Washington D.C.: Federal Works Agency, 1941.
[3]
Annales des ponts et chaussées: Rapport de la Commission d'enquête nommée par arrêté de M. le Préfet de Maine-et-Loire, en date du 20 avril 1850, pour rechercher les causes et les circonstances qui ont amené la chûte du pont suspendu de la Baisse-Chaîne, 1850.
[4]
Anonymous, Fall of the Broughton Suspension Bridge, near Manchester, The Manchester Guardian, Vol. 9, No. 53, 1831,384–389.
[5]
P. R. S. Antunes, F. Gazzola, Some solutions of minimaxmax problems for the torsional displacements of rectangular plates, ZAMM-Z. Angew. Math. Mech., 98 (2018), 1974–1991. http://doi.org/10.1002/zamm.201800065 doi: 10.1002/zamm.201800065
[6]
E. Arioglu, Importance of "heuristics" in suspension bridge engineering and 1915 Çanakkale bridge, In: Developments in international bridge engineering, Cham: Springer, 2021, 19–41. http://doi.org/10.1007/978-3-030-59169-4_2
[7]
G. Arioli, F. Gazzola, A new mathematical explanation of what triggered the catastrophic torsional mode of the Tacoma Narrows Bridge collapse, Appl. Math. Model., 39 (2015), 901–912. http://doi.org/10.1016/j.apm.2014.06.022 doi: 10.1016/j.apm.2014.06.022
[8]
G. Arioli, F. Gazzola, On a nonlinear nonlocal hyperbolic system modeling suspension bridges, Milan J. Math., 83 (2015), 211–236. http://doi.org/10.1007/s00032-015-0239-9 doi: 10.1007/s00032-015-0239-9
[9]
G. Arioli, F. Gazzola, Torsional instability in suspension bridges: the Tacoma Narrows Bridge case, Commun. Nonlinear Sci. Numer. Simulat., 42 (2017), 342–357. http://doi.org/10.1016/j.cnsns.2016.05.028 doi: 10.1016/j.cnsns.2016.05.028
[10]
A Great bridge falls, The New York Times, November 9, 1940.
[11]
J. R. Banerjee, A simplified method for the free vibration and flutter analysis of bridge decks, J. Sound Vib., 260 (2003), 829–845. http://doi.org/10.1016/S0022-460X(02)00929-X doi: 10.1016/S0022-460X(02)00929-X
[12]
U. Battisti, E. Berchio, A. Ferrero, F. Gazzola, Energy transfer between modes in a nonlinear beam equation, J. Math. Pure. Appl., 108 (2017), 885–917. http://doi.org/10.1016/j.matpur.2017.05.010 doi: 10.1016/j.matpur.2017.05.010
[13]
J. A. Bello, E. Fernández-Cara, J. Lemoine, J. Simon, The differentiability of the drag with respect to the variations of a Lipschitz domain in a Navier-Stokes flow, SIAM J. Control Optim., 35 (1997), 626–640. http://doi.org/10.1137/S0363012994278213 doi: 10.1137/S0363012994278213
[14]
V. Benci, D. Fortunato, F. Gazzola, Existence of torsional solitons in a beam model of suspension bridge, Arch. Rational Mech. Anal., 226 (2017), 559–585. http://doi.org/10.1007/s00205-017-1138-8 doi: 10.1007/s00205-017-1138-8
[15]
E. Berchio, D. Buoso, F. Gazzola, A measure of the torsional performances of partially hinged rectangular plates, In: Integral methods in science and engineering, Cham: Birkäuser, 2017, 35–46. http://doi.org/10.1007/978-3-319-59384-5_4
[16]
E. Berchio, D. Buoso, F. Gazzola, On the variation of longitudinal and torsional frequencies in a partially hinged rectangular plate, ESAIM: COCV, 24 (2018), 63–87. http://doi.org/10.1051/cocv/2016076 doi: 10.1051/cocv/2016076
[17]
E. Berchio, D. Buoso, F. Gazzola, D. Zucco, A minimaxmax problem for improving the torsional stability of rectangular plates, J. Optim. Theory Appl., 177 (2018), 64–92. http://doi.org/10.1007/s10957-018-1261-1 doi: 10.1007/s10957-018-1261-1
[18]
E. Berchio, A. Falocchi, About symmetry in partially hinged composite plates, Appl. Math. Optim., 84 (2021), 2645–2669. http://doi.org/10.1007/s00245-020-09722-y doi: 10.1007/s00245-020-09722-y
[19]
E. Berchio, A. Falocchi, Maximizing the ratio of eigenvalues of non-homogeneous partially hinged plates, J. Spectr. Theory, 11 (2021), 743–780. http://doi.org/10.4171/JST/355 doi: 10.4171/JST/355
[20]
E. Berchio, A. Falocchi, Some remarks about a worst-case problem for the torsional response of a plate, In: Interactions between elasticity and fluid dynamics, EMS Press, in press.
[21]
E. Berchio, A. Falocchi, A. Ferrero, D. Ganguly, On the first frequency of reinforced partially hinged plates, Commun. Contemp, Math., 23 (2021), 1950074. http://doi.org/10.1142/S0219199719500743 doi: 10.1142/S0219199719500743
[22]
E. Berchio, A. Falocchi, M. Garrione, On the stability of a nonlinear nonhomogeneous multiply hinged beam, SIAM J. Appl. Dyn. Syst., 20 (2021), 908–940. http://doi.org/10.1137/20M1374109 doi: 10.1137/20M1374109
[23]
E. Berchio, A. Ferrero, F. Gazzola, Structural instability of nonlinear plates modelling suspension bridges: mathematical answers to some long-standing questions, Nonlinear Anal. Real, 28 (2016), 91–125. http://doi.org/10.1016/j.nonrwa.2015.09.005 doi: 10.1016/j.nonrwa.2015.09.005
[24]
E. Berchio, F. Gazzola, A qualitative explanation of the origin of torsional instability in suspension bridges, Nonlinear Anal. Theor., 121 (2015), 54–72. http://doi.org/10.1016/j.na.2014.10.026 doi: 10.1016/j.na.2014.10.026
[25]
E. Berchio, F. Gazzola, The role of aerodynamic forces in a mathematical model for suspension bridges, Conference Publications, 2015 (2015), 112–121. http://doi.org/10.3934/proc.2015.0112 doi: 10.3934/proc.2015.0112
[26]
E. Berchio, F. Gazzola, C. Zanini, Which residual mode captures the energy of the dominating mode in second order Hamiltonian systems?, SIAM J. Appl. Dyn. Syst., 15 (2016), 338–355. http://doi.org/10.1137/140990577 doi: 10.1137/140990577
[27]
K. Y. Billah, R. H. Scanlan, Resonance, Tacoma Narrows Bridge failure, and undergraduate physics textbooks, Amer. J. Phys., 59 (1991), 118–124. http://doi.org/10.1119/1.16590 doi: 10.1119/1.16590
[28]
D. Bonheure, F. Gazzola, I. Lasiecka, J. Webster, Long-time dynamics of a hinged-free plate driven by a nonconservative force, Ann. Inst. H. Poincaré Anal. Non Linéaire, 39 (2022), 457–500. http://doi.org/10.4171/AIHPC/13 doi: 10.4171/AIHPC/13
[29]
D. Bonheure, F. Gazzola, E. M. dos Santos, Periodic solutions and torsional instability in a nonlinear nonlocal plate equation, SIAM J. Math. Anal., 51 (2019), 3052–3091. http://doi.org/10.1137/18M1221242 doi: 10.1137/18M1221242
[30]
D. Bonheure, F. Gazzola, G. Sperone, Eight(y) mathematical questions on fluids and structures, Atti Accad. Naz. Lincei Cl. Sci. Fis. Mat. Natur., 30 (2019), 759–815. http://doi.org/10.4171/RLM/870 doi: 10.4171/RLM/870
[31]
P. Cannarsa, F. Gazzola, Dynamic optimization for beginners – with prerequisites and applications, EMS, 2021.
[32]
H. Cao, X. Qian, Z. Chen, H. Zhu, Layout and size optimization of suspension bridges based on coupled modelling approach and enhanced particle swarm optimization, Eng. Struct., 146 (2017), 170–183. http://doi.org/10.1016/j.engstruct.2017.05.048 doi: 10.1016/j.engstruct.2017.05.048
[33]
A. Capsoni, R. Ardito, A. Guerrieri, Stability of dynamic response of suspension bridges, J. Sound Vib., 393 (2017), 285–307. http://doi.org/10.1016/j.jsv.2017.01.009 doi: 10.1016/j.jsv.2017.01.009
[34]
S. Chanillo, C. E. Kenig, T. To, Regularity of the minimizers in the composite membrane problem in R2, J. Funct. Anal., 255 (2008), 2299–2320. http://doi.org/10.1016/j.jfa.2008.04.015 doi: 10.1016/j.jfa.2008.04.015
[35]
S. Chanillo, C. E. Kenig, Weak uniqueness and partial regularity for the composite membrane problem, J. Eur. Math. Soc., 10 (2008), 705–737. http://doi.org/10.4171/JEMS/127 doi: 10.4171/JEMS/127
J. Chu, M. Garrione, F. Gazzola, Stability analysis in some strongly prestressed rectangular plates, Evol. Equ. Control Theory, 9 (2020), 275–299. http://doi.org/10.3934/eect.2020006 doi: 10.3934/eect.2020006
[38]
G. Crasta, A. Falocchi, F. Gazzola, A new model for suspension bridges involving the convexification of the cables, Z. Angew. Math. Phys., 71 (2020), 93. http://doi.org/10.1007/s00033-020-01316-6 doi: 10.1007/s00033-020-01316-6
[39]
Destruction of the Wheeling Suspension Bridge, The Intelligencer, Wheeling, Va., Vol. 2, no. 225, p. 3, Thursday, May 18, 1854.
A. Falocchi, Torsional instability in a nonlinear isolated model for suspension bridges with fixed cables and extensible hangers, IMA J. Appl. Math., 83 (2018), 1007–1036. http://doi.org/10.1093/imamat/hxy032 doi: 10.1093/imamat/hxy032
[42]
A. Falocchi, Torsional instability and sensitivity analysis in a suspension bridge model related to the Melan equation, Commun. Nonlinear Sci. Numer. Simul., 67 (2019), 60–75. http://doi.org/10.1016/j.cnsns.2018.07.005 doi: 10.1016/j.cnsns.2018.07.005
[43]
A. Falocchi, Optimization of the structural performance of non-homogeneous partially hinged rectangular plates, In: Geometric properties for parabolic and elliptic PDE's, Cham: Springer, 2021, 43–65. http://doi.org/10.1007/978-3-030-73363-6_3
[44]
S. Farhangdoust, P. Eghbali, D. Younesian, Bistable tuned mass damper for suppressing the vortex induced vibrations in suspension bridges, Earthq. Struct., 18 (2020), 313–320. http://doi.org/10.12989/eas.2020.18.3.313 doi: 10.12989/eas.2020.18.3.313
[45]
F. B. Farquharson, Letter to the Editor, ENR, July 3, 1941, 1–37.
[46]
V. Ferreira, F. Gazzola, E. M. dos Santos, Instability of modes in a partially hinged rectangular plate, J. Differ. Equations, 261 (2016), 6302–6340. http://doi.org/10.1016/j.jde.2016.08.037 doi: 10.1016/j.jde.2016.08.037
[47]
A. Ferrero, An orthotropic plate model for decks of suspension bridges, Nonlinear Anal. Real, 68 (2022), 103701. http://doi.org/10.1016/j.nonrwa.2022.103701 doi: 10.1016/j.nonrwa.2022.103701
[48]
A. Ferrero, A note on an orthotropic plate model describing the deck of a bridge, 2021, arXiv: 2110.00421.
[49]
A. Ferrero, F. Gazzola, A partially hinged rectangular plate as a model for suspension bridges, Discrete Cont. Dyn. Syst., 35 (2015), 5879–5908. http://doi.org/10.3934/dcds.2015.35.5879 doi: 10.3934/dcds.2015.35.5879
[50]
J. Finley, A description of the patent Chain Bridge, Philadelphia: Bradford & Inskeep, 1810.
[51]
I. Fragalà, F. Gazzola, G. Sperone, Solenoidal extensions in domains with obstacles: explicit bounds and applications to Navier-Stokes equations, Calc. Var., 59 (2020), 196. http://doi.org/10.1007/s00526-020-01844-z doi: 10.1007/s00526-020-01844-z
[52]
K. Friedrichs, Die randwert und eigenwertprobleme aus der theorie der elastischen platten. (Anwendung der direkten methoden der variationsrechnung), Math. Ann., 98 (1928), 205–247. http://doi.org/10.1007/BF01451590 doi: 10.1007/BF01451590
[53]
M. Garrione, Beams with an intermediate pier: spectral properties, asymmetry and stability, Mathematics in Engineering, 3 (2021), 1–21. http://doi.org/10.3934/mine.2021016 doi: 10.3934/mine.2021016
[54]
M. Garrione, F. Gazzola, Loss of energy concentration in nonlinear evolution beam equations, J. Nonlinear Sci., 27 (2017), 1789–1827. http://doi.org/10.1007/s00332-017-9386-1 doi: 10.1007/s00332-017-9386-1
[55]
M. Garrione, F. Gazzola, Nonlinear equations and stability for beams and degenerate plates with several intermediate piers, Cham: Springer, 2019. http://doi.org/10.1007/978-3-030-30218-4
[56]
M. Garrione, F. Gazzola, Linear theory for beams with intermediate piers, Commun. Contemp. Math., 22 (2020), 1950081. http://doi.org/10.1142/S0219199719500810 doi: 10.1142/S0219199719500810
[57]
C. Gasparetto, F. Gazzola, Resonance tongues for the Hill equation with Duffing coefficients and instabilities in a nonlinear beam equation, Commun. Contemp. Math., 20 (2018), 1750022. http://doi.org/10.1142/S0219199717500225 doi: 10.1142/S0219199717500225
[58]
F. Gazzola, Hexagonal design for stiffening trusses, Annali di Matematica, 194 (2015), 87–108. http://doi.org/10.1007/s10231-013-0366-2 doi: 10.1007/s10231-013-0366-2
F. Gazzola, M. Jleli, B. Samet, On the Melan equation for suspension bridges, J. Fixed Point Theory Appl., 16 (2014), 159–188. http://doi.org/10.1007/s11784-014-0200-5 doi: 10.1007/s11784-014-0200-5
[62]
F. Gazzola, R. Pavani, Wide oscillations finite time blow up for solutions to nonlinear fourth order differential equations, Arch. Rational Mech. Anal., 207 (2013), 717–752. http://doi.org/10.1007/s00205-012-0569-5 doi: 10.1007/s00205-012-0569-5
[63]
F. Gazzola, V. Racič, A model of synchronisation in crowd dynamics, Appl. Math. Model., 59 (2018), 305–318. http://doi.org/10.1016/j.apm.2018.02.001 doi: 10.1016/j.apm.2018.02.001
[64]
F. Gazzola, A. Soufyane, Long-time behavior of partially damped systems modeling degenerate plates with piers, Nonlinearity, 34 (2021), 7705–7727. http://doi.org/10.1088/1361-6544/ac24e2 doi: 10.1088/1361-6544/ac24e2
[65]
F. Gazzola, G. Sperone, Thresholds for hanger slackening and cable shortening in the Melan equation for suspension bridges, Nonlinear Anal. Real, 39 (2018), 520–536. http://doi.org/10.1016/j.nonrwa.2017.08.001 doi: 10.1016/j.nonrwa.2017.08.001
[66]
F. Gazzola, G. Sperone, Steady Navier-Stokes equations in planar domains with obstacle and explicit bounds for unique solvability, Arch. Rational Mech. Anal., 238 (2020), 1283–1347. http://doi.org/10.1007/s00205-020-01565-9 doi: 10.1007/s00205-020-01565-9
[67]
F. Gazzola, G. Sperone, T. Weth, A connection between symmetry breaking for Sobolev minimizers and stationary Navier-Stokes flows past a circular obstacle, Appl. Math. Optim., 85 (2022), 10. http://doi.org/10.1007/s00245-022-09831-w doi: 10.1007/s00245-022-09831-w
[68]
F. Gazzola, Y. Wang, R. Pavani, Variational formulation of the Melan equation, Math. Method. Appl. Sci., 41 (2018), 943–951. http://doi.org/10.1002/mma.3962 doi: 10.1002/mma.3962
[69]
D. Green, W. G. Unruh, The failure of the Tacoma Bridge: A physical model, Amer. J. Phys., 74 (2006), 706–716. http://doi.org/10.1119/1.2201854 doi: 10.1119/1.2201854
H. M. Irvine, Cable structures, Massachusetts: The MIT Press, 1981.
[72]
J. A. Jurado, S. Hernández, F. Nieto, A. Mosquera, Bridge aeroelasticity: sensitivity analysis and optimum design (high performance structures and materials), WIT Press, 2011.
[73]
I. B. Karintsev, I. V. Pavlenko, Hydroaeroelasticity, Sumy State University, 2017.
[74]
G. R. Kirchhoff, Über das gleichgewicht und die bewegung einer elastischen scheibe, J. Reine Angew. Math., 1850 (1850), 51–88. http://doi.org/10.1515/crll.1850.40.51 doi: 10.1515/crll.1850.40.51
[75]
B. Kawohl, J. Stará, G. Wittum, Analysis and numerical studies of a problem of shape design, Arch. Rational Mech. Anal., 114 (1991), 349–363. http://doi.org/10.1007/BF00376139 doi: 10.1007/BF00376139
A. C. Lazer, P. J. McKenna, Large-amplitude periodic oscillations in suspension bridges: some new connections with nonlinear analysis, SIAM Rev., 32 (1990), 537–578. http://doi.org/10.1137/1032120 doi: 10.1137/1032120
[78]
W. J. Lewis, Tension cables in suspension bridges. A case of form-finding, In: Tension structures, form and behaviour, ICE Publishing, 2017,101–133. http://doi.org/10.1680/tsfab.61736.101
[79]
J. H. Lienhard, Synopsis of lift, drag, and vortex frequency data for rigid circular cylinders, Research Division Bulletin, Washington State University College of Engineering, 1966.
[80]
A. E. H. Love, A treatise on the mathematical theory of elasticity, 4 Eds., Cambridge University Press, 1927.
[81]
M. Matsumoto, H. Matsumiya, S. Fujiwara, Y. Ito, New consideration on flutter properties based on step-by-step analysis, J. Wind Eng. Ind. Aerod., 98 (2010), 429–437. http://doi.org/10.1016/j.jweia.2010.02.001 doi: 10.1016/j.jweia.2010.02.001
[82]
P. J. McKenna, Large torsional oscillations in suspension bridges revisited: fixing an old approximation, Amer. Math. Mon., 106 (1999), 1–18. http://doi.org/10.1080/00029890.1999.12005001 doi: 10.1080/00029890.1999.12005001
[83]
P. J. McKenna, Oscillations in suspension bridges, vertical and torsional, Discrete. Cont. Dyn. Syst. S, 7 (2014), 785–791. http://doi.org/10.3934/dcdss.2014.7.785 doi: 10.3934/dcdss.2014.7.785
[84]
J. Melan, Theory of arches and suspension bridges, London: Myron Clark Pul. Comp., 1913.
[85]
O. Pironneau, On optimum profiles in Stokes flow, J. Fluid Mech., 59 (1973), 117–128. http://doi.org/10.1017/S002211207300145X doi: 10.1017/S002211207300145X
[86]
O. Pironneau, On optimum design in fluid mechanics, J. Fluid Mech., 64 (1974), 97–110. http://doi.org/10.1017/S0022112074002023 doi: 10.1017/S0022112074002023
[87]
W. Podolny, Cable-suspended bridges, In: Structural steel designer's handbook: AISC, AASHTO, AISI, ASTM, AREMA, and ASCE-07 design standards, 5 Eds., New York: McGraw-Hill, 2011.
[88]
W. A. Provis, Observations on the effects produced by wind on the suspension bridge over the Menai Strait, more especially as relates to the injuries sustained by the roadways during the storm of January, 1839; together with brief notices of various suggestions for repairing the structure, Transactions of the Institution of Civil Engineers, 3 (1842), 357–370. http://doi.org/10.1680/itrcs.1842.24373 doi: 10.1680/itrcs.1842.24373
[89]
W. Reid, A short account of the failure of a part of the Brighton Chain Pier, in the gale of the 30th of November 1836, Papers on Subjects Connected with the Duties of the Corps of Royal Engineers, Professional Papers of the Corps of Royal Engineers, Vol.I, 1844.
R. H. Scanlan, The action of flexible bridges under wind, I: flutter theory, J. Sound Vib., 60 (1978), 187–199. http://doi.org/10.1016/S0022-460X(78)80028-5 doi: 10.1016/S0022-460X(78)80028-5
[92]
R. H. Scanlan, The action of flexible bridges under wind, II: buffeting theory, J. Sound Vib., 60 (1978), 201–211. http://doi.org/10.1016/S0022-460X(78)80029-7 doi: 10.1016/S0022-460X(78)80029-7
[93]
R. H. Scanlan, J. J. Tomko, Airfoil and bridge deck flutter derivatives, Journal of the Engineering Mechanics Division, 97 (1971), 1717–1737. http://doi.org/10.1061/JMCEA3.0001526 doi: 10.1061/JMCEA3.0001526
[94]
R. Scott, In the wake of Tacoma. Suspension bridges and the quest for aerodynamic stability, ASCE Press, 2001. http://doi.org/10.1061/9780784405420
[95]
A. Selberg, Oscillation and aerodynamic instability of suspension bridges, Acta Polytechnica Scandinavica, Civil Engineering and Construction Series, 1961.
[96]
B. Semper, A mathematical model for suspension bridge vibration, Math. Comput. Model., 18 (1993), 17–28. http://doi.org/10.1016/0895-7177(93)90203-B doi: 10.1016/0895-7177(93)90203-B
[97]
B. Semper, Finite element methods for suspension bridge models, Comput. Math. Appl., 26 (1993), 77–91. http://doi.org/10.1016/0898-1221(93)90076-8 doi: 10.1016/0898-1221(93)90076-8
[98]
B. Semper, Finite element approximation of a fourth order integro-differential equation, Appl. Math. Lett., 7 (1994), 59–62. http://doi.org/10.1016/0893-9659(94)90054-X doi: 10.1016/0893-9659(94)90054-X
[99]
E. Simiu, R. H. Scanlan, Wind effects on structures: fundamentals and applications to design, 3 Eds., New York: John Wiley, 1996.
[100]
F. C. Smith, G. S. Vincent, Aerodynamic stability of suspension bridges: with special reference to the Tacoma Narrows Bridge, Part II: Mathematical analysis, University of Washington Press, 1950.
E. Ventsel, T. Krauthammer, Thin plates and shells: theory, analysis, and applications, New York: CRC Press, 2001. http://doi.org/10.1201/9780203908723
[103]
F. Verantii, Machinae novae, Venetiis cum Privilegiis, 1595.
H. Wagner, Über die entstehung des dynamischen auftriebes von tragflügeln, ZAMM-Z. Angew. Math. Mech., 5 (1925), 17–35. http://doi.org/10.1002/zamm.19250050103 doi: 10.1002/zamm.19250050103
[106]
L. Xu, Y. Hui, W. Zhu, X. Hua, Three-to-one internal resonance analysis for a suspension bridge with spatial cable through a continuum model, Eur. J. Mech. A-Solid., 90 (2021), 104354. http://doi.org/10.1016/j.euromechsol.2021.104354 doi: 10.1016/j.euromechsol.2021.104354
[107]
M. Zurru, Non-linear normal modes of plane cable trusses, Comput. Struct., 257 (2021), 106662. http://doi.org/10.1016/j.compstruc.2021.106662 doi: 10.1016/j.compstruc.2021.106662
This article has been cited by:
1.
Xu Hao, Deyu Zhou, Ruiheng Zhong, Shunxi Li, Xianming Meng, Bo Liu,
Electrification pathways for light-duty logistics vehicles based on perceived cost of ownership in Northern China,
2024,
3,
2831-932X,
10.20517/cf.2024.24
Filippo Gazzola, Mohamed Jleli, Bessem Samet. A new detailed explanation of the Tacoma collapse and some optimization problems to improve the stability of suspension bridges[J]. Mathematics in Engineering, 2023, 5(2): 1-35. doi: 10.3934/mine.2023045
Filippo Gazzola, Mohamed Jleli, Bessem Samet. A new detailed explanation of the Tacoma collapse and some optimization problems to improve the stability of suspension bridges[J]. Mathematics in Engineering, 2023, 5(2): 1-35. doi: 10.3934/mine.2023045
Algorithm 2: Pseudo-code of large neighborhood search [13].
Input: data of the instance (dij, qi, Q) and parameter Timelimit Initialization S0←InitialSol() S'←LocalSearch() BestSol←S' Timeelapsed←0 repeat time←now() S'←DestryAndRebuild(S') S'←LocalSearch(S') ifD(S')≤D(BestSol) BestSol←S' else ϵ←rand(0,1) If ϵ≤pvalue BestSol←S' end if end if Timeelapsed←now()−time untilTimeelapsed>Timelimit returnBestSol
Inputs: data of the instance (dij, qi, Q) and parameters T0, Tf, α, NT, Nstop, time_limit Initialization time_elapsed←0; time←now() create S0 using a randomized greedy procedure evaluateS0, D(S0), using Equation (1) SA←S0; S∗←S0; t←1; n←1; Ncnt←0; T1←T0 repeat counter←0 repeat create a new solution Sc, Sc∈V(SA) evaluate Sc, D(Sc) Cost←D(Sc)−D(SA) if Cost≤0 then SA←Sc; ; Ncont←0 ifD(S∗)<D(SA)then S∗←SA endif else pA←e−CostTn; ϵ←rand(0,1) ifϵ≤pAthen SA←Sc; Ncnt←0 else Ncnt←Ncnt+1 endif endif t←t+1; time_elapsed←now()−time; counter←counter+1 untilcounter≥NT n←n+1; Tn←α×Tn−1 untilNcnt>Nstop OR Tn>Tf OR timeelapsed>time_limit return S∗
Algorithm 2: Pseudo-code of large neighborhood search [13].
Input: data of the instance (dij, qi, Q) and parameter Timelimit Initialization S0←InitialSol() S'←LocalSearch() BestSol←S' Timeelapsed←0 repeat time←now() S'←DestryAndRebuild(S') S'←LocalSearch(S') ifD(S')≤D(BestSol) BestSol←S' else ϵ←rand(0,1) If ϵ≤pvalue BestSol←S' end if end if Timeelapsed←now()−time untilTimeelapsed>Timelimit returnBestSol
Algorithm 3: Pseudo-code of genetic algorithm [19].
Input: data of the instance (dij, qi, Q) and parameters pc, pm, #P, and Timelimit Initialization P←InitialPopulation() Timeelapsed←0 repeat time←now() evaluate(P) parents←selection(Pt) offspring←crossover(parents) offspring←mutation(offspring) P←variationoperations(parents) untilTimeelapsed>Timelimit returnbestindividualfound
Instance
Sector
Type of waste
Collection frequency
Number of collection points
Waste generation per collection point (m3)
Average
Std. dev.
A-F2HUM
A
Humid
6 per week
69
0.83
0.22
A-F2DRY
A
Dry
4 per week
69
2.22
0.62
A-F3HUM
A
Humid
6 per week
79
0.73
0.18
A-F3 DRY
A
Dry
3 per week
79
2.94
0.66
B-F2HUM
B
Humid
6 per week
68
0.79
0.21
B-F2 DRY
B
Dry
4 per week
68
2.85
0.79
B-F3HUM
B
Humid
6 per week
101
0.55
0.17
B-F3 DRY
B
Dry
3 per week
101
2.95
0.69
A + B-F2HUM
A + B
Humid
6 per week
137
0.81
0.21
A + B-F2 DRY
A + B
Dry
4 per week
137
2.55
0.74
A + B-F3HUM
A + B
Humid
6 per week
180
0.63
0.19
A + B-F3DRY
A + B
Dry
3 per week
180
2.95
0.67
Instance
SA
LNS
GA
min
median
max
iqr
min
median
max
iqr
min
median
max
iqr
A-F2HUM
25.99
*26.81
27.91
0.75
25.88
*26.87
27.90
0.73
32.80
36.59
41.79
2.95
A-F2DRY
46.13
*46.89
47.41
0.25
46.41
*46.89
48.20
0.33
52.93
55.67
58.86
1.75
A-F3HUM
27.31
27.95
29.30
0.39
27.73
28.81
29.33
0.66
37.48
40.74
43.23
2.50
A-F3DRY
66.23
66.74
67.15
0.39
65.95
66.56
67.30
0.38
72.61
75.36
77.59
2.20
B-F2HUM
24.56
24.96
26.02
0.52
24.72
25.30
25.60
0.03
31.01
34.24
36.03
3.24
B-F2DRY
39.80
*40.41
42.88
0.35
39.65
*40.36
40.90
0.48
45.72
48.13
52.64
2.76
B-F3HUM
29.04
29.54
30.44
0.73
29.30
30.16
31.20
1.12
44.12
47.59
53.63
2.75
B-F3DRY
57.35
*58.33
58.89
0.44
57.36
*58.32
58.97
0.36
68.86
72.66
77.03
3.75
A + B-F2HUM
48.43
49.30
50.54
0.88
50.14
50.88
51.83
0.89
77.82
82.91
88.79
5.54
A + B-F2DRY
88.99
90.51
92.51
1.11
88.54
91.59
94.61
1.98
111.65
115.34
121.69
3.30
A + B-F3HUM
54.83
*56.54
59.19
1.37
55.10
*56.25
57.78
0.78
114.27
127.10
140.38
5.75
A + B-F3DRY
121.24
122.72
123.96
1.10
125.87
128.70
131.30
1.56
174.92
182.04
186.23
5.75
Instance
CPLEX
Comparison with minimal D
Comparison with median D
D
CPLEX gap %
ΔSA
ΔLNS
ΔGA
ΔSA
ΔLNS
ΔGA
A-F2HUM
25.49
*0.00%
1.96%
1.53%
28.63%
5.18%
5.41%
43.55%
A-F2DRY
47.18
10.73%
–2.23%
–1.63%
10.49%
–0.61%
–0.61%
17.99%
A-F3HUM
27.21
*0.00%
0.37%
1.91%
36.49%
2.72%
5.88%
49.73%
A-F3 DRY
67.42
13.76%
–1.77%
–2.18%
7.58%
–1.01%
–1.28%
11.77%
B-F2HUM
24.53
0.43%
0.12%
0.77%
27.49%
1.75%
3.14%
39.59%
B-F2 DRY
40.66
10.65%
–2.12%
–2.48%
12.37%
–0.61%
–0.74%
18.37%
B-F3HUM
28.54
0.10%
1.75%
2.66%
57.64%
3.50%
5.68%
66.74%
B-F3 DRY
63.46
26.30%
–9.63%
–9.61%
7.73%
–8.08%
–8.10%
14.50%
A + B-F2HUM
49.12
10.13%
–1.40%
2.08%
57.64%
0.37%
3.58%
68.80%
A + B-F2 DRY
96.09
31.47%
–7.39%
–7.86%
15.61%
–5.81%
–4.68%
20.03%
A + B-F3HUM
57.62
16.54%
–4.84%
–4.37%
98.53%
1.87%
–2.38%
120.59%
A + B-F3DRY
141.18
39.09%
–14.12%
–10.84%
23.84%
–13.08%
–8.84%
28.94%
Average
–3.27%
–2.50%
32.00%
–1.46%
–0.24%
41.72%
Note: *These solutions are proven optimal by CPLEX.
Instance
M (sec)
Average number of iterations
SA
LNS
GA
A-F2HUM
828
2785036.17
905.97
66449.33
A-F2DRY
828
4234573.77
1623.03
64646.87
A-F3HUM
948
5310001.37
549.90
68082.77
A-F3 DRY
948
5153516.90
828.00
67384.67
B-F2HUM
816
4906570.60
862.00
64281.60
B-F2 DRY
816
2121397.27
1587.80
63497.00
B-F3HUM
1212
7424337.37
371.97
77485.87
B-F3 DRY
1212
7101348.27
591.30
76806.13
A + B-F2HUM
1644
10063074.37
308.03
90283.23
A + B-F2 DRY
1644
9726814.20
121.37
89513.53
A + B-F3HUM
2160
12840985.67
111.60
99323.93
A + B-F3DRY
2160
57603690.73
68.63
98254.67
Instance
SA
LNS
GA
min
median
max
iqr
min
median
max
iqr
min
median
max
iqr
E-n13-k4
247.00
247.00
248.00
0.00
247.00
247.00
247.00
0.00
247.00
248.00
265.00
1.00
E-n22-k4
375.00
375.00
383.00
0.00
375.00
375.00
375.00
0.00
375.00
389.00
439.00
14.50
E-n23-k3
569.00
569.00
597.00
0.00
619.00
619.00
619.00
0.00
569.00
628.50
732.00
58.00
E-n30-k3
503.00
503.00
503.00
0.00
534.00
534.00
537.00
3.00
507.00
547.00
636.00
40.00
E-n31-k7
379.00
390.00
425.00
16.00
379.00
379.00
393.00
0.00
395.00
471.00
573.00
40.75
E-n33-k4
835.00
835.00
843.00
1.75
835.00
835.00
835.00
0.00
507.00
547.00
636.00
40.00
E-n51-k5
521.00
521.00
538.00
5.75
521.00
521.00
536.00
0.00
565.00
610.00
681.00
46.75
E-n76-k7
684.00
689.00
694.00
1.75
830.00
*830.00
853.00
0.00
776.00
*833.50
912.00
59.75
E-n76-k8
736.00
738.50
747.00
2.75
737.00
737.00
740.00
0.00
846.00
935.00
1061.00
65.75
E-n76-k10
830.00
843.00
862.00
7.50
830.00
830.00
853.00
0.00
930.00
967.00
1052.00
42.25
E-n76-k14
1023.00
1034.00
1051.00
9.00
1026.00
1026.00
1026.00
0.00
1102.00
1158.50
1651.00
55.00
E-n101-k8
817.00
825.50
863.00
5.00
822.00
822.00
834.00
0.75
1119.00
1205.00
1365.00
80.00
E-n101-k14
1082.00
1093.00
1127.00
12.75
1080.00
1080.00
1086.00
0.00
1279.00
1401.50
1570.00
109.50
Instance
M (sec)
BKS
Comparison with best D value
Comparison with median D value
Δ'SA
Δ'LNS
Δ'GA
Δ'SA
Δ'LNS
Δ'GA
E-n13-k4
156
247
0.00%
0.00%
0.00%
0.00%
0.00%
0.40%
E-n22-k4
264
375
0.00%
0.00%
0.00%
0.00%
0.00%
3.73%
E-n23-k3
276
569
0.00%
8.79%
0.00%
0.00%
8.79%
10.46%
E-n30-k3
360
534
*–5.81%
0.00%
*–5.06%
–5.81%
0.00%
2.43%
E-n31-k7
372
379
0.00%
0.00%
4.22%
2.90%
0.00%
24.27%
E-n33-k4
396
835
0.00%
0.00%
1.68%
0.00%
0.00%
9.52%
E-n51-k5
612
521
0.00%
0.00%
8.45%
0.00%
0.00%
17.08%
E-n76-k7
912
682
0.29%
21.70%
13.78%
1.03%
21.70%
22.21%
E-n76-k8
912
735
0.14%
0.27%
15.10%
0.48%
0.27%
27.21%
E-n76-k10
912
830
0.00%
0.00%
12.05%
1.57%
0.00%
16.51%
E-n76-k14
912
1021
0.20%
0.49%
7.93%
1.27%
0.49%
13.47%
E-n101-k8
1212
815
0.25%
0.86%
37.30%
1.29%
0.86%
47.85%
E-n101-k14
1212
1071
1.03%
0.84%
19.42%
2.05%
0.84%
30.86%
Average
–
–
–0.30%
2.53%
8.84%
0.37%
2.53%
17.39%
Average without instance E-n30-k3
–
0.16%
2.75%
9.99%
0.88%
2.75%
18.63%
Note: *The solutions found have a lower value of D, but a greater number of routes (k = 4) than the reference BKS.
Feature
SA
LNS
GA
Type of algorithm
Local search
Neighborhood search
Evolutionary algorithm
Stopping criterion
Time limit/maximum allowable number of iterations without improvement
Time limit
Time limit/maximum time without improvement
Programming language
VBA
VBA
Python
Main parameters
Initial temperature/ function that determines the cooling mechanism
Auto-tuning by the author
Population size, crossover and mutation probability,
Instance
CPLEX
SA
LNS
GA
F2HUM
–1.80%
–4.19%
–0.91%
20.87%
F2 DRY
9.39%
3.56%
2.88%
13.57%
F3HUM
3.35%
–2.70%
–3.38%
39.29%
F3DRY
7.87%
–1.89%
2.08%
24.09%
Average
4.70%
–1.31%
0.17%
24.45%
Figure 1. Sketch of a suspension bridge
Figure 2. Cross section of the Messina Bridge
Figure 3. From left to right: first and second vertical modes, second torsional mode
Figure 4. Vortices around a plate generated in the wind tunnel of the Politecnico di Milano
Figure 5. Drag D and lift L acting on a disk and on a stadium-like section of a bridge
Figure 6. Regimes of flow across a circular cylinder, taken from [79]
Figure 7. Plots of the functions ω↦Ak(ω) in (2.11) for k=1,3,5,7
Figure 8. Left: sketch of a suspension bridge. Right: a fish-bone degenerate plate with piers
Figure 9. The residual energy E∞ in dependence of w(0) (left) and of S (right)
Figure 10. The domains D and Ω (left) and their intersections K and Σ with the plane x=0
Figure 11. Lift on the cross section of the deck of a bridge
Figure 12. CFD simulation of vortices around possible cross sections of the deck