An adaptive amoeba algorithm for constrained shortest paths

• The classical amoeba model is extended to solve the shortest path problem in directed networks.
• The amoeba algorithm is incorporated with Lagrangian relaxation method to solve the constrained shortest path problem.
• Two examples are used to demonstrate the efficiency of the proposed method.

The constrained shortest path problem (CSP) is one of the basic network optimization problems, which plays an important part in real applications. In this paper, an adaptive amoeba algorithm is combined with the Lagrangian relaxation algorithm to solve the CSP problem. The proposed method is divided into two steps: (1) the adaptive amoeba algorithm is modified to solve the shortest path problem (SPP) in a directed network; (2) the modified adaptive amoeba algorithm is combined with the Lagrangian relaxation method to solve the CSP problem. In addition, the evolving processes of the adaptive amoeba model have been detailed in the paper. Two examples are used to illustrate the efficiency of the proposed method. The results show that the proposed method can deal with the CSP problem effectively.