A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems

This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.     

A multicast routing algorithm based on searching in directed graph

Aiming at constructing a delay and delay variation bounded Steiner tree in the real-time streaming media communication, in this paper, we discuss a multicast routing algorithm based on searching a directed graph (MRASDH). During the process of the construction of the multicast tree, some nodes and links in the network topology do not affect the outcome of the constructed tree. Therefore, based on the thought of shrinking the search space through deleting these non-relative nodes and edges to the utmost, the ant algorithm is utilized to generate a directed sub-graph of the network topology for each destination node, in which each node owns a bounded out-degree. And all these sub-graphs can be merged into a new directed graph that serves as the new search space. In the new space, the simulated annealing algorithm is applied to obtain a multicast tree that satisfies the condition for the optimization. The performance analysis and simulation results demonstrate that this algorithm can effectively construct a delay and delay variation bounded multicast tree. They also show that the algorithm have lower time complexity than the current ones, which means a much better result would be achieved when the system scale rises greatly.     

Branch-and-price algorithm for a multicast routing problem

This paper considers a multicast routing problem to find the minimum cost tree where the whole communication link delay on each path(route) of the tree is subject to a given delay allowance. The problem is formulated as an integer programming problem by using path variables. An associated problem reduction property is then characterised to reduce the solution space. Moreover, a polynomial time column generation procedure is exploited to solve the associated linear programming relaxation with such solution space reduced. Therefore a branch-and-price algorithm is derived to obtain the optimal integer solution(tree) for the problem. Computational results show that the algorithm can solve practical size problems in a reasonable length of time.     

A biased random-key genetic algorithm for routing and wavelength assignment

The problem of routing and wavelength assignment in wavelength division multiplexing optical networks consists in routing a set of lightpaths and assigning a wavelength to each of them, such that lightpaths whose routes share a common fiber are assigned different wavelengths. This problem was shown to be NP-hard when the objective is to minimize the total number of wavelengths used. We propose a genetic algorithm with random keys for routing and wavelength assignment with the goal of minimizing the number of different wavelengths used in the assignment. This algorithm extends the best heuristic in the literature by embedding it into an evolutionary framework. Computational results show that the new heuristic improves the state-of-the-art algorithms in the literature.     

Optimised crossover genetic algorithm for capacitated vehicle routing problem

This paper presents a genetic algorithm for solving capacitated vehicle routing problem, which is mainly characterised by using vehicles of the same capacity based at a central depot that will be optimally routed to supply customers with known demands. The proposed algorithm uses an optimised crossover operator designed by a complete undirected bipartite graph to find an optimal set of delivery routes satisfying the requirements and giving minimal total cost. We tested our algorithm with benchmark instances and compared it with some other heuristics in the literature. Computational results showed that the proposed algorithm is competitive in terms of the quality of the solutions found.     

A new hybrid genetic algorithm for the capacitated vehicle routing problem

Recently proved successful for variants of the vehicle routing problem (VRP) involving time windows, genetic algorithms have not yet shown to compete or challenge current best search techniques in solving the classical capacitated VRP. A new hybrid genetic algorithm to address the capacitated VRP is proposed. The basic scheme consists in concurrently evolving two populations of solutions to minimize total travelled distance using genetic operators combining variations of key concepts inspired from routing techniques and search strategies used for a time variant of the problem to further provide search guidance while balancing intensification and diversification. Results from a computational experiment over common benchmark problems report the proposed approach to be very competitive with the best-known methods.     

A hybrid generational genetic algorithm for the periodic vehicle routing problem with time windows

We propose a new population-based hybrid meta-heuristic for the periodic vehicle routing problem with time windows. This meta-heuristic is a generational genetic algorithm that uses two neighborhood-based meta-heuristics to optimize offspring. Local search methods have previously been proposed to enhance the fitness of offspring generated by crossover operators. In the proposed method, neighborhood-based meta-heuristics are used for their capacity to escape local optima, and deliver optimized and diversified solutions to the population of the next generation. Furthermore, the search performed by the neighborhood-based meta-heuristics repairs most of the constraint violations that naturally occur after the application of the crossover operators. The genetic algorithm we propose introduces two new crossover operators addressing the periodic vehicle routing problem with time windows. The two crossover operators are seeking the diversification of the exploration in the solution space from solution recombination, while simultaneously aiming not to destroy information about routes in the population as computing routes is NP-hard. Extensive numerical experiments and comparisons with all methods proposed in the literature show that the proposed methodology is highly competitive, providing new best solutions for a number of large instances.     

Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems

This paper presents the first investigation on applying a particle swarm optimization (PSO) algorithm to both the Steiner tree problem and the delay constrained multicast routing problem. Steiner tree problems, being the underlining models of many applications, have received significant research attention within the meta-heuristics community. The literature on the application of meta-heuristics to multicast routing problems is less extensive but includes several promising approaches. Many interesting research issues still remain to be investigated, for example, the inclusion of different constraints, such as delay bounds, when finding multicast trees with minimum cost. In this paper, we develop a novel PSO algorithm based on the jumping PSO (JPSO) algorithm recently developed by Moreno-Perez et al. (Proc. of the 7th Metaheuristics International Conference, 2007), and also propose two novel local search heuristics within our JPSO framework. A path replacement operator has been used in particle moves to improve the positions of the particle with regard to the structure of the tree. We test the performance of our JPSO algorithm, and the effect of the integrated local search heuristics by an extensive set of experiments on multicast routing benchmark problems and Steiner tree problems from the OR library. The experimental results show the superior performance of the proposed JPSO algorithm over a number of other state-of-the-art approaches.     

A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm

The Vehicle Routing Problem (VRP) is one of the most well studied problems in operations research, both in real life problems and for scientific research purposes. During the last 50 years a number of different formulations have been proposed, together with an even greater number of algorithms for the solution of the problem. In this paper, the VRP is formulated as a problem of two decision levels. In the first level, the decision maker assigns customers to the vehicles checking the feasibility of the constructed routes (vehicle capacity constraints) and without taking into account the sequence by which the vehicles will visit the customers. In the second level, the decision maker finds the optimal routes of these assignments. The decision maker of the first level, once the cost of each routing has been calculated in the second level, estimates which assignment is the better one to choose. Based on this formulation, a bilevel genetic algorithm is proposed. In the first level of the proposed algorithm, a genetic algorithm is used for calculating the population of the most promising assignments of customers to vehicles. In the second level of the proposed algorithm, a Traveling Salesman Problem (TSP) is solved, independently for each member of the population and for each assignment to vehicles. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the average quality is less than 1%. More specifically in the set with the 14 classic instances proposed by Christofides, the quality is 0.479% and in the second set with the 20 large scale vehicle routing problems, the quality is 0.826%. The algorithm is ranked in the tenth place among the 36 most known and effective algorithms in the literature for the first set of instances and in the sixth place among the 16 algorithms for the second set of instances. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the Expanding Neighborhood Search Strategy is used.     

Fault tolerant routing algorithm based on the artificial potential field model in Network-on-Chip

Recent advances in semiconductor technology enable the VLSI chips to integrate hundreds of intellectual properties with complex functionality. However, as the chip scales, the probability of faults is increasing, making fault tolerance a key concern in designing the large scale chips. The fault tolerant routing algorithms can guarantee sustained communication even the faults exist. It is an efficient technique to achieve fault tolerance in Networks-on-Chip. In this paper, we propose a new model based on the theory of artificial potential field (APF) to design various fault tolerant routing algorithms. In our model, the faults are considered as the poles of the repulsive potential fields while the destinations as the poles of the attractive potential fields. Messages are attracted to destinations and repelled by faults in the combined artificial potential field. The parameters used in the proposed APF based model are optimized through theoretical analysis and simulation experiments. They can support flexible fault tolerant routing algorithms. Finally, we evaluate the performance of the proposed fault tolerant routing algorithm based on the APF model in 2D-mesh NoCs with random faults. The simulation results show that the proposed APF based model is feasible and the routing algorithm can maintain good network performance.     

An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts

This paper presents a new exact algorithm for the Capacitated Vehicle Routing Problem (CVRP) based on the set partitioning formulation with additional cuts that correspond to capacity and clique inequalities. The exact algorithm uses a bounding procedure that finds a near optimal dual solution of the LP-relaxation of the resulting mathematical formulation by combining three dual ascent heuristics. The first dual heuristic is based on the q-route relaxation of the set partitioning formulation of the CVRP. The second one combines Lagrangean relaxation, pricing and cut generation. The third attempts to close the duality gap left by the first two procedures using a classical pricing and cut generation technique. The final dual solution is used to generate a reduced problem containing only the routes whose reduced costs are smaller than the gap between an upper bound and the lower bound achieved. The resulting problem is solved by an integer programming solver. Computational results over the main instances from the literature show the effectiveness of the proposed algorithm.      

Impact of source load and routing on QoS of packets delivery

We study how the number of packets in transit (NPT), that is an aggregate measure of a network quality of service (QoS) performance, is affected by routing algorithm coupled with volume of incoming traffic. We use our simulation model that is an abstraction of the Network Layer of the OSI Reference Model. We consider a static routing and two different types of dynamic routings and different volumes of incoming traffic in the network free flow state. Our study shows that the efficiency of performance of a routing changes with the volume of incoming traffic among the considered routings.     

A new exact algorithm for the vehicle routing problem based onq-paths andk-shortest paths relaxations

We consider the basic Vehicle Routing Problem (VRP) in which a fleet ofM identical vehicles stationed at a central depot is to be optimally routed to supply customers with known demands subject only to vehicle capacity constraints. In this paper, we present an exact algorithm for solving the VRP that uses lower bounds obtained from a combination of two relaxations of the original problem which are based on the computation ofq-paths andk-shortest paths. A set of reduction tests derived from the computation of these bounds is applied to reduce the size of the problem and to improve the quality of the bounds. The resulting lower bounds are then embedded into a tree-search procedure to solve the problem optimally. Computational results are presented for a number of problems taken from the literature. The results demonstrate the effectiveness of the proposed method in solving problems involving up to about 50 customers and in providing tight lower bounds for problems up to about 150 customers.     

Mathematical programming approaches for dual multicast routing problem with multilayer risk cost

This paper addresses a dual multicast routing problem with shared risk link group (SRLG) diverse costs (DMR-SRLGD) that arises from large-scale distribution of realtime multicast data (e.g., internet protocol TV, videocasting, online games, stock price update). The goal of this problem is to find two redundant multicast trees, each from one of the two sources to every destination at a minimum cost. The cost of the problem contains two parts: the multicast routing cost and the shard common risk cost. Such common risk could cause the failures of multiple links simultaneously. Therefore, the DMR-SRLGD ensures the availability and reliability of multicast service. We formulate an edge-based model for the DMR-SRLGD. In addition, we also propose a path-based model that rises from the Dantzig-Wolfe decomposition of the edge-based model, and develop a column-generation framework to solve the linear relaxation of the path-based formulation. We then employ a branch-and-price solution method to find integer solutions to DMR-SRLGD. We also extend both edge-based and path-based models to handle the complex quality of service requirements. The computational results show the edge-based model is superior than the path-based model for the easy and small test instances, whereas the path-based model provides better solutions in a timely fashion for hard or large test instances.     

A genetic algorithm for service level based vehicle scheduling

In many practical applications, vehicle scheduling problems involve more complex evaluation criteria than simple distance or travel time minimization. Scheduling to minimize delays between the accumulation and delivery of correspondence represents a class of vehicle scheduling problems, where: the evaluation of candidate solutions is costly, there are no efficient schemes for evaluation of partial solutions or perturbations to existing solutions, and dimensionality is limiting even for problems with relatively few locations. Several features of genetic algorithms (GA's) suggest that they may have advantages relative to alternative heuristic solution algorithms for such problems. These include ease of implementation through efficient coding of solution alternatives, simultaneous emphasis on global as well as local search, and the use of randomization in the search process. In addition, a GA may realize advantages usually associated with interactive methods by replicating the positive attributes of existing solutions in the search process, without explicitly defining or measuring these attributes. This study investigates these potential advantages through application of a GA to a service level based vehicle scheduling problem. The procedure is demonstrated for a vehicle scheduling problem with 15 locations where the objective is to minimize the time between the accumulation of correspondence at each location and delivery to destination locations. The results suggest that genetic algorithms can be effective for finding good quality scheduling solutions with only limited search of the solution space.     

An algorithm for node-capacitated ring routing

A strongly polynomial time algorithm is described to solve the node-capacitated routing problem in an undirected ring network.     

The savings algorithm for the vehicle routing problem

Survey is given concerning the savings method for the vehicle routing problem. Results for several methods and data sets are compared. Furthermore, modifications of the savings method are presented which show less CPU time and reduced storage requirements. Therefore, the savings method can be implemented on microcomputers.     

A memetic algorithm for the inventory routing problem

Journal of Heuristics - In this article, we study an Inventory Routing Problem with deterministic customer demand in a two-tier supply chain. The supply chain network consists of a supplier using a...     

Multirate multicast service provisioning I: an algorithm for optimal price splitting along multicast trees

In this two-part paper we present a general framework for addressing the optimal rare control problem in multirate multicast where the objective is the maximization of a social welfare function expressed by the sum of the users’ utility functions. Specifically, we propose a market-based mechanism that satisfies the informational constraints imposed by the decentralization of information in multirate multicast service provisioning, and achieves an optimal solution to the corresponding centralized optimization problem. In Part I we discover properties of an optimal solution to the centralized problem. Based on these properties, we develop a distributed algorithm that determines how link prices are split among users whose connections along a multicast tree share the same link.     

Optimal parameter estimation for Muskingum model based on Gray-encoded accelerating genetic algorithm

In order to reduce the computational amount and improve the computational precision for parameter optimization of Muskingum model, a new algorithm, Gray-encoded accelerating genetic algorithm (GAGA) is proposed. With the shrinking of searching range, the method gradually directs to an optimal result with the excellent individuals obtained by Gray genetic algorithm (GGA). The global convergence is analyzed for the new genetic algorithm. Its efficiency is verified by application of Muskingum model. Compared with the nonlinear programming methods, least residual square method and the test method, GAGA has higher precision. And compared with GGA and BGA (binary-encoded genetic algorithm), GAGA has rapider convergent speed.