Vehicle routing optimization algorithm based on time windows and dynamic demand

To provide the supplier with the minimizum vehicle travel distance in the distribution process of goods in three situations of new customer demand,customer cancellation service,and change of customer delivery address,based on the ideas of pre-optimization and real-time optimization,a two-stage planning model of dynamic demand based vehicle routing problem with time windows was established.At the pre-optimization stage,an improved genetic algorithm was used to obtain the pre-optimized distribution route,a large-scale neighborhood search method was integrated into the mutation operation to improve the local optimization performance of the genetic algorithm,and a variety of operators were introduced to expand the search space of neighborhood solutions;At the real-time optimization stage,a periodic optimization strategy was adopted to transform a complex dynamic problem into several static problems,and four neighborhood search operators were used to quickly adjust the route.Two different scale examples were designed for experiments.It is proved that the algorithm can plan the better route,and adjust the distribution route in time under the real-time constraints.Therefore,the proposed algorithm can provide theoretical guidance for suppliers to solve the dynamic demand based vehicle routing problem.

Real-time Threshold Routing Algorithm Based on Wireless Sensor Network

[Objective] This study was to design an intelligent greenhouse real-time monitoring system based on the core technology of Internet of Things in order to meet the needs of agricultural informatization and intellectualization. [Method] Based on the application characteristics of Wireless Sensor Network （WSN）, the intelligent greenhouse monitoring system was designed. And for the incompleteness strategy of load balancing in the Low-Energy Adaptive Clustering Hierarchy （LEACH）, a Real- time Threshold Routing Algorithm （RTRA） was proposed. [Result] The performance of network lifetime and network delay of RTRA were tested in MATLAB and found that, within the same testing environment, RTRA can save nodes energy consumption, prolong network lifetime, and had better real-time performance than LEACH. The al- gorithm satisfies the crops＇ requirements on real-time and energy efficiency in the greenhouse system. [Conclusion] For the good performance on real-time, the de- signed intelligent greenhouse real-time monitoring system laid the foundation for the research and development of agricultural informatization and intellectualization.

Multiple People Picking Assignment and Routing Optimization Based on Genetic Algorithm

In order to improve the picking efficiency,reduce the picking time,this paper take artificial picking operation of a certain distribution center which has double-area warehouse as the studying object.Discuss the picking task allocation and routing problems.Establish the TSP model of order-picking system.Create a heuristic algorithm bases on the Genetic Algorithm(GA)which help to solve the task allocating problem and to get the associated order-picking routes.And achieve the simulation experiment with the Visual 6.0C++platform to prove the rationality of the model and the effectiveness of the arithmetic.

QoS multicast routing algorithm based on GA

The multicast routing problem with multiple QoS constraints in networks with uncertain parameters is discussed, and a network model that is suitable to research such QoS multicast routing problem is described. The QMRGA, a multicast routing policy for Internet, mobile network or other highperformance networks is mainly presented, which is based on the genetic algorithm(GA), and can provide QoSsensitive paths in a scalable and flexible way in the network environment with uncertain parameters. The QMRGA can also optimize the network resources such as bandwidth and delay, and can converge to the optimal or nearoptimal solution within few iterations, even for the network environment with uncertain parameters. The incremental rate of computational cost can be close to a polynomial and is less than exponential rate. The performance measures of the QMRGA are evaluated by using simulations. The results show that QMRGA provides an available approach to QoS multicast routing in network environment with uncertain parameters.

A Memetic Algorithm With Competition for the Capacitated Green Vehicle Routing Problem

In this paper, a memetic algorithm with competition(MAC) is proposed to solve the capacitated green vehicle routing problem(CGVRP). Firstly, the permutation array called traveling salesman problem(TSP) route is used to encode the solution, and an effective decoding method to construct the CGVRP route is presented accordingly. Secondly, the k-nearest neighbor(k NN) based initialization is presented to take use of the location information of the customers. Thirdly, according to the characteristics of the CGVRP, the search operators in the variable neighborhood search(VNS) framework and the simulated annealing(SA) strategy are executed on the TSP route for all solutions. Moreover, the customer adjustment operator and the alternative fuel station(AFS) adjustment operator on the CGVRP route are executed for the elite solutions after competition. In addition, the crossover operator is employed to share information among different solutions. The effect of parameter setting is investigated using the Taguchi method of design-ofexperiment to suggest suitable values. Via numerical tests, it demonstrates the effectiveness of both the competitive search and the decoding method. Moreover, extensive comparative results show that the proposed algorithm is more effective and efficient than the existing methods in solving the CGVRP.

Multiple constraints-based QoS multicast routing: model and algorithms

Constraint-based multicast routing, which aims at identifying a path that satisfies a set of quality of service (QoS) constraints, has became a very important research issue in the areas of networks and distributed systems. In general, multi-constrained path selection with or without optimization is a NP-complete problem that can not be exactly solved in polynomial time. Hence, accurate constraints-based routing algorithms with a fast running time are scarce, perhaps even non-existent. The expected impact of such a constrained-based routing algorithm has resulted in the proposal of numerous heuristics and a few exact QoS algorithms. This paper aims to give a thorough, concise and fair evaluation of the most important multiple constraint-based QoS multicast routing algorithms known today, and it provides a descriptive overview and simulation results of these multi-constrained routing algorithms.

Anycast service model and its QoS routing algorithm

In the Internet, a group of replicated servers is commonly used in order to improve the scalability of network service. Anycast service is a new network service that can improve network load distribution and simplify certain applications. In this paper, the authors described a simple anycast service model in the Internet without significant affecting the routing and protocol processing infrastructure that was already in place, and proposed an anycast QoS routing algorithm for this model. The algorithm used randomized method to balance network load and improve its performance. Several new techniques are proposed in the algorithm, first, theminimum hops for each node are used in the algorithm, which are used as metric for computing the probability of possible out links. The metric is pre computed for each node in the network, which can simplify the network complexity and provide the routing process with useful information. Second, randomness is used at the link level and depends dynamically on the routing configuration. This provides great flexibility for the routing process, prevents the routing process from overusing certain fixed routing paths, and adequately balances the delay of the routing path. the authors assess the quality of QoS algorithm in terms of the acceptance ratio on anycast QoS requests, and the simulation results on a variety of network topologies and on various parameters show that the algorithm has good performances and can balance network load effectively.

Application of Improved Multi-Objective Ant Colony Optimization Algorithm in Ship Weather Routing

This paper presents a novel intelligent and effective method based on an improved ant colony optimization(ACO)algorithm to solve the multi-objective ship weather routing optimization problem,considering the navigation safety,fuel consumption,and sailing time.Here the improvement of the ACO algorithm is mainly reflected in two aspects.First,to make the classical ACO algorithm more suitable for long-distance ship weather routing and plan a smoother route,the basic parameters of the algorithm are improved,and new control factors are introduced.Second,to improve the situation of too few Pareto non-dominated solutions generated by the algorithm for solving multi-objective problems,the related operations of crossover,recombination,and mutation in the genetic algorithm are introduced in the improved ACO algorithm.The final simulation results prove the effectiveness of the improved algorithm in solving multi-objective weather routing optimization problems.In addition,the black-box model method was used to study the ship fuel consumption during a voyage;the model was constructed based on an artificial neural network.The parameters of the neural network model were refined repeatedly through the historical navigation data of the test ship,and then the trained black-box model was used to predict the future fuel consumption of the test ship.Compared with other fuel consumption calculation methods,the black-box model method showed higher accuracy and applicability.

Load Balancing Routing Algorithm Based on Extended Link States in LEO Constellation Network

As an important part of satellite communication network,LEO satellite constellation network is one of the hot research directions.Since the nonuniform distribution of terrestrial services may cause inter-satellite link congestion,improving network load balancing performance has become one of the key issues that need to be solved for routing algorithms in LEO network.Therefore,by expanding the range of available paths and combining the congestion avoidance mechanism,a load balancing routing algorithm based on extended link states in LEO constellation network is proposed.Simulation results show that the algorithm achieves a balanced distribution of traffic load,reduces link congestion and packet loss rate,and improves throughput of LEO satellite network.

Ant Colony Algorithm for Solving QoS Routing Problem

Based on the state transition rule, the local updating rule and the global updating rule of ant colony algorithm, we propose an improved ant colony algorithm of the least\|cost quality of service (QoS) unicast routing. The algorithm is used for solving the routing problem with delay, delay jitter, bandwidth, and packet loss\|constrained. In the simulation, about 52.33% ants find the successful QoS routing , and converge to the best. It is proved that the algorithm is efficient and effective.

Single Failure Routing Protection Algorithm in the Hybrid SDN Network

Loop free alternate(LFA)is a routing protection scheme that is currently deployed in commercial routers.However,LFA cannot handle all single network component failure scenarios in traditional networks.As Internet service providers have begun to deploy software defined network(SDN)technology,the Internet will be in a hybrid SDN network where traditional and SDN devices coexist for a long time.Therefore,this study aims to deploy the LFA scheme in hybrid SDN network architecture to handle all possible single network component failure scenarios.First,the deployment of LFA scheme in a hybrid SDN network is described as a 0-1 integer linear programming(ILP)problem.Then,two greedy algorithms,namely,greedy algorithm for LFA based on hybrid SDN(GALFAHSDN)and improved greedy algorithm for LFA based on hybrid SDN(IGALFAHSDN),are proposed to solve the proposed problem.Finally,both algorithms are tested in the simulation environment and the real platform.Experiment results show that GALFAHSDN and IGALFAHSDN can cope with all single network component failure scenarios when only a small number of nodes are upgraded to SDN nodes.The path stretch of the two algorithms is less than 1.36.

Solving material distribution routing problem in mixed manufacturing systems with a hybrid multi-objective evolutionary algorithm

The material distribution routing problem in the manufacturing system is a complex combinatorial optimization problem and its main task is to deliver materials to the working stations with low cost and high efficiency. A multi-objective model was presented for the material distribution routing problem in mixed manufacturing systems, and it was solved by a hybrid multi-objective evolutionary algorithm (HMOEA). The characteristics of the HMOEA are as follows: 1) A route pool is employed to preserve the best routes for the population initiation; 2) A specialized best?worst route crossover (BWRC) mode is designed to perform the crossover operators for selecting the best route from Chromosomes 1 to exchange with the worst one in Chromosomes 2, so that the better genes are inherited to the offspring; 3) A route swap mode is used to perform the mutation for improving the convergence speed and preserving the better gene; 4) Local heuristics search methods are applied in this algorithm. Computational study of a practical case shows that the proposed algorithm can decrease the total travel distance by 51.66%, enhance the average vehicle load rate by 37.85%, cut down 15 routes and reduce a deliver vehicle. The convergence speed of HMOEA is faster than that of famous NSGA-II.

Multipath Source Self Repair Routing Algorithm for Mobile Ad Hoc Networks

A multipath source self repair routing (MSSRR) algorithm for mobile ad hoc networks is proposed. By using multiple paths which can be repaired by themselves to transmit packets alternately, the network's load is balanced, the link state in the network can be checked in time, the number of the times the route discovery mechanism starts is decreased. If only one route which will be broken can be used to transmit the packets, the route discovery mechanism is restarted.The algorithm is implemented on the basis of dynamic source routing (DSR). The effect of MSSRR on lifetime of the access from the source to the destination and the overhead is discussed. Compared with the performance of DSR,it can be seen that the algorithm can improve the performance of the network obviously and the overhead almost does not increase if the average hop count is larger.

Congestion aware routing algorithm for delay-disruption tolerance networks

There were many contradictory evaluation criteria to select next-hop in the delay-disruption tolerance networks(DTN).To solve this problem,an attribute hierarchical model was proposed,in which the predefined criteria were summarized as static identity attributes,forwarding desire attributes and delivery capability attributes(IDC).Based on this model,a novel multi-attributes congestion aware routing(MACAR) scheme with uncertain information for next-hop selection was presented,by adopting an decision theory to aggregate attributes with belief structure and computing partial ordering relations.The simulation results show that MACAR presents higher successful delivery rate,lower average delay and effectively alleviate congestion.

A Genetic Algorithm for the Split Delivery Vehicle Routing Problem

The Split Delivery Vehicle Routing Problem (SDVRP) allows customers to be assigned to multiple routes. Two hybrid genetic algorithms are developed for the SDVRP and computational results are given for thirty-two data sets from previous literature. With respect to the total travel distance and computer time, the genetic algorithm compares favorably versus a column generation method and a two-phase method.

A Discrete-Time Traffic and Topology Adaptive Routing Algorithm for LEO Satellite Networks

“Minimizing path delay” is one of the challenges in low Earth orbit (LEO) satellite network routing algo-rithms. Many authors focus on propagation delays with the distance vector but ignore the status information and processing delays of inter-satellite links. For this purpose, a new discrete-time traffic and topology adap-tive routing (DT-TTAR) algorithm is proposed in this paper. This routing algorithm incorporates both inher-ent dynamics of network topology and variations of traffic load in inter-satellite links. The next hop decision is made by the adaptive link cost metric, depending on arrival rates, time slots and locations of source-destination pairs. Through comprehensive analysis, we derive computation formulas of the main per-formance indexes. Meanwhile, the performances are evaluated through a set of simulations, and compared with other static and adaptive routing mechanisms as a reference. The results show that the proposed DT-TTAR algorithm has better performance of end-to-end delay than other algorithms, especially in high traffic areas.

A DISTRIBUTED QOS ROUTING BASED ON ANT ALGORITHM FOR LEO SATELLITE NETWORK

Low Earth Orbit (LEO) satellites provide short round-trip delays and are becoming in- creasingly important. One of the challenges in LEO satellite networks is the development of specialized and efficient routing algorithms. To satisfy the QoS requirements of multimedia applications, satellite routing protocols should consider handovers and minimize their effect on the active connections. A distributed QoS routing scheme based on heuristic ant algorithm is proposed for satisfying delay bound and avoiding link congestion. Simulation results show that the call blocking probabilities of this al- gorithm are less than that of Shortest Path First (SPF) with different delay bound.

Use of genetic algorithm in new approach to modeling of flood routing

The hydrological models and simpli?ed methods of Saint-venant equations are used extensively in hydrological modeling, in particular for the simulation of the ?ood routing. These models require speci?c and extensive data that usually makes the study of ?ood propagation an arduous practice. We present in this work a new model, based on a transfer function, this function is a function of parametric probability density, having a physical meaning with respect to the propagation of a hydrological signal. The inversion of the model is carried out by an optimization technique called Genetic Algorithm. It consists of evolving a population of parameters based primarily on genetic recombination operators and natural selection to?nd the minimum of an objective function that measures the distance between observed and simulated data. The precision of the simulations of the proposed model is compared with the response of the Hayami model and the applicability of the model is tested on a real case, the N'Fis basin river, located in the High Atlas Occidental, which presents elements that appear favorable to the study of the propagation. The results obtained are very satisfactory and the simulation of the proposed model is very close to the response of the Hayami model.

Quality of Service Routing Strategy Using Supervised Genetic Algorithm

A supervised genetic algorithm (SGA) is proposed to solve the quality of service (QoS) routing problems in computer networks. The supervised rules of intelligent concept are introduced into genetic algorithms (GAs) to solve the constraint optimization problem. One of the main characteristics of SGA is its searching space can be limited in feasible regions rather than infeasible regions. The superiority of SGA to other GAs lies in that some supervised search rules in which the information comes from the problems are incorporated into SGA. The simulation results show that SGA improves the ability of searching an optimum solution and accelerates the convergent process up to 20 times.

An Overview and Experimental Study of Learning-Based Optimization Algorithms for the Vehicle Routing Problem

The vehicle routing problem(VRP)is a typical discrete combinatorial optimization problem,and many models and algorithms have been proposed to solve the VRP and its variants.Although existing approaches have contributed significantly to the development of this field,these approaches either are limited in problem size or need manual intervention in choosing parameters.To solve these difficulties,many studies have considered learning-based optimization(LBO)algorithms to solve the VRP.This paper reviews recent advances in this field and divides relevant approaches into end-to-end approaches and step-by-step approaches.We performed a statistical analysis of the reviewed articles from various aspects and designed three experiments to evaluate the performance of four representative LBO algorithms.Finally,we conclude the applicable types of problems for different LBO algorithms and suggest directions in which researchers can improve LBO algorithms.