A bicriterion shortest path algorithm |
| |
Authors: | João Carlos Namorado Climaco Ernesto Queirós Vieira Martins |
| |
Institution: | Departamento de Engenharia Electrotécnica, Universidade de Coimbra, 3000 Coimbra, Portugal;Departamento de Matemática, Universidade de Coimbra, 3000 Commbra, Portugal |
| |
Abstract: | Among the network models, one of the more popular is the so called shortest path problem. This model is used whenever it is intended to minimize a linear function which represents a distance between a predetermined pair of nodes in a given network.Often a single objective function is not sufficient to completely characterize some real-world problems. For instance, in a road network two parameters - as cost and time - can be assigned to each arc. Clearly the fastest path may be too costly. Nevertheless the decision-maker must choose one solution, possibly not the best for both criteria.In this paper we present an algorithm for this problem. With this algorithm a special set of paths (the set of Pareto optimal paths) is determined. One objective for any Pareto optimal path can not be improved without worsening the other one. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|