Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Marvin Caspar (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: