Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows - Archive ouverte HAL Access content directly
Journal Articles Central European Journal of Operations Research Year : 2013

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.

Dates and versions

hal-02493964 , version 1 (28-02-2020)

Identifiers

Cite

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, 2013, 21 (2), pp.307-336. ⟨10.1007/s10100-011-0204-9⟩. ⟨hal-02493964⟩
29 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More