Given the following: The office, which was apparently the captain’s quarters given the rumpled bed built into one wall, was nicely appointed without being lavish; clearly a working man’s space, though a man of some success. A chart was pinned to the wall that separated the cabin from the rest of the ship. It showed the Adriatic Sea in detail, including hazards, major port cities, and islands. Lines, which must be navigation aids, crisscrossed the map at strange and seemingly arbitrary angles. Should the last sentence read "Lines, which must be navigation aids..." or "Lines, which must have been navigation aids..."?
I like presumably, but one of my favorite words is "likely" so "Lines, likely navigation aids..." Same effect, fewer syllables.
Be careful of your chosen narrative voice, or you could fix the tense error but create a narrative voice error
If you look at just that one line, it works perfectly. So you're not really fighting the grammar. Okay, in a way you are, but it's not about being grammatical. It has more to do with letting grammar create a shifting POV and whether or not you want/need that. It's still the narrator speaking, but he's shifting in time. You can have events happen in the past but expressed in the present: Yesterday, I was at the library, when this bum staggers up to me and recites a sonnet. He's quite good. I know this gets marked wrong on an exam, but it happens in fiction anyway. It's sort of a conversational, historical present tense. It feels like some buddy of yours is telling you a story while having a beer. It's a nice effect. That's kind of what you're doing, just not so pronounced. From the narrator's point of view, the lines are being thought of in the present, even though they reside in the past. The problem is, do you mean to do that? If it just happens once, then you probably don't. It's possible to adjust a different section and fix things: The office, which is apparently the captain’s quarters given the rumpled bed built into one wall, was nicely appointed without being lavish; clearly a working man’s space, though a man of some success. A chart was pinned to the wall that separated the cabin from the rest of the ship. It showed the Adriatic Sea in detail, including hazards, major port cities, and islands. Lines, which must be navigation aids, crisscrossed the map at strange and seemingly arbitrary angles. Now those two "which" phrases align (okay, non-essential relative clauses, whatever . . .). That's the main thing I would do. Match those two in tense. By pushing them to the present, it makes the description seem more conversational, as if the narrator is casually musing over details. Leaving them in the past is more proper, and "safe," I suppose. I mean, this paragraph shouldn't suddenly jump out as conversational in tone if none of its neighbors do the same. Then you should ask yourself if you really want that matching structure so close together: [noun], [which . . .], [verb phrase] Lines crisscrossed the map at strange and seemingly arbitrary angles. Navigation aids, presumably. Something like that ties up the structure. It dodges issues of grammar, though at the end the narrator is making a value judgment and that pulls the idea to the present even though there's no verb there (and hence, no tense). That seems nice to me though because it happens at the end rather than in the middle.
and they wouldn't be in the captains quarters since officers need to consult them while he is off watch - in general the chart space is just behind the bridge
The ship is a carrack; the year is 1575. The "bridge" is a spot to stand behind the wheel in the center of the deck.
in which case the charts would be in the chart room, where the navigator works - they still wouldn't be on the wall of the captains quarters
I would say yes. You really shouldn't mix tenses at all unless you have a very specific reason for doing so, and I don't see one here. Also, the rest of that sentence is in past tense.