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)

Division/Institute:

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, Trautmann, Norbert

Subjects:

600 Technology > 650 Management & public relations

Publisher:

IEEE

Language:

English

Submitter:

Nina Ackermann

Date Deposited:

23 Jul 2021 10:17

Last Modified:

05 Dec 2022 15:52

Publisher DOI:

10.1109/IEEM45057.2020.9309753

BORIS DOI:

10.48350/157603

URI:

https://boris.unibe.ch/id/eprint/157603

Actions (login required)

Edit item Edit item
Provide Feedback