@Joaquim I do not think you are saying nonsense, but one of the ways in which I now feel my brain getting old is that it takes me more time than I can give this problem to understand issues in differential geometry. I am intrigued by the problem, and particularly by your statement that swapping the roles of the start and end points gives a different answer (should this be true or is it a bug?). The following remarks are completely useless and do not present a solution, but maybe they will help someone smarter than me (or more handy with differential geometry) help us think it through.

First, I note that the term “longest straight line path” in https://arxiv.org/pdf/1804.07389.pdf is not really properly defined, as any path that is contained in the surface of a sphere or an ellipsoid and which is not of length zero is not contained in a straight line. On a sphere, the shortest path between two distinct points is a great circle and so is contained in a plane; what the problem as originally posed seemed to have in mind is the portion of the great circle defined by two distinct points which is not the shortest path but the remainder of the great circle after the shortest path is removed. I will call this the “longer way around” path. Because it is in the same plane and the same great circle as the shortest path, it is unambiguously defined (assuming that the two points are not antipodal): as a point moves along the shortest path in the sphere the antipode of that point traces the “longer way around” path on the sphere.

Given two (non-antipodal and distinct) points on the surface of an ellipsoid, there is only one unique path between them that is the shortest possible path. But is that sufficient to determine uniquely the ellipsoidal analog of the spherical “longer way around” path? How? Is the shortest ellipsoidal surface path contained in the intersection of the ellipsoid with a plane? (I don’t think so, but these days I have to drink decaffeinated coffee…) As a point moves along the shortest path on an ellipsoidal surface, does its antipodal point trace out the “longer way around” path on the ellipsoid? (I think it is clear what we mean by antipode on an ellipsoid.)

So how do we define the “long way around” on an ellipsoid? Note that it is not enough to say that we want the longest path between two points contained in an ellipsoid. To see this, imagine starting at the North Pole and taking a spiral path so that each time you have moved through 360 degrees of longitude you have moved a small amount southward. If you move an infinitesimally small amount southward with each rotation of longitude then you will eventually arrive at the South Pole but by an infinitely long path.

I am particularly intrigued by @Joaquim 's comment that he can find a solution that starts at point A and ends at point B, but if he swaps the positions of A and B then the path fails to be a solution. It seems intuitive (though differential geometry on strange surfaces is not intuitive to me; my intellect is infinitely smaller than Gauss’s) that the shortest path from A to B and the shortest path from B to A must be the same path, apart from a reversal of the direction of traverse. So, should we expect that our definition of longest “longer way around” path should also have that property (that swapping A and B doesn’t change the path)? If yes, then is there a bug in the code @Joaquim is using? Or is the problem that the longest path is so ill-posed that even an infinitely perfect coder cannot write an algorithm to compute it?

Is it possible that someone has defined the “longer way around” path as follows:

“Given two distinct and non-antipodal points A and B on an ellipsoid,

Find the shortest path from A to B, and the azimuth of this path at A; call this azimuth Alpha.

Then define the “longer way around” path as a path that departs from A with azimuth Alpha + Pi.”

Is this definition even workable? Would this definition arrive at B? Would it explain Joaquim’s paradox?

Maybe this is another way to define it:

Given two distinct and non-antipodal points, A and B, and with longitude defined to be periodic as usual, consider that A and B divide the 2 pi period of longitude into a larger and a smaller interval. The shortest path from A to B goes through each longitude in the smaller interval only once; that is, for each longitude in the smaller interval there is one and only one latitude at that longitude such that that lat,lon pair is a point on the shortest path. Now define the “long way around” path so that it goes through each longitude in the larger interval, but otherwise behaves like a geodesic path (in the surface of the ellipsoid, continuous, differentiable, with one and only one latitude occupied at each longitude in the set).

Is this the definition we have in mind? If so, is the swap(A,B) paradox correct and expected, or not?

Sorry I cannot offer solutions. I am eager to hear more about this from someone who is good at differential geometry on ellipsoids. (And please explain in enough detail so that non-experts can understand.)