Mostrar el registro sencillo del ítem

Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem

hal.structure.identifierDepartemento de Matematica [Beja]
dc.contributor.authorGODINHO, Maria Teresa
hal.structure.identifierCentro de Investigação Operacional [CIO]
dc.contributor.authorGOUVEIA, Luís
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorPESNEAU, Pierre
dc.date.accessioned2024-04-04T03:07:47Z
dc.date.available2024-04-04T03:07:47Z
dc.date.issued2014
dc.identifier.issn0166-218X
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/193476
dc.description.abstractEnIn this paper we present a new formulation for the Time-Dependent Travelling Salesman Problem (TDTSP). We start by reviewing well known natural formulations with some emphasis on the formulation by Picard and Queyranne (1978). The main feature of this formulation is that it uses, as a subproblem, an exact description of the n-circuit problem. Then, we present a new formulation that uses more variables and is based on using, for each node, a stronger subproblem, namely a n-circuit subproblem with the additional constraint that the corresponding node is not repeated in the circuit. Although the new model has more variables and constraints than the original PQ model, the results given from our computational experiments show that the linear programming relaxation of the new model gives, for many of the instances tested, gaps that are close to zero. Thus, the new model is worth investigating for solving TDTSP instances. We have also provided a complete characterization of the feasible set of the corresponding linear programming relaxation in the space of the variables of the PQ model. This characterization permits us to suggest alternative methods of using the proposed formulations.
dc.language.isoen
dc.publisherElsevier
dc.title.enNatural and Extended formulations for the Time-Dependent Traveling Salesman Problem
dc.typeArticle de revue
dc.identifier.doi10.1016/j.dam.2011.11.019
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalDiscrete Applied Mathematics
bordeaux.page138-153
bordeaux.volume164
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00648451
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00648451v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Discrete%20Applied%20Mathematics&rft.date=2014&rft.volume=164&rft.spage=138-153&rft.epage=138-153&rft.eissn=0166-218X&rft.issn=0166-218X&rft.au=GODINHO,%20Maria%20Teresa&GOUVEIA,%20Lu%C3%ADs&PESNEAU,%20Pierre&rft.genre=article


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem