A heuristic algorithm for shortest path with multiple constraints

Consider a network G=(V,E) with distinguished vertices 1 and n, and with a length function len:E→Z⁺ and a weight function wei: E→Z⁺ on every edge. Two numbers L and W are preset positive integers. The problem, which finds a path from 1 to n such that the length of the path is at most L and the weight of the path is at most W, is NP-complete. Furthermore it is an interesting problem to find a path from 1 to n with length less than L and weight less than W does exist. Two problems are considered in this paper. At first an interactive algorithm is presented for solving the second problem. After the problem is formulated by a biobjective integer programming model in which the length and weight of the path are minimized. A reference point of the objective value considered is introduced in the algorithm and it is generated in each iteration step to adapt to the decision-maker´s information, which compressed the solution space. In the second a heuristic algorithm is put forward for solving two problems and the complete description of the algorithm is given at last. Finally an example demonstrates that the two algorithms are effective.