We propose two new algorithms called BiLAD and ExactBiLAD for the well-known Single-Constrained Shortest Path (SCSP) problem. It is a fundamental problem in quality-of-service (QoS) routing, where one seeks a source-destination path with the least cost satisfying a delay QoS constraint in a network. As pointed out by Jüttner et al., there is no widely accepted algorithm with polynomial time to the SCSP problem because the SCSP problem is NP-hard. The remarkable feature of BiLAD is that it ensures that the length of iteratively updated angle interval is shrunk at least at a constant ratio. With the help of this feature, we prove its polynomial time complexity. To the best of our knowledge, this is the first time that the polynomial time complexity is proved in details. The numerical results show that, in most QoS routing test instances, the performance of BiLAD is close to their primal optimal solutions. The proposed modified Dijkstra procedure, whose complexity is the same as that of the Dijkstra algorithm, also accelerates BiLAD. In the second part of the paper, based on the information obtained by BiLAD, we design an exact algorithm-ExactBiLAD, in which an optimal solution to the SCSP problem is finally obtained by scanning the steadily reduced optimal-path-candidate triangle area. The simulation results indicate that ExactBiLAD needs only a dozen times of executing the modified Dijkstra algorithm regardless of the network size or the average node degree. Distinguished from many other exact algorithms, ExactBiLAD has a satisfactory performance in the practical computation.

Bare-bones Particle Swarm Optimization (BPSO) is a simplified PSO variant, which has shown potential performance on many multimodal optimization problems. However, BPSO is also possible to be trapped into local optima for high-dimensional and complicated optimization problems. In order to enhance the performance of BPSO, this paper presents a modified BPSO, called NMBPSO. It combined the ideas of the traditional PSO and a modified BPSO to improve the capacity of balancing exploration and exploitation during the search process. To verify the effect and benefit of the proposed algorithm, a set of well known benchmark functions are employed and compared against some competitive PSO variants. Experiment results indicate that NMBPSO performs better than the traditional PSO, BPSO and a modified BPSO algorithm.