Scheduling band concert tours is an important and challenging task faced by many band management companies and producers. A band has to perform in various cities over a period of time, and the specific route they follow is subject to numerous constraints, such as: venue availability, travel limits, and required rest periods. A good tour must consider several objectives regarding the desirability of certain days of the week, as well as travel cost. We developed and implemented a heuristic algorithm in Java, which was based on simulated annealing, to automatically generate good tours that both satisfied the above constraints and improved objectives significantly when compared to the best manual tour created by the client. Our program also enabled the client to see and explore trade-offs among objectives while choosing the best tour that meets the requirements of the business.