widelands-dev team mailing list archive

[Benedikt Straub <benedikt-straub@xxxxxx>]

Benedikt Straub has proposed merging lp:~widelands-dev/widelands/new-shipping into lp:widelands.

Commit message:
New planning-ahead ship scheduling algorithm

Requested reviews:
  Widelands Developers (widelands-dev)
Related bugs:
  Bug #1827033 in widelands: "Bugs in new ShipScheduling algorithm"
  https://bugs.launchpad.net/widelands/+bug/1827033

For more details, see:
https://code.launchpad.net/~widelands-dev/widelands/new-shipping/+merge/371155

This algorithm uses a new approach. Each ship has a sorted list of the ports it´s planning to visit next. When new wares are loaded or some port requires a ship, the destinations may be reordered to accommodate for the importance of the several destinations (which depends on distance and number of wares). Ports whose visit is often postponed increase in priority so single wares won´t be sailing around forever if more important orders keep dropping in. Ports that can be visited on-the-fly (only a small detour) between two more important ports are also preferred. Ships may also be called back if a new ware arrives at the port immediately after the ship has left.

I hacked together some savegame compatibility; however, due to the linked bug, trunk savegames may show irrational behaviour.
-- 
Your team Widelands Developers is requested to review the proposed merge of lp:~widelands-dev/widelands/new-shipping into lp:widelands.

=== modified file 'src/economy/fleet.cc'
--- src/economy/fleet.cc	2019-04-24 15:11:23 +0000
+++ src/economy/fleet.cc	2019-08-10 09:34:44 +0000
@@ -336,7 +336,7 @@
 uint32_t Fleet::count_ships_heading_here(EditorGameBase& egbase, PortDock* port) const {
 	uint32_t ships_on_way = 0;
 	for (uint16_t s = 0; s < ships_.size(); s += 1) {
-		if (ships_[s]->get_destination(egbase) == port) {
+		if (ships_[s]->get_current_destination(egbase) == port) {
 			ships_on_way += 1;
 		}
 	}
@@ -400,8 +400,8 @@
 	if (upcast(Game, game, &egbase))
 		ship->set_economy(*game, nullptr);
 
-	if (ship->get_destination(egbase)) {
-		ship->get_destination(egbase)->ship_coming(false);
+	if (ship->get_current_destination(egbase)) {
+		ship->get_current_destination(egbase)->ship_coming(*ship, false);
 		update(egbase);
 	}
 
@@ -665,13 +665,14 @@
 		bool waiting = true;
 
 		for (Ship* s : ships_) {
-			if (s->get_destination(game)) {
-				if (s->get_destination(game) == p) {
+			bool fallback = false;
+			if (s->get_current_destination(game)) {
+				if (s->has_destination(game, *p)) {
 					waiting = false;
 					--waiting_ports;
 					break;
 				}
-				continue;  // The ship already has a destination
+				fallback = true;  // The ship already has a destination
 			}
 			if (s->get_ship_state() != Ship::ShipStates::kTransport) {
 				continue;  // Ship is not available, e.g. in expedition
@@ -699,6 +700,46 @@
 			if (route_length == kRouteNotCalculated) {
 				route_length = s->calculate_sea_route(game, *p);
 			}
+			if (fallback) {
+				// This ship is employed transporting wares, lower its priority drastically
+				const uint32_t real_length = route_length;
+				uint32_t malus = 1;
+				uint32_t index = 0;
+				PortDock* iterator = nullptr;
+				uint32_t shortest_detour = std::numeric_limits<uint32_t>::max();
+				uint32_t best_index;
+				for (const auto& pair : s->destinations_) {
+					PortDock* pd = pair.first.get(game);
+					Path path;
+					uint32_t detour;
+					if (iterator == p) {
+						detour = 0;
+					} else if (iterator) {
+						get_path(*iterator, *p, path);
+						detour = path.get_nsteps();
+					} else {
+						s->calculate_sea_route(game, *p, &path);
+						detour = path.get_nsteps();
+					}
+					if (p != pd) {
+						get_path(*p, *pd, path);
+						detour += path.get_nsteps();
+					}
+					if (detour < shortest_detour) {
+						shortest_detour = detour;
+						best_index = index;
+					}
+					malus += pair.second;
+					iterator = pd;
+					++index;
+				}
+				route_length += shortest_detour * best_index;
+				if (route_length + shortest_detour > real_length * malus) {
+					// Unreasonably long detour
+					continue;
+				}
+				route_length *= malus;
+			}
 
 			if (route_length < shortest_dist) {
 				shortest_dist = route_length;
@@ -708,7 +749,7 @@
 
 		if (waiting && closest_ship) {
 			--waiting_ports;
-			closest_ship->set_destination(p);
+			closest_ship->push_destination(game, *p);
 			closest_ship->send_signal(game, "wakeup");
 		}
 	}
@@ -721,7 +762,7 @@
 
 	// Deal with edge-case of losing destination before reaching it
 	for (Ship* s : ships_) {
-		if (s->get_destination(game)) {
+		if (s->get_current_destination(game)) {
 			continue;  // The ship has a destination
 		}
 		if (s->get_ship_state() != Ship::ShipStates::kTransport) {
@@ -744,107 +785,93 @@
 		}
 
 		if (closest_port) {
-			s->set_destination(closest_port);
+			s->push_destination(game, *closest_port);
 			s->send_signal(game, "wakeup");
 		}
 	}
 }
 
 /**
- * For the given three consecutive ports, decide if their path is favourable or not.
- * \return true if the path from start to finish >= the path from middle to finish
- */
-bool Fleet::is_path_favourable(const PortDock& start,
-                               const PortDock& middle,
-                               const PortDock& finish) {
-	if (&middle != &finish) {
-		Path path_start_to_finish;
-		Path path_middle_to_finish;
-#ifndef NDEBUG
-		assert(get_path(start, finish, path_start_to_finish));
-#else
-		get_path(start, finish, path_start_to_finish);
-#endif
-		if (get_path(middle, finish, path_middle_to_finish)) {
-			if (path_middle_to_finish.get_nsteps() > path_start_to_finish.get_nsteps()) {
-				return false;
-			}
-		}
-	}
-	return true;  // default
-}
-
-/**
- * For the given ship, go through all ports of this fleet
- * and find the one with the best score.
- * \return that port
- */
-PortDock* Fleet::find_next_dest(Game& game, const Ship& ship, const PortDock& from_port) {
-	PortDock* best_port = nullptr;
-	float best_score = 0.0f;
-
-	for (PortDock* p : ports_) {
-		if (p == &from_port) {
-			continue;  // same port
-		}
-
-		float score = 0.0f;
-		WareInstance* ware;
-		Worker* worker;
-
-		// Score for wares/workers onboard that ship for that port
-		for (const ShippingItem& si : ship.items_) {
-			if (si.get_destination(game) == p) {
-				si.get(game, &ware, &worker);
-				if (ware) {
-					score += 1;  // TODO(ypopezios): increase by ware's importance
-				} else {        // worker
-					score += 4;
-				}
-			}
-		}
-
-		// Score for wares/workers waiting at that port
-		for (const ShippingItem& si : from_port.waiting_) {
-			if (si.get_destination(game) == p) {
-				si.get(game, &ware, &worker);
-				if (ware) {
-					score += 1;  // TODO(ypopezios): increase by ware's importance
-				} else {        // worker
-					score += 4;
-				}
-			}
-		}
-
-		if (score == 0.0f && p->get_need_ship() == 0) {
-			continue;  // empty ship to empty port
-		}
-
-		// Here we get distance ship->port
-		uint32_t route_length = kRouteNotCalculated;
-
-		// Get precalculated distance if the ship is at a port
-		{
-			Path precalculated_path;
-			if (get_path(from_port, *p, precalculated_path)) {  // try to use precalculated path
-				route_length = precalculated_path.get_nsteps();
-			}
-		}
-
-		// Get distance for when the ship is not at a port (should not happen frequently)
-		if (route_length == kRouteNotCalculated) {
-			route_length = ship.calculate_sea_route(game, *p);
-		}
-
-		score = (score + 1.0f) * (score + p->get_need_ship());
-		score = score * (1.0f - route_length / (score + route_length));
-		if (score > best_score) {
-			best_score = score;
-			best_port = p;
-		}
-	}
-
-	return best_port;
+ * Tell the given ship where to go next. May push any number of destinations.
+ */
+void Fleet::push_next_destinations(Game& game, Ship& ship, const PortDock& from_port) {
+	std::vector<std::pair<PortDock*, uint32_t>> destinations;
+	uint32_t total_items = ship.get_nritems(); // All waiting and shipping items
+	uint32_t waiting_items = 0; // Items that have a destination which this ship is not currently planning to visit
+	for (auto& it : from_port.waiting_) {
+		if (PortDock* pd = it.destination_dock_.get(game)) {
+			++total_items;
+			if (ship.has_destination(game, *pd)) {
+				continue;
+			}
+			++waiting_items;
+			bool found = false;
+			for (auto& pair : destinations) {
+				if (pair.first == pd) {
+					++pair.second;
+					found = true;
+					break;
+				}
+			}
+			if (!found) {
+				destinations.push_back(std::make_pair(pd, 1));
+			}
+		}
+	}
+	assert(waiting_items <= total_items);
+	if (waiting_items == 0) {
+		// Nothing to do
+		return;
+	}
+	total_items -= waiting_items;
+	// For each destination, decide whether to tell the ship to visit it
+	// or whether it would be better to wait for another ship
+	for (const auto& destpair : destinations) {
+		Path path;
+		get_path(from_port, *destpair.first, path);
+		const uint32_t direct_route = path.get_nsteps();
+		assert(direct_route);
+		uint32_t malus = 1;
+		uint32_t shortest_detour = std::numeric_limits<uint32_t>::max();
+		uint32_t best_index;
+		if (ship.destinations_.empty()) {
+			best_index = 0;
+			malus = 0;
+			shortest_detour = 0;
+		} else {
+			const PortDock* iterator = &from_port;
+			uint32_t index = 0;
+			for (const auto& pair : ship.destinations_) {
+				const PortDock* pd = pair.first.get(game);
+				uint32_t base_length = 0;
+				uint32_t detour = 0;
+				if (iterator != pd) {
+					get_path(*iterator, *pd, path);
+					base_length = path.get_nsteps();
+				}
+				if (iterator != &from_port) {
+					get_path(*iterator, from_port, path);
+					detour = path.get_nsteps();
+				}
+				if (pd != &from_port) {
+					get_path(from_port, *pd, path);
+					detour += path.get_nsteps();
+				}
+				assert(detour >= base_length);
+				detour -= base_length;
+				if (detour < shortest_detour) {
+					shortest_detour = detour;
+					best_index = index;
+				}
+				malus += pair.second;
+				iterator = pd;
+				++index;
+			}
+		}
+		if (shortest_detour * malus * best_index <= direct_route * destpair.second * total_items) {
+			ship.push_destination(game, *destpair.first);
+		}
+	}
 }
 
 void Fleet::log_general_info(const EditorGameBase& egbase) const {

=== modified file 'src/economy/fleet.h'
--- src/economy/fleet.h	2019-04-24 06:51:31 +0000
+++ src/economy/fleet.h	2019-08-10 09:34:44 +0000
@@ -155,8 +155,7 @@
 	void save(EditorGameBase&, MapObjectSaver&, FileWrite&) override;
 
 	static MapObject::Loader* load(EditorGameBase&, MapObjectLoader&, FileRead&);
-	bool is_path_favourable(const PortDock& start, const PortDock& middle, const PortDock& finish);
-	PortDock* find_next_dest(Game&, const Ship&, const PortDock& from_port);
+	void push_next_destinations(Game&, Ship&, const PortDock& from_port);
 };
 
 }  // namespace Widelands

=== modified file 'src/economy/portdock.cc'
--- src/economy/portdock.cc	2019-07-01 14:58:07 +0000
+++ src/economy/portdock.cc	2019-08-10 09:34:44 +0000
@@ -56,7 +56,6 @@
    : PlayerImmovable(g_portdock_descr),
      fleet_(nullptr),
      warehouse_(wh),
-     ships_coming_(0),
      expedition_ready_(false) {
 }
 
@@ -118,7 +117,7 @@
 }
 
 uint32_t PortDock::get_need_ship() const {
-	return (waiting_.size() + (expedition_ready_ ? 20 : 0)) / (ships_coming_ + 1);
+	return (waiting_.size() + (expedition_ready_ ? 20 : 0)) / (ships_coming_.size() + 1);
 }
 
 /**
@@ -198,6 +197,11 @@
 		for (ShippingItem& shipping_item : waiting_) {
 			shipping_item.remove(*game);
 		}
+		for (Ship* s : ships_coming_) {
+			if (egbase.objects().object_still_available(s)) {
+				s->pop_destination(*game, *this);
+			}
+		}
 	}
 
 	if (fleet_)
@@ -288,7 +292,7 @@
 
 	// Destination might have vanished or be in another economy altogether.
 	if (dst && dst->get_economy() == get_economy()) {
-		if (ships_coming_ <= 0) {
+		if (ships_coming_.empty()) {
 			set_need_ship(game, true);
 		}
 	} else {
@@ -320,11 +324,14 @@
 /**
  * A ship changed destination and is now coming to the dock. Increase counter for need_ship.
  */
-void PortDock::ship_coming(bool affirmative) {
+void PortDock::ship_coming(Ship& ship, bool affirmative) {
 	if (affirmative) {
-		++ships_coming_;
+		assert(ships_coming_.find(&ship) == ships_coming_.end());
+		ships_coming_.insert(&ship);
 	} else {
-		--ships_coming_;
+		auto it = ships_coming_.find(&ship);
+		assert(it != ships_coming_.end());
+		ships_coming_.erase(it);
 	}
 }
 
@@ -332,14 +339,12 @@
  * A ship has arrived at the dock. Set its next destination and load it accordingly.
  */
 void PortDock::ship_arrived(Game& game, Ship& ship) {
-	ship_coming(false);
-
 	if (expedition_ready_) {
 		assert(expedition_bootstrap_ != nullptr);
 
 		// Only use an empty ship.
-		if (ship.get_nritems() < 1) {
-			ship.set_destination(nullptr);
+		if (ship.get_nritems() == 0) {
+			ship.clear_destinations(game);
 			// Load the ship
 			std::vector<Worker*> workers;
 			std::vector<WareInstance*> wares;
@@ -363,11 +368,55 @@
 		}
 	}
 
-	// Decide where the arrived ship will go next
-	PortDock* next_port = fleet_->find_next_dest(game, ship, *this);
-	if (next_port) {
-		// Unload any wares/workers onboard the departing ship which are not favored by next dest
-		ship.unload_unfit_items(game, *this, *next_port);
+	ship.pop_destination(game, *this);
+	fleet_->push_next_destinations(game, ship, *this);
+	if (ship.get_current_destination(game)) {
+		uint32_t free_capacity = ship.descr().get_capacity() - ship.get_nritems();
+		std::unordered_map<const PortDock*, bool> destination_check;
+		for (auto it = waiting_.begin(); it != waiting_.end() && free_capacity;) {
+			const PortDock* dest = it->get_destination(game);
+			assert(dest);
+			assert(dest != this);
+			// Decide whether to load this item
+			bool load;
+			auto dc = destination_check.find(dest);
+			if (dc != destination_check.end()) {
+				load = dc->second;
+			} else {
+				int32_t time = ship.estimated_arrival_time(game, *dest);
+				Path direct_route;
+				fleet_->get_path(*this, *dest, direct_route);
+				if (time < 0) {
+					time = direct_route.get_nsteps();
+				}
+				for (Ship* s : ships_coming_) {
+					int32_t t = s->estimated_arrival_time(game, *dest, this);
+					if (t < 0) {
+						// The ship is not planning to go there yet, perhaps we can ask for a detour?
+						t = s->estimated_arrival_time(game, *this);
+						assert(t >= 0);
+						assert(s->count_destinations() >= 1);
+						if (time > t + static_cast<int32_t>(direct_route.get_nsteps() * s->count_destinations())) {
+							time = -1;
+							break;
+						}
+					} else if (t < time) {
+						// A ship is coming that is planning to visit the ware's destination sooner than this one
+						time = -1;
+						break;
+					}
+				}
+				load = time >= 0;
+				destination_check.emplace(dest, load);
+			}
+			if (load) {
+				ship.add_item(game, *it);
+				it = waiting_.erase(it);
+				--free_capacity;
+			} else {
+				++it;
+			}
+		}
 	}
 #ifndef NDEBUG
 	else {
@@ -375,51 +424,11 @@
 	}
 #endif
 
-	// Check for items with invalid destination. TODO(ypopezios): Prevent invalid destinations
-	for (auto si_it = waiting_.begin(); si_it != waiting_.end(); ++si_it) {
-		if (!si_it->get_destination(game)) {
-			// Invalid destination. Carry the item back into the warehouse
-			// TODO(Nordfriese): This readds the invalid item to the list
-			si_it->set_location(game, warehouse_);
-			si_it->end_shipping(game);
-			si_it = waiting_.erase(si_it);
-		}
-	}
-
-	if (!next_port) {
-		ship.set_destination(nullptr);
-		return;  // no need to load anything
-	}
-
-	// Then load the remaining capacity of the departing ship with relevant items
-	uint32_t remaining_capacity = ship.descr().get_capacity() - ship.get_nritems();
-
-	// Firstly load the wares/workers which go to chosen destination
-	for (auto si_it = waiting_.begin(); si_it != waiting_.end() && remaining_capacity > 0; ++si_it) {
-		if (si_it->get_destination(game) == next_port) {
-			ship.add_item(game, *si_it);
-			si_it = waiting_.erase(si_it);
-			--remaining_capacity;
-		}
-	}
-
-	// Then load any wares/workers favored by the chosen destination
-	for (auto si_it = waiting_.begin(); si_it != waiting_.end() && remaining_capacity > 0; ++si_it) {
-		const PortDock* dest = si_it->get_destination(game);
-		if (dest && fleet_->is_path_favourable(*this, *next_port, *dest)) {
-			ship.add_item(game, *si_it);
-			si_it = waiting_.erase(si_it);
-			--remaining_capacity;
-		}
-	}
-
-	ship.set_destination(next_port);
 	set_need_ship(game, !waiting_.empty());
 }
 
 void PortDock::set_need_ship(Game& game, bool need) {
 	if (need && fleet_) {
-		molog("trigger fleet update\n");
 		fleet_->update(game);
 	}
 }
@@ -449,8 +458,18 @@
 
 /**
  * Return the number of wares or workers waiting at the dock.
+ * If a destination dock is specified, count only items heading for this destination.
  */
-uint32_t PortDock::count_waiting() const {
+uint32_t PortDock::count_waiting(const PortDock* dest) const {
+	if (dest) {
+		uint32_t w = 0;
+		for (const ShippingItem& si : waiting_) {
+			if (si.destination_dock_.serial() == dest->serial()) {
+				++w;
+			}
+		}
+		return w;
+	}
 	return waiting_.size();
 }
 
@@ -504,7 +523,7 @@
 	}
 }
 
-constexpr uint8_t kCurrentPacketVersion = 4;
+constexpr uint8_t kCurrentPacketVersion = 5;
 
 PortDock::Loader::Loader() : warehouse_(0) {
 }
@@ -523,15 +542,18 @@
 		pd.set_position(egbase(), pd.dockpoints_[i]);
 	}
 
-	pd.ships_coming_ = fr.unsigned_8();
-
-	// TODO(GunChleoc): Savegame compatibility Build 20
-	if (packet_version < 4) {
-		pd.ships_coming_ = 0;
+	if (packet_version >= 5) {
+		const uint32_t ships = fr.unsigned_32();
+		for (uint32_t i = 0; i < ships; ++i) {
+			ships_coming_.insert(fr.unsigned_32());
+		}
+	} else {
+		// TODO(GunChleoc): Savegame compatibility Build 20
+		fr.unsigned_8();
 		for (const Serial ship_serial : pd.owner().ships()) {
 			Ship* ship = dynamic_cast<Ship*>(egbase().objects().get_object(ship_serial));
-			if (ship->get_destination(egbase())->serial() == pd.serial()) {
-				++pd.ships_coming_;
+			if (ship->has_destination(egbase(), pd)) {
+				ships_coming_.insert(ship_serial);
 			}
 		}
 	}
@@ -554,6 +576,9 @@
 	PortDock& pd = get<PortDock>();
 	pd.warehouse_ = &mol().get<Warehouse>(warehouse_);
 
+	for (Serial s : ships_coming_) {
+		pd.ships_coming_.insert(&mol().get<Ship>(s));
+	}
 	for (uint32_t i = 0; i < waiting_.size(); ++i) {
 		pd.waiting_.push_back(waiting_[i].get(mol()));
 	}
@@ -609,7 +634,10 @@
 		write_coords_32(&fw, coords);
 	}
 
-	fw.unsigned_8(ships_coming_);
+	fw.unsigned_32(ships_coming_.size());
+	for (Ship* s : ships_coming_) {
+		fw.unsigned_32(mos.get_object_file_index(*s));
+	}
 
 	fw.unsigned_32(waiting_.size());
 	for (ShippingItem& shipping_item : waiting_) {

=== modified file 'src/economy/portdock.h'
--- src/economy/portdock.h	2019-07-05 11:16:24 +0000
+++ src/economy/portdock.h	2019-08-10 09:34:44 +0000
@@ -109,13 +109,13 @@
 
 	void shipping_item_arrived(Game&, ShippingItem&);
 	void shipping_item_returned(Game&, ShippingItem&);
-	void ship_coming(bool affirmative);
+	void ship_coming(Ship&, bool affirmative);
 	void ship_arrived(Game&, Ship&);
 
 	void log_general_info(const EditorGameBase&) const override;
 
 	uint32_t count_waiting(WareWorker waretype, DescriptionIndex wareindex) const;
-	uint32_t count_waiting() const;
+	uint32_t count_waiting(const PortDock* = nullptr) const;
 
 	// Returns true if a expedition is started or ready to be send out.
 	bool expedition_started() const;
@@ -147,7 +147,7 @@
 	Warehouse* warehouse_;
 	PositionList dockpoints_;
 	std::list<ShippingItem> waiting_;
-	uint8_t ships_coming_;
+	std::set<Ship*> ships_coming_;
 	bool expedition_ready_;
 
 	std::unique_ptr<ExpeditionBootstrap> expedition_bootstrap_;
@@ -165,6 +165,7 @@
 	private:
 		uint32_t warehouse_;
 		std::vector<ShippingItem::Loader> waiting_;
+		std::set<Serial> ships_coming_;
 	};
 
 public:

=== modified file 'src/economy/shippingitem.cc'
--- src/economy/shippingitem.cc	2019-04-24 06:51:31 +0000
+++ src/economy/shippingitem.cc	2019-08-10 09:34:44 +0000
@@ -139,13 +139,20 @@
 	}
 }
 
-constexpr uint16_t kCurrentPacketVersion = 1;
+constexpr uint16_t kCurrentPacketVersion = 2;
 
 void ShippingItem::Loader::load(FileRead& fr) {
 	try {
 		uint8_t packet_version = fr.unsigned_8();
-		if (packet_version == kCurrentPacketVersion) {
+		if (packet_version <= kCurrentPacketVersion) {
 			serial_ = fr.unsigned_32();
+			if (packet_version >= 2) {
+				destination_serial_ = fr.unsigned_32();
+			} else {
+				// TODO(Nordfriese): Remove when we break savegame compatibility
+				log("WARNING: Loading shippingitem with possible nullptr destination, which may result in bugs later\n");
+				destination_serial_ = 0;
+			}
 		} else {
 			throw UnhandledVersionError("ShippingItem", packet_version, kCurrentPacketVersion);
 		}
@@ -156,14 +163,17 @@
 
 ShippingItem ShippingItem::Loader::get(MapObjectLoader& mol) {
 	ShippingItem it;
-	if (serial_ != 0)
+	if (serial_ != 0) {
 		it.object_ = &mol.get<MapObject>(serial_);
+		it.destination_dock_ = destination_serial_ ? &mol.get<PortDock>(destination_serial_) : nullptr;
+	}
 	return it;
 }
 
 void ShippingItem::save(EditorGameBase& egbase, MapObjectSaver& mos, FileWrite& fw) {
 	fw.unsigned_8(kCurrentPacketVersion);
 	fw.unsigned_32(mos.get_object_file_index_or_zero(object_.get(egbase)));
+	fw.unsigned_32(mos.get_object_file_index_or_zero(destination_dock_.get(egbase)));
 }
 
 }  // namespace Widelands

=== modified file 'src/economy/shippingitem.h'
--- src/economy/shippingitem.h	2019-04-24 06:51:31 +0000
+++ src/economy/shippingitem.h	2019-08-10 09:34:44 +0000
@@ -63,11 +63,13 @@
 
 	private:
 		uint32_t serial_ = 0U;
+		uint32_t destination_serial_ = 0U;
 	};
 
 	void save(EditorGameBase& egbase, MapObjectSaver& mos, FileWrite& fw);
 
 private:
+	friend struct Fleet;
 	friend class PortDock;
 	friend struct Ship;
 

=== modified file 'src/economy/ware_instance.cc'
--- src/economy/ware_instance.cc	2019-05-25 10:47:18 +0000
+++ src/economy/ware_instance.cc	2019-08-10 09:34:44 +0000
@@ -107,7 +107,7 @@
 		return worker->get_location(game);
 
 	if (upcast(Ship, ship, loc)) {
-		if (PortDock* pd = ship->get_destination(game))
+		if (PortDock* pd = ship->get_current_destination(game))
 			return pd;
 
 		return ship->get_fleet()->get_arbitrary_dock();

=== modified file 'src/logic/map_objects/tribes/ship.cc'
--- src/logic/map_objects/tribes/ship.cc	2019-05-27 14:28:34 +0000
+++ src/logic/map_objects/tribes/ship.cc	2019-08-10 09:34:44 +0000
@@ -134,8 +134,8 @@
 Ship::~Ship() {
 }
 
-PortDock* Ship::get_destination(EditorGameBase& egbase) const {
-	return destination_.get(egbase);
+PortDock* Ship::get_current_destination(EditorGameBase& egbase) const {
+	return destinations_.empty() ? nullptr : destinations_.front().first.get(egbase);
 }
 
 PortDock* Ship::get_lastdock(EditorGameBase& egbase) const {
@@ -294,7 +294,7 @@
 bool Ship::ship_update_transport(Game& game, Bob::State& state) {
 	const Map& map = game.map();
 
-	PortDock* dst = get_destination(game);
+	PortDock* dst = get_current_destination(game);
 	if (!dst) {
 		// The ship has no destination, so let it sleep
 		ship_update_idle(game, state);
@@ -313,7 +313,7 @@
 		}
 
 		dst->ship_arrived(game, *this);  // This will also set the destination
-		dst = get_destination(game);
+		dst = get_current_destination(game);
 		if (dst) {
 			start_task_movetodock(game, *dst);
 		} else {
@@ -736,22 +736,209 @@
 	}
 }
 
+bool Ship::has_destination(EditorGameBase& egbase, const PortDock& pd) const {
+	for (const auto& pair : destinations_) {
+		if (pair.first.get(egbase) == &pd) {
+			return true;
+		}
+	}
+	return false;
+}
+
 /**
  * Enter a new destination port for the ship.
  * Call this after (un)loading the ship, for proper logging.
  */
-void Ship::set_destination(PortDock* pd) {
-	destination_ = pd;
-	if (pd) {
-		molog("set_destination / sending to portdock %u (carrying %" PRIuS " items)\n", pd->serial(),
-		      items_.size());
-		pd->ship_coming(true);
-	} else {
-		molog("set_destination / none\n");
+void Ship::push_destination(Game& game, PortDock& pd) {
+	for (auto it = destinations_.begin(); it != destinations_.end(); ++it) {
+		if (it->first.get(game) == &pd) {
+			// We're already going there
+			return;
+		}
 	}
+	destinations_.push_back(std::make_pair(OPtr<PortDock>(&pd), 1));
+	reorder_destinations(game);
+	molog("push_destination(%u): rerouted to portdock %u (carrying %" PRIuS " items)\n",
+			pd.serial(), get_current_destination(game)->serial(), items_.size());
+	pd.ship_coming(*this, true);
 	Notifications::publish(NoteShip(this, NoteShip::Action::kDestinationChanged));
 }
 
+void Ship::clear_destinations(Game& game) {
+	while (!destinations_.empty()) {
+		pop_destination(game, *destinations_.front().first.get(game));
+	}
+}
+
+/**
+ * Remove this destination from the queue
+ */
+void Ship::pop_destination(Game& game, PortDock& pd) {
+	pd.ship_coming(*this, false);
+	for (auto it = destinations_.begin(); it != destinations_.end(); ++it) {
+		if (it->first.get(game) == &pd) {
+			destinations_.erase(it);
+			reorder_destinations(game);
+			if (destinations_.empty()) {
+				molog("pop_destination(%u): no destinations and %" PRIuS " items left\n",
+						pd.serial(), items_.size());
+			} else {
+				molog("pop_destination(%u): rerouted to portdock %u (carrying %" PRIuS " items)\n",
+						pd.serial(), get_current_destination(game)->serial(), items_.size());
+			}
+			return;
+		}
+	}
+}
+
+// Recursively find the best ordering for our destinations
+static inline float prioritised_distance(Path& path, uint32_t priority, uint32_t items) {
+	return static_cast<float>(path.get_nsteps() * items) / (priority * priority);
+}
+using DestinationsQueue = std::vector<std::pair<PortDock*, uint32_t>>;
+static std::pair<DestinationsQueue, float> shortest_order(Game& game,
+                                                          Fleet& fleet,
+                                                          bool is_on_dock,
+                                                          void* start,
+                                                          const DestinationsQueue& remaining_to_visit,
+                                                          const std::map<PortDock*, uint32_t> shipping_items) {
+	const size_t nr_dests = remaining_to_visit.size();
+	assert(nr_dests > 0);
+	if (nr_dests == 1) {
+		// Recursion break: Only one portdock left
+		Path path;
+		if (is_on_dock) {
+			PortDock* p = static_cast<PortDock*>(start);
+			if (p != remaining_to_visit[0].first) {
+				fleet.get_path(*p, *remaining_to_visit[0].first, path);
+			}
+		} else {
+			static_cast<Ship*>(start)->calculate_sea_route(game, *remaining_to_visit[0].first, &path);
+		}
+		return std::pair<DestinationsQueue, float>(remaining_to_visit, prioritised_distance(
+				path, remaining_to_visit[0].second, shipping_items.at(remaining_to_visit[0].first)));
+	}
+
+	std::pair<DestinationsQueue, float> best_result;
+	best_result.second = std::numeric_limits<float>::max();
+	for (const auto& pair : remaining_to_visit) {
+		DestinationsQueue remaining;
+		for (const auto& p : remaining_to_visit) {
+			if (p.first != pair.first) {
+				remaining.push_back(p);
+			}
+		}
+		auto result = shortest_order(game, fleet, true, pair.first, remaining, shipping_items);
+		result.first.emplace(result.first.begin(), pair);
+		Path path;
+		if (is_on_dock) {
+			PortDock* p = static_cast<PortDock*>(start);
+			if (p != remaining_to_visit[0].first) {
+				fleet.get_path(*static_cast<PortDock*>(start), *pair.first, path);
+			}
+		} else {
+			static_cast<Ship*>(start)->calculate_sea_route(game, *pair.first, &path);
+		}
+		const float length = result.second + prioritised_distance(path, pair.second, shipping_items.at(pair.first));
+		if (length < best_result.second) {
+			best_result.first = result.first;
+			best_result.second = length;
+		}
+	}
+	assert(best_result.second < std::numeric_limits<float>::max());
+	assert(best_result.first.size() == nr_dests);
+	return best_result;
+}
+
+void Ship::reorder_destinations(Game& game) {
+	upcast(PortDock, pd, get_position().field->get_immovable());
+	size_t nr_dests = 0;
+	DestinationsQueue old_dq;
+	std::map<PortDock*, uint32_t> shipping_items;
+	for (const auto& pair : destinations_) {
+		PortDock* p = pair.first.get(game);
+		assert(p);
+		uint32_t nr_items = 0;
+		for (const auto& si : items_) {
+			if (si.get_destination(game) == p) {
+				++nr_items;
+			}
+		}
+		if (nr_items == 0 && p->count_waiting() == 0 && !p->expedition_started() && (!pd || pd->count_waiting(p) == 0)) {
+			// We don't need to go there anymore
+			p->ship_coming(*this, false);
+			continue;
+		}
+		old_dq.push_back(std::make_pair(p, pair.second));
+		++nr_dests;
+		shipping_items[p] = nr_items;
+	}
+	if (nr_dests <= 1) {
+		destinations_.clear();
+		if (nr_dests > 0) {
+			destinations_.push_back(old_dq[0]);
+		}
+		return;
+	}
+
+	const OPtr<PortDock> old_dest = destinations_.front().first;
+	DestinationsQueue dq = shortest_order(game, *fleet_, pd,
+			pd ? static_cast<void*>(pd) : static_cast<void*>(this), old_dq, shipping_items).first;
+	assert(dq.size() == nr_dests);
+
+	std::vector<std::pair<OPtr<PortDock>, uint32_t>> old_destinations = destinations_;
+	destinations_.clear();
+	size_t index = 0;
+	for (const auto& pair : dq) {
+		OPtr<PortDock> optr(pair.first);
+		uint32_t priority = pair.second;
+		size_t old_index = 0;
+		for (;; ++old_index) {
+			assert(old_index < nr_dests);
+			if (old_destinations[old_index].first == optr) {
+				break;
+			}
+		}
+		if (old_index < index) {
+			priority += index - old_index;
+		}
+		destinations_.push_back(std::make_pair(optr, priority));
+		++index;
+	}
+	if (old_dest != destinations_.front().first) {
+		send_signal(game, "wakeup");
+	}
+}
+
+/**
+ * Returns an estimation for the time in arbitarry units from now until the moment when
+ * this ship will probably arrive at the given PortDock. This may change later when
+ * destinations are added or removed.
+ * Returns -1 if we are not planning to visit this PortDock or if we are not planning
+ * to visit the given intermediate portdock earlier thaan the destination.
+ */
+int32_t Ship::estimated_arrival_time(Game& game, const PortDock& dest, const PortDock* intermediate) const {
+	uint32_t time = 0;
+	const PortDock* iterator = nullptr;
+	for (const auto& pair : destinations_) {
+		Path path;
+		if (iterator) {
+			fleet_->get_path(*iterator, *pair.first.get(game), path);
+		} else {
+			calculate_sea_route(game, *pair.first.get(game), &path);
+		}
+		iterator = pair.first.get(game);
+		if (iterator == intermediate) {
+			intermediate = nullptr;
+		}
+		time += path.get_nsteps();
+		if (iterator == &dest) {
+			return intermediate ? -1 : time;
+		}
+	}
+	return -1;
+}
+
 void Ship::add_item(Game& game, const ShippingItem& item) {
 	assert(items_.size() < descr().get_capacity());
 
@@ -782,23 +969,6 @@
 }
 
 /**
- * Unload all items not favored by given next dest.
- * Assert all items for current portdock have already been unloaded.
- */
-void Ship::unload_unfit_items(Game& game, PortDock& here, const PortDock& nextdest) {
-	size_t dst = 0;
-	for (ShippingItem& si : items_) {
-		const PortDock* dest = si.get_destination(game);
-		if (dest && fleet_->is_path_favourable(here, nextdest, *dest)) {
-			items_[dst++] = si;
-		} else {
-			here.shipping_item_returned(game, si);
-		}
-	}
-	items_.resize(dst);
-}
-
-/**
  * Find a path to the dock @p pd, returns its length, and the path optionally.
  */
 uint32_t Ship::calculate_sea_route(Game& game, PortDock& pd, Path* finalpath) const {
@@ -1032,7 +1202,7 @@
 	if ((draw_text & TextToDraw::kStatistics) != TextToDraw::kNone) {
 		switch (ship_state_) {
 		case (ShipStates::kTransport):
-			if (destination_.is_set()) {
+			if (!destinations_.empty()) {
 				/** TRANSLATORS: This is a ship state. The ship is currently transporting wares. */
 				statistics_string = pgettext("ship_state", "Shipping");
 			} else {
@@ -1073,25 +1243,25 @@
 void Ship::log_general_info(const EditorGameBase& egbase) const {
 	Bob::log_general_info(egbase);
 
-	molog("Ship belongs to fleet: %u\n destination: %s\n lastdock: %s\n",
+	molog("Ship belongs to fleet %u\nlastdock: %s\n",
 	      fleet_ ? fleet_->serial() : 0,
-	      (destination_.is_set()) ? (boost::format("%u (%d x %d)") % destination_.serial() %
-	                                 destination_.get(egbase)->get_positions(egbase)[0].x %
-	                                 destination_.get(egbase)->get_positions(egbase)[0].y)
-	                                   .str()
-	                                   .c_str() :
-	                                "-",
 	      (lastdock_.is_set()) ? (boost::format("%u (%d x %d)") % lastdock_.serial() %
 	                              lastdock_.get(egbase)->get_positions(egbase)[0].x %
 	                              lastdock_.get(egbase)->get_positions(egbase)[0].y)
 	                                .str()
 	                                .c_str() :
 	                             "-");
+	molog("Has %" PRIuS " destination(s):\n", destinations_.size());
+	for (const auto& pair : destinations_) {
+		molog("    · %u (%3dx%3d) (priority %u)\n",
+				pair.first.serial(), pair.first.get(egbase)->get_positions(egbase)[0].x,
+				pair.first.get(egbase)->get_positions(egbase)[0].y, pair.second);
+	}
 
 	molog("In state: %u (%s)\n", static_cast<unsigned int>(ship_state_),
 	      (expedition_) ? "expedition" : "transportation");
 
-	if (destination_.is_set() && get_position().field->get_immovable() == destination_.get(egbase)) {
+	if (!destinations_.empty() && get_position().field->get_immovable() == destinations_.front().first.get(egbase)) {
 		molog("Currently in destination portdock\n");
 	}
 
@@ -1149,7 +1319,7 @@
 ==============================
 */
 
-constexpr uint8_t kCurrentPacketVersion = 8;
+constexpr uint8_t kCurrentPacketVersion = 9;
 
 const Bob::Task* Ship::Loader::get_task(const std::string& name) {
 	if (name == "shipidle" || name == "ship")
@@ -1157,7 +1327,7 @@
 	return Bob::Loader::get_task(name);
 }
 
-void Ship::Loader::load(FileRead& fr) {
+void Ship::Loader::load(FileRead& fr, uint8_t packet_version) {
 	Bob::Loader::load(fr);
 
 	// Economy
@@ -1194,7 +1364,18 @@
 
 	shipname_ = fr.c_string();
 	lastdock_ = fr.unsigned_32();
-	destination_ = fr.unsigned_32();
+
+	if (packet_version >= 9) {
+		const uint32_t nr_dest = fr.unsigned_32();
+		for (uint32_t i = 0; i < nr_dest; ++i) {
+			const uint32_t s = fr.unsigned_32();
+			const uint32_t p = fr.unsigned_32();
+			destinations_.push_back(std::make_pair(s, p));
+		}
+	} else {
+		// TODO(Nordfriese): Remove when we break savegame compatibility
+		destinations_.push_back(std::make_pair(fr.unsigned_32(), 1));
+	}
 
 	items_.resize(fr.unsigned_32());
 	for (ShippingItem::Loader& item_loader : items_) {
@@ -1207,10 +1388,12 @@
 
 	Ship& ship = get<Ship>();
 
-	if (lastdock_)
+	if (lastdock_) {
 		ship.lastdock_ = &mol().get<PortDock>(lastdock_);
-	if (destination_)
-		ship.destination_ = &mol().get<PortDock>(destination_);
+	}
+	for (const auto& pair : destinations_) {
+		ship.destinations_.push_back(std::make_pair(&mol().get<PortDock>(pair.first), pair.second));
+	}
 
 	ship.items_.resize(items_.size());
 	for (uint32_t i = 0; i < items_.size(); ++i) {
@@ -1259,7 +1442,7 @@
 	try {
 		// The header has been peeled away by the caller
 		uint8_t const packet_version = fr.unsigned_8();
-		if (packet_version == kCurrentPacketVersion) {
+		if (packet_version >= 8 && packet_version <= kCurrentPacketVersion) {
 			try {
 				const ShipDescr* descr = nullptr;
 				// Removing this will break the test suite
@@ -1267,7 +1450,7 @@
 				const DescriptionIndex& ship_index = egbase.tribes().safe_ship_index(name);
 				descr = egbase.tribes().get_ship_descr(ship_index);
 				loader->init(egbase, mol, descr->create_object());
-				loader->load(fr);
+				loader->load(fr, packet_version);
 			} catch (const WException& e) {
 				throw GameDataError("Failed to load ship: %s", e.what());
 			}
@@ -1316,7 +1499,11 @@
 
 	fw.string(shipname_);
 	fw.unsigned_32(mos.get_object_file_index_or_zero(lastdock_.get(egbase)));
-	fw.unsigned_32(mos.get_object_file_index_or_zero(destination_.get(egbase)));
+	fw.unsigned_32(destinations_.size());
+	for (const auto& pair : destinations_) {
+		fw.unsigned_32(mos.get_object_file_index_or_zero(pair.first.get(egbase)));
+		fw.unsigned_32(pair.second);
+	}
 
 	fw.unsigned_32(items_.size());
 	for (ShippingItem& shipping_item : items_) {

=== modified file 'src/logic/map_objects/tribes/ship.h'
--- src/logic/map_objects/tribes/ship.h	2019-04-24 06:51:31 +0000
+++ src/logic/map_objects/tribes/ship.h	2019-08-10 09:34:44 +0000
@@ -96,7 +96,8 @@
 
 	// Returns the current destination or nullptr if there is no current
 	// destination.
-	PortDock* get_destination(EditorGameBase& egbase) const;
+	PortDock* get_current_destination(EditorGameBase& egbase) const;
+	bool has_destination(EditorGameBase&, const PortDock&) const;
 
 	// Returns the last visited portdock of this ship or nullptr if there is none or
 	// the last visited was removed.
@@ -106,7 +107,13 @@
 		return economy_;
 	}
 	void set_economy(Game&, Economy* e);
-	void set_destination(PortDock*);
+	void push_destination(Game&, PortDock&);
+	void pop_destination(Game&, PortDock&);
+	void clear_destinations(Game&);
+	int32_t estimated_arrival_time(Game&, const PortDock& dest, const PortDock* intermediate = nullptr) const;
+	size_t count_destinations() const {
+		return destinations_.size();
+	}
 
 	void init_auto_task(Game&) override;
 
@@ -130,7 +137,6 @@
 
 	void add_item(Game&, const ShippingItem&);
 	bool withdraw_item(Game&, PortDock&);
-	void unload_unfit_items(Game&, PortDock& here, const PortDock& nextdest);
 
 	// A ship with task expedition can be in four states: kExpeditionWaiting, kExpeditionScouting,
 	// kExpeditionPortspaceFound or kExpeditionColonizing in the first states, the owning player of
@@ -270,11 +276,17 @@
 	Fleet* fleet_;
 	Economy* economy_;
 	OPtr<PortDock> lastdock_;
-	OPtr<PortDock> destination_;
 	std::vector<ShippingItem> items_;
 	ShipStates ship_state_;
 	std::string shipname_;
 
+	// Our destinations in the order on which we are planning to visit them.
+	// When destinations are added or removed, the whole list will be reordered under
+	// the aspect of efficiency. Every time an entry is postponed, its priority will
+	// be increased to make it less likely that it will never be visited.
+	std::vector<std::pair<OPtr<PortDock>, uint32_t>> destinations_;
+	void reorder_destinations(Game&);
+
 	struct Expedition {
 		~Expedition();
 
@@ -294,14 +306,14 @@
 
 		const Task* get_task(const std::string& name) override;
 
-		void load(FileRead& fr);
+		void load(FileRead& fr, uint8_t);
 		void load_pointers() override;
 		void load_finish() override;
 
 	private:
 		// Initialize everything to make cppcheck happy.
 		uint32_t lastdock_ = 0U;
-		uint32_t destination_ = 0U;
+		std::vector<std::pair<uint32_t, uint32_t>> destinations_;
 		Serial economy_serial_;
 		ShipStates ship_state_ = ShipStates::kTransport;
 		std::string shipname_;

=== modified file 'src/scripting/lua_map.cc'
--- src/scripting/lua_map.cc	2019-06-23 11:41:17 +0000
+++ src/scripting/lua_map.cc	2019-08-10 09:34:44 +0000
@@ -5696,7 +5696,7 @@
 // UNTESTED
 int LuaShip::get_destination(lua_State* L) {
 	EditorGameBase& egbase = get_egbase(L);
-	return upcasted_map_object_to_lua(L, get(L, egbase)->get_destination(egbase));
+	return upcasted_map_object_to_lua(L, get(L, egbase)->get_current_destination(egbase));
 }
 
 /* RST

=== modified file 'src/wui/seafaring_statistics_menu.cc'
--- src/wui/seafaring_statistics_menu.cc	2019-06-25 07:34:58 +0000
+++ src/wui/seafaring_statistics_menu.cc	2019-08-10 09:34:44 +0000
@@ -260,7 +260,7 @@
 	ShipFilterStatus status = ShipFilterStatus::kAll;
 	switch (state) {
 	case Widelands::Ship::ShipStates::kTransport:
-		if (ship.get_destination(iplayer().game()) != nullptr) {
+		if (ship.get_current_destination(iplayer().game())) {
 			status = ShipFilterStatus::kShipping;
 		} else {
 			status = ShipFilterStatus::kIdle;

=== modified file 'src/wui/shipwindow.cc'
--- src/wui/shipwindow.cc	2019-02-23 11:00:49 +0000
+++ src/wui/shipwindow.cc	2019-08-10 09:34:44 +0000
@@ -233,7 +233,7 @@
 	}
 	bool can_act = igbase_.can_act(ship->owner().player_number());
 
-	btn_destination_->set_enabled(ship->get_destination(igbase_.egbase()));
+	btn_destination_->set_enabled(ship->get_current_destination(igbase_.egbase()));
 	btn_sink_->set_enabled(can_act);
 
 	display_->clear();
@@ -311,7 +311,7 @@
 	if (ship == nullptr) {
 		return;
 	}
-	if (PortDock* destination = ship->get_destination(igbase_.egbase())) {
+	if (PortDock* destination = ship->get_current_destination(igbase_.egbase())) {
 		igbase_.map_view()->scroll_to_field(
 		   destination->get_warehouse()->get_position(), MapView::Transition::Smooth);
 	}