A hybrid metaheuristic for the time-dependent vehicle routing problem with hard time windows

A hybrid metaheuristic for the time-dependent vehicle routing problem with hard time windows

Authors: Rincon-Garcia, N.; Waterson, B.J.; Cherrett, T.J.

International Journal of Industrial Engineering Computations - 2017 Pages 141-160

© 2017 Growing Science Ltd. All rights reserved.This article paper presents a hybrid metaheuristic algorithm to solve the time-dependent vehicle routing problem with hard time windows. Time-dependent travel times are influenced by different congestion levels experienced throughout the day. Vehicle scheduling without consideration of congestion might lead to underestimation of travel times and consequently missed deliveries. The algorithm presented in this paper makes use of Large Neighbourhood Search approaches and Variable Neighbourhood Search techniques to guide the search. A first stage is specifically designed to reduce the number of vehicles required in a search space by the reduction of penalties generated by time-window violations with Large Neighbourhood Search procedures. A second stage minimises the travel distance and travel time in an ‘always feasible’ search space. Comparison of results with available test instances shows that the proposed algorithm is capable of obtaining a reduction in the number of vehicles (4.15%), travel distance (10.88%) and travel time (12.00%) compared to previous implementations in reasonable time.

https://doi.org/10.5267/j.ijiec.2016.6.002

Cite as:

@article{Rincon_Garcia_2017,
	doi = {10.5267/j.ijiec.2016.6.002},
	url = {https://doi.org/10.5267%2Fj.ijiec.2016.6.002},
	year = 2017,
	publisher = {Growing Science},
	pages = {141--160},
	author = {N. Rincon-Garcia and B.J. Waterson and T.J. Cherrett},
	title = {A hybrid metaheuristic for the time-dependent vehicle routing problem with hard time windows},
	journal = {International Journal of Industrial Engineering Computations}
}



    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