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:

This paper presents an Ant Colony System algorithm hybridized with insertion heuristics for the Time-Dependent Vehicle Routing Problem with Time Windows (TDVRPTW). In the TDVRPTW a fleet of vehicles must deliver goods to a set of customers, time window constraints of the customers must be respected and the fact that the travel time between two points depends on the time of departure has to be taken into account. The latter assumption is particularly important in an urban context where the traffic plays a significant role. A shortcoming of Ant Colony algorithms for capacitated routing problems is that, at the final stages of the algorithm, ants tend to create infeasible solutions with unrouted clients. Hence, we propose enhancing the algorithm with an aggressive insertion heuristic relying on the minimum delay metric. Computational results confirm the benefits of more involved insertion heuristics. Moreover, the resulting algorithm turns out to be competitive, matching or improving the best known results in several benchmark problems. © 2010 Elsevier Ltd. All rights reserved.

Registro:

Documento: Artículo
Título:An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows
Autor:Balseiro, S.R.; Loiseau, I.; Ramonet, J.
Filiación:Graduate School of Business, Columbia University, United States
Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina
Facultad de Ingenieria, Universidad de Buenos Aires, Argentina
Palabras clave:Ant Colony System; Insertion heuristics; Minimum delay; Time-dependent; Vehicle Routing Problem with Time Windows; Ant colony systems; Insertion heuristics; Minimum delay; Time-dependent; Vehicle Routing Problem with Time Windows; Fleet operations; Optimization; Routing algorithms; Vehicle routing; Vehicles; Global optimization
Año:2011
Volumen:38
Número:6
Página de inicio:954
Página de fin:966
DOI: http://dx.doi.org/10.1016/j.cor.2010.10.011
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_v38_n6_p954_Balseiro

Referencias:

  • Balseiro, S.R., Logística y distribución: algoritmos para problemas de ruteo de vehículos con restricciones de capacidad y ventanas de tiempo (2007) Tesis de Ingeniería Industrial, , Facultad de Ingeniería, Universidad de Buenos Aires
  • Barr, R., Golden, B., Kelly, J., Resende, M., Stewart, W., Designing and reporting on computational experiments with heuristic methods (1995) Journal of Heuristics, 1 (1), pp. 9-32
  • Bent, R., Van Hentenryck, P., A two stage hybrid local search for the vehicle routing problem with time windows (2004) Transportation Science, 38 (4), pp. 515-530
  • Berger, J., Barkaoui, M., A parallel hybrid genetic algorithm for the vehicle routing problem with time windows (2004) Computers and Operations Research, 31 (12), pp. 2037-2053
  • Brysy, O., Gendreau, M., Vehicle routing problem with time windows, part I: Route construction and local search algorithms (2005) Transportation Science, 39 (1), pp. 104-118
  • Campbell, A., Savelsbergh, M., Efficient insertion heuristics for vehicle routing and scheduling problems (2004) Transportation Science, 38 (3), pp. 369-378
  • Chiang, W.C., Russell, R.A., Simulated annealing metaheuristics for the vehicle routing problem with time windows (1996) Annals of Operations Research, 63, pp. 3-27
  • Cordeau, J.-F., Laporte, G., Mercier, A., A unified tabu search heuristic for vehicle routing problems with time windows (2001) Journal of the Operational Research Society, 52 (8), pp. 928-936. , DOI 10.1057/palgrave/jors/2601163
  • Czech, Z.J., Czarnas, P., A parallel simulated annealing for the vehicle routing problem with time windows (2002) Proceedings of 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, pp. 376-383. , Canary Islands, Spain; January
  • Dantzig, G.B., Ramser, J.H., The truck dispatching problem (1959) Management Science, 6 (1), pp. 80-91
  • Donati, A., Montemanni, R., Casagrande, N., Rizzoli, A., Gambardella, L.M., Time dependent vehicle routing problem with a multi ant colony system (2008) European Journal of Operational Research, 185 (3), pp. 1174-1191
  • Dorigo, M., Gamardella, L.M., Ant colony system: A cooperative learning approach to the traveling salesman problem (1997) IEEE Transactions on Evolutionary Computation, 1 (1), pp. 53-66
  • Dorigo, M., Stutzle, T., (2004) Ant Colony Optimization, , The MIT Press
  • Dorigo, M., Maniezzo, V., Colorni, A., Ant system: Optimization by a colony of cooperating agents (1996) IEEE Transactions on Systems, Man, and CyberneticsPart B, 26 (1), pp. 1-13
  • Fleischmann, B., Gietz, M., Gnutzmann, S., Time-varying travel times in vehicle routing (2004) Transportation Science, 38 (2), pp. 160-173
  • Gambardella, L.M., Taillard, R., Agazzi, G., Multiple ant colony system for vehicle routing problems with time windows (1999) New Ideas in Optimization, pp. 63-76. , McGraw-Hill London, UK
  • Golden, B., Raghavan, S., Wasil, E., (2008) The Vehicle Routing Problem: Latest Advances and New Challenges, , Springer
  • Homberger, J., Gehring, H., Two evolutionary metaheuristics for the vehicle routing problem with time windows (1999) INFOR, 37 (3), pp. 297-318
  • Ichoua, S., Gendreau, M., Potvin, J.-Y., Vehicle dispatching with time-dependent travel times (2003) European Journal of Operational Research, 144 (2), pp. 379-396
  • Lau, H.C., Sim, M., Meng Teo, K., Vehicle routing problem with time windows and a limited number of vehicles (2003) European Journal of Operational Research, 148 (3), pp. 559-569
  • Lim, A., Zhang, X., A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows (2007) INFORMS Journal on Computing, 19 (3), pp. 443-457
  • Lin, S., Computer solutions of the traveling salesman problem (1965) Bell System Technical Journal, 44, pp. 2245-2269
  • Malandraki, C., (1989) Time Dependent Vehicle Routing Problems: Formulations, Solution Algorithms and Computations Experiments, , PhD dissertation, Northwestern University, Evanston, III
  • Malandraki, C., Daskin, M., Time dependent vehicle routing problems: Formulations, properties and heuristic algorithm (1992) Transportation Science, 26 (3), pp. 185-200
  • Savelsbergh, M.W.P., Local search in routing problems with time windows (1985) Annals of Operations Research, 4 (1), pp. 285-305
  • Savelsbergh, M.W.P., An efficient implementation of local search algorithms for constrained routing problems (1990) European Journal of Operational Research, 47 (1), pp. 75-85
  • Solomon, M., Algorithms for the vehicle routing and scheduling problems with time window constraints (1987) Operations Research, 35 (2), pp. 254-265
  • Taillard, E., Badeau, P., Gendreau, M., Guertin, F., Potvin, J.-Y., A tabu search heuristic for the vehicle routing problem with soft time windows (1997) Transportation Science, 31 (2), pp. 170-186
  • Thangiah, S.R., Nygard, K.E., Juell, P.L., GIDEON: A genetic algorithm system for vehicle routing with time windows (1991) Proceedings of the Seventh Conference on Artificial Intelligence for Applications, Vol. 1., pp. 322-328. , February
  • Toth, P., Vigo, D., (2002) The Vehicle Routing Problem, , SIAM

Citas:

---------- APA ----------
Balseiro, S.R., Loiseau, I. & Ramonet, J. (2011) . An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows. Computers and Operations Research, 38(6), 954-966.
http://dx.doi.org/10.1016/j.cor.2010.10.011
---------- CHICAGO ----------
Balseiro, S.R., Loiseau, I., Ramonet, J. "An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows" . Computers and Operations Research 38, no. 6 (2011) : 954-966.
http://dx.doi.org/10.1016/j.cor.2010.10.011
---------- MLA ----------
Balseiro, S.R., Loiseau, I., Ramonet, J. "An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows" . Computers and Operations Research, vol. 38, no. 6, 2011, pp. 954-966.
http://dx.doi.org/10.1016/j.cor.2010.10.011
---------- VANCOUVER ----------
Balseiro, S.R., Loiseau, I., Ramonet, J. An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows. Comp. Oper. Res. 2011;38(6):954-966.
http://dx.doi.org/10.1016/j.cor.2010.10.011