Skip to main content
Kent Academic Repository

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)

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: Divisions > Kent Business School - Division > Department of Analytics, Operations and Systems
Depositing User: Said Salhi
Date Deposited: 05 Dec 2018 16:28 UTC
Last Modified: 04 Mar 2024 18:38 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/70655 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.