×

An aggregate label setting policy for the multi-objective shortest path problem. (English) Zbl 1206.90161

Summary: We consider label setting algorithms for the multi-objective shortest path problem with any number of sum and bottleneck objectives. We propose a weighted sum aggregate ordering of the labels, specifically tailored to combine sum and bottleneck objectives. We show that the aggregate order leads to a consistent reduction of solution times (up to two-thirds) with respect to the classical lexicographic order.

MSC:

90C29 Multi-objective and goal programming
90C35 Programming involving graphs or networks
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Erkut, E., Editorial: Introduction to the special issue, Computers & Operations Research, 34, 1241-1242 (2007)
[2] 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) · Zbl 1125.90405
[3] Guerriero, F.; Musmanno, R., Label correcting methods to solve multicriteria shortest path problems, Journal of Optimization Theory and Applications, 111, 589-613 (2001) · Zbl 0984.90050
[4] Hansen, P., Bicriterion path problems, (Fandel, G.; Gal, T., Multiple Criteria Decision Making Theory and Application. Multiple Criteria Decision Making Theory and Application, Lecture Notes in Economics and Mathematical Systems, vol. 177 (1980), Springer), 109-127
[5] Jozefowiez, N.; Semet, F.; Talbi, E.-G., Multi-objective vehicle routing problems, European Journal of Operational Research, 189, 293-309 (2008) · Zbl 1148.90338
[6] de Lima Pinto, L.; Bornstein, C. T.; Maculan, N., The tricriterion shortest path problem with at least two bottleneck objective functions, European Journal of Operational Research, 198, 387-391 (2009) · Zbl 1163.90794
[7] de Lima Pinto, L.; Pascoal, M. M.B., On algorithms for the tricriteria shortest path problem with two bottleneck objective functions, Computers & Operations Research, 37, 1774-1779 (2010) · Zbl 1188.90246
[8] Martins, E. Q.V., On a multicriteria shortest path problem, European Journal of Operational Research, 16, 236-245 (1984) · Zbl 0533.90090
[9] Martins, E. Q.V., On a special class of bicriterion path problems, European Journal of Operational Research, 17, 85-94 (1984) · Zbl 0538.90086
[10] J.P. Paixão, J.L. Santos, Labelling methods for the general case of the multiobjective shortest path problem-a computational study. Technical Report 7-2009, Centro de InvestigaçÃo Operacional, University of Coimbra, (2009); J.P. Paixão, J.L. Santos, Labelling methods for the general case of the multiobjective shortest path problem-a computational study. Technical Report 7-2009, Centro de InvestigaçÃo Operacional, University of Coimbra, (2009)
[11] Raith, A.; Ehrgott, M., A comparison of solution strategies for biobjective shortest path problems, Computers & Operations Research, 36, 1299-1331 (2009) · Zbl 1162.90579
[12] Sastry, V. N.; Janakiraman, T. N.; Ismail Mohideen, I., New polynomial time algorithms to compute a set of pareto optimal paths for multi-objective shortest path problems, International Journal of Computer Mathematics, 82, 289-300 (2005) · Zbl 1079.90146
[13] Skriver, A. J.V., A classification of bicriterion shortest path (bsp) algorithms, Asia Pacific Journal of Operational Research, 17, 192-212 (2000) · Zbl 1042.90633
[14] Tung, C. T.; Chew, K. L., A multicriteria pareto-optimal path algorithm, European Journal of Operational Research, 62, 203-209 (1992) · Zbl 0769.90079
[15] Vincke, P., Problèmes multicritères, Cahiers du Centre d’Études de Recherche Operationnelle, 16, 425-439 (1974) · Zbl 0305.90045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.