A scenario-based shortest path algorithm for optimizing the sequence of choices under uncertainty

Gaspars-Wieloch, H.

doi:10.29119/1641-3466.2018.113.6

Artykuł - szczegóły

Tytuł artykułu

A scenario-based shortest path algorithm for optimizing the sequence of choices under uncertainty

Autorzy

Gaspars-Wieloch H.

Treść / Zawartość

Pełne teksty:

gaspars-wieloch_ZNPSL_OrgZarz_2017_113.pdf

Pobierz

Identyfikatory

DOI

10.29119/1641-3466.2018.113.6

Warianty tytułu

Scenariuszowy algorytm najkrótszej ścieżki do optymalizacji sekwencji decyzji w warunkach niepewności

Języki publikacji

Abstrakty

The paper presents a procedure based on the shortest path problem (SPP) and on scenario planning. The goal of the method is to find the optimal (with respect to a chosen criterion) sequence of choices under uncertainty, i.e. when at least one parameter of the decision problem is not deterministic. In contrast to existing approaches concerning SPP with uncertainty, we assume that the probability of the occurrence of particular events is not known. The decision rule can be successfully applied for instance to innovative or innovation projects (for both reactive and proactive management) and takes into account the decision maker’s attitude towards risk.

Artykuł przedstawia procedurę opartą o zagadnienie najkrótszej ścieżki w grafie (ang. SPP – shortest path problem) i o planowanie scenariuszowe. Celem metody jest znalezienie optymalnej (ze względu na wybrane kryterium) sekwencji decyzji w warunkach niepewności, tj. wówczas, gdy przynajmniej jeden parametr problemu decyzyjnego nie jest deterministyczny. W przeciwieństwie do istniejących podejść dotyczących SPP w warunkach niepewności, przyjmujemy, iż prawdopodobieństwo wystąpienia poszczególnych scenariuszy nie jest znane. Opracowana reguła decyzyjna może z powodzeniem znaleźć zastosowanie przy realizacji projektów innowacyjnych (w przypadku zarządzania zarówno reaktywnego, jak i proaktywnego). Uwzględnia ona nastawienie decydenta do ryzyka.

Słowa kluczowe

shortest path problem sequence of choices innovative projects innovation project uncertainty decision maker attitude towards risk optimization model

zagadnienie najkrótszej drogi w grafie sekwencja decyzji projekt innowacyjny niepewność decydent nastawienie do ryzyka model optymalizacji

Wydawca

Wydawnictwo Politechniki Śląskiej

Czasopismo

Zeszyty Naukowe. Organizacja i Zarządzanie / Politechnika Śląska

Rocznik

2017

Tom

z. 113

Strony

83--95

Opis fizyczny

Bibliogr. 44 poz.

Twórcy

autor

Gaspars-Wieloch H.

Helena.gaspars@ue.poznan.pl

Poznan University of Economics and Business, Faculty of Informatics and Electronic Economy, Department of Operations Research, Poznan

Bibliografia

1. Ahuja R.K, Magnanti T., Orlin J.B.: Network flows. Theory, algorithms, and applications. Prentice Hall, Upper Saddle River, New Jersey 1993.
2. Deng Y., Chen Y., Zhang Y., Mahadevan S.: Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment. “Applied Soft Computing”, Vol. 12, No. 3, p.1231- 1237, 2012.
3. Dubois D., Prade H.: Gradualness, uncertainty and bipolarity: making sense of fuzzy sets. “Fuzzy Sets and Systems”, Vol.192, p.3–24, 2012.
4. Feder T., Motwani R., O’Callaghan L., Olston C., Panigrahy R.: Computing shortest path with uncertainty. “Journal of Algorithms”, Vol. 62, No. 1, p.1-18, 2007.
5. Frank H.: Shortest paths in probability graphs. “Operations Research”, Vol. 17, No. 4, p. 583-599, 1969.
6. Gao Y.: Shortest path problem with uncertain arc lengths. “Computers and Mathematics with Applications”, Vol. 62, No. 6, p.2591-2600, 2011.
7. Gaspars-Wieloch H.: Modifications of the Hurwicz’s decision rules. “Central European Journal of Operations Research”, Vol. 22, No. 4, p. 779–794, 2014.
8. Gaspars-Wieloch H.: A decision rule supported by a forecasting stage based on the decision maker’s coefficient of optimism. “Central European Journal of Operations Research”, Vol. 23, No. 3, p.579–594, 2015a.
9. Gaspars-Wieloch H.: Modifications of the Omega ratio in decision making under uncertainty. “Croatian Operational Research Review”, Vol. 6, No. 1, p.181-194. 2015b.
10. Gaspars-Wieloch H.: Resource allocation under complete uncertainty – case of asymmetric payoffs. “Organization and Management” (Organizacja i Zarzadzanie), Vol. 96, p.247–258, 2016.
11. Gaspars-Wieloch H.: Newsvendor problem under complete uncertainty: a case of innovative products. “Central European Journal of Operations Research”, Vol. 25, No. 3, p.561-585, 2017a.
12. Gaspars-Wieloch H.: Innovative projects scheduling with scenario-based decision project graphs. “Contemporary Issues in Business, Management and Education 2017 – Conference Proceedings”. 2017b. http://dx.doi.org/cbme.2017.078 .
13. Gaspars-Wieloch H.: A decision rule based on goal programming and one-stage models for uncertain multi-criteria mixed decision making and games against nature. “Croatian Operational Research Review”, Vol. 8, No. 1, p.61–75, 2017c.
14. Gaspars-Wieloch H.: Project Net Present Value estimation under uncertainty. “Central European Journal of Operations Research”. 2017d. http://dx.doi.org/10.1007/s10100-017- 0500-0
15. Gaspars-Wieloch H.: The impact of the structure of the payoff matrix on the final decision made under uncertainty. “Asia-Pacific Journal of Operational Research”, Vol. 35, No. 1, 2018. https://doi.org/10.1142/S021759591850001X
16. Hall R.: The fastest path through a network with random time-dependent travel time. “Transportation Science”, Vol. 20, No. 3, p.182-188, 1986.
17. Issac P., Campbell A.M.: Shortest path problem with arc failure scenarios. “EURO Journal on Transportation and Logistics”, p. 1-25, 2015.
18. Iwamura X.J.K.: New models for shortest path problem with fuzzy arc lengths. “Applied Mathematical Modelling”, Vol. 31, No. 2, p.259-269, 2007.
19. Janczura M., Kuchta D.: Proactive and reactive scheduling in practice. “Research Papers of Wroclaw University of Economics”, Vol. 238, p.34-51, 2011.
20. Kaplan S., Barish N.N.: Decision-making allowing for uncertainty of future investment opportunities. “Management Science”, Vol. 13, No. 10, p.569–577, 1967.
21. Karasan O.E., Pinar M.C., Yaman H.: The robust shortest path problem with interval data. Bilkent University, Ankara, Turkey 2001.
22. Klein C.M.: Fuzzy shortest paths. “Fuzzy Sets and Systems”, Vol. 39, No.1, p. 27-41. 1991.
23. Kmietowicz Z.W., Pearman A.D.: Decision theory, linear partial information and statistical dominance. “Omega”, Vol.12, p.391–399. 1984.
24. Knight F. H.: Risk, uncertainty, profit. Hart. Boston MA. Schaffner & Marx. Houghton Mifflin Co. 1921.
25. Kuchta D., Ślusarczyk A.: Application of proactive and reactive project scheduling – case study. “Research Papers of Wroclaw University of Economics”, Vol. 386, p.99-111, 2015.
26. Liu W.: Uncertain programming models for shortest path problem with uncertain arc lengths. “Proceedings of the First International Conference on Uncertainty Theory”. Urumchi, China, Autust 11-19, 2010, pp. 148-153.
27. Merigo J.M.: Decision-making under risk and uncertainty and its application in strategic management. “Journal of Business Economics and Management”, Vol. 2015, No. 1, p. 93–116. 2015.
28. Michnik J.: Scenario planning+MCDA procedure for innovation selection problem. “Foundations of Computing and Decision Sciences”, Vol. 38, No. 3, p. 207-220. 2013.
29. Millet S.M.: Should probabilities be used with scenarios. “Journal of Futures Studies”, Vol. 13, No. 4, p. 61-68. 2009.
30. Mirchandani P.B.: Shortest distance and reliability of probabilistic networks. “Computers and Operations Research”, Vol. 3, No. 4, p. 347-676. 1976.
31. Montemanni R., Gambardella L.M.: The robust shortest path problem with interval data via Benders decomposition. “A Quarterly Journal of Operations Research”, Vol. 3, p. 315- 328. 2005.
32. Okada S.: Fuzzy shortest path problems incorporating interactivity among paths. “Fuzzy Sets and Systems”, Vol. 142, No. 3, p. 335-357. 2004.
33. Pascoal M.M.B., Resende M.: The minmax regret robust shortest path problem in a finite multi-scenario model. “Applied Mathematics and Computation”, Vol. 241, p. 88-111. 2014.
34. Piasecki K. Intuicyjne zbiory rozmyte jako narzędzie finansów behawioralnych [Intuitive fuzzy sets as a tool f behavioral finances]. Edu-Libri. 2016 (in Polish).
35. Pomerol J.C.: Scenario development and practical decision making under uncertainty. “Decision Support Systems“, Vol. 31, No. 2, p. 197–204. 2001.
36. Sheng Y., Gao Y.: Shortest path problem of uncertain random network. “Computers and Industrial Engineering“, Vol. 99, p. 97-105. 2016.
37. Spalek S.: Innovative vs. Innovation Projects in Organisations, [in:] Wszendybył Skulska E. (ed.): Innowacyjność współczesnych organizacji, TNOiK, Toruń, p. 226-237. 2016.
38. Trzaskalik T.: Wprowadzenie do badan operacyjnych z komputerem [Introduction to operations research with computer]. (2nd ed.). Polskie Wydawnictwo Ekonomiczne, Warsaw 2008. (in Polish).
39. Van der Heijden K.: Scenarios: the art of strategic conversation. John Wiley and Sons, Chichester 1996.
40. Von Mises L.: Human action: a treatise on economics. Yale University Press 1949.
41. von Neumann J., Morgenstern O.: Theory of games and economic behavior. Princeton University Press. Princeton. New York 1944.
42. Ward S., Chapman C.: Transforming project risk management into project uncertainty management. “International Journal of Project Management”, Vol. 21, p. 97–105. 2003.
43. Yao J.-S., Lin F.-T.: Fuzzy shortest-path network problems with uncertain edge weights. “Journal of Information Science and Engineering”, Vol. 19, p. 329-351. 2003.
44. Zhou J., Yang F., Wang K.: An inverse shortest path problem on an uncertain graph. “Journal of Networks”, Vol. 9, No. 9, p. 2353-2359. 2014.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-d1c1040d-3bca-4f31-81f7-5144e21100b2