A branch-and-price algorithm for the Minimum Latency Problem
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | SADYKOV, Ruslan | |
| hal.structure.identifier | Instituto de Computação [Niteroi-Rio de Janeiro] [IC-UFF] | |
| dc.contributor.author | BULHOES, Teobaldo | |
| hal.structure.identifier | Universidade Federal Fluminense [Rio de Janeiro] [UFF] | |
| dc.contributor.author | UCHOA, Eduardo | |
| dc.date.accessioned | 2024-04-04T03:07:32Z | |
| dc.date.available | 2024-04-04T03:07:32Z | |
| dc.date.issued | 2018-05 | |
| dc.identifier.issn | 0305-0548 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193454 | |
| dc.description.abstractEn | This paper deals with the Minimum Latency Problem (MLP), a variant of the well-known Travel- ing Salesman Problem in which the objective is to minimize the sum of waiting times of customers. This problem arises in many applications where customer satisfaction is more important than the total time spent by the server. This paper presents a novel branch-and-price algorithm for MLP that strongly relies on new features for the ng-path relaxation, namely: (1) a new labeling algo- rithm with an enhanced dominance rule named multiple partial label dominance; (2) a generalized definition of ng-sets in terms of arcs, instead of nodes; and (3) a strategy for decreasing ng-set size when those sets are being dynamically chosen. Also, other elements of efficient exact algorithms for vehicle routing problems are incorporated into our method, such as reduced cost fixing, dual stabilization, route enumeration and strong branching. Computational experiments over TSPLIB instances are reported, showing that several instances not solved by the current state-of-the-art method can now be solved. | |
| dc.language.iso | en | |
| dc.publisher | Elsevier | |
| dc.subject.en | Minimum latency | |
| dc.subject.en | ng-paths | |
| dc.subject.en | Branch-and-price | |
| dc.title.en | A branch-and-price algorithm for the Minimum Latency Problem | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1016/j.cor.2018.01.016 | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.journal | Computers and Operations Research | |
| bordeaux.page | 66-78 | |
| bordeaux.volume | 93 | |
| 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.peerReviewed | oui | |
| hal.identifier | hal-01664835 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01664835v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Computers%20and%20Operations%20Research&rft.date=2018-05&rft.volume=93&rft.spage=66-78&rft.epage=66-78&rft.eissn=0305-0548&rft.issn=0305-0548&rft.au=SADYKOV,%20Ruslan&BULHOES,%20Teobaldo&UCHOA,%20Eduardo&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||