Abstract
We address the route selection problem for Unmanned Air Vehicles (UAV) under multiple objectives. We consider a general case for this problem, where the UAV has to visit several targets and return to the base. We model this problem as a combination of two combinatorial problems. First, the path to be followed between each pair of targets should be determined. We model this as a multi-objective shortest path problem. Additionally, we need to determine the order of the targets to be visited. We model this as a multi-objective traveling salesperson problem (MOTSP). The overall problem is a combination of these two problems, which we define as a generalized MOTSP. We develop an exact interactive approach to identify the best paths and the best tour of a decision maker under a linear utility function.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Gudaitis, M.S.: Multi criteria mission route planning using a parallel A∗ search. M.S. Thesis, Air Force Institute of Technology (1994)
Olsan, J.B.: Genetic algorithms applied to a mission routing problem. M.S. Thesis, Air Force Institute of Technology (1993)
Yavuz, K.: Mission route planning using particle swarm optimization. M.S. Thesis, Air Force Institute of Technology (2002)
Ehrgott, M.: Multi Objective Optimization. Springer, Berlin (2000)
Gandibleux, X., Beugnies, F., Randriamasy, S.: Martins’ Algorithm revisited for multi-objective shortest path problems with a MaxMin cost function. 4OR 4(1), 47–59 (2006)
Raith, A., Ehrgott, M.: A comparison of solution strategies for biobjective shortest path problems. Comput. Oper. Res. 36(4), 1299–1331 (2009)
Gabrel, V., Vanderpooten, D.: Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an Earth observing satellite. Eur. J. Oper. Res. 139, 533–542 (2002)
Granat, J., Guerriero, F.: The interactive analysis of the multicriteria shortest path problem by the reference point method. Eur. J. Oper. Res. 151, 103–118 (2003)
Karademir, S.: A genetic algorithm for the biobjective traveling salesman problem with profits. M.S. Thesis, Department of Industrial Engineering, Middle East Technical University (2008)
Berube, J.F., Gendreau, M., Potvin, J.Y.: An exact ε-constraint method for bi-objective combinatorial optimization problems–application to the traveling salesman problem with profits. Eur. J. Oper. Res. 194(1), 39–50 (2009)
Özpeynirci, Ö., Köksalan, M.: Multiobjective traveling salesperson problem on Halin graphs. Eur. J. Oper. Res. 196, 155–161 (2009)
Özpeynirci, Ö., Köksalan, M.: Pyramidal tours and multiple objectives. J. Glob. Optim. 48(4), 569–582 (2010)
Ramesh, R., Karwan, M.H., Zionts, S.: An interactive method for bicriteria integer programming. IEEE Trans. Syst. Man Cybern. 20, 395–403 (1990)
Zionts, S.: A multiple criteria method for choosing among discrete alternatives. Eur. J. Oper. Res. 7(1), 143–147 (1981)
Aneja, Y.P., Nair, K.P.K.: Bicriteria transportation problem. Manag. Sci. 25(1), 73–78 (1979)
Cohon, J.L.: Multiobjective programming and planning. Academic Press, New York (1978)
Winston, W.L.: Operations research—applications and algorithms, 4th edn., Brooks/Cole–Thomson, Belmont (2004)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Harold P. Benson.
Rights and permissions
About this article
Cite this article
Tezcaner, D., Köksalan, M. An Interactive Algorithm for Multi-objective Route Planning. J Optim Theory Appl 150, 379–394 (2011). https://doi.org/10.1007/s10957-011-9838-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-011-9838-y
Keywords
- Multi-objective decision making
- Combinatorial optimization
- Interactive method
- Multi-objective shortest path
- Multi-objective traveling salesperson problem
- Unmanned Air Vehicle