Please note that I regard the "expedition" as fantasy, it is the engineering that interests me.
First, it is almost certain that the Hellenistic Age did know how to measure longitude, because we have maps that prove it. Or, at least, copies of those maps. The most famous - or infamous - is probably the Piri Reis map discussed in Charles Hapgood's fascinating book Maps of the Ancient Sea Kings, but there are better examples.
The Dulcert Portolano of 1339 is in my opinion the best, because it contains fewer copying errors than most, mesured by islands, rivers, estuaries etc. It could not have been produced in the Middle Ages - their idea of a map is the Mappa mundi in Hereford Cathedral, 1289 or so.
So an earlier civilization drew the original portolano, which is further indicated by some features of the map, for example the Guadalquivir is shown with an estuary, as it was in Greek times, rather than a delta. I don't buy Hapgood's thesis that the map makers came from Atlantis, so that leaves the Ancients.
Now, the average error in longitude on the Dulcert Portolano is about 45 minutes arc, three quarters of a degree, or at that latitude about 40 nautical miles. Good enough for point-to-point navigation.
So yes, they did it. But how?
Not with a marine chronometer, that's also pretty certain. No such device is described in the texts, and all we know of ancient clocks says they could not have kept accurate time on a moving vessel. That had to wait until Harrison's time.
That leaves a natural clock, and the obvious first choice is the moon. Would it work?
The math is simple. The moon revolves once around the Earth in 30 days, which is 12 degrees a day or 30 minutes arc an hour. The Earth rotates once in 24 hours, which is 15 degrees an hour or one degree in 4 minutes.
Therefore, to measure longitude accurate to one degree, you need to measure time accurate to 4 minutes. If you are measuring time by tracking the moon against the fixed stars, well, in 4 minutes it moves just 2 minutes arc, one-thirtieth of a degree, or, if you prefer, just one-fifteenth of its own diameter.
Could you do that with naked-eye observation? Absolutely not. Working with the largest and best astronomical instruments ever built, at Uraniborg on the island of Hveen, the great Tycho de Brahe could achieve only half that accuracy.
So you need a faster-running clock, or a telescope, or both. From Heron of Alexandria's Catoptrica, we know the Ancients understood enough of the science of optics to build telescopes, and from Herodotus we have mention of an instrument that sounds very like a telescope, but alas there is no direct proof or "smoking tube".
And if you have a telescope, you will find in the sky as fine a clock as you would ever need: the Galilean satellites of Jupiter. That's my best guess as to how they did it.
Take a peek at the new book Decipher by Stel Pavlou, mentioned in my # 12 Post. I just finished it, and plan to reread it again very soon. Marvelous, simply marvelous.