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.]

Improve this question
$\endgroup$
2
  • 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 ♦
    Commented May 5, 2019 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
    Commented May 5, 2019 at 14:01

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
10
  • 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 ♦
    Commented May 5, 2019 at 15:00
  • $\begingroup$ Nothing wrong with being exactly 20 miles, and indeed this solution is optimal. However there is another optimal (i.e., equally good) solution -- anyone want to take a crack at finding it? $\endgroup$
    – LarrySnyder610
    Commented May 5, 2019 at 20:04
  • 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 ♦
    Commented May 5, 2019 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
    Commented May 5, 2019 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 ♦
    Commented May 5, 2019 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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