Solving the Vehicle Routing Problem with Genetic ALgorithm and Simulated Annealing

This Thesis Work will concentrate on a very interesting problem, the Vehicle Routing Problem (VRP). In this problem, customers or cities have to be visited and packages have to be transported to each of them, starting from a basis point on the map. The goal is to solve the transportation problem, to be able to deliver the packages-on time for the customers,-enough package for each Customer,-using the available resources- and – of course - to be so effective as it is possible.Although this problem seems to be very easy to solve with a small number of cities or customers, it is not. In this problem the algorithm have to face with several constraints, for example opening hours, package delivery times, truck capacities, etc. This makes this problem a so called Multi Constraint Optimization Problem (MCOP). What’s more, this problem is intractable with current amount of computational power which is available for most of us. As the number of customers grow, the calculations to be done grows exponential fast, because all constraints have to be solved for each customers and it should not be forgotten that the goal is to find a solution, what is best enough, before the time for the calculation is up. This problem is introduced in the first chapter: form its basics, the Traveling Salesman Problem, using some theoretical and mathematical background it is shown, why is it so hard to optimize this problem, and although it is so hard, and there is no best algorithm known for huge number of customers, why is it a worth to deal with it. Just think about a huge transportation company with ten thousands of trucks, millions of customers: how much money could be saved if we would know the optimal path for all our packages.Although there is no best algorithm is known for this kind of optimization problems, we are trying to give an acceptable solution for it in the second and third chapter, where two algorithms are described: the Genetic Algorithm and the Simulated Annealing. Both of them are based on obtaining the processes of nature and material science. These algorithms will hardly ever be able to find the best solution for the problem, but they are able to give a very good solution in special cases within acceptable calculation time.In these chapters (2nd and 3rd) the Genetic Algorithm and Simulated Annealing is described in details, from their basis in the “real world” through their terminology and finally the basic implementation of them. The work will put a stress on the limits of these algorithms, their advantages and disadvantages, and also the comparison of them to each other.Finally, after all of these theories are shown, a simulation will be executed on an artificial environment of the VRP, with both Simulated Annealing and Genetic Algorithm. They will both solve the same problem in the same environment and are going to be compared to each other. The environment and the implementation are also described here, so as the test results obtained.Finally the possible improvements of these algorithms are discussed, and the work will try to answer the “big” question, “Which algorithm is better?”, if this question even exists.

Inflation and debt indexation : the equivalence of two alternative schemes for the case of periodic payments

The presence of inflation has induced the financial institutions to implement procedures devised to protect the real values of theirs loans. Two of such procedurcs, the floaaing rale scheme and the monetary correction mechanism, tend to lead to very different streams of payments. However, whenever the floating rate scheme follows the rule of Strict adhercnce to lhe Fisher equation, lhe two procedures are financially equivalent.

Collateral avoids Ponzi schemes in incomplete markets

Without introducing neither debt constraints nor transversality conditions to avoid the possibility of Ponzi schemes, we show existence of equilibrium in an incomplete markets economy with a collateral structure.

On Ponzi schemes in infinite horizon collateralized economies with default penalties

Araujo, Páscoa and Torres-Martínez (2002) showed that, without imposing any debt constraint, Ponzi schemes are ruled out in infinite horizon economies with limited commitment when collateral is the only mechanism that partially secures loans. Páscoa and Seghir (2009) presented two examples in which they argued that Ponzi schemes may reappear if, additionally to the seizure of the collateral, there are sufficiently harsh default penalties assessed (directly in terms of utility) against the defaulters. Moreover, they claimed that if default penalties are moderate then Ponzi schemes are ruled out and existence of a competitive equilibrium is restored. This paper questions the validity of the claims made in Páscoa and Seghir (2009). First, we show that it is not true that harsh default penalties lead to Ponzi schemes in the examples they have proposed. A competitive equilibrium with no trade can be supported due to unduly pessimistic expectations on asset deliveries. We subsequently refine the equilibrium concept in the spirit of Dubey, Geanakoplos and Shubik (2005) in order to rule out spurious inactivity on asset markets due to irrational expectations. Our second contribution is to provide a specific example of an economy with moderate default penalties in which Ponzi schemes reappear when overpessimistic beliefs on asset deliveries are ruled out. Our finding shows that, contrary to what is claimed by Páscoa and Seghir (2009), moderate default penalties do not always prevent agents to run a Ponzi scheme.

On the construction of explicit exponential based schemes for Stiff SDEs

Trabalho apresentado Numerical Solution of Differential and Differential-Algebraic Equations (NUMDIFF-14), Halle, 7-11 Sep 2015

Search schemes for random optimization algorithms that preserve the asymptotic distribution

Markovian algorithms for estimating the global maximum or minimum of real valued functions defined on some domain Omega subset of R-d are presented. Conditions on the search schemes that preserve the asymptotic distribution are derived. Global and local search schemes satisfying these conditions are analysed and shown to yield sharper confidence intervals when compared to the i.i.d. case.

The open capacitated arc routing problem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

The Poisson-exponential regression model under different latent activation schemes

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Performance Comparisons of EWMA Control Chart Schemes

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Antibiotic treatment schemes for very severe community-acquired pneumonia in children: a randomized clinical study

Objective. To compare clinical response to initial empiric treatment with oxacillin plus ceftriaxone and amoxicillin plus clavulanic acid in hospitalized children diagnosed with very severe community-acquired pneumonia (CAP).Methods. A prospective randomized clinical study was conducted among children 2 months to 5 years old with a diagnosis of very severe CAP in the pediatric ward of São Paulo State University Hospital in Botucatu, São Paulo, Brazil, from April 2007 to May 2008. Patients were randomly divided into two groups by type of treatment: an oxacillin/ceftriaxone group (OCG, n = 48) and an amoxicillin/clavulanic acid group (ACG, n = 56). Analyzed outcomes were: time to clinical improvement (fever and tachypnea), time on oxygen therapy, length of stay in hospital, need to widen antimicrobial spectrum, and complications (including pleural effusion).Results. The two groups did not differ statistically for age, sex, symptom duration before admission, or previous antibiotic treatment. Time to improve tachypnea was less among ACG patients than OCG patients (4.8 +/- 2.2 versus 5.8 +/- 2.4 days respectively; P = 0.028), as was length of hospital stay (11.0 +/- 6.2 versus 14.4 +/- 4.5 days respectively; P = 0.002). There were no statistically significant differences between the two groups for fever improvement time, time on oxygen therapy, need to widen antimicrobial spectrum, or frequency of pleural effusion.Conclusions. Both treatment plans are effective in treating very severe CAP in 2-monthto 5-year-old hospitalized children. The only analyzed outcome that favored amoxicillin/clavulanic acid treatment was time required to improve tachypnea.

Study of alternative schemes for the parameterization step of the continuation power flow method based on physical parameters, part I: Mathematical modeling

The conventional power flow method is considered to be inadequate to obtain the maximum loading point because of the singularity of Jacobian matrix. Continuation methods are efficient tools for solving this kind of problem since different parameterization schemes can be used to avoid such ill-conditioning problems. This paper presents the details of new schemes for the parameterization step of the continuation power flow method. The new parameterization options are based on physical parameters, namely, the total power losses (real and reactive), the power at the slack bus (real or reactive), the reactive power at generation buses, and transmission line power losses (real and reactive). The simulation results obtained with the new approach for the IEEE test systems (14, 30, 57, and 118 buses) are presented and discussed in the companion paper. The results show that the characteristics of the conventional method are not only preserved but also improved.

Study of alternative schemes for the parameterization step of the continuation power flow method based on physical parameters, part II: Performance evaluation

New parameterization schemes have been proposed by the authors in Part I of this paper. In this part these new options for the parameterization of power flow equations are tested, namely, the total power losses (real and reactive), the power at the slack bus (real or reactive), the reactive power at generation buses, and the transmission line power losses (real and reactive). These different parameterization schemes can be used to obtain the maximum loading point without ill-conditioning problems, once the singularity of Jacobian matrix is avoided. The results obtained with the new approach for the IEEE test systems (14, 30, 57, and 118 buses) show that the characteristics of the conventional method are not only preserved but also improved. In addition, it is shown that the proposed method and the conventional one can be switched during the tracing of PV curves to determine, with few iterations, all points of the PV curve. Several tests were also carried out to compare the performance of the proposed parameterization schemes for the continuation power flow method with the use of both the secant and tangent predictors.

GRASP with evolutionary path-relinking for the capacitated arc routing problem

The Capacitated Arc Routing Problem (CARP) is a well-known NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours servicing a subset of required edges under vehicle capacity constraints. There are numerous applications for the CARP, such as street sweeping, garbage collection, mail delivery, school bus routing, and meter reading. A Greedy Randomized Adaptive Search Procedure (GRASP) with Path-Relinking (PR) is proposed and compared with other successful CARP metaheuristics. Some features of this GRASP with PR are (i) reactive parameter tuning, where the parameter value is stochastically selected biased in favor of those values which historically produced the best solutions in average; (ii) a statistical filter, which discard initial solutions if they are unlikely to improve the incumbent best solution; (iii) infeasible local search, where high-quality solutions, though infeasible, are used to explore the feasible/infeasible boundaries of the solution space; (iv) evolutionary PR, a recent trend where the pool of elite solutions is progressively improved by successive relinking of pairs of elite solutions. Computational tests were conducted using a set of 81 instances, and results reveal that the GRASP is very competitive, achieving the best overall deviation from lower bounds and the highest number of best solutions found. © 2011 Elsevier Ltd. All rights reserved.