A matheuristic for the split delivery capacitated profitable tour problem with incomplete service

Abstract This paper investigates the Split Delivery Capacitated Profitable Tour Problem with Incomplete Service (SDCPTP-IS), an extension of the Capacitated Profitable Tour Problem (CPTP) that introduces two key relaxations: split delivery (SD), allowing a request to be fulfilled by multiple vehicles, and incomplete service (IS), permitting partial fulfillment of request demands. The objective of the CPTP is to select a subset of requests and determine feasible tours for a fleet of homogeneous vehicles, maximizing the net collected prize (revenue minus delivery cost). We formulate the SDCPTP-IS as a Mixed-Integer Linear Program (MILP). A numerical study using benchmark instances from the literature to investigate the effect of split delivery or/and incomplete service in the CPTP with a state-of-the-art solver and a Matheuristic is conducted. This matheuristic exploits the problem structure of the Capacitated Vehicle Routing Problem (CVRP) to solve the SDCPTP-IS as a MILP. More precisely, we use a Guided Local Search (GLS) heuristic to obtain a CVRP solution that is embedded in the matheuristic to solve the SDCPTP-IS. For managerial insights, we conduct a sensitivity analysis on the CPTP, CPTP with split delivery (SDCPTP), CPTP with incomplete service (CPTP-IS), and the SDCPTP-IS, which investigates a varying number of requests, vehicles, and vehicle capacity.