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 sy...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.展开更多
In recent years, QoS multicast routing has continued to be a very important research topic in the areas of networks. This paper presents a heuristic algorithm for the QoS multicast routing (HAQMR). This heuristic algo...In recent years, QoS multicast routing has continued to be a very important research topic in the areas of networks. This paper presents a heuristic algorithm for the QoS multicast routing (HAQMR). This heuristic algorithm deals with delay and bandwidth constraints and has low cost. The HAQMR attempts to significantly reduce the overhead for constructing a multicast tree, the proof for correctness of the HAQMR is given, and the performance of the HAQMR is evaluated by simulations. The study shows that HAQMR provides an available approach to QoS multicast routing.展开更多
An efficient QoS routing algorithm was proposed for multiple constrained path selection. Making use of efficient pruning policy, the algorithm reduces greatly the size of search space and the computing time. Although ...An efficient QoS routing algorithm was proposed for multiple constrained path selection. Making use of efficient pruning policy, the algorithm reduces greatly the size of search space and the computing time. Although the proposed algorithm has exponential time complexity in the worst case, it can get the running results quickly in practical application. When the scale of network increases, the algorithm can efficiently control the size of search space by constraint conditions and prior queue. The results of simulation show that successful request ratio ( r ) of efficient algorithm for multi-constrained optimal path (EAMCOP) is better than that of heuristic algorithm for multi-constrained optimal path (H-MCOP), but average computing time ( t ) of EAMCOP is far less than that of H-MCOP. And it can be seen that the computing time of EAMCOP is only one fourth of that of H-MCOP in Advanced Research Projects Agency Network (ARPANet) topology.展开更多
With the challenge of great growing of transport diversity for the automobile enterprises, the heterogeneous vehicle routing problem with multiple depots, multiple types of finished vehicles and multiple types of tran...With the challenge of great growing of transport diversity for the automobile enterprises, the heterogeneous vehicle routing problem with multiple depots, multiple types of finished vehicles and multiple types of transport vehicles in finished vehicle logistics(HVRPMD) is modelled and solved. A multi-objective optimization model for HVRPMD is presented considering loading constraints to minimize the total cost and minimize the number of transport vehicles. Then a hybrid heuristic algorithm based on genetic algorithm and particle swarm optimization(GA-PSO) is developed. Moreover, a case study is used to evaluate the effectiveness of this algorithm. By comparing the GA-PSO algorithm with the traditional GA algorithm, the simulation results demonstrate the proposed GA-PSO algorithm is able to better support the HVRPMD problem in practice. Contributions of the paper are the modelling and solving of a complex HVRPMD in logistics industry.展开更多
文摘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.
基金National Natural Science Foundation of China(60172035)Natural Science Foundation of Hubei Province(2000J154)
文摘In recent years, QoS multicast routing has continued to be a very important research topic in the areas of networks. This paper presents a heuristic algorithm for the QoS multicast routing (HAQMR). This heuristic algorithm deals with delay and bandwidth constraints and has low cost. The HAQMR attempts to significantly reduce the overhead for constructing a multicast tree, the proof for correctness of the HAQMR is given, and the performance of the HAQMR is evaluated by simulations. The study shows that HAQMR provides an available approach to QoS multicast routing.
文摘An efficient QoS routing algorithm was proposed for multiple constrained path selection. Making use of efficient pruning policy, the algorithm reduces greatly the size of search space and the computing time. Although the proposed algorithm has exponential time complexity in the worst case, it can get the running results quickly in practical application. When the scale of network increases, the algorithm can efficiently control the size of search space by constraint conditions and prior queue. The results of simulation show that successful request ratio ( r ) of efficient algorithm for multi-constrained optimal path (EAMCOP) is better than that of heuristic algorithm for multi-constrained optimal path (H-MCOP), but average computing time ( t ) of EAMCOP is far less than that of H-MCOP. And it can be seen that the computing time of EAMCOP is only one fourth of that of H-MCOP in Advanced Research Projects Agency Network (ARPANet) topology.
基金Supported by the National Natural Science Foundation of China(No.51565036)。
文摘With the challenge of great growing of transport diversity for the automobile enterprises, the heterogeneous vehicle routing problem with multiple depots, multiple types of finished vehicles and multiple types of transport vehicles in finished vehicle logistics(HVRPMD) is modelled and solved. A multi-objective optimization model for HVRPMD is presented considering loading constraints to minimize the total cost and minimize the number of transport vehicles. Then a hybrid heuristic algorithm based on genetic algorithm and particle swarm optimization(GA-PSO) is developed. Moreover, a case study is used to evaluate the effectiveness of this algorithm. By comparing the GA-PSO algorithm with the traditional GA algorithm, the simulation results demonstrate the proposed GA-PSO algorithm is able to better support the HVRPMD problem in practice. Contributions of the paper are the modelling and solving of a complex HVRPMD in logistics industry.
