An evolutionary algorithm for the vehicle routing problem with route balancing

In this paper, we address a bi-objective vehicle routing problem in which the total length of routes is minimized as well as the balance of routes, i.e. the difference between the maximal route length and the minimal route length. We propose a meta-heuristic method based on an evolutionary algorithm involving classical multi-objective operators. To improve its efficiency, two mechanisms, which favor the diversification of the search, have been added. First, an elitist diversification mechanism is used in cooperation with classical diversification methodologies. Second, a parallel model designed to take into account the elitist diversification is proposed. Our method is tested on standard benchmarks for the vehicle routing problem. The contribution of the introduced mechanisms is evaluated by different performance metrics. All the experimentations indicate a strict improvement of the generated Pareto set.     

An algorithm for evolutionary surfaces

Summary An Algorithm is presented which allows to split the calculation of the mean curvature flow of surfaces with or without boundary into a series of Poisson problems on a series of surfaces. This gives a new method to solve Plateau's problem forH-surfaces.     

Shortest-route formulation of mixed-model assembly line balancing problem

A shortest-route formulation of the mixed-model assembly line balancing problem is presented. Common tasks across models are assumed to exist and these tasks are performed in the same stations. The formulation is based on an algorithm which solves the single-model version of the problem. The mixed-model system is transformed into a single-model system with a combined precedence diagram. The model is capable of considering any constraint that can be expressed as a function of task assignments.     

An algorithm for Gauss-Romberg integration

WhenR ^(m) f is anm copy version of a quadrature ruleRf, the error functional satisfies an asymptotic expansion $$R^{(m)} f - If \simeq d_2 h^2 + d_4 h^4 + ...,m = 1/h.$$ In the conventional form of Romberg Integration,Rf is the trapezoidal rule and early terms of this expansion are “eliminated.” For this purpose the Neville-Romberg algorithm is used to construct the conventionalT-table. IfRf is taken to be a ruleGf of polynomial degree 2t+1 the firstt terms in this expansion are in any case zero. A generalization of the Neville-Romberg algorithm is derived. This “eliminates” termsd _2s h ^2s ,s=t+1,t+2, ... An associatedG-table is defined and some of its properties are noted.     

GRASP-ASP: An algorithm for the CVRP with route balancing

An extension of the capacitated vehicle routing problem is studied in this paper. In this version the difference between the individual route lengths is minimized simultaneously with the total length. The drivers’ workload and perhaps, income, may be affected by the route lengths; so adding this objective makes the problem closer to real-life than the original, single-objective problem. A heuristic based on GRASP is used to obtain an approximation of the Pareto set. The proposed heuristic is tested on instances from the literature, obtaining good approximations of the Pareto set.     

Bicriteria sequencing methods for the mixed-model assembly line in just-in-time production systems

A mixed-model manufacturing facility operating in a pull production environment can be controlled by setting a production schedule only for the last process in the facility which is usually an assembly line of mixed-model type. In the mixed-model sequencing problems, two major goals are considered: (1) smoothing the workload on each workstation on the assembly line, and (2) keeping a constant rate of usage of all parts used on the assembly line. In this study, first, some well-known solution approaches with goal 2 are analyzed through minimizing the sum-of-deviations of actual production from the desired amount. The approaches that are found to be performing better than the others are extended for the bicriteria problem considering goals 1 and 2, simultaneously. It is also shown that the bicriteria problem with the sum-of-deviations type objective function can also be formulated as an assignment problem, and the optimal solution to the small-sized problems can thus be obtained by solving the assignment problem. Finally, the conditions when it is important to take the workload-smoothing goal into consideration are analyzed.     

An efficient evolutionary algorithm for the ring star problem

This paper addresses the ring star problem (RSP). The goal is to locate a cycle through a subset of nodes of a network aiming to minimize the sum of the cost of installing facilities on the nodes on the cycle, the cost of connecting them and the cost of assigning the nodes not on the cycle to their closest node on the cycle. A fast and efficient evolutionary algorithm is developed which is based on a new formulation of the RSP as a bilevel programming problem with one leader and two independent followers. The leader decides which nodes to include in the ring, one follower decides about the connections of the cycle and the other follower decides about the assignment of the nodes not on the cycle. The bilevel approach leads to a new form of chromosome encoding in which genes are associated to values of the upper level variables. The quality of each chromosome is evaluated by its fitness, by means of the objective function of the RSP. Hence, in order to compute the value of the lower level variables, two optimization problems are solved for each chromosome. The computational results show the efficiency of the algorithm in terms of the quality of the solutions yielded and the computing time. A study to select the best configuration of the algorithm is presented. The algorithm is tested on a set of benchmark problems providing very accurate solutions within short computing times. Moreover, for one of the problems a new best solution is found.     

An algorithm for the capacitated vehicle routing problem with route balancing

In this paper, we present a multi-objective evolutionary algorithm for the capacitated vehicle routing problem with route balancing. The algorithm is based on a formerly developed multi-objective algorithm using an explicit collective memory method, namely the extended virtual loser (EVL). We adapted and improved the algorithm and the EVL method for this problem. We achieved good results with this simple technique. In case of this problem the quality of the results of the algorithm is similar to that of other evolutionary algorithms.     

An adjoint-based scalable algorithm for time-parallel integration

As parallel architectures evolve the number of available cores continues to increase. Applications need to display a high degree of concurrency in order to effectively utilize the available resources. Large scale partial differential equations mainly rely on a spatial domain decomposition approach, where the number of parallel tasks is limited by the size of the spatial domain. Time parallelism offers a promising approach to increase the degree of concurrency. ‘Parareal’ is an iterative parallel in time algorithm that uses both low and high accuracy numerical solvers. Though the high accuracy solvers are computed in parallel, the low accuracy ones are in serial.This paper revisits the parallel in time algorithm [11] using a nonlinear optimization approach. Like in the traditional ‘Parareal’ method, the time interval is partitioned into subintervals, and local time integrations are carried out in parallel. The objective cost function quantifies the mismatch of local solutions between adjacent subintervals. The optimization problem is solved iteratively using gradient-based methods. All the computational steps – forward solutions, gradients, and Hessian-vector products – involve only ideally parallel computations and therefore are highly scalable.The feasibility of the proposed algorithm is studied on three different model problems, namely, heat equation, Arenstorf's orbit, and the Lorenz model.     

An evolutionary programming algorithm for continuous global optimization

Evolutionary computations are very effective at performing global search (in probability), however, the speed of convergence could be slow. This paper presents an evolutionary programming algorithm combined with macro-mutation (MM), local linear bisection search (LBS) and crossover operators for global optimization. The MM operator is designed to explore the whole search space and the LBS operator to exploit the neighborhood of the solution. Simulated annealing is adopted to prevent premature convergence. The performance of the proposed algorithm is assessed by numerical experiments on 12 benchmark problems. Combined with MM, the effectiveness of various local search operators is also studied.     

A balancing method and genetic algorithm for disassembly line balancing

Disassembly activities take place in various recovery operations including remanufacturing, recycling and disposal. The disassembly line is the best choice for automated disassembly of returned products. It is therefore important that the disassembly line be designed and balanced so that it works as efficiently as possible. The disassembly line balancing problem seeks a sequence which: is feasible, minimizes workstations, and ensures similar idle times, as well as other end-of-life specific concerns. However finding the optimal balance is computationally intensive with exhaustive search quickly becoming prohibitively large even for relatively small products. In this paper the problem is mathematically defined and proven NP-complete. Additionally, a new formula for quantifying the level of balancing is proposed. A first-ever set of a priori instances to be used in the evaluation of any disassembly line balancing solution technique is then developed. Finally, a genetic algorithm is presented for obtaining optimal or near-optimal solutions for disassembly line balancing problems and examples are presented to illustrate implementation of the methodology.     

An algorithm of evolutionarily stable strategies for the single-population evolutionary game

In this paper, we study the single-population evolutionary game and construct an algorithm to find evolutionarily stable strategies. Finally, by an example, we illuminate the computing process of algorithm.     

An algorithm for numerical integration based on quasi-interpolating splines

In this paper product quadratures based on quasi-interpolating splines are proposed for the numerical evaluation of integrals with anL ₁-kernel and of Cauchy Principal Value integrals.Work sponsored by Ministero dell'Università e Ricerca Scientifica of Italy.     

An algorithm for finding optimal integration lattices of composite order

In this paper we describe a search algorithm that can be used to determine good lattices of orderN whenN=N _L N _R has two nontrivial integer factors. This algorithm is based on relationships between an integer latticeA _R of orderN _R and its various sublattices all of orderN. Using this we have determined all four dimensional good lattices of order 599 or less. Our list has 23 entries.This work was supported by the Applied Mathematical Sciences Subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the Norwegian Council for Humanities and Science.     

An adaptive algorithm for numerical integration over an n-dimensional cube

A program is presented for automatic numerical integration over the n-dimensional cube. Interesting advantages of this program are the strong adaptivity of the algorithm combined with the use of a good basic integration rule. This is shown by some comparative tests with other programs.     

A genetic algorithm for robotic assembly line balancing

Flexibility and automation in assembly lines can be achieved by the use of robots. The robotic assembly line balancing (RALB) problem is defined for robotic assembly line, where different robots may be assigned to the assembly tasks, and each robot needs different assembly times to perform a given task, because of its capabilities and specialization. The solution to the RALB problem includes an attempt for optimal assignment of robots to line stations and a balanced distribution of work between different stations. It aims at maximizing the production rate of the line. A genetic algorithm (GA) is used to find a solution to this problem. Two different procedures for adapting the GA to the RALB problem, by assigning robots with different capabilities to workstations are introduced: a recursive assignment procedure and a consecutive assignment procedure. The results of the GA are improved by a local optimization (hill climbing) work-piece exchange procedure. Tests conducted on a set of randomly generated problems, show that the Consecutive Assignment procedure achieves, in general, better solution quality (measured by average cycle time). Further tests are conducted to determine the best combination of parameters for the GA procedure. Comparison of the GA algorithm results with a truncated Branch and Bound algorithm for the RALB problem, demonstrates that the GA gives consistently better results.     

An efficient and reliable quadrature algorithm for integration with respect to binomial measures

In this work numerical methods for integration with respect to binomial measures are considered. Binomial measures are examples of fractal measures and arise when multifractal properties are investigated. Interpolatory quadrature rules are considered. An automatic integrator with local quadrature rules that generalize the five points Newton Cotes formula and error estimates based on null rules is then described. Numerical tests are performed to verify the efficiency and accuracy of the method. These tests confirm that the automatic integrator turns out to be as good as one of the best known quadrature algorithms with respect to the Lebesgue measure. AMS subject classification (2000)  28A25, 60G18, 65D30, 65D32, 68M15