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:

Congestion in large cities and populated areas is one of the major challenges in urban logistics, and should be addressed at different planning and operational levels. The Time Dependent Travelling Salesman Problem (TDTSP) is a generalization of the well known Traveling Salesman Problem (TSP) where the travel times are not assumed to be constant along the day. The motivation to consider the time dependency factor is that it enables to have better approximations to many problems arising from practice. In this paper, we consider the Time-Dependent Traveling Salesman Problem with Time Windows (TDTSP-TW), where the time dependence is captured by considering variable average travel speeds. We propose an Integer Linear Programming model for the problem and develop an exact algorithm, which is compared on benchmark instances with another approach from the related literature. The results show that the approach is able to solve instances with up to 40 customers. © 2017 Elsevier Ltd

Registro:

Documento: Artículo
Título:An integer programming approach for the time-dependent traveling salesman problem with time windows
Autor:Montero, A.; Méndez-Díaz, I.; Miranda-Bront, J.J.
Filiación:Departamento de Computación, FCEyN, Universidad de Buenos Aires, Pabellón I, Ciudad Universitaria, C1428EGA, CABA, Argentina
Universidad Torcuato Di Tella, Av. Figueroa Alcorta 7350, C1428BCW, CABA, Argentina
Consejo Nacional de Investigaciones Científicas y Técnicas, Argentina
CONICET-Universidad de Buenos Aires. Instituto de Investigación en Ciencias de la Computación (ICC), Buenos Aires, Argentina
Palabras clave:Branch-and-Cut; Integer linear programming; Time windows; Time-dependent TSP; Benchmarking; Integer programming; Branch and cut; Integer Linear Programming; Integer linear programming models; Operational level; Time dependent; Time windows; Time-dependent traveling salesman; Travelling salesman problem; Traveling salesman problem
Año:2017
Volumen:88
Página de inicio:280
Página de fin:289
DOI: http://dx.doi.org/10.1016/j.cor.2017.06.026
Título revista:Computers and Operations Research
Título revista abreviado:Comp. Oper. Res.
ISSN:03050548
CODEN:CMORA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03050548_v88_n_p280_Montero

Referencias:

  • Abeledo, H., Fukasawa, R., Pessoa, A., Uchoa, E., The time dependent traveling salesman problem: polyhedra and algorithm (2012) Math. Programm. Comput., 5 (1), pp. 27-55
  • Albiach, J., Sanchis, J.M., Soler, D., An asymmetric tsp with time windows and with time-dependent travel times and costs: an exact solution through a graph transformation (2008) Eur. J. Oper. Res., 189 (3), pp. 789-802. , http://dx.doi.org/10.1016/j.ejor.2006.09.099
  • Arigliano, A., Ghiani, G., Grieco, A., Guerriero, E., Time Dependent Traveling Salesman Problem with Time Windows: Properties and an Exact Algorithm (2015) Technical Report
  • Ascheuer, N., Fischetti, M., Grötschel, M., Solving the asymmetric travelling salesman problem with time windows by branch-and-cut (2001) Math. Program., 90 (3), pp. 475-506
  • Balas, E., Fischetti, M., Pulleyblank, W.R., The precedence-constrained asymmetric traveling salesman polytope (1995) Math. Program., 68, pp. 241-265
  • Cordeau, J.-F., Ghiani, G., Guerriero, E., Analysis and branch-and-cut algorithm for the time-dependent travelling salesman problem (2012) Transp. Sci., 48 (1), pp. 46-58
  • Dabia, S., Ropke, S., van Woensel, T., De Kok, T., Branch and price for the time-dependent vehicle routing problem with time windows (2013) Transp. Sci., 47 (3), pp. 380-396
  • Dash, S., Günlük, O., Lodi, A., Tramontani, A., A time bucket formulation for the traveling salesman problem with time windows (2012) INFORMS J. Comput., 24 (1), pp. 132-147
  • Fischetti, M., Laporte, G., Martello, S., The delivery man problem and cumulative matroids (1993) Oper. Res., 41 (6), pp. 1055-1064
  • Furini, F., Kidd, M.P., Persiani, C.A., Toth, P., Improved rolling horizon approaches to the aircraft sequencing problem (2015) J. Scheduling, 18 (5), pp. 435-447
  • Gendreau, M., Ghiani, G., Guerriero, E., Time-dependent routing problems: a review (2015) Comput. Oper. Res., 64, pp. 189-197
  • Ghiani, G., Guerriero, E., A note on the ichoua, gendreau, and potvin (2003) travel time model (2014) Transp. Sci., 48 (3), pp. 458-462
  • Godinho, M.T., Gouveia, L., Pesneau, P., Natural and extended formulations for the time-Dependent traveling salesman problem (2014) Discrete Appl. Math., 164, pp. 138-153
  • Gouveia, L., Voß, S., A classification of formulations for the (time-dependent) traveling salesman problem (1995) Eur. J. Oper. Res., 2217 (93)
  • Hill, A.V., Benton, W., Modelling intra-city time-dependent travel speeds for vehicle scheduling problems (1992) J. Oper. Res. Soc., pp. 343-351
  • Ichoua, S., Gendreau, M., Potvin, J.-Y., Vehicle dispatching with time-dependent travel times (2003) Eur. J. Oper. Res., 144 (2), pp. 379-396
  • Lucena, A., Time-dependent traveling salesman problem—the deliveryman case (1990) Networks, 20 (6), pp. 753-763
  • Malandraki, C., Daskin, M.S., Time dependent vehicle routing problems: formulations, properties and heuristic algorithms (1992) Transp. Sci., 26 (3), pp. 185-200
  • Melgarejo, P.A., Laborie, P., Solnon, C., A time-dependent no-overlap constraint: application to urban delivery problems (2015) Integration of AI and OR Techniques in Constraint Programming, pp. 1-17. , Springer
  • Méndez-Dıaz, I., Miranda-Bront, J., Toth, P., Zabala, P., Infeasible path formulations for the time-dependent tsp with time windows (2011) 10 th Cologne-Twente Workshop on Graphs and Combinatorial Optimization CTW 2011, pp. 198-202
  • Méndez-Díaz, I., Zabala, P., Lucena, A., A new formulation for the traveling deliveryman problem (2008) Discrete Appl. Math., 156 (17), pp. 3223-3237
  • Miranda-Bront, J.J., (2012) Integer Programming approaches to the Time Dependent Travelling Salesman Problem, , Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
  • Miranda-Bront, J.J., Méndez-Díaz, I., Zabala, P., Facets and valid inequalities for the time-dependent travelling salesman problem (2013) Eur. J. Oper. Res.
  • Nagamochi, H., Ono, T., Ibaraki, T., Implementing an efficient minimum capacity cut algorithm (1994) Math. Program., 67 (1), pp. 325-341
  • Picard, J.-C., Queyranne, M., The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling (1978) Oper. Res., 26 (1), pp. 86-110
  • Stecco, G., Cordeau, J.-F., Moretti, E., A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times (2008) Comput. Oper. Res., 35 (8), pp. 2635-2655. , http://dx.doi.org/10.1016/j.cor.2006.12.021
  • Sun, P., Dabia, S., Veelenturf, L.P., Van Woensel, T., The Time-Dependent Pro_table Pickup and Delivery Traveling Salesman Problem with Time Windows (2015) Technical Report, , Eindhoven University of Technology
  • Toth, P., Vigo, D., (2014), Vehicle Routing: Problems, Methods, and Applications, Second Edition. MOS-SIAM Series on Optimization

Citas:

---------- APA ----------
Montero, A., Méndez-Díaz, I. & Miranda-Bront, J.J. (2017) . An integer programming approach for the time-dependent traveling salesman problem with time windows. Computers and Operations Research, 88, 280-289.
http://dx.doi.org/10.1016/j.cor.2017.06.026
---------- CHICAGO ----------
Montero, A., Méndez-Díaz, I., Miranda-Bront, J.J. "An integer programming approach for the time-dependent traveling salesman problem with time windows" . Computers and Operations Research 88 (2017) : 280-289.
http://dx.doi.org/10.1016/j.cor.2017.06.026
---------- MLA ----------
Montero, A., Méndez-Díaz, I., Miranda-Bront, J.J. "An integer programming approach for the time-dependent traveling salesman problem with time windows" . Computers and Operations Research, vol. 88, 2017, pp. 280-289.
http://dx.doi.org/10.1016/j.cor.2017.06.026
---------- VANCOUVER ----------
Montero, A., Méndez-Díaz, I., Miranda-Bront, J.J. An integer programming approach for the time-dependent traveling salesman problem with time windows. Comp. Oper. Res. 2017;88:280-289.
http://dx.doi.org/10.1016/j.cor.2017.06.026