×

Two-phase algorithm for solving the preference-based multicriteria optimal path problem with reference points. (English) Zbl 1458.90610

Summary: The shortest path problem arises in several contexts like transportation, telecommunication or data analysis. New requirements in solving practical problems (e.g., efficient content delivery for information-centric networks, urban passenger transport system or social network) impose that more than one criterion should be considered. Since the objectives are in conflict, the solution is not unique, rather a set of (efficient) paths is defined as optimal. The most satisfactory path should be selected considering additional preference information. Generally, computing the entire set of efficient solutions is time consuming. In this paper, we apply the reference point method for finding the best path. In a reference point-based approach, non-additive scalarizing function is applied. In this case, the classical optimality principle for the shortest path problem is not valid. To overcome this issue, we propose an equivalent formulation dealing with the constrained shortest path (CSP) problem. The idea is to define a set of constraints guaranteeing that an optimal solution to the problem at hand lies in the feasible region of the defined CSP problem. We propose a two-phase method where, in the first phase, a bound on the optimal solution is computed and used to define the constraints, whereas, in the second phase a labelling algorithm is applied to search for an optimal solution to the defined CSP problem. The method is tested on instances generated from random and grid networks, considering several scenarios. The computational results show that, on average, the proposed solution strategy is competitive with the state-of-the-art approaches and behaves the best on grid networks.

MSC:

90C35 Programming involving graphs or networks
90C29 Multi-objective and goal programming

Software:

NETGEN
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Antunes, C. H.; Craveirinha, J.; Climaco, J.; Barrico, J., Multiple objective routing in integrated communication networks, (Key, P.; Smith, D., ITC-16 Teletraffic Engineering in a Competitive World (1999), Elsevier: Elsevier North Holland), 1291-1300
[2] Azevedo, J.; Marins, E. Q.V., An algorithm for the multiobjective shortest path problem on acyclic networks, Invest. Oper., 11, 52-69 (1991)
[3] Barndorff-Nielsen, O.; Sobel, M., On the distribution of the number of admissible points in a vector random sample, Theory Probab. Appl., 11, 2, 283-305 (1966) · Zbl 0278.60007
[4] Batta, R.; Chiu, S. S., Optimal obnoxious path on a network: transportation of hazardous materials, Oper. Res., 36, 84-92 (1988)
[5] Beben, A.; Batalla, J. M.; Chai, W. K.; Sliwinski, J., Multi-criteria decision algorithms for efficient content delivery in content networks, Ann. Telecommun., 68, 3-4, 153-165 (2013)
[6] Benson, H., Existence of efficient solutions for vector maximization problems, J. Optim. Theory Appl., 26, 4, 569-580 (1978) · Zbl 0373.90085
[7] Bentley, J. L.; Kung, H. T.; Schkolnick, M.; Thompson, C. D., On the average number of maxima in a set of vectors and applications, J. ACM, 25, 4, 536-543 (1978) · Zbl 0388.68056
[8] Bertsekas, D. P., Network Optimization: Continuous and Discrete Models (1998), Athena Scientific · Zbl 0997.90505
[9] Cherkassky, B.; Goldberg, A.; Radzik, T., Shortest paths algorithms: theory and experimental evaluation, Math. Program., 73, 2, 129-174 (1996) · Zbl 0853.90111
[10] Chinchuluun, Z.; Pardalos, P. M., A survey of recent developments in multiobjective optimization, Ann. Oper. Res., 154, 29-50 (2007) · Zbl 1146.90060
[11] Climaco, J. C.N.; Craveirinha, J. M.F.; Pascoal, M. M.B., A bicriterion approach for routing problem in multimedia network, Networks, 41, 206-220 (2003) · Zbl 1090.90026
[12] Climaco, J. C.N.; Craveirinha, J. M.F.; Pascoal, M. M.B., An automated reference point-like approach for multicriteria shortest path problem, J. Syst. Sci. Syst. Eng., 15, 3, 314-329 (2006)
[13] Climaco, J. C.N.; Martins, E. Q.V., A bicriterion shortest path algorithm, Eur. J. Oper. Res., 11, 4, 399-404 (1982) · Zbl 0488.90068
[14] Coutinho-Rodrigues, J. M.; Climaco, J. C.N.; Current, J. R., A pc-based interactive decision support system fot two objective direct delivery probelms, J. Bus. Logist., 15, 305-322 (1994)
[15] Coutinho-Rodrigues, J. M.; Climaco, J. C.N.; Current, J. R., An interactive bi-objective shortest path approach: searching for unsupported nondominated solutions, Comput. Oper. Res., 26, 8, 789-798 (1999) · Zbl 0932.90005
[16] Current, J. R.; Marsh, M., Multiobjective transportation network design and routing problems: taxonomy and annotation, Eur. J. Oper. Res., 103, 426-438 (1993) · Zbl 0775.90150
[17] Current, J. R.; Min, H., Multiobjective network design of transportation networks: taxonomy and annotation, Eur. J. Oper. Res., 26, 187-201 (1986)
[18] Current, J. R.; Revelle, C. S.; Cohon, J. L., An interactive approach to identify the best compromise solution for two objective shortest path problems, Comput. Oper. Res., 17, 2, 187-198 (1990) · Zbl 0698.90084
[19] Di Puglia Pugliese, L.; Guerriero, F., Dynamic programming approaches to solve the shortest path problem with forbidden paths, Optim. Method Softw., 28, 2, 221-255 (2013) · Zbl 1271.90093
[20] Di Puglia Pugliese, L.; Guerriero, F., Shortest path problem with forbidden paths: the elementary version, Eur. J. Oper. Res., 227, 2, 254-267 (2013) · Zbl 1292.90246
[21] Di Puglia Pugliese, L.; Guerriero, F., A survey of resource constrained shortest path problems: exact solution approaches, Networks, 62, 3, 183-200 (2013) · Zbl 1338.90432
[22] Di Puglia Pugliese, L.; Guerriero, F., On the shortest path problem with negative cost cycles, Comput. Optim. Appl., 63, 2, 559-583 (2016) · Zbl 1339.90323
[23] Dial, R., A model and algorithm for multicriteria route-mode choice, Transport. Res. Part B, 13, 4, 311-316 (1979)
[24] Francisco Javier Pulido, F.; Mandow, L.; Pérez de la Cruz, J., Multiobjective shortest path problems with lexicographic goal-based preferences, Eur. J. Oper. Res., 229, 1, 89-101 (2014) · Zbl 1339.90287
[25] Galand, L.; Perny, P., Search for compromise solutions in multiobjective state space graphs, ECAI 2006: 17th European Conference on Artificial Intelligence, 93-97 (2006)
[26] Galand, L.; Perny, P.; Spanjaard, O., Choquet-based optimisation in multiobjective shortest path and spanning tree problems, Eur. J. Oper. Res., 204, 2, 303-315 (2010) · Zbl 1178.90333
[27] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman San Francisco · Zbl 0411.68039
[28] Geoffrion, A., Proper efficiency and the theory of vector maximization, J. Math. Anal. Appl., 22, 618-630 (1968) · Zbl 0181.22806
[29] Granat, J.; Guerriero, F., The interactive analysis of the multicriteria shortest path problem by the reference point method, Eur. J. Oper. Res., 151, 1, 103-118 (2003) · Zbl 1043.90077
[30] Guerriero, F.; Musmanno, R., Label correcting methods to solve multicriteria shortest path problems, J. Optim. Theory Appl., 111, 3, 589-613 (2001) · Zbl 0984.90050
[31] Hallam, C.; Harrison, K. J.; Ward, J. A., A multiobjective optimal path algorithm, Digit. Signal Process., 11, 2, 133-143 (2001)
[32] Hansen, P., Bicriterion path problem, (Fendel, G.; Gal, T., Multiple Criteria Decision Making Theory and Application (1979), Springer Verlag: Springer Verlag Berlin), 109-127 · Zbl 0444.90098
[33] Henig, M. I., The domination property in multicriteria optimization, J. Math. Anal. Appl., 114, 1, 7-16 (1986) · Zbl 0629.90084
[34] Klingman, D.; Napier, A.; Stutz, J., Netgen: a program for generating large-scale (un)capacitated assignment, transportation, and minimum cost flow network problems, Manage. Sci., 20 (1974) · Zbl 0303.90042
[35] 10.1007/978-3-642-40643-0_1
[36] Mandow, L.; Pérez de la Cruz, J., A heuristic search algorithm with lexicographic goals, Eng. Appl. Artif. Intell., 14, 6, 751-762 (2001)
[37] Martins, E. Q.V.; Santos, J. L.E., An algorithm for the quickest path problem, Oper. Res. Lett., 20, 4, 195-198 (1997) · Zbl 0881.90124
[38] https://doi.org/10.1007/978-3-540-88908-3_2
[39] Miller, J. A.; Ramaswamy, L.; Kochut, K. J.; Fard, A., Research directions for big data graph analytics, Proceedings of the 2015 IEEE International Congress on Big Data, 785-794 (2015), IEEE Computer Society: IEEE Computer Society Washington, DC, USA
[40] Modesti, P.; Sciomachen, A., A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks, Eur. J. Oper. Res., 111, 3, 495-508 (1998) · Zbl 0948.90021
[41] Mote, I.; Murthy, I.; Olson, D. L., A parametric approach to solving bicriterion shortest path problems, Eur. J. Oper. Res., 53, 1, 81-92 (1991) · Zbl 0733.90073
[42] Nembhard, D.; White, C. C.I., A heuristic search approach for solving multiobjective non-order-preserving path selection problems, Syst. Man Cybern. Part A, 29, 5, 450-459 (1999)
[43] Ogryczak, W., On goal programming formulations of the reference point method, J. Oper. Res. Soc, 52, 6, pp.691-698 (2001) · Zbl 1179.90301
[44] Ogryczak, W., On goal programming formulations of the reference point method, J. Oper. Res. Soc., 52, 691-698 (2001) · Zbl 1179.90301
[45] Decision-Aid to Improve Organisational Performance · Zbl 1065.90064
[46] Raith, A.; Ehrgott, M., A comparison of solution strategies for biobjective shortest path problems, Comput. Oper. Res., 36, 1299-1331 (2009) · Zbl 1162.90579
[47] Reinhardt, L.; Pisinger, D., Multi-objective and multi-constrained non-additive shortest path problems, Comput. Oper. Res., 38, 3, 605-616 (2011) · Zbl 1201.90035
[48] Santos, J.; Di Puglia Pugliese, L.; Guerriero, F., A new approach for the multiobjective minimum spanning tree, Comput. Oper. Res., 98, 69-83 (2018) · Zbl 1391.90618
[49] Skriver, A. J.V.; Andersen, K. A., A label correcting approach for solving bicriterion shortest-path problems, Comput. Oper. Res., 27, 6, 507-524 (2000) · Zbl 0955.90144
[50] Tung, C. T.; Chew, K. T., A multicriteria pareto-optimal path algorithm, Eur. J. Oper. Res., 62, 2, 203-209 (1992) · Zbl 0769.90079
[51] Wang, H.; He, S.; Yao, X., Nadir point estimation for many-objective optimization problems based on emphasized critical regions, Soft Comput., 21, 9, 2283-2295 (2017)
[52] Warburton, A., Approximation of pareto optima in multiple objective shortest path problems, Oper. Res., 35, 70-79 (1987) · Zbl 0623.90084
[53] Wierzbicki, A., Basic properties of scalarizing functionals for multiobjective optimization, Math. Oper. Stat. Optim., 8, 55-60 (1977)
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.