Skip to Main content Skip to Navigation
Journal articles

Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows

Abstract : This work deals with a new combinatorial optimization problem, the two-dimensional loading capacitated vehicle routing problem with time windows which is a realistic extension of the well known vehicle routing problem. The studied problem consists in determining vehicle trips to deliver rectangular objects to a set of customers with known time windows, using a homogeneous fleet of vehicles, while ensuring a feasible loading of each vehicle used. Since it includes NP-hard routing and packing sub-problems, six heuristics are firstly designed to quickly compute good solutions for realistic instances. They are obtained by combining algorithms for the vehicle routing problem with time windows with heuristics for packing rectangles. Then, a Memetic algorithm is developed to improve the heuristic solutions. The quality and the efficiency of the proposed heuristics and metaheuristic are evaluated by adding time windows to a set of 144 instances with 15–255 customers and 15–786 items, designed by Iori et al. (Transport Sci 41:253–264, 2007) for the case without time windows.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02493964
Contributor : Daniel Gavrysiak <>
Submitted on : Friday, February 28, 2020 - 12:32:47 PM
Last modification on : Tuesday, May 5, 2020 - 11:50:17 AM

Links full text

Identifiers

Citation

Selma Khebbache-Hadji, Christian Prins, Alice Yalaoui, Mohamed Reghioui. Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows. Central European Journal of Operations Research, Springer Verlag, 2013, 21 (2), pp.307-336. ⟨10.1007/s10100-011-0204-9⟩. ⟨hal-02493964⟩

Share

Metrics

Record views

49