Traveling Salesperson Problem (TSP)

A dairy facility located in Itajubá/MG seeks to distribute its cheese products to the nearby cities of Pouso Alegre/MG, Santa Rita do Sapucaí/MG, and Paraisópolis/MG. The following graph illustrates the transportation costs between each municipality.

Applying the Traveling Salesperson Problem (TSP), which of the provided alternatives reflects the empirically most cost-effective route, commencing from Itajubá/MG (identified as the central vertex)?

A) 50

B) 55

C) 60

D) 75

E) None of the above

Original idea by: Jonas Henrique Ribeiro Paula