A matheuristic for a real-world variant of the multiple traveling salesman problem

Baumann, Philipp (19 December 2018). A matheuristic for a real-world variant of the multiple traveling salesman problem. In: IEEM 2018: IEEE International Conference on Industrial Engineering and Engineering Management. Bangkok. 16.12-19.12.2018.

[img] Text
PB.pdf - Published Version
Restricted to registered users only
Available under License Publisher holds Copyright.

Download (314kB) | Request a copy

Significant long-term cost savings can be achieved when labor-intensive daily operations are executed at minimal cost. We consider here a real-world planning problem that was reported to us by a real estate valuation company. The planning problem consists of
scheduling on-site visits such that the total operating costs are minimized. We show that this problem represents a new variant of the multiple traveling salesman problem to which existing approaches cannot be applied directly. We formulate the problem as a mixed-binary linear program and develop a matheuristic for large-scale instances. The matheuristic employs a new strategy to construct subproblems effectively and techniques to exclude variables that are unlikely to be non-zero in an optimal solution. Our
computational analysis demonstrates that the mixed-binary linear program is able to devise optimal or near-optimal solutions for instances with up to 200 visits in short running times. The matheuristic performs equally well on small and medium-sized instances and proves to be highly scalable.

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:

Baumann, Philipp


600 Technology > 650 Management & public relations




Juliana Kathrin Moser-Zurbrügg

Date Deposited:

22 Jan 2019 11:31

Last Modified:

28 Jan 2020 13:49





Actions (login required)

Edit item Edit item
Provide Feedback