An Order-First Split-Second Approach to a Novel Variant of the Cardinality-Constrained Covering Traveling Salesperson Problem

摘要

We deal with the following application of the cardinality-constrained covering traveling salesperson problem. A company offers the valuation of real-estate properties, which includes an on-site visit by a contractor. Each contractor visits several properties during a tour, which must comprise not less than a minimum and not more than a maximum number of visits and must not exceed a prescribed length. Given a set of properties, the planning problem is to determine the respective tours such that the total relevant cost of all tours is minimized; for each tour, this cost consists of some fixed costs plus some variable costs proportional to the total distance of the tour. We propose a novel order-first split-second approach which at first devises a giant tour, then splits this tour into feasible tours, and eventually tries to improve these tours individually. Our computational results for a set of test instances from the literature indicate that the proposed approach runs much faster than the reference approaches and devises good feasible solutions; for the largest instances, the proposed approach even outperforms the reference approaches.