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

[img] 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) | Request a copy

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.

Item Type:

Conference or Workshop Item (Paper)


03 Faculty of Business, Economics and Social Sciences > Department of Business Management > Institute of Financial Management > Professorship for Quantitative Methods in Business Administration

UniBE Contributor:

Schöni, Chantal Jacqueline; Baumann, Philipp and Trautmann, Norbert


600 Technology > 650 Management & public relations






Nina Ackermann

Date Deposited:

23 Jul 2021 10:17

Last Modified:

23 Jul 2021 10:29

Publisher DOI:





Actions (login required)

Edit item Edit item
Provide Feedback