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

Guardado en:

Detalles Bibliográficos
Autor principal:	Loiseau, Irene
Publicado:	2011
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:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03050548_v38_n6_p954_Balseiro 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	paper:paper_03050548_v38_n6_p954_Balseiro
record_format	dspace
spelling	paper:paper_03050548_v38_n6_p954_Balseiro2023-06-08T15:30:26Z An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows Loiseau, Irene 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. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03050548_v38_n6_p954_Balseiro 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 Loiseau, Irene 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.
author	Loiseau, Irene
author_facet	Loiseau, Irene
author_sort	Loiseau, Irene
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
publishDate	2011
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03050548_v38_n6_p954_Balseiro http://hdl.handle.net/20.500.12110/paper_03050548_v38_n6_p954_Balseiro
work_keys_str_mv	AT loiseauirene anantcolonyalgorithmhybridizedwithinsertionheuristicsforthetimedependentvehicleroutingproblemwithtimewindows AT loiseauirene antcolonyalgorithmhybridizedwithinsertionheuristicsforthetimedependentvehicleroutingproblemwithtimewindows
_version_	1768544410119700480

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

Ejemplares similares