Name
Title | ||
|---|---|---|
Martins' algorithm revisited for multi-objective shortest path problems with a MaxMin cost function |
Abstract | ||
|---|---|---|
. This paper presents a direct extension of the label setting algorithm proposed by Martins in 1984 for the shortest path problem
with multiple objectives. This extended version computes all the efficient paths from a given source vertex, to all the other
vertices of the network. The algorithm copes with problems in which the "cost values" associated with the network arcs are
positive. The proposed extension can handle objective functions that are either of the "sum" type or of the "bottleneck" type.
The main modifications to Martins' algorithm for multi-objective shortest path problems are linked to the dominance test and
the procedure for identifying efficient paths. The algorithmic features are described and a didactic example is provided to
illustrate the working principle. The results of numerical experiments concerning the number of efficient solutions produced
and the CPU time consumed for several configurations of objectives, on a set of randomly generated networks, are also provided. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/s10288-005-0074-x | A Quarterly Journal of Operations Research |
Keywords | DocType | Volume |
shortest path problem,multi-objective combinatorial optimization,labelling algorithm.,objective function,cost function,combinatorial optimization | Journal | 4 |
Issue | Citations | PageRank |
1 | 14 | 0.87 |
References | Authors | |
2 | 9 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xavier Gandibleux | 1 | 436 | 32.53 |
| recherche operationnelle et informatique | 2 | 28 | 1.73 |
| recherche operationnelle et informatique | 3 | 28 | 1.73 |
| sabine randriamasy | 4 | 15 | 1.27 |
| universite de | 5 | 14 | 0.87 |
| valenciennes et | 6 | 14 | 0.87 |
| du hainautcambresis | 7 | 14 | 0.87 |
| g xavier | 8 | 14 | 0.87 |
| r sabine | 9 | 14 | 1.54 |