Title: A matheuristic approach for the split delivery vehicle routing problem: an efficient set covering-based model with guided route generation schemes

Authors: Nurul Huda Mohamed; Said Salhi; Gábor Nagy; Nurul Akmal Mohamed

Addresses: Department of Mathematics, Faculty of Science and Mathematics, Universiti Pendidikan Sultan Idris, 35900 Tanjong Malim, Perak, Malaysia ' The Centre for Logistics and Heuristic Optimisation, Kent Business School, University of Kent, Canterbury CT2 7PE, UK ' The Centre for Logistics and Heuristic Optimisation, Kent Business School, University of Kent, Canterbury CT2 7PE, UK ' Department of Mathematics, Faculty of Science and Mathematics, Universiti Pendidikan Sultan Idris, 35900 Tanjong Malim, Perak, Malaysia

Abstract: The split delivery vehicle routing problem (SDVRP) is a relaxed version of the classical VRP where customers can be visited more than once. The SDVRP is also applicable for problems where one or more of the customers require a demand larger than the vehicle capacity. Constructive heuristics adapted from the parallel savings and the sweep methods are first proposed to generate a set of solutions which is then used in the new and more efficient set covering-based formulation which we put forward. An effective repair mechanism to remedy any infeasibility due to the set covering problem is presented. A reduced set of promising routes is used in our model, instead of the original set of routes, proposing and using well defined reduction schemes. This set covering-based approach is tested on large datasets from the literature with encouraging results. In brief, seven best solutions including ties are found among the 137 SDVRP instances.

Keywords: split deliveries; vehicle routing; set covering; hybrid method; matheuristic.

DOI: 10.1504/IJMOR.2019.101613

International Journal of Mathematics in Operational Research, 2019 Vol.15 No.1, pp.65 - 91

Received: 04 May 2017
Accepted: 10 Feb 2018
Published online: 14 Aug 2019 *

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