An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows

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...

Descripción completa

Detalles Bibliográficos
Autores principales: Balseiro, S.R., Loiseau, I., Ramonet, J.
Formato: JOUR
Materias:
Ant Colony System
Insertion heuristics
Minimum delay
Time-dependent
Vehicle Routing Problem with Time Windows
Ant colony systems
Fleet operations
Optimization
Routing algorithms
Vehicle routing
Vehicles
Global optimization
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03050548_v38_n6_p954_Balseiro
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_03050548_v38_n6_p954_Balseiro
record_format dspace
spelling todo:paper_03050548_v38_n6_p954_Balseiro2023-10-03T15:21:23Z An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows Balseiro, S.R. Loiseau, I. Ramonet, J. 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 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. Fil:Loiseau, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03050548_v38_n6_p954_Balseiro
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic 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
spellingShingle 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
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
topic_facet 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
description 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.
format JOUR
author Balseiro, S.R.
Loiseau, I.
Ramonet, J.
author_facet Balseiro, S.R.
Loiseau, I.
Ramonet, J.
author_sort Balseiro, S.R.
title An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows
title_short An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows
title_full An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows
title_fullStr An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows
title_full_unstemmed An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows
title_sort ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows
url http://hdl.handle.net/20.500.12110/paper_03050548_v38_n6_p954_Balseiro
work_keys_str_mv AT balseirosr anantcolonyalgorithmhybridizedwithinsertionheuristicsforthetimedependentvehicleroutingproblemwithtimewindows
AT loiseaui anantcolonyalgorithmhybridizedwithinsertionheuristicsforthetimedependentvehicleroutingproblemwithtimewindows
AT ramonetj anantcolonyalgorithmhybridizedwithinsertionheuristicsforthetimedependentvehicleroutingproblemwithtimewindows
AT balseirosr antcolonyalgorithmhybridizedwithinsertionheuristicsforthetimedependentvehicleroutingproblemwithtimewindows
AT loiseaui antcolonyalgorithmhybridizedwithinsertionheuristicsforthetimedependentvehicleroutingproblemwithtimewindows
AT ramonetj antcolonyalgorithmhybridizedwithinsertionheuristicsforthetimedependentvehicleroutingproblemwithtimewindows
_version_ 1807316489717415936

Ejemplares similares