Facets and valid inequalities for the time-dependent travelling salesman problem

dc.creatorMiranda Bront, Juan Jose
dc.creatorMéndez-Díaz, Isabel
dc.creatorZabala, Paula Lorena
dc.date2013-05
dc.identifierhttp://hdl.handle.net/11336/31995
dc.identifierZabala, Paula Lorena; Méndez-Díaz, Isabel; Miranda Bront, Juan Jose; Facets and valid inequalities for the time-dependent travelling salesman problem; Elsevier Science; European Journal of Operational Research; 236; 3; 5-2013; 891-902
dc.identifier0377-2217
dc.identifierCONICET Digital
dc.identifierCONICET
dc.descriptionThe Time-Dependent Travelling Salesman Problem (TDTSP) is a generalization of the traditional TSP where the travel cost between two cities depends on the moment of the day the arc is travelled. In this paper, we focus on the case where the travel time between two cities depends not only on the distance between them, but also on the position of the arc in the tour. We consider two formulations proposed in the literature, we analyze the relationship between them and derive several families of valid inequalities and facets. In addition to their theoretical properties, they prove to be very effective in the context of a Branch and Cut algorithm.
dc.descriptionFil: Miranda Bront, Juan Jose. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.descriptionFil: Méndez-Díaz, Isabel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.descriptionFil: Zabala, Paula Lorena. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.formatapplication/pdf
dc.formatapplication/pdf
dc.formatapplication/pdf
dc.languageeng
dc.publisherElsevier Science
dc.relationinfo:eu-repo/semantics/altIdentifier/doi/10.1016/j.ejor.2013.05.022
dc.relationinfo:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S0377221713004219
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rightshttps://creativecommons.org/licenses/by-nc-nd/2.5/ar/
dc.subjectCombinatorial Optimization
dc.subjectInteger Programming
dc.subjectTime-Dependent Tsp
dc.subjectBranch And Cut
dc.subjecthttps://purl.org/becyt/ford/1.2
dc.subjecthttps://purl.org/becyt/ford/1
dc.titleFacets and valid inequalities for the time-dependent travelling salesman problem
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:ar-repo/semantics/artículo
dc.typeinfo:eu-repo/semantics/publishedVersion


Este ítem pertenece a la siguiente institución