Navegar

Colección

Datos Estadísticas

Artículo

Aprea, M.; Feuerstein, E.; Sadovoy, G.; De Loma, A.S. "Discrete online TSP" (2009) 5th International Conference on Algorithmic Aspects in Information and Management, AAIM 2009. 5564 LNCS:29-42
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

In this paper we introduce a discrete version of the online traveling salesman problem (DOLTSP). We represent the metric space using a weighted graph, where the server is allowed to modify its route only at the vertices. This limitation directly affects the capacity of the server to react and increases the risk related to each decision. We prove lower bounds on the performance of deterministic online algorithms in different scenarios of DOLTSP, and we present distinct algorithms for the problem, some of them achieving the best possible performance. We measure the performance of the algorithms using competitive analysis, the most widely accepted method for evaluating online algorithms. Besides, we perform an empirical simulation on paths, generating a significant set of instances and measuring the quality of the solutions given by each algorithm. Our experiments show that algorithms with the best competitive ratio do not have the best performance in practice. © 2009 Springer Berlin Heidelberg.

Registro:

Documento: Artículo
Título:Discrete online TSP
Autor:Aprea, M.; Feuerstein, E.; Sadovoy, G.; De Loma, A.S.
Ciudad:San Francisco, CA
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellón I, (1428) Capital Federal, Argentina
Palabras clave:Discrete metric spaces; Online algorithms; TSP; Competitive analysis; Competitive ratio; Deterministic online algorithms; Discrete metric spaces; Empirical simulations; Lower bounds; Metric spaces; Online algorithms; TSP; Weighted graph; Control theory; Risk perception; Set theory; Topology; Traveling salesman problem; Algorithms
Año:2009
Volumen:5564 LNCS
Página de inicio:29
Página de fin:42
DOI: http://dx.doi.org/10.1007/978-3-642-02158-9_5
Título revista:5th International Conference on Algorithmic Aspects in Information and Management, AAIM 2009
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v5564LNCS_n_p29_Aprea

Referencias:

  • de Paepe, W.E., (2002) Complexity Results and Competitive Analysis for Vehicle Routing Problems, , PhD thesis, Technische Universiteit Eindhoven
  • Deif, I., Bodin, L., Extension of the Clarke and Wright algorithm for solving the vehicle routing problem with backhauling (1984) Babson Conference on Software Uses in Transportation and Logistics Management, Babson Park, , MA
  • Savelsbergh, M.W.P., Local search in routing problems with time windows (1985) Annals of Operations Research, 4 (1-4), pp. 285-305
  • Stein, D., An asymptotic, probabilistic analysis of a routing problem (1978) Mathematics of Operations Research, 3 (2), pp. 89-101
  • Borodin, A., El-Yaniv, R., (1998) Online Computation and Competitive Analysis, , Cambridge University Press, Cambridge
  • Fiat, A., Woeginger, G.J., Online Algorithms: The State of the Art (1998) LNCS, 1442. , Springer, Heidelberg
  • Ascheuer, N., Krumke, S.O., Rambau, J., Online dial-a-ride problems: Minimizing the completion time (2000) LNCS, 1770, pp. 639-650. , Reichel, H, Tison, S, eds, STACS 2000, Springer, Heidelberg
  • Ausiello, G., Bonifaci, V., Laura, L., The on-line asymmetric traveling salesman problem (2008) Journal of Discrete Algorithms, 6 (2), pp. 290-298
  • Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M., Algorithms for the on-line travelling salesman (2001) Algorithmica, 29 (4), pp. 560-581
  • Blom, M., Krumke, S.O., de Paepe, W., Stougie, L., The online-TSP against fair adversaries (2001) INFORMS Journal on Computing, 13 (2), pp. 138-148
  • Lipmann, M., (2003) On-line Routing, , PhD thesis, Technische Universiteit Eindhoven
  • Psaraftis, H.N., Solomon, M.M., Magnanti, T.L., Kim, T.U., Routing and scheduling on a shoreline with release times (1990) Management Science, 36 (2), pp. 212-223
  • Sleator, D.D., Tarjan, R.E., Amortized effciency of list update and paging rules (1985) Communications of ACM, 28, pp. 202-208
  • Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D., Competitive snoopy caching (1988) Algorithmica, 3, pp. 79-119
  • Koutsoupias, E., Papadimitriou, C.H., Beyond competitive analysis (2000) SIAM Journal on Computing, 30 (1), pp. 300-317

Citas:

---------- APA ----------
Aprea, M., Feuerstein, E., Sadovoy, G. & De Loma, A.S. (2009) . Discrete online TSP. 5th International Conference on Algorithmic Aspects in Information and Management, AAIM 2009, 5564 LNCS, 29-42.
http://dx.doi.org/10.1007/978-3-642-02158-9_5
---------- CHICAGO ----------
Aprea, M., Feuerstein, E., Sadovoy, G., De Loma, A.S. "Discrete online TSP" . 5th International Conference on Algorithmic Aspects in Information and Management, AAIM 2009 5564 LNCS (2009) : 29-42.
http://dx.doi.org/10.1007/978-3-642-02158-9_5
---------- MLA ----------
Aprea, M., Feuerstein, E., Sadovoy, G., De Loma, A.S. "Discrete online TSP" . 5th International Conference on Algorithmic Aspects in Information and Management, AAIM 2009, vol. 5564 LNCS, 2009, pp. 29-42.
http://dx.doi.org/10.1007/978-3-642-02158-9_5
---------- VANCOUVER ----------
Aprea, M., Feuerstein, E., Sadovoy, G., De Loma, A.S. Discrete online TSP. Lect. Notes Comput. Sci. 2009;5564 LNCS:29-42.
http://dx.doi.org/10.1007/978-3-642-02158-9_5