The quest line starts in Barcelona Port by talking to the Traveling Explorer next to the Trader. You then must sail from City to City talking to the Traveling Explorer in each one and getting a World Expedition Certificate. You must first accept the quest and then submit it to get the next certificate.
The location in the NPC chat box is incorrect, the correct location is on the item description for the certificate or in the Voyage Log. This is due to an update that changed the route but never changed the text in the chat box.
It is recommended to run the questline with a Raider Ship and a Sea Mermaid in order to run it as fast as possible and not get caught in a storm.
You can use autotrack to find the Traveling Explorer quickly. In most cities he is at or near the bottom of the list, except in Seville, in Seville he is in the middle of the list.
Barcelona[]
Stop Number
Cordinates
Reward
Location in City
0
171, -58
World Exploration Certificate
Port
Seville[]
Stop Number
Cordinates
Reward
Location in City
1
15, -16
1 - Low-level Healing Potion
Port
Lisbon[]
Stop Number
Cordinates
Reward
Location in City
2
22, -15
5 - Low-level Healing Potion
City
Madeira[]
Stop Number
Cordinates
Reward
Location in City
3
13, -25
2 - Low-Level Recovery Potion
City
Luanda[]
Stop Number
Cordinates
Reward
Location in City
4
-95, -2
5 - Low-Level Recovery Potion
Port
Magellan Supply Station[]
Stop Number
Cordinates
Reward
Location in City
5
-129, 70
3 - Low-level Incitantia
Port
San Diego[]
Stop Number
Cordinates
Reward
Location in City
6
-60, -45
5 - Low-level Incitantia
Port
Salinas[]
Stop Number
Cordinates
Reward
Location in City
7
-126, -84
5 - Secondary Healing Potion
Port
Semarang[]
Stop Number
Cordinates
Reward
Location in City
8
70, -89
5 - Secondary Recovery Potion
Port
Malacca[]
Stop Number
Cordinates
Reward
Location in City
9
32, -72
5 - Secondary Incitantia
Port
Sri Lanka[]
Stop Number
Cordinates
Reward
Location in City
10
87, -421
1 - Level 1 rage medicament
Port
Bombay[]
Stop Number
Cordinates
Reward
Location in City
11
-98, 16
1 - Level 1 cuirass medicament
Port
Muscat[]
Stop Number
Cordinates
Reward
Location in City
12
8, 23
1 - Level 1 accuracy medicament
Port
Mozambique[]
Stop Number
Cordinates
Reward
Location in City
13
-33, 10
1 - Level 1 sensitive medicament
Port
Cape Town[]
Stop Number
Cordinates
Reward
Location in City
14
15, -37
10K Compressing provisions
Port
Accra[]
Stop Number
Cordinates
Reward
Location in City
15
9, -52
20K Compressing previsions
Port
Dakar[]
Stop Number
Cordinates
Reward
Location in City
16
-20, 70
50K Compressing provisions
Port
Las Palmas[]
Stop Number
Cordinates
Reward
Location in City
17
-25, -20
5 - Imperial Gold
2 - Seal of Poseidon
15 - Original Magnetic Ore
3,000,000 Profession Experience
City
At this point you can go back to Barcelona to submit the quest and get the reward, or to trade in your World Exploration Certificate for the rewards.