Skip to main content

A Matheuristic Approach for the Split Delivery Vehicle Routing Problem: An Efficient Set Covering-Based Model with Guided Route Generation Schemes

Mohamed, Nurul Huda, Salhi, Said, Nagy, Gábor, Mohamed, Nurul Akmal (2019) A Matheuristic Approach for the Split Delivery Vehicle Routing Problem: An Efficient Set Covering-Based Model with Guided Route Generation Schemes. International Journal of Mathematics in Operational Research, 15 (1). pp. 65-91. ISSN 1757-5869. E-ISSN 1757-5850. (doi:10.1504/IJMOR.2019.10022832) (KAR id:70655)

PDF Author's Accepted Manuscript
Language: English
Download (393kB) Preview
Official URL
http://dx.doi.org/10.1504/IJMOR.2019.10022832

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 data sets from the literature with encouraging results. In brief, 7 best solutions including ties are found among the 137 SDVRP instances.

Item Type: Article
DOI/Identification number: 10.1504/IJMOR.2019.10022832
Uncontrolled keywords: split deliveries, vehicle routing, set covering, hybrid method, matheuristic
Divisions: Faculties > Social Sciences > Kent Business School
Depositing User: Said Salhi
Date Deposited: 05 Dec 2018 16:28 UTC
Last Modified: 01 Aug 2020 23:00 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/70655 (The current URI for this page, for reference purposes)
Salhi, Said: https://orcid.org/0000-0002-3384-5240
Nagy, Gábor: https://orcid.org/0000-0002-7609-5718
  • Depositors only (login required):