Title: An effective genetic algorithm for solving the capacitated vehicle routing problem with two-dimensional loading constraint

Authors: Ines Sbai; Olfa Limam; Saoussen Krichen

Addresses: LARODEC, Institut Supérieur de Gestion de Tunis, Université de Tunis, 41, Avenue de la Liberté, Cité Bouchoucha, Le Bardo 2000, Tunisia ' LARODEC, Institut Supérieur d'Informatique Tunis, Université de Tunis El Manar, Tunisia ' LARODEC, Institut Supérieur de Gestion de Tunis, Université de Tunis, 41, Avenue de la Liberté, Cité Bouchoucha, Le Bardo 2000, Tunisia

Abstract: In this article, we focus on the symmetric capacitated vehicle routing problem where customer demand is composed of two-dimensional weighted items. The objective consists in designing a set of trips, starting and terminating at a central depot, that minimise the total transportation cost with a homogenous fleet of vehicles based on a depot node. Items in each vehicle trip must satisfy the two-dimensional orthogonal packing constraint. The capacitated vehicle routing problem with two-dimensional loading constraint is an NP-hard problem of high complexity. Given the importance of this problem, many solution approaches have been developed. However, it still a challenging problem. Then, we propose to use a new heuristic based on an adaptive genetic algorithm in order to find better solution. Our algorithm is tested with 150 benchmark instances and compared with state-of-the-art approaches. Results shown that our proposed approach is competitive in terms of the quality of the solutions found.

Keywords: capacitated vehicle routing problem; CVRP; loading; genetic algorithm; GA; 2L-CVRP.

DOI: 10.1504/IJCISTUDIES.2020.106491

International Journal of Computational Intelligence Studies, 2020 Vol.9 No.1/2, pp.85 - 106

Received: 28 Feb 2018
Accepted: 20 Sep 2018
Published online: 09 Apr 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article