Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

The 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. © 2013 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Facets and valid inequalities for the time-dependent travelling salesman problem
Autor:Miranda-Bront, J.J.; Méndez-Díaz, I.; Zabala, P.
Filiación:Departamento de Computación, FCEyN, Universidad de Buenos Aires, Pabellón I, Ciudad Universitaria, C1428EGA, CABA, Argentina
Consejo Nacional de Investigaciones Científicas y Técnicas, Argentina
Palabras clave:Branch and Cut; Combinatorial optimization; Integer programming; Time-Dependent TSP; Combinatorial optimization; Integer programming; Linear programming; Branch and cut; Branch-and-cut algorithms; Time-Dependent TSP; Travel costs; Travelling salesman problem; Valid inequality; Traveling salesman problem
Año:2014
Volumen:236
Número:3
Página de inicio:891
Página de fin:902
DOI: http://dx.doi.org/10.1016/j.ejor.2013.05.022
Título revista:European Journal of Operational Research
Título revista abreviado:Eur J Oper Res
ISSN:03772217
CODEN:EJORD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03772217_v236_n3_p891_MirandaBront

Referencias:

  • Abeledo, H., Fukasawa, R., Pessoa, A., Uchoa, E., The time dependent traveling salesman problem: Polyhedra and branch-cut-and-price algorithm (2010) Experimental Algorithms, 6049, pp. 202-213. , P. Festa, Lecture Notes in Computer Science Springer Berlin/Heidelberg
  • Balas, E., Fischetti, M., Lifted cycle inequalities for the asymmetric traveling salesman problem (1999) Mathematics of Operations Research, 24, pp. 273-292
  • Balas, E., Oosten, M., On the dimension of projected polyhedra (1998) Discrete Applied Mathematics, 87, pp. 1-9
  • Bigras, L., Gamache, M., Savard, G., The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times (2008) Discrete Optimization, 5, pp. 685-699
  • Fischetti, M., Laporte, G., Martello, S., The delivery man problem and cumulative matroids (1993) Operations Research, 41, pp. 1055-1064
  • Fox, K., (1973) Production Scheduling on Parallel Lines with Dependencies, , Ph.D. Thesis, John Hopkins University
  • Fox, K.R., Gavish, B., Graves, S.C., An n-constraint formulation of the (time-dependent) traveling salesman problem (1980) Operations Research, 28, pp. 1018-1021
  • Godinho, M.T., Gouveia, L., Pesneau, P., Natural and extended formulations for the time-dependent traveling salesman problem (2011) Discrete Applied Mathematics
  • Gouveia, L., Voss, S., A classification of formulations for the (time-dependent) traveling salesman problem (1995) European Journal of Operational Research, 83, pp. 69-82
  • Gutin, G., Punnen, A., (2002) The Traveling Salesman Problem and Its Variations, , Combinatorial Optimization Kluwer Academic Publishers
  • Letchford, A.N., Eglese, R.W., Lysgaard, J., Multistars, partial multistars and the capacitated vehicle routing problem (2002) Mathematical Programming, 94, pp. 21-40
  • Lin, S., Computer solutions of the traveling salesman problem (1965) Bell System Technical Journal, 44, pp. 2245-2269
  • Lucena, A., Time-dependent traveling salesman problem - The deliveryman case (1990) Networks, 20, pp. 753-763
  • Lysgaard, J., Letchford, A.N., Eglese, R.W., A new branch-and-cut algorithm for the capacitated vehicle routing problem (2004) Mathematical Programming, 100, pp. 423-445
  • Méndez-Díaz, I., Zabala, P., Lucena, A., A new formulation for the traveling deliveryman problem (2008) Discrete Applied Mathematics, 156, pp. 3223-3237
  • Müller, M.C., (1996) Das Dynamische Travelling Salesman Problem. Master's Thesis, , Universität Kaiserslautern, Fachbereich Mathematik
  • Picard, J., Queyranne, M., The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling (1978) Operations Research, 26, pp. 86-110
  • Rubin, P.A., Ragatz, G.L., Scheduling in a sequence dependent setup environment with genetic search (1995) Computers & or, 22, pp. 85-99
  • Vander Wiel, R.J., Sahinidis, N.V., Heuristic bounds and test problem generation for the time-dependent traveling salesman problem (1995) Transportation Science, 29, pp. 167-183
  • Vander Wiel, R.J., Sahinidis, N.V., An exact solution approach for the time-dependent traveling-salesman problem (1996) Naval Research Logistics, 43, pp. 797-820
  • Van Eijl, C.A., (1995) A Polyhedral Approach to the Delivery Man Problem, , Memorandum COSOR 95-19, Eindhoven University of Technology

Citas:

---------- APA ----------
Miranda-Bront, J.J., Méndez-Díaz, I. & Zabala, P. (2014) . Facets and valid inequalities for the time-dependent travelling salesman problem. European Journal of Operational Research, 236(3), 891-902.
http://dx.doi.org/10.1016/j.ejor.2013.05.022
---------- CHICAGO ----------
Miranda-Bront, J.J., Méndez-Díaz, I., Zabala, P. "Facets and valid inequalities for the time-dependent travelling salesman problem" . European Journal of Operational Research 236, no. 3 (2014) : 891-902.
http://dx.doi.org/10.1016/j.ejor.2013.05.022
---------- MLA ----------
Miranda-Bront, J.J., Méndez-Díaz, I., Zabala, P. "Facets and valid inequalities for the time-dependent travelling salesman problem" . European Journal of Operational Research, vol. 236, no. 3, 2014, pp. 891-902.
http://dx.doi.org/10.1016/j.ejor.2013.05.022
---------- VANCOUVER ----------
Miranda-Bront, J.J., Méndez-Díaz, I., Zabala, P. Facets and valid inequalities for the time-dependent travelling salesman problem. Eur J Oper Res. 2014;236(3):891-902.
http://dx.doi.org/10.1016/j.ejor.2013.05.022