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

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

Authors: Balseiro, S.R.; Loiseau, I.; Ramonet, J.

Computers and Operations Research - 2011 Volume 38, Pages 954-966

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.

https://doi.org/10.1016/j.cor.2010.10.011

Cite as:

@article{Balseiro_2011,
	doi = {10.1016/j.cor.2010.10.011},
	url = {https://doi.org/10.1016%2Fj.cor.2010.10.011},
	year = 2011,
	month = {jun},
	publisher = {Elsevier {BV}},
	volume = {38},
	number = {6},
	pages = {954--966},
	author = {S.R. Balseiro and I. Loiseau and J. Ramonet},
	title = {An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows},
	journal = {Computers {&}amp$mathsemicolon$ Operations Research}
}



    Leave a Reply

    Your email address will not be published. Required fields are marked *

    x
    This site uses cookies to make navigation simple and efficient. By continuing you declare that you want to automatically accept the privacy policy. More. Close