- -

An Exact Algorithm for the Shortest Path Problem With Position-Based Learning Effects

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

An Exact Algorithm for the Shortest Path Problem With Position-Based Learning Effects

Show simple item record

Files in this item

dc.contributor.author Wang, Yamin es_ES
dc.contributor.author Li, Xiaoping es_ES
dc.contributor.author Ruiz García, Rubén es_ES
dc.date.accessioned 2020-10-17T03:32:44Z
dc.date.available 2020-10-17T03:32:44Z
dc.date.issued 2017-11 es_ES
dc.identifier.issn 1083-4427 es_ES
dc.identifier.uri http://hdl.handle.net/10251/152276
dc.description.abstract [EN] The shortest path problems (SPPs) with learning effects (SPLEs) have many potential and interesting applications. However, at the same time they are very complex and have not been studied much in the literature. In this paper, we show that learning effects make SPLEs completely different from SPPs. An adapted A* (AA*) is proposed for the SPLE problem under study. Though global optimality implies local optimality in SPPs, it is not the case for SPLEs. As all subpaths of potential shortest solution paths need to be stored during the search process, a search graph is adopted by AA* rather than a search tree used by A*. Admissibility of AA* is proven. Monotonicity and consistency of the heuristic functions of AA* are redefined and the corresponding properties are analyzed. Consistency/monotonicity relationships between the heuristic functions of AA* and those of A* are explored. Their impacts on efficiency of searching procedures are theoretically analyzed and experimentally evaluated. es_ES
dc.description.sponsorship This work was supported in part by the National Natural Science Foundation of China under Grant 61572127 and Grant 61272377, and in part by the Specialized Research Fund for the Doctoral Program of Higher Education under Grant 20120092110027. The work of R. Ruiz was supported in part by the Spanish Ministry of Economy and Competitiveness under Project "RESULT-Realistic Extended Scheduling Using Light Techniques" under Grant DPI2012-36243-C02-01, and in part by the FEDER. es_ES
dc.language Inglés es_ES
dc.publisher Institute of Electrical and Electronics Engineers es_ES
dc.relation NSFC/61572127 es_ES
dc.relation NSFC/61272377 es_ES
dc.relation MOE/20120092110027 es_ES
dc.relation MINECO/DPI2012-36243-C02-01 es_ES
dc.relation.ispartof IEEE Transactions on Systems Man and Cybernetics - Part A Systems and Humans es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject A* search es_ES
dc.subject Admissibility es_ES
dc.subject Learning effect es_ES
dc.subject Shortest path es_ES
dc.subject.classification ESTADISTICA E INVESTIGACION OPERATIVA es_ES
dc.title An Exact Algorithm for the Shortest Path Problem With Position-Based Learning Effects es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1109/TSMC.2016.2560418 es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Estadística e Investigación Operativa Aplicadas y Calidad - Departament d'Estadística i Investigació Operativa Aplicades i Qualitat es_ES
dc.description.bibliographicCitation Wang, Y.; Li, X.; Ruiz García, R. (2017). An Exact Algorithm for the Shortest Path Problem With Position-Based Learning Effects. IEEE Transactions on Systems Man and Cybernetics - Part A Systems and Humans. 47(11):3037-3049. https://doi.org/10.1109/TSMC.2016.2560418 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1109/TSMC.2016.2560418 es_ES
dc.description.upvformatpinicio 3037 es_ES
dc.description.upvformatpfin 3049 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 47 es_ES
dc.description.issue 11 es_ES
dc.relation.pasarela 353565 es_ES
dc.contributor.funder European Regional Development Fund es_ES
dc.contributor.funder Ministerio de Economía y Competitividad es_ES
dc.contributor.funder National Natural Science Foundation of China es_ES
dc.contributor.funder Ministry of Education of the People's Republic of China es_ES


This item appears in the following Collection(s)

Show simple item record