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.

Text PB.pdf - Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (314kB)

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.

Interest & Impact

Downloads

9 since deposited on 22 Jan 2019
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