<p>This paper investigates the <i>Split Delivery Capacitated Profitable Tour Problem with Incomplete Service</i> (SDCPTP-IS), an extension of the <i>Capacitated Profitable Tour Problem</i> (CPTP) that introduces two key relaxations: <i>split delivery</i> (SD), allowing a request to be fulfilled by multiple vehicles, and <i>incomplete service</i> (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 <i>Mixed-Integer Linear Program</i> (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 <i>Matheuristic</i> is conducted. This matheuristic exploits the problem structure of the <i>Capacitated Vehicle Routing Problem</i> (CVRP) to solve the SDCPTP-IS as a MILP. More precisely, we use a <i>Guided Local Search</i> (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.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Marvin Caspar

摘要

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.