People have known that the earth was round for a long time. Did ships use routes like this to exploit this to reduce travel time? Or is this a more recent idea? Who was the first to utilize the great circle (plane or boat)?
Anyone that travels from point A to point B without turning left or right is using a great circle route. Great circle is just a way to describe what a direct route looks like on a flat map. It comes from the fact that if you continued past your destination using the same heading, you would eventually end up where you started, having traced a circle around the globe. From the traveler's perspective it is a straight line.
Although historical ships could have used great circle routes, there are some factors that worked against it.
The first is that it is a tricky navigation. The compass heading in your example would be gradually changing, which might be fine in the GPS era, tricky in the chronometer era, and practically guesswork with just a sextant. Since latitude was easy to measure and longitude difficult, the typical practice was to sail to the latitude of your destination and keep on that line until you hit land.
The second is that the gain really was not all that much unless you are travelling a substantial portion of the earths circumference and you are not near the equator. For example the great circle route from New York to London is only about 4% shorter than the rhumb line (constant heading) route. You can't really sale it though, because Cape Cod and Cornwall get in the way. It worked out faster to look for the gulf stream heading east, and avoid the gulf stream heading west that to do the math.
