Peter Zekert is an up-and-coming Pharma salesperson who wants to optimize his next hospital visits in his sales territory. He lives in St Louis and has hospitals he visits in three sub-regions.

East subregion: Peoria and Evansville.

West subregion: Omaha, Kansas City, Des Moines and Columbia

South subregion: Wichita, Tulsa and Springfield

Over a six day period, he wishes to visit 6 hospitals, one each day. He cannot visit a hospital more than once. He wishes to visit at least one hospital in each of the three sub-regions, but doesn’t want to visit ALL hospitals in the West subregion nor ALL hospitals in the South subregion (independently). The hospitals only have a couple of days when they are available.

Peoria: Day 4 and Day 6. (75)

Evansville: Day 3 and Day 5. (92)

Omaha: Day 1 and Day 5. (94)

Kansas City: Day 2 only. (81)

Des Moines: Day 2 and Day 4 (63)

Columbia: Day 3 and Day 6. (70)

Wichita: Day 2 and Day 5 (80)

Tulsa: Day 1 and Day 4. (65)

Springfield: Day 1 and Day 6. (72)

(importance rating)

Peter will start from St Louis (Day 0), travel to one hospital each day, and then return to St. Louis (Day 7). He wishes to find the minimum distance route to visit 6 hospitals and return home. Distances are provided below. Note that all requirements above must be met, and he wishes to visit hospitals such that their combined “importance” is at least 485 units. The importance measure is shown above in parenthesis.

Summarize Peter’s schedule by day, and with total miles traveled.
 

Witchita iTulsa KC Omaha IDM Columbia Sfield STL !Peoria Evansville Witchita Tulsa 176 KC 196 271 Omaha 328 382 188 DM 392 462 193 140 Columbia Sfield 320 346 121 317 243 249 180 165 353 357 168 STL 441 393 247 439 338 123 214 Peoria 552 566 353 403 265 241 387 171 Evansville 611 567! 4171 609 509 293! 388! 1741 271j