On a Time-Dependent Formulation and an Updated Classification of ATSP Formulations
| hal.structure.identifier | Departemento de Matematica [Beja] | |
| dc.contributor.author | GODINHO, Maria Teresa | |
| hal.structure.identifier | Centro de Investigação Operacional [CIO] | |
| dc.contributor.author | GOUVEIA, Luís | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | PESNEAU, Pierre | |
| dc.contributor.editor | Ali Ridha Mahjoub | |
| dc.date.accessioned | 2024-04-04T03:07:47Z | |
| dc.date.available | 2024-04-04T03:07:47Z | |
| dc.date.issued | 2011-10-01 | |
| dc.identifier.isbn | 9781848212060 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193475 | |
| dc.description.abstractEn | In this chapter we contextualize, in terms of the ATSP, a recent compact formulation presented in Godinho et al [11] for the time-dependent traveling salesman problem (TDTSP). The previous paper provides one way of viewing the new model, the time-dependent TSP point of view where it is put in evidence how to obtain the new model by tightening the linear programming relaxation of a well known formulation for the TDTSP. In this chapter, we will present the ATSP point of view and will show how to obtain the model by i) enhancing the subproblem arising in the standard multicommodity ow (MCF) model for the ATSP and then ii) by using modelling enhancement techniques. We will compare the linear programming relaxation of the new formulation with the linear programming relaxation of the three compact and non-dominated formulations presented in Oncan et al. [19]. As a result of this comparison we present an updated classication of formulations for the asymmetric traveling salesman problem (ATSP). | |
| dc.language.iso | en | |
| dc.publisher | Wiley | |
| dc.source.title | Progress in Combinatorial Optimization | |
| dc.title.en | On a Time-Dependent Formulation and an Updated Classification of ATSP Formulations | |
| dc.type | Chapitre d'ouvrage | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.title.proceeding | Progress in Combinatorial Optimization | |
| hal.identifier | hal-00648457 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00648457v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Progress%20in%20Combinatorial%20Optimization&rft.date=2011-10-01&rft.au=GODINHO,%20Maria%20Teresa&GOUVEIA,%20Lu%C3%ADs&PESNEAU,%20Pierre&rft.isbn=9781848212060&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||