Change search
ReferencesLink to record
Permanent link

Direct link
Exact and heuristic algorithms for the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection
Christian-Albrechts Universität Kiel.
Christian-Albrechts Universität Kiel.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Christian-Albrechts Universität Kiel.
Show others and affiliations
2015 (English)In: Journal of the Operational Research Society, ISSN 0160-5682, E-ISSN 1476-9360, Vol. 66, no 4, 615-626 p.Article in journal (Refereed) Published
Abstract [en]

We introduce and study the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection (TSP-MTWHS), which generalises the well-known Travelling Salesman Problem with Time Windows and the recently introduced Travelling Salesman Problem with Hotel Selection. The TSP-MTWHS consists in determining a route for a salesman (eg, an employee of a services company) who visits various customers at different locations and different time windows. The salesman may require a several-day tour during which he may need to stay in hotels. The goal is to minimise the tour costs consisting of wage, hotel costs, travelling expenses and penalty fees for possibly omitted customers. We present a mixed integer linear programming (MILP) model for this practical problem and a heuristic combining cheapest insert, 2-OPT and randomised restarting. We show on random instances and on real world instances from industry that the MILP model can be solved to optimality in reasonable time with a standard MILP solver for several small instances. We also show that the heuristic gives the same solutions for most of the small instances, and is also fast, efficient and practical for large instances.

Place, publisher, year, edition, pages
2015. Vol. 66, no 4, 615-626 p.
Keyword [en]
Traveling Salesman Problem, Branch-and-bound, Branch-and-cut, Heuristical methods, Exact methods
National Category
Discrete Mathematics Economics and Business
URN: urn:nbn:se:umu:diva-82881DOI: 10.1057/jors.2014.17ISI: 000351561600008OAI: diva2:663694
Available from: 2013-11-12 Created: 2013-11-12 Last updated: 2015-04-21Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jäger, Gerold
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
Journal of the Operational Research Society
Discrete MathematicsEconomics and Business

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 129 hits
ReferencesLink to record
Permanent link

Direct link