5
$\begingroup$

It is the zombie apocalypse. Your car has limited fuel in it, and you will not be able to refill your tank once you run out. You are planning one final mission to gather supplies. You have identified 10 locations that you would like to visit, but you do not have enough fuel to visit all of the locations. Therefore, you have assigned each site a number of “survival points” that indicate how valuable the site’s resources are.

The diagram below shows your base, as well as the sites you would like to visit and their survival points.

enter image description here

The distances in miles among the locations are given below. (Each site name is abbreviated to its initial letter.) Your car has enough fuel to travel 20 miles. Your mission will begin at your base and, of course, must end there as well (otherwise the zombies will get you on your way back).

enter image description here

Plan a route that collects as many survival points as possible and can be completed using only your available fuel.

[Source: This book (yes, I wrote it) -- cited here for attribution, not self-promotion.]

$\endgroup$
  • 2
    $\begingroup$ There is a [no-computers] tag for puzzles you don't want to see computerized solutions to. I've no idea whether you do prefer non-computerized solutions (and it's not obvious that there'll be any way to prove that a given solution is optimal that doesn't involve something like a branch-and-bound computer search), but if you do then you should add the no-computers tag. $\endgroup$ – Gareth McCaughan May 5 at 13:50
  • 1
    $\begingroup$ I opted not to use that tag. At the very least, it would be very tedious to do the calculations without a computer. It’s up to solvers whether they want to use a computer for the optimization part. $\endgroup$ – LarrySnyder610 May 5 at 14:01
3
$\begingroup$

Here's my shot:

Base-->Hospital-->Beer Store-->Doctor's Office-->City Hall-->Grocery-->Police Station-->Library-->Base

This journey takes

Exactly 20 miles. If that makes you nervous, skip the beer store - it only adds 1 point and 1.4 miles.

The trip accumulates

22 survival points - 21 if you want to skip the beer shop.

Gareth has said below that he ran this problem through a program of some sort and this appears to be the optimal solution.

$\endgroup$
  • 1
    $\begingroup$ I did a computerized search. I can confirm that either your solution is optimal or the LKH program for solving TSP instances is failing to find optimal solutions in cases where I would very strongly expect it to find them reliably. $\endgroup$ – Gareth McCaughan May 5 at 15:00
  • $\begingroup$ @GarethMcCaughan thanks! $\endgroup$ – Brandon_J May 5 at 15:05
  • 1
    $\begingroup$ What I actually did was: for every subset of the nodes (that includes the base), compute a hopefully-optimal TSP for that subset. (Except that I pruned sets of nodes with subsets already found to have over-long tours.) So, lots of invocations of LKH, not just one. $\endgroup$ – Gareth McCaughan May 5 at 20:45
  • 1
    $\begingroup$ @LarrySnyder610 no problem! Thanks for the puzzle. Hope to see you post again sometime! I also hope that I learn to not use so many exclamation points! Yay! $\endgroup$ – Brandon_J May 5 at 21:20
  • 2
    $\begingroup$ Glad to hear there isn't another solution -- because I tweaked my code to look for it and found none :-). $\endgroup$ – Gareth McCaughan May 5 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.