An order-first split-second approach to a novel variant of the cardinality-constrained covering traveling salesperson problem

Schöni, C.; Baumann, P.; Trautmann, N. (2020). An order-first split-second approach to a novel variant of the cardinality-constrained covering traveling salesperson problem. In: 2020 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM) (pp. 615-619). IEEE 10.1109/IEEM45057.2020.9309753

Text An_Order-First_Split-Second_Approach_to_a_Novel_Variant_of_the_Cardinality-Constrained_Covering_Traveling_Salesperson_Problem.pdf - Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (3MB)

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.

Interest & Impact

Downloads

6 since deposited on 23 Jul 2021
0 in the past 12 months

Citations

5 Citations in Web of Science ®
6 Citations in Scopus

Search

in Google Scholar™

Services

Actions (login required)

Edit item

Actions (login required)

Edit item