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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
Received: February 2005 / Revised version: June 2005
AMS classification:
90C29, 90C27, 05C38, 90B18, 68M12
Rights and permissions
About this article
Cite this article
Gandibleux, X., Beugnies, F. & Randriamasy, S. Martins' algorithm revisited for multi-objective shortest path problems with a MaxMin cost function. 4OR 4, 47–59 (2006). https://doi.org/10.1007/s10288-005-0074-x
Issue Date:
DOI: https://doi.org/10.1007/s10288-005-0074-x