(svn r25361) -Feature: distribute cargo according to plan given by linkgraph

16 files changed, 585 insertions, 205 deletions

diff --git a/src/cargoaction.cpp b/src/cargoaction.cpp
index 51e06f16a..9a13e5329 100644
--- a/src/cargoaction.cpp
+++ b/src/cargoaction.cpp
@@ -12,6 +12,7 @@
 #include "stdafx.h"
 #include "economy_base.h"
 #include "cargoaction.h"
+#include "station_base.h"
 
 /**
  * Decides if a packet needs to be split.
@@ -153,7 +154,7 @@ bool CargoReturn::operator()(CargoPacket *cp)
 	assert(cp_new->Count() <= this->destination->reserved_count);
 	this->source->RemoveFromMeta(cp_new, VehicleCargoList::MTA_LOAD, cp_new->Count());
 	this->destination->reserved_count -= cp_new->Count();
-	this->destination->Append(cp_new);
+	this->destination->Append(cp_new, this->next);
 	return cp_new == cp;
 }
 
@@ -167,8 +168,8 @@ bool CargoTransfer::operator()(CargoPacket *cp)
 	CargoPacket *cp_new = this->Preprocess(cp);
 	if (cp_new == NULL) return false;
 	this->source->RemoveFromMeta(cp_new, VehicleCargoList::MTA_TRANSFER, cp_new->Count());
-	cp_new->AddFeederShare(this->payment->PayTransfer(cp_new, cp_new->Count()));
-	this->destination->Append(cp_new);
+	/* No transfer credits here as they were already granted during Stage(). */
+	this->destination->Append(cp_new, cp_new->NextStation());
 	return cp_new == cp;
 }
 
@@ -186,6 +187,29 @@ bool CargoShift::operator()(CargoPacket *cp)
 	return cp_new == cp;
 }
 
+/**
+ * Reroutes some cargo from one Station sublist to another.
+ * @param cp Packet to be rerouted.
+ * @return True if the packet was completely rerouted, false if part of it was.
+ */
+bool CargoReroute::operator()(CargoPacket *cp)
+{
+	CargoPacket *cp_new = this->Preprocess(cp);
+	if (cp_new == NULL) cp_new = cp;
+	StationID next = this->ge->GetVia(cp_new->SourceStation(), this->avoid, this->avoid2);
+	assert(next != this->avoid && next != this->avoid2);
+	if (this->source != this->destination) {
+		this->source->RemoveFromCache(cp_new, cp_new->Count());
+		this->destination->AddToCache(cp_new);
+	}
+
+	/* Legal, as insert doesn't invalidate iterators in the MultiMap, however
+	 * this might insert the packet between range.first and range.second (which might be end())
+	 * This is why we check for GetKey above to avoid infinite loops. */
+	this->destination->packets.Insert(next, cp_new);
+	return cp_new == cp;
+}
+
 template uint CargoRemoval<VehicleCargoList>::Preprocess(CargoPacket *cp);
 template uint CargoRemoval<StationCargoList>::Preprocess(CargoPacket *cp);
 template bool CargoRemoval<VehicleCargoList>::Postprocess(CargoPacket *cp, uint remove);
diff --git a/src/cargoaction.h b/src/cargoaction.h
index d59f05279..b6879fb76 100644
--- a/src/cargoaction.h
+++ b/src/cargoaction.h
@@ -71,11 +71,9 @@ public:
 
 /** Action of transferring cargo from a vehicle to a station. */
 class CargoTransfer : public CargoMovement<VehicleCargoList, StationCargoList> {
-protected:
-	CargoPayment *payment;  ///< Payment object for registering transfer credits.
 public:
-	CargoTransfer(VehicleCargoList *source, StationCargoList *destination, uint max_move, CargoPayment *payment) :
-			CargoMovement<VehicleCargoList, StationCargoList>(source, destination, max_move), payment(payment) {}
+	CargoTransfer(VehicleCargoList *source, StationCargoList *destination, uint max_move) :
+			CargoMovement<VehicleCargoList, StationCargoList>(source, destination, max_move) {}
 	bool operator()(CargoPacket *cp);
 };
 
@@ -99,9 +97,10 @@ public:
 
 /** Action of returning previously reserved cargo from the vehicle to the station. */
 class CargoReturn: public CargoMovement<VehicleCargoList, StationCargoList> {
+	StationID next;
 public:
-	CargoReturn(VehicleCargoList *source, StationCargoList *destination, uint max_move) :
-			CargoMovement<VehicleCargoList, StationCargoList>(source, destination, max_move) {}
+	CargoReturn(VehicleCargoList *source, StationCargoList *destination, uint max_move, StationID next) :
+			CargoMovement<VehicleCargoList, StationCargoList>(source, destination, max_move), next(next) {}
 	bool operator()(CargoPacket *cp);
 };
 
@@ -113,4 +112,16 @@ public:
 	bool operator()(CargoPacket *cp);
 };
 
+/** Action of rerouting cargo between different station cargo lists and/or next hops. */
+class CargoReroute : public CargoMovement<StationCargoList, StationCargoList> {
+protected:
+	StationID avoid;
+	StationID avoid2;
+	const GoodsEntry *ge;
+public:
+	CargoReroute(StationCargoList *source, StationCargoList *dest, uint max_move, StationID avoid, StationID avoid2, const GoodsEntry *ge) :
+			CargoMovement<StationCargoList, StationCargoList>(source, dest, max_move), avoid(avoid), avoid2(avoid2), ge(ge) {}
+	bool operator()(CargoPacket *cp);
+};
+
 #endif /* CARGOACTION_H */
diff --git a/src/cargopacket.cpp b/src/cargopacket.cpp
index 56ab6b91c..16a5e61b1 100644
--- a/src/cargopacket.cpp
+++ b/src/cargopacket.cpp
@@ -10,7 +10,9 @@
 /** @file cargopacket.cpp Implementation of the cargo packets. */
 
 #include "stdafx.h"
+#include "station_base.h"
 #include "core/pool_func.hpp"
+#include "core/random_func.hpp"
 #include "economy_base.h"
 #include "cargoaction.h"
 #include "order_type.h"
@@ -151,8 +153,8 @@ void CargoPacket::Reduce(uint count)
 /**
  * Destroy the cargolist ("frees" all cargo packets).
  */
-template <class Tinst>
-CargoList<Tinst>::~CargoList()
+template <class Tinst, class Tcont>
+CargoList<Tinst, Tcont>::~CargoList()
 {
 	for (Iterator it(this->packets.begin()); it != this->packets.end(); ++it) {
 		delete *it;
@@ -163,8 +165,8 @@ CargoList<Tinst>::~CargoList()
  * Empty the cargo list, but don't free the cargo packets;
  * the cargo packets are cleaned by CargoPacket's CleanPool.
  */
-template <class Tinst>
-void CargoList<Tinst>::OnCleanPool()
+template <class Tinst, class Tcont>
+void CargoList<Tinst, Tcont>::OnCleanPool()
 {
 	this->packets.clear();
 }
@@ -175,8 +177,8 @@ void CargoList<Tinst>::OnCleanPool()
  * @param cp Packet to be removed from cache.
  * @param count Amount of cargo from the given packet to be removed.
  */
-template <class Tinst>
-void CargoList<Tinst>::RemoveFromCache(const CargoPacket *cp, uint count)
+template <class Tinst, class Tcont>
+void CargoList<Tinst, Tcont>::RemoveFromCache(const CargoPacket *cp, uint count)
 {
 	assert(count <= cp->count);
 	this->count                 -= count;
@@ -188,83 +190,16 @@ void CargoList<Tinst>::RemoveFromCache(const CargoPacket *cp, uint count)
  * Increases count and days_in_transit.
  * @param cp New packet to be inserted.
  */
-template <class Tinst>
-void CargoList<Tinst>::AddToCache(const CargoPacket *cp)
+template <class Tinst, class Tcont>
+void CargoList<Tinst, Tcont>::AddToCache(const CargoPacket *cp)
 {
 	this->count                 += cp->count;
 	this->cargo_days_in_transit += cp->days_in_transit * cp->count;
 }
 
-/**
- * Truncates the cargo in this list to the given amount. It leaves the
- * first cargo entities and removes max_move from the back of the list.
- * @param max_move Maximum amount of entities to be removed from the list.
- * @return Amount of entities actually moved.
- */
-template <class Tinst>
-uint CargoList<Tinst>::Truncate(uint max_move)
-{
-	max_move = min(this->count, max_move);
-	this->PopCargo(CargoRemoval<Tinst>(static_cast<Tinst *>(this), max_move));
-	return max_move;
-}
-
-/**
- * Shifts cargo from the front of the packet list and applies some action to it.
- * @tparam Taction Action class or function to be used. It should define
- *                 "bool operator()(CargoPacket *)". If true is returned the
- *                 cargo packet will be removed from the list. Otherwise it
- *                 will be kept and the loop will be aborted.
- * @param action Action instance to be applied.
- */
-template <class Tinst>
-template <class Taction>
-void CargoList<Tinst>::ShiftCargo(Taction action)
-{
-	Iterator it(this->packets.begin());
-	while (it != this->packets.end() && action.MaxMove() > 0) {
-		CargoPacket *cp = *it;
-		if (action(cp)) {
-			it = this->packets.erase(it);
-		} else {
-			break;
-		}
-	}
-}
-
-/**
- * Pops cargo from the back of the packet list and applies some action to it.
- * @tparam Taction Action class or function to be used. It should define
- *                 "bool operator()(CargoPacket *)". If true is returned the
- *                 cargo packet will be removed from the list. Otherwise it
- *                 will be kept and the loop will be aborted.
- * @param action Action instance to be applied.
- */
-template <class Tinst>
-template <class Taction>
-void CargoList<Tinst>::PopCargo(Taction action)
-{
-	if (this->packets.empty()) return;
-	Iterator it(--(this->packets.end()));
-	Iterator begin(this->packets.begin());
-	while (action.MaxMove() > 0) {
-		CargoPacket *cp = *it;
-		if (action(cp)) {
-			if (it != begin) {
-				this->packets.erase(it--);
-			} else {
-				this->packets.erase(it);
-				break;
-			}
-		} else {
-			break;
-		}
-	}
-}
-
 /** Invalidates the cached data and rebuilds it. */
-template <class Tinst>
-void CargoList<Tinst>::InvalidateCache()
+template <class Tinst, class Tcont>
+void CargoList<Tinst, Tcont>::InvalidateCache()
 {
 	this->count = 0;
 	this->cargo_days_in_transit = 0;
@@ -281,11 +216,11 @@ void CargoList<Tinst>::InvalidateCache()
  * @param cp Packet to be eliminated.
  * @return If the packets could be merged.
  */
-template <class Tinst>
-/* static */ bool CargoList<Tinst>::TryMerge(CargoPacket *icp, CargoPacket *cp)
+template <class Tinst, class Tcont>
+/* static */ bool CargoList<Tinst, Tcont>::TryMerge(CargoPacket *icp, CargoPacket *cp)
 {
 	if (Tinst::AreMergable(icp, cp) &&
-				icp->count + cp->count <= CargoPacket::MAX_COUNT) {
+			icp->count + cp->count <= CargoPacket::MAX_COUNT) {
 		icp->Merge(cp);
 		return true;
 	} else {
@@ -341,6 +276,57 @@ void VehicleCargoList::Append(CargoPacket *cp, MoveToAction action)
 }
 
 /**
+ * Shifts cargo from the front of the packet list and applies some action to it.
+ * @tparam Taction Action class or function to be used. It should define
+ *                 "bool operator()(CargoPacket *)". If true is returned the
+ *                 cargo packet will be removed from the list. Otherwise it
+ *                 will be kept and the loop will be aborted.
+ * @param action Action instance to be applied.
+ */
+template<class Taction>
+void VehicleCargoList::ShiftCargo(Taction action)
+{
+	Iterator it(this->packets.begin());
+	while (it != this->packets.end() && action.MaxMove() > 0) {
+		CargoPacket *cp = *it;
+		if (action(cp)) {
+			it = this->packets.erase(it);
+		} else {
+			break;
+		}
+	}
+}
+
+/**
+ * Pops cargo from the back of the packet list and applies some action to it.
+ * @tparam Taction Action class or function to be used. It should define
+ *                 "bool operator()(CargoPacket *)". If true is returned the
+ *                 cargo packet will be removed from the list. Otherwise it
+ *                 will be kept and the loop will be aborted.
+ * @param action Action instance to be applied.
+ */
+template<class Taction>
+void VehicleCargoList::PopCargo(Taction action)
+{
+	if (this->packets.empty()) return;
+	Iterator it(--(this->packets.end()));
+	Iterator begin(this->packets.begin());
+	while (action.MaxMove() > 0) {
+		CargoPacket *cp = *it;
+		if (action(cp)) {
+			if (it != begin) {
+				this->packets.erase(it--);
+			} else {
+				this->packets.erase(it);
+				break;
+			}
+		} else {
+			break;
+		}
+	}
+}
+
+/**
  * Update the cached values to reflect the removal of this packet or part of it.
  * Decreases count, feeder share and days_in_transit.
  * @param cp Packet to be removed from cache.
@@ -406,16 +392,36 @@ void VehicleCargoList::AgeCargo()
 }
 
 /**
+ * Sets loaded_at_xy to the current station for all cargo to be transfered.
+ * This is done when stopping or skipping while the vehicle is unloading. In
+ * that case the vehicle will get part of its transfer credits early and it may
+ * get more transfer credits than it's entitled to.
+ * @param xy New loaded_at_xy for the cargo.
+ */
+void VehicleCargoList::SetTransferLoadPlace(TileIndex xy)
+{
+	uint sum = 0;
+	for (Iterator it = this->packets.begin(); sum < this->action_counts[MTA_TRANSFER]; ++it) {
+		CargoPacket *cp = *it;
+		cp->loaded_at_xy = xy;
+		sum += cp->count;
+	}
+}
+
+/**
  * Stages cargo for unloading. The cargo is sorted so that packets to be
  * transferred, delivered or kept are in consecutive chunks in the list. At the
  * same time the designation_counts are updated to reflect the size of those
  * chunks.
  * @param accepted If the cargo will be accepted at the station.
  * @param current_station ID of the station.
+ * @param next_station ID of the station the vehicle will go to next.
  * @param order_flags OrderUnloadFlags that will apply to the unload operation.
+ * @param ge GoodsEntry for getting the flows.
+ * @param payment Payment object for registering transfers.
  * return If any cargo will be unloaded.
  */
-bool VehicleCargoList::Stage(bool accepted, StationID current_station, uint8 order_flags)
+bool VehicleCargoList::Stage(bool accepted, StationID current_station, StationID next_station, uint8 order_flags, const GoodsEntry *ge, CargoPayment *payment)
 {
 	this->AssertCountConsistency();
 	assert(this->action_counts[MTA_LOAD] == 0);
@@ -423,20 +429,59 @@ bool VehicleCargoList::Stage(bool accepted, StationID current_station, uint8 ord
 	Iterator deliver = this->packets.end();
 	Iterator it = this->packets.begin();
 	uint sum = 0;
+
+	bool force_keep = (order_flags & OUFB_NO_UNLOAD) != 0;
+	bool force_unload = (order_flags & OUFB_UNLOAD) != 0;
+	bool force_transfer = (order_flags & (OUFB_TRANSFER | OUFB_UNLOAD)) != 0;
+	assert(this->count > 0 || it == this->packets.end());
 	while (sum < this->count) {
 		CargoPacket *cp = *it;
+
 		this->packets.erase(it++);
-		if ((order_flags & OUFB_TRANSFER) != 0 || (!accepted && (order_flags & OUFB_UNLOAD) != 0)) {
-			this->packets.push_front(cp);
-			this->action_counts[MTA_TRANSFER] += cp->count;
-		} else if (accepted && current_station != cp->source && (order_flags & OUFB_NO_UNLOAD) == 0) {
-			this->packets.insert(deliver, cp);
-			this->action_counts[MTA_DELIVER] += cp->count;
+		StationID cargo_next = INVALID_STATION;
+		MoveToAction action = MTA_LOAD;
+		if (force_keep) {
+			action = MTA_KEEP;
+		} else if (force_unload && accepted && cp->source != current_station) {
+			action = MTA_DELIVER;
+		} else if (force_transfer) {
+			action = MTA_TRANSFER;
+			cargo_next = ge->GetVia(cp->source, current_station, next_station);
+			assert((cargo_next != next_station || cargo_next == INVALID_STATION) &&
+					cargo_next != current_station);
 		} else {
-			this->packets.push_back(cp);
-			if (deliver == this->packets.end()) --deliver;
-			this->action_counts[MTA_KEEP] += cp->count;
+			cargo_next = ge->GetVia(cp->source);
+			if (cargo_next == INVALID_STATION) {
+				action = (accepted && cp->source != current_station) ? MTA_DELIVER : MTA_KEEP;
+			} else if (cargo_next == current_station) {
+				action = MTA_DELIVER;
+			} else if (cargo_next == next_station) {
+				action = MTA_KEEP;
+			} else {
+				action = MTA_TRANSFER;
+			}
+		}
+		Money share;
+		switch (action) {
+			case MTA_KEEP:
+				this->packets.push_back(cp);
+				if (deliver == this->packets.end()) --deliver;
+				break;
+			case MTA_DELIVER:
+				this->packets.insert(deliver, cp);
+				break;
+			case MTA_TRANSFER:
+				this->packets.push_front(cp);
+				/* Add feeder share here to allow reusing field for next station. */
+				share = payment->PayTransfer(cp, cp->count);
+				cp->AddFeederShare(share);
+				this->feeder_share += share;
+				cp->next_station = cargo_next;
+				break;
+			default:
+				NOT_REACHED();
 		}
+		this->action_counts[action] += cp->count;
 		sum += cp->count;
 	}
 	this->AssertCountConsistency();
@@ -468,14 +513,15 @@ uint VehicleCargoList::Reassign(uint max_move, MoveToAction from, MoveToAction t
 
 /**
  * Returns reserved cargo to the station and removes it from the cache.
- * @param dest Station the cargo is returned to.
  * @param max_move Maximum amount of cargo to move.
+ * @param dest Station the cargo is returned to.
+ * @param ID of next the station the cargo wants to go next.
  * @return Amount of cargo actually returned.
  */
-uint VehicleCargoList::Return(uint max_move, StationCargoList *dest)
+uint VehicleCargoList::Return(uint max_move, StationCargoList *dest, StationID next)
 {
 	max_move = min(this->action_counts[MTA_LOAD], max_move);
-	this->PopCargo(CargoReturn(this, dest, max_move));
+	this->PopCargo(CargoReturn(this, dest, max_move, next));
 	return max_move;
 }
 
@@ -505,7 +551,7 @@ uint VehicleCargoList::Unload(uint max_move, StationCargoList *dest, CargoPaymen
 	uint moved = 0;
 	if (this->action_counts[MTA_TRANSFER] > 0) {
 		uint move = min(this->action_counts[MTA_TRANSFER], max_move);
-		this->ShiftCargo(CargoTransfer(this, dest, move, payment));
+		this->ShiftCargo(CargoTransfer(this, dest, move));
 		moved += move;
 	}
 	if (this->action_counts[MTA_TRANSFER] == 0 && this->action_counts[MTA_DELIVER] > 0 && moved < max_move) {
@@ -516,6 +562,19 @@ uint VehicleCargoList::Unload(uint max_move, StationCargoList *dest, CargoPaymen
 	return moved;
 }
 
+/**
+ * Truncates the cargo in this list to the given amount. It leaves the
+ * first cargo entities and removes max_move from the back of the list.
+ * @param max_move Maximum amount of entities to be removed from the list.
+ * @return Amount of entities actually moved.
+ */
+uint VehicleCargoList::Truncate(uint max_move)
+{
+	max_move = min(this->count, max_move);
+	this->PopCargo(CargoRemoval<VehicleCargoList>(this, max_move));
+	return max_move;
+}
+
 /*
  *
  * Station cargo list implementation.
@@ -523,24 +582,112 @@ uint VehicleCargoList::Unload(uint max_move, StationCargoList *dest, CargoPaymen
  */
 
 /**
- * Appends the given cargo packet. Tries to merge it with another one in the
- * packets list. If no fitting packet is found, appends it.
+ * Appends the given cargo packet to the range of packets with the same next station
  * @warning After appending this packet may not exist anymore!
  * @note Do not use the cargo packet anymore after it has been appended to this CargoList!
- * @param cp Cargo packet to add.
+ * @param next the next hop
+ * @param cp the cargo packet to add
  * @pre cp != NULL
  */
-void StationCargoList::Append(CargoPacket *cp)
+void StationCargoList::Append(CargoPacket *cp, StationID next)
 {
 	assert(cp != NULL);
 	this->AddToCache(cp);
 
-	for (List::reverse_iterator it(this->packets.rbegin()); it != this->packets.rend(); it++) {
+	StationCargoPacketMap::List &list = this->packets[next];
+	for (StationCargoPacketMap::List::reverse_iterator it(list.rbegin());
+			it != list.rend(); it++) {
 		if (StationCargoList::TryMerge(*it, cp)) return;
 	}
 
 	/* The packet could not be merged with another one */
-	this->packets.push_back(cp);
+	list.push_back(cp);
+}
+
+/**
+ * Shifts cargo from the front of the packet list for a specific station and
+ * applies some action to it.
+ * @tparam Taction Action class or function to be used. It should define
+ *                 "bool operator()(CargoPacket *)". If true is returned the
+ *                 cargo packet will be removed from the list. Otherwise it
+ *                 will be kept and the loop will be aborted.
+ * @param action Action instance to be applied.
+ * @param next Next hop the cargo wants to visit.
+ * @return True if all packets with the given next hop have been removed,
+ *         False otherwise.
+ */
+template <class Taction>
+bool StationCargoList::ShiftCargo(Taction &action, StationID next)
+{
+	std::pair<Iterator, Iterator> range(this->packets.equal_range(next));
+	for (Iterator it(range.first); it != range.second && it.GetKey() == next;) {
+		if (action.MaxMove() == 0) return false;
+		CargoPacket *cp = *it;
+		if (action(cp)) {
+			it = this->packets.erase(it);
+		} else {
+			return false;
+		}
+	}
+	return true;
+}
+
+/**
+ * Shifts cargo from the front of the packet list for a specific station and
+ * and optional also from the list for "any station", then applies some action
+ * to it.
+ * @tparam Taction Action class or function to be used. It should define
+ *                 "bool operator()(CargoPacket *)". If true is returned the
+ *                 cargo packet will be removed from the list. Otherwise it
+ *                 will be kept and the loop will be aborted.
+ * @param action Action instance to be applied.
+ * @param next Next hop the cargo wants to visit.
+ * @param include_invalid If cargo from the INVALID_STATION list should be
+ *                        used if necessary.
+ * @return Amount of cargo actually moved.
+ */
+template <class Taction>
+uint StationCargoList::ShiftCargo(Taction action, StationID next, bool include_invalid)
+{
+	uint max_move = action.MaxMove();
+	if (this->ShiftCargo(action, next) && include_invalid && action.MaxMove() > 0) {
+		this->ShiftCargo(action, INVALID_STATION);
+	}
+	return max_move - action.MaxMove();
+}
+
+/**
+ * Truncates where each destination loses roughly the same percentage of its
+ * cargo. This is done by randomizing the selection of packets to be removed.
+ * @param max_move Maximum amount of cargo to remove.
+ * @return Amount of cargo actually moved.
+ */
+uint StationCargoList::Truncate(uint max_move)
+{
+	max_move = min(max_move, this->count);
+	uint prev_count = this->count;
+	uint moved = 0;
+	while (max_move > moved) {
+		for (Iterator it(this->packets.begin()); it != this->packets.end();) {
+			if (prev_count > max_move && RandomRange(prev_count) < prev_count - max_move) {
+				++it;
+				continue;
+			}
+			CargoPacket *cp = *it;
+			uint diff = max_move - moved;
+			if (cp->count > diff) {
+				this->RemoveFromCache(cp, diff);
+				cp->Reduce(diff);
+				return moved + diff;
+			} else {
+				it = this->packets.erase(it);
+				moved += cp->count;
+				this->RemoveFromCache(cp, cp->count);
+				delete cp;
+			}
+		}
+	}
+	return moved;
 }
 
 /**
@@ -550,10 +697,10 @@ void StationCargoList::Append(CargoPacket *cp)
  * @param load_place Tile index of the current station.
  * @return Amount of cargo actually reserved.
  */
-uint StationCargoList::Reserve(uint max_move, VehicleCargoList *dest, TileIndex load_place)
+uint StationCargoList::Reserve(uint max_move, VehicleCargoList *dest, TileIndex load_place, StationID next)
 {
 	max_move = min(this->count, max_move);
-	this->ShiftCargo(CargoReservation(this, dest, max_move, load_place));
+	this->ShiftCargo(CargoReservation(this, dest, max_move, load_place), next, true);
 	return max_move;
 }
 
@@ -564,21 +711,34 @@ uint StationCargoList::Reserve(uint max_move, VehicleCargoList *dest, TileIndex
  * @param max_move Amount of cargo to load.
  * @return Amount of cargo actually loaded.
  */
-uint StationCargoList::Load(uint max_move, VehicleCargoList *dest, TileIndex load_place)
+uint StationCargoList::Load(uint max_move, VehicleCargoList *dest, TileIndex load_place, StationID next_station)
 {
 	uint move = min(dest->ActionCount(VehicleCargoList::MTA_LOAD), max_move);
 	if (move > 0) {
 		this->reserved_count -= move;
 		dest->Reassign(move, VehicleCargoList::MTA_LOAD, VehicleCargoList::MTA_KEEP);
+		return move;
 	} else {
 		move = min(this->count, max_move);
-		this->ShiftCargo(CargoLoad(this, dest, move, load_place));
+		return this->ShiftCargo(CargoLoad(this, dest, move, load_place), next_station, true);
 	}
-	return move;
+}
+
+/**
+ * Routes packets with station "avoid" as next hop to a different place.
+ * @param max_move Maximum amount of cargo to move.
+ * @param dest List to append the cargo to.
+ * @param avoid Station to exclude from routing and current next hop of packets to reroute.
+ * @param avoid2 Additional station to exclude from routing.
+ * @oaram ge GoodsEntry to get the routing info from.
+ */
+uint StationCargoList::Reroute(uint max_move, StationCargoList *dest, StationID avoid, StationID avoid2, const GoodsEntry *ge)
+{
+	return this->ShiftCargo(CargoReroute(this, dest, max_move, avoid, avoid2, ge), avoid, false);
 }
 
 /*
  * We have to instantiate everything we want to be usable.
  */
-template class CargoList<VehicleCargoList>;
-template class CargoList<StationCargoList>;
+template class CargoList<VehicleCargoList, CargoPacketList>;
+template class CargoList<StationCargoList, StationCargoPacketMap>;
diff --git a/src/cargopacket.h b/src/cargopacket.h
index 15b233fd0..c31e4db58 100644
--- a/src/cargopacket.h
+++ b/src/cargopacket.h
@@ -15,8 +15,10 @@
 #include "core/pool_type.hpp"
 #include "economy_type.h"
 #include "station_type.h"
+#include "order_type.h"
 #include "cargo_type.h"
 #include "vehicle_type.h"
+#include "core/multimap.hpp"
 #include <list>
 
 /** Unique identifier for a single cargo packet. */
@@ -28,10 +30,14 @@ typedef Pool<CargoPacket, CargoPacketID, 1024, 0xFFF000, PT_NORMAL, true, false>
 /** The actual pool with cargo packets. */
 extern CargoPacketPool _cargopacket_pool;
 
-template <class Tinst> class CargoList;
+struct GoodsEntry; // forward-declare for Stage() and RerouteStalePackets()
+
+template <class Tinst, class Tcont> class CargoList;
 class StationCargoList; // forward-declare, so we can use it in VehicleCargoList.
 extern const struct SaveLoad *GetCargoPacketDesc();
 
+typedef uint32 TileOrStationID;
+
 /**
  * Container for cargo from the same location and time.
  */
@@ -44,10 +50,13 @@ private:
 	SourceID source_id;         ///< Index of source, INVALID_SOURCE if unknown/invalid.
 	StationID source;           ///< The station where the cargo came from first.
 	TileIndex source_xy;        ///< The origin of the cargo (first station in feeder chain).
-	TileIndex loaded_at_xy;     ///< Location where this cargo has been loaded into the vehicle.
+	union {
+		TileOrStationID loaded_at_xy; ///< Location where this cargo has been loaded into the vehicle.
+		TileOrStationID next_station; ///< Station where the cargo wants to go next.
+	};
 
 	/** The CargoList caches, thus needs to know about it. */
-	template <class Tinst> friend class CargoList;
+	template <class Tinst, class Tcont> friend class CargoList;
 	friend class VehicleCargoList;
 	friend class StationCargoList;
 	/** We want this to be saved, right? */
@@ -165,6 +174,14 @@ public:
 		return this->loaded_at_xy;
 	}
 
+	/**
+	 * Gets the ID of station the cargo wants to go next.
+	 * @return Next station for this packets.
+	 */
+	inline StationID NextStation() const
+	{
+		return this->next_station;
+	}
 
 	static void InvalidateAllFrom(SourceType src_type, SourceID src);
 	static void InvalidateAllFrom(StationID sid);
@@ -188,19 +205,17 @@ public:
  * Simple collection class for a list of cargo packets.
  * @tparam Tinst Actual instantiation of this cargo list.
  */
-template <class Tinst>
+template <class Tinst, class Tcont>
 class CargoList {
 public:
-	/** Container with cargo packets. */
-	typedef std::list<CargoPacket *> List;
 	/** The iterator for our container. */
-	typedef List::iterator Iterator;
+	typedef typename Tcont::iterator Iterator;
 	/** The reverse iterator for our container. */
-	typedef List::reverse_iterator ReverseIterator;
+	typedef typename Tcont::reverse_iterator ReverseIterator;
 	/** The const iterator for our container. */
-	typedef List::const_iterator ConstIterator;
+	typedef typename Tcont::const_iterator ConstIterator;
 	/** The const reverse iterator for our container. */
-	typedef List::const_reverse_iterator ConstReverseIterator;
+	typedef typename Tcont::const_reverse_iterator ConstReverseIterator;
 
 	/** Kind of actions that could be done with packets on move. */
 	enum MoveToAction {
@@ -217,18 +232,12 @@ protected:
 	uint count;                 ///< Cache for the number of cargo entities.
 	uint cargo_days_in_transit; ///< Cache for the sum of number of days in transit of each entity; comparable to man-hours.
 
-	List packets;               ///< The cargo packets in this list.
+	Tcont packets;              ///< The cargo packets in this list.
 
 	void AddToCache(const CargoPacket *cp);
 
 	void RemoveFromCache(const CargoPacket *cp, uint count);
 
-	template<class Taction>
-	void ShiftCargo(Taction action);
-
-	template<class Taction>
-	void PopCargo(Taction action);
-
 	static bool TryMerge(CargoPacket *cp, CargoPacket *icp);
 
 public:
@@ -243,21 +252,12 @@ public:
 	 * Returns a pointer to the cargo packet list (so you can iterate over it etc).
 	 * @return Pointer to the packet list.
 	 */
-	inline const List *Packets() const
+	inline const Tcont *Packets() const
 	{
 		return &this->packets;
 	}
 
 	/**
-	 * Returns source of the first cargo packet in this list.
-	 * @return The before mentioned source.
-	 */
-	inline StationID Source() const
-	{
-		return this->count == 0 ? INVALID_STATION : this->packets.front()->source;
-	}
-
-	/**
 	 * Returns average number of days in transit for a cargo entity.
 	 * @return The before mentioned number.
 	 */
@@ -266,22 +266,28 @@ public:
 		return this->count == 0 ? 0 : this->cargo_days_in_transit / this->count;
 	}
 
-	uint Truncate(uint max_move = UINT_MAX);
-
 	void InvalidateCache();
 };
 
+typedef std::list<CargoPacket *> CargoPacketList;
+
 /**
  * CargoList that is used for vehicles.
  */
-class VehicleCargoList : public CargoList<VehicleCargoList> {
+class VehicleCargoList : public CargoList<VehicleCargoList, CargoPacketList> {
 protected:
 	/** The (direct) parent of this class. */
-	typedef CargoList<VehicleCargoList> Parent;
+	typedef CargoList<VehicleCargoList, CargoPacketList> Parent;
 
 	Money feeder_share;                     ///< Cache for the feeder share.
 	uint action_counts[NUM_MOVE_TO_ACTION]; ///< Counts of cargo to be transfered, delivered, kept and loaded.
 
+	template<class Taction>
+	void ShiftCargo(Taction action);
+
+	template<class Taction>
+	void PopCargo(Taction action);
+
 	/**
 	 * Assert that the designation counts add up.
 	 */
@@ -300,8 +306,10 @@ protected:
 	void RemoveFromMeta(const CargoPacket *cp, MoveToAction action, uint count);
 
 public:
+	/** The station cargo list needs to control the unloading. */
+	friend class StationCargoList;
 	/** The super class ought to know what it's doing. */
-	friend class CargoList<VehicleCargoList>;
+	friend class CargoList<VehicleCargoList, CargoPacketList>;
 	/** The vehicles have a cargo list (and we want that saved). */
 	friend const struct SaveLoad *GetVehicleDescription(VehicleType vt);
 
@@ -313,6 +321,15 @@ public:
 	friend class CargoReturn;
 
 	/**
+	 * Returns source of the first cargo packet in this list.
+	 * @return The before mentioned source.
+	 */
+	inline StationID Source() const
+	{
+		return this->count == 0 ? INVALID_STATION : this->packets.front()->source;
+	}
+
+	/**
 	 * Returns total sum of the feeder share for all packets.
 	 * @return The before mentioned number.
 	 */
@@ -383,7 +400,9 @@ public:
 
 	void InvalidateCache();
 
-	bool Stage(bool accepted, StationID current_station, uint8 order_flags);
+	void SetTransferLoadPlace(TileIndex xy);
+
+	bool Stage(bool accepted, StationID current_station, StationID next_station, uint8 order_flags, const GoodsEntry *ge, CargoPayment *payment);
 
 	/**
 	 * Marks all cargo in the vehicle as to be kept. This is mostly useful for
@@ -401,9 +420,10 @@ public:
 	 * applicable), return value is amount of cargo actually moved. */
 
 	uint Reassign(uint max_move, MoveToAction from, MoveToAction to);
-	uint Return(uint max_move, StationCargoList *dest);
+	uint Return(uint max_move, StationCargoList *dest, StationID next_station);
 	uint Unload(uint max_move, StationCargoList *dest, CargoPayment *payment);
 	uint Shift(uint max_move, VehicleCargoList *dest);
+	uint Truncate(uint max_move = UINT_MAX);
 
 	/**
 	 * Are two the two CargoPackets mergeable in the context of
@@ -422,19 +442,21 @@ public:
 	}
 };
 
+typedef MultiMap<StationID, CargoPacket *> StationCargoPacketMap;
+
 /**
  * CargoList that is used for stations.
  */
-class StationCargoList : public CargoList<StationCargoList> {
+class StationCargoList : public CargoList<StationCargoList, StationCargoPacketMap> {
 protected:
 	/** The (direct) parent of this class. */
-	typedef CargoList<StationCargoList> Parent;
+	typedef CargoList<StationCargoList, StationCargoPacketMap> Parent;
 
 	uint reserved_count; ///< Amount of cargo being reserved for loading.
 
 public:
 	/** The super class ought to know what it's doing. */
-	friend class CargoList<StationCargoList>;
+	friend class CargoList<StationCargoList, StationCargoPacketMap>;
 	/** The stations, via GoodsEntry, have a CargoList. */
 	friend const struct SaveLoad *GetGoodsDesc();
 
@@ -444,6 +466,36 @@ public:
 	friend class CargoRemoval;
 	friend class CargoReservation;
 	friend class CargoReturn;
+	friend class CargoReroute;
+
+	static void InvalidateAllFrom(SourceType src_type, SourceID src);
+
+	template<class Taction>
+	bool ShiftCargo(Taction &action, StationID next);
+
+	template<class Taction>
+	uint ShiftCargo(Taction action, StationID next, bool include_invalid);
+
+	void Append(CargoPacket *cp, StationID next);
+
+	/**
+	 * Check for cargo headed for a specific station.
+	 * @param next Station the cargo is headed for.
+	 * @return If there is any cargo for that station.
+	 */
+	inline bool HasCargoFor(StationID next) const
+	{
+		return this->packets.find(next) != this->packets.end();
+	}
+
+	/**
+	 * Returns source of the first cargo packet in this list.
+	 * @return The before mentioned source.
+	 */
+	inline StationID Source() const
+	{
+		return this->count == 0 ? INVALID_STATION : this->packets.begin()->second.front()->source;
+	}
 
 	/**
 	 * Returns sum of cargo still available for loading at the sation.
@@ -474,14 +526,14 @@ public:
 		return this->count + this->reserved_count;
 	}
 
-	void Append(CargoPacket *cp);
-
 	/* Methods for moving cargo around. First parameter is always maximum
 	 * amount of cargo to be moved. Second parameter is destination (if
 	 * applicable), return value is amount of cargo actually moved. */
 
-	uint Reserve(uint max_move, VehicleCargoList *dest, TileIndex load_place);
-	uint Load(uint max_move, VehicleCargoList *dest, TileIndex load_place);
+	uint Reserve(uint max_move, VehicleCargoList *dest, TileIndex load_place, StationID next);
+	uint Load(uint max_move, VehicleCargoList *dest, TileIndex load_place, StationID next);
+	uint Truncate(uint max_move = UINT_MAX);
+	uint Reroute(uint max_move, StationCargoList *dest, StationID avoid, StationID avoid2, const GoodsEntry *ge);
 
 	/**
 	 * Are two the two CargoPackets mergeable in the context of
diff --git a/src/economy.cpp b/src/economy.cpp
index 552839192..d22d35e6f 100644
--- a/src/economy.cpp
+++ b/src/economy.cpp
@@ -42,6 +42,7 @@
 #include "economy_base.h"
 #include "core/pool_func.hpp"
 #include "core/backup_type.hpp"
+#include "cargo_type.h"
 #include "water.h"
 #include "game/game.hpp"
 #include "cargomonitor.h"
@@ -1210,33 +1211,42 @@ Money CargoPayment::PayTransfer(const CargoPacket *cp, uint count)
 
 /**
  * Prepare the vehicle to be unloaded.
+ * @param curr_station the station where the consist is at the moment
  * @param front_v the vehicle to be unloaded
  */
 void PrepareUnload(Vehicle *front_v)
 {
+	Station *curr_station = Station::Get(front_v->last_station_visited);
+	curr_station->loading_vehicles.push_back(front_v);
+
 	/* At this moment loading cannot be finished */
 	ClrBit(front_v->vehicle_flags, VF_LOADING_FINISHED);
 
-	/* Start unloading in at the first possible moment */
+	/* Start unloading at the first possible moment */
 	front_v->load_unload_ticks = 1;
 
-	if ((front_v->current_order.GetUnloadType() & OUFB_NO_UNLOAD) == 0) {
+	assert(front_v->cargo_payment == NULL);
+	/* One CargoPayment per vehicle and the vehicle limit equals the
+	 * limit in number of CargoPayments. Can't go wrong. */
+	assert_compile(CargoPaymentPool::MAX_SIZE == VehiclePool::MAX_SIZE);
+	assert(CargoPayment::CanAllocateItem());
+	front_v->cargo_payment = new CargoPayment(front_v);
+
+	StationID next_station = front_v->GetNextStoppingStation();
+	if (front_v->orders.list == NULL || (front_v->current_order.GetUnloadType() & OUFB_NO_UNLOAD) == 0) {
+		Station *st = Station::Get(front_v->last_station_visited);
 		for (Vehicle *v = front_v; v != NULL; v = v->Next()) {
+			const GoodsEntry *ge = &st->goods[v->cargo_type];
 			if (v->cargo_cap > 0 && v->cargo.TotalCount() > 0) {
 				v->cargo.Stage(
-						HasBit(Station::Get(front_v->last_station_visited)->goods[v->cargo_type].acceptance_pickup, GoodsEntry::GES_ACCEPTANCE),
-						front_v->last_station_visited, front_v->current_order.GetUnloadType());
+						HasBit(ge->acceptance_pickup, GoodsEntry::GES_ACCEPTANCE),
+						front_v->last_station_visited, next_station,
+						front_v->current_order.GetUnloadType(), ge,
+						front_v->cargo_payment);
 				if (v->cargo.UnloadCount() > 0) SetBit(v->vehicle_flags, VF_CARGO_UNLOADING);
 			}
 		}
 	}
-
-	assert(front_v->cargo_payment == NULL);
-	/* One CargoPayment per vehicle and the vehicle limit equals the
-	 * limit in number of CargoPayments. Can't go wrong. */
-	assert_compile(CargoPaymentPool::MAX_SIZE == VehiclePool::MAX_SIZE);
-	assert(CargoPayment::CanAllocateItem());
-	front_v->cargo_payment = new CargoPayment(front_v);
 }
 
 /**
@@ -1280,8 +1290,9 @@ static byte GetLoadAmount(Vehicle *v)
  * @param st Station where the consist is loading at the moment.
  * @param u Front of the loading vehicle consist.
  * @param consist_capleft If given, save free capacities after reserving there.
+ * @param next_station Station the vehicle will stop at next.
  */
-static void ReserveConsist(Station *st, Vehicle *u, CargoArray *consist_capleft)
+static void ReserveConsist(Station *st, Vehicle *u, CargoArray *consist_capleft, StationID next_station)
 {
 	Vehicle *next_cargo = u;
 	uint32 seen_cargos = 0;
@@ -1310,7 +1321,7 @@ static void ReserveConsist(Station *st, Vehicle *u, CargoArray *consist_capleft)
 
 			/* Nothing to do if the vehicle is full */
 			if (cap > 0) {
-				cap -= st->goods[v->cargo_type].cargo.Reserve(cap, &v->cargo, st->xy);
+				cap -= st->goods[v->cargo_type].cargo.Reserve(cap, &v->cargo, st->xy, next_station);
 			}
 
 			if (consist_capleft != NULL) {
@@ -1347,11 +1358,14 @@ static void LoadUnloadVehicle(Vehicle *front)
 	StationID last_visited = front->last_station_visited;
 	Station *st = Station::Get(last_visited);
 
+	StationID next_station = front->GetNextStoppingStation();
 	bool use_autorefit = front->current_order.IsRefit() && front->current_order.GetRefitCargo() == CT_AUTO_REFIT;
 	CargoArray consist_capleft;
 	if (_settings_game.order.improved_load &&
 			((front->current_order.GetLoadType() & OLFB_FULL_LOAD) != 0 || use_autorefit)) {
-		ReserveConsist(st, front, (use_autorefit && front->load_unload_ticks != 0) ? &consist_capleft : NULL);
+		ReserveConsist(st, front,
+				(use_autorefit && front->load_unload_ticks != 0) ? &consist_capleft : NULL,
+				next_station);
 	}
 
 	/* We have not waited enough time till the next round of loading/unloading */
@@ -1408,7 +1422,7 @@ static void LoadUnloadVehicle(Vehicle *front)
 					uint new_remaining = v->cargo.RemainingCount() + v->cargo.ActionCount(VehicleCargoList::MTA_DELIVER);
 					if (v->cargo_cap < new_remaining) {
 						/* Return some of the reserved cargo to not overload the vehicle. */
-						v->cargo.Return(new_remaining - v->cargo_cap, &ge->cargo);
+						v->cargo.Return(new_remaining - v->cargo_cap, &ge->cargo, INVALID_STATION);
 					}
 
 					/* Keep instead of delivering. This may lead to no cargo being unloaded, so ...*/
@@ -1474,18 +1488,19 @@ static void LoadUnloadVehicle(Vehicle *front)
 			}
 
 			if (new_cid == CT_AUTO_REFIT) {
-				/* Get refittable cargo type with the most waiting cargo. */
-				int amount = 0;
+				/* Get a refittable cargo type with waiting cargo for next_station or INVALID_STATION. */
 				CargoID cid;
+				new_cid = v_start->cargo_type;
 				FOR_EACH_SET_CARGO_ID(cid, refit_mask) {
-					/* Consider refitting to this cargo, if other vehicles of the consist cannot
-					 * already take the cargo without refitting */
-					if ((int)st->goods[cid].cargo.AvailableCount() > (int)consist_capleft[cid] + amount) {
+					if (st->goods[cid].cargo.HasCargoFor(next_station) ||
+							st->goods[cid].cargo.HasCargoFor(INVALID_STATION)) {
 						/* Try to find out if auto-refitting would succeed. In case the refit is allowed,
 						 * the returned refit capacity will be greater than zero. */
 						DoCommand(v_start->tile, v_start->index, cid | 1U << 6 | 0xFF << 8 | 1U << 16, DC_QUERY_COST, GetCmdRefitVeh(v_start)); // Auto-refit and only this vehicle including artic parts.
-						if (_returned_refit_capacity > 0) {
-							amount = st->goods[cid].cargo.AvailableCount() - consist_capleft[cid];
+						/* Try to balance different loadable cargoes between parts of the consist, so that
+						 * all of them can be loaded. Avoid a situation where all vehicles suddenly switch
+						 * to the first loadable cargo for which there is only one packet. */
+						if (_returned_refit_capacity > 0 && consist_capleft[cid] < consist_capleft[new_cid]) {
 							new_cid = cid;
 						}
 					}
@@ -1493,7 +1508,7 @@ static void LoadUnloadVehicle(Vehicle *front)
 			}
 
 			/* Refit if given a valid cargo. */
-			if (new_cid < NUM_CARGO) {
+			if (new_cid < NUM_CARGO && new_cid != v_start->cargo_type) {
 				CommandCost cost = DoCommand(v_start->tile, v_start->index, new_cid | 1U << 6 | 0xFF << 8 | 1U << 16, DC_EXEC, GetCmdRefitVeh(v_start)); // Auto-refit and only this vehicle including artic parts.
 				if (cost.Succeeded()) front->profit_this_year -= cost.GetCost() << 8;
 				ge = &st->goods[v->cargo_type];
@@ -1502,7 +1517,7 @@ static void LoadUnloadVehicle(Vehicle *front)
 			/* Add new capacity to consist capacity and reserve cargo */
 			w = v_start;
 			do {
-				st->goods[w->cargo_type].cargo.Reserve(w->cargo_cap, &w->cargo, st->xy);
+				st->goods[w->cargo_type].cargo.Reserve(w->cargo_cap, &w->cargo, st->xy, next_station);
 				consist_capleft[w->cargo_type] += w->cargo_cap - w->cargo.RemainingCount();
 				w = w->HasArticulatedPart() ? w->GetNextArticulatedPart() : NULL;
 			} while (w != NULL);
@@ -1534,14 +1549,15 @@ static void LoadUnloadVehicle(Vehicle *front)
 		ge->last_age = min(_cur_year - front->build_year, 255);
 		ge->time_since_pickup = 0;
 
+		assert(v->cargo_cap >= v->cargo.StoredCount());
 		/* If there's goods waiting at the station, and the vehicle
 		 * has capacity for it, load it on the vehicle. */
-		int cap_left = v->cargo_cap - v->cargo.StoredCount();
+		uint cap_left = v->cargo_cap - v->cargo.StoredCount();
 		if (cap_left > 0 && (v->cargo.ActionCount(VehicleCargoList::MTA_LOAD) > 0 || ge->cargo.AvailableCount() > 0)) {
 			if (_settings_game.order.gradual_loading) cap_left = min(cap_left, load_amount);
 			if (v->cargo.StoredCount() == 0) TriggerVehicle(v, VEHICLE_TRIGGER_NEW_CARGO);
 
-			uint loaded = ge->cargo.Load(cap_left, &v->cargo, st->xy);
+			uint loaded = ge->cargo.Load(cap_left, &v->cargo, st->xy, next_station);
 			if (v->cargo.ActionCount(VehicleCargoList::MTA_LOAD) > 0) {
 				/* Remember if there are reservations left so that we don't stop
 				 * loading before they're loaded. */
@@ -1549,7 +1565,7 @@ static void LoadUnloadVehicle(Vehicle *front)
 			}
 
 			/* Store whether the maximum possible load amount was loaded or not.*/
-			if (loaded == (uint)cap_left) {
+			if (loaded == cap_left) {
 				SetBit(full_load_amount, v->cargo_type);
 			} else {
 				ClrBit(full_load_amount, v->cargo_type);
diff --git a/src/order_base.h b/src/order_base.h
index d361ce67d..7f8ce41f5 100644
--- a/src/order_base.h
+++ b/src/order_base.h
@@ -201,6 +201,8 @@ private:
 	friend void AfterLoadVehicles(bool part_of_load); ///< For instantiating the shared vehicle chain
 	friend const struct SaveLoad *GetOrderListDescription(); ///< Saving and loading of order lists.
 
+	const Order *GetBestLoadableNext(const Vehicle *v, const Order *o1, const Order *o2) const;
+
 	Order *first;                     ///< First order of the order list.
 	VehicleOrderID num_orders;        ///< NOSAVE: How many orders there are in the list.
 	VehicleOrderID num_manual_orders; ///< NOSAVE: How many manually added orders are there in the list.
@@ -262,7 +264,7 @@ public:
 	inline VehicleOrderID GetNumManualOrders() const { return this->num_manual_orders; }
 
 	StationID GetNextStoppingStation(const Vehicle *v) const;
-	const Order *GetNextStoppingOrder(const Vehicle *v, const Order *next, uint hops) const;
+	const Order *GetNextStoppingOrder(const Vehicle *v, const Order *next, uint hops, bool is_loading = false) const;
 
 	void InsertOrderAt(Order *new_order, int index);
 	void DeleteOrderAt(int index);
diff --git a/src/order_cmd.cpp b/src/order_cmd.cpp
index 833d23ff3..71edbb406 100644
--- a/src/order_cmd.cpp
+++ b/src/order_cmd.cpp
@@ -351,19 +351,61 @@ Order *OrderList::GetOrderAt(int index) const
 }
 
 /**
+ * Choose between the two possible next orders so that the given consist can
+ * load most cargo.
+ * @param v Head of the consist.
+ * @param o1 First order to choose from.
+ * @param o2 Second order to choose from.
+ * @return Either o1 or o2, depending on the amounts of cargo waiting at the
+ *         vehicle's current station for each.
+ */
+const Order *OrderList::GetBestLoadableNext(const Vehicle *v, const Order *o2, const Order *o1) const
+{
+	SmallMap<CargoID, uint> capacities;
+	v->GetConsistFreeCapacities(capacities);
+	uint loadable1 = 0;
+	uint loadable2 = 0;
+	StationID st1 = o1->GetDestination();
+	StationID st2 = o2->GetDestination();
+	const Station *cur_station = Station::Get(v->last_station_visited);
+	for (SmallPair<CargoID, uint> *i = capacities.Begin(); i != capacities.End(); ++i) {
+		const StationCargoPacketMap *loadable_packets = cur_station->goods[i->first].cargo.Packets();
+		uint loadable_cargo = 0;
+		std::pair<StationCargoPacketMap::const_iterator, StationCargoPacketMap::const_iterator> p =
+				loadable_packets->equal_range(st1);
+		for (StationCargoPacketMap::const_iterator j = p.first; j != p.second; ++j) {
+			loadable_cargo = (*j)->Count();
+		}
+		loadable1 += min(i->second, loadable_cargo);
+
+		loadable_cargo = 0;
+		p = loadable_packets->equal_range(st2);
+		for (StationCargoPacketMap::const_iterator j = p.first; j != p.second; ++j) {
+			loadable_cargo = (*j)->Count();
+		}
+		loadable2 += min(i->second, loadable_cargo);
+	}
+	if (loadable1 == loadable2) return RandomRange(2) == 0 ? o1 : o2;
+	return loadable1 > loadable2 ? o1 : o2;
+}
+
+/**
  * Get the next order which will make the given vehicle stop at a station
  * or refit at a depot if its state doesn't change.
  * @param v The vehicle in question.
  * @param next The order to start looking at.
  * @param hops The number of orders we have already looked at.
+ * @param is_loading If the vehicle is loading. This triggers a different
+ * behaviour on conditional orders based on load percentage.
  * @return Either an order or NULL if the vehicle won't stop anymore.
+ * @see OrderList::GetBestLoadableNext
  */
-const Order *OrderList::GetNextStoppingOrder(const Vehicle *v, const Order *next, uint hops) const
+const Order *OrderList::GetNextStoppingOrder(const Vehicle *v, const Order *next, uint hops, bool is_loading) const
 {
 	if (hops > this->GetNumOrders() || next == NULL) return NULL;
 
 	if (next->IsType(OT_CONDITIONAL)) {
-		if (next->GetConditionVariable() == OCV_LOAD_PERCENTAGE) {
+		if (is_loading && next->GetConditionVariable() == OCV_LOAD_PERCENTAGE) {
 			/* If the condition is based on load percentage we can't
 			 * tell what it will do. So we choose randomly. */
 			const Order *skip_to = this->GetNextStoppingOrder(v,
@@ -373,7 +415,7 @@ const Order *OrderList::GetNextStoppingOrder(const Vehicle *v, const Order *next
 					this->GetNext(next), hops + 1);
 			if (advance == NULL) return skip_to;
 			if (skip_to == NULL) return advance;
-			return RandomRange(2) == 0 ? skip_to : advance;
+			return this->GetBestLoadableNext(v, skip_to, advance);
 		}
 		/* Otherwise we're optimistic and expect that the
 		 * condition value won't change until it's evaluated. */
@@ -401,6 +443,8 @@ const Order *OrderList::GetNextStoppingOrder(const Vehicle *v, const Order *next
  * Recursively determine the next deterministic station to stop at.
  * @param v The vehicle we're looking at.
  * @return Next stoppping station or INVALID_STATION.
+ * @pre The vehicle is currently loading and v->last_station_visited is meaningful.
+ * @note This function may draw a random number. Don't use it from the GUI.
  */
 StationID OrderList::GetNextStoppingStation(const Vehicle *v) const
 {
@@ -420,7 +464,7 @@ StationID OrderList::GetNextStoppingStation(const Vehicle *v) const
 
 	uint hops = 0;
 	do {
-		next = this->GetNextStoppingOrder(v, next, ++hops);
+		next = this->GetNextStoppingOrder(v, next, ++hops, true);
 		/* Don't return a next stop if the vehicle has to unload everything. */
 		if (next == NULL || (next->GetDestination() == v->last_station_visited &&
 				(next->GetUnloadType() & (OUFB_TRANSFER | OUFB_UNLOAD)) == 0)) {
diff --git a/src/saveload/cargopacket_sl.cpp b/src/saveload/cargopacket_sl.cpp
index f9ebd3408..fbc38cc85 100644
--- a/src/saveload/cargopacket_sl.cpp
+++ b/src/saveload/cargopacket_sl.cpp
@@ -29,7 +29,7 @@
 		 * to the current tile of the vehicle to prevent excessive profits
 		 */
 		FOR_ALL_VEHICLES(v) {
-			const VehicleCargoList::List *packets = v->cargo.Packets();
+			const CargoPacketList *packets = v->cargo.Packets();
 			for (VehicleCargoList::ConstIterator it(packets->begin()); it != packets->end(); it++) {
 				CargoPacket *cp = *it;
 				cp->source_xy = Station::IsValidID(cp->source) ? Station::Get(cp->source)->xy : v->tile;
@@ -47,7 +47,7 @@
 			for (CargoID c = 0; c < NUM_CARGO; c++) {
 				GoodsEntry *ge = &st->goods[c];
 
-				const StationCargoList::List *packets = ge->cargo.Packets();
+				const StationCargoPacketMap *packets = ge->cargo.Packets();
 				for (StationCargoList::ConstIterator it(packets->begin()); it != packets->end(); it++) {
 					CargoPacket *cp = *it;
 					cp->source_xy = Station::IsValidID(cp->source) ? Station::Get(cp->source)->xy : st->xy;
diff --git a/src/saveload/oldloader_sl.cpp b/src/saveload/oldloader_sl.cpp
index 987af757a..791e63db5 100644
--- a/src/saveload/oldloader_sl.cpp
+++ b/src/saveload/oldloader_sl.cpp
@@ -711,7 +711,8 @@ static bool LoadOldGood(LoadgameState *ls, int num)
 	SB(ge->acceptance_pickup, GoodsEntry::GES_ACCEPTANCE, 1, HasBit(_waiting_acceptance, 15));
 	SB(ge->acceptance_pickup, GoodsEntry::GES_PICKUP, 1, _cargo_source != 0xFF);
 	if (GB(_waiting_acceptance, 0, 12) != 0 && CargoPacket::CanAllocateItem()) {
-		ge->cargo.Append(new CargoPacket(GB(_waiting_acceptance, 0, 12), _cargo_days, (_cargo_source == 0xFF) ? INVALID_STATION : _cargo_source, 0, 0));
+		ge->cargo.Append(new CargoPacket(GB(_waiting_acceptance, 0, 12), _cargo_days, (_cargo_source == 0xFF) ? INVALID_STATION : _cargo_source, 0, 0),
+				INVALID_STATION);
 	}
 
 	return true;
diff --git a/src/saveload/station_sl.cpp b/src/saveload/station_sl.cpp
index 6f1a864a2..7c43cc7a8 100644
--- a/src/saveload/station_sl.cpp
+++ b/src/saveload/station_sl.cpp
@@ -237,6 +237,9 @@ static const SaveLoad _station_speclist_desc[] = {
 	SLE_END()
 };
 
+std::list<CargoPacket *> _packets;
+uint32 _num_dests;
+
 struct FlowSaveLoad {
 	FlowSaveLoad() : via(0), share(0) {}
 	StationID source;
@@ -273,7 +276,8 @@ const SaveLoad *GetGoodsDesc()
 		SLEG_CONDVAR(            _cargo_feeder_share,  SLE_FILE_U32 | SLE_VAR_I64, 14, 64),
 		SLEG_CONDVAR(            _cargo_feeder_share,  SLE_INT64,                  65, 67),
 		 SLE_CONDVAR(GoodsEntry, amount_fract,         SLE_UINT8,                 150, SL_MAX_VERSION),
-		 SLE_CONDLST(GoodsEntry, cargo.packets,        REF_CARGO_PACKET,           68, SL_MAX_VERSION),
+		SLEG_CONDLST(            _packets,             REF_CARGO_PACKET,           68, 182),
+		SLEG_CONDVAR(            _num_dests,           SLE_UINT32,                183, SL_MAX_VERSION),
 		 SLE_CONDVAR(GoodsEntry, cargo.reserved_count, SLE_UINT,                  181, SL_MAX_VERSION),
 		 SLE_CONDVAR(GoodsEntry, link_graph,           SLE_UINT16,                183, SL_MAX_VERSION),
 		 SLE_CONDVAR(GoodsEntry, node,                 SLE_UINT16,                183, SL_MAX_VERSION),
@@ -284,6 +288,35 @@ const SaveLoad *GetGoodsDesc()
 	return goods_desc;
 }
 
+typedef std::pair<const StationID, std::list<CargoPacket *> > StationCargoPair;
+
+static const SaveLoad _cargo_list_desc[] = {
+	SLE_VAR(StationCargoPair, first,  SLE_UINT16),
+	SLE_LST(StationCargoPair, second, REF_CARGO_PACKET),
+	SLE_END()
+};
+
+/**
+ * Swap the temporary packets with the packets without specific destination in
+ * the given goods entry. Assert that at least one of those is empty.
+ * @param ge Goods entry to swap with.
+ */
+static void SwapPackets(GoodsEntry *ge)
+{
+	StationCargoPacketMap &ge_packets = const_cast<StationCargoPacketMap &>(*ge->cargo.Packets());
+
+	if (_packets.empty()) {
+		std::map<StationID, std::list<CargoPacket *> >::iterator it(ge_packets.find(INVALID_STATION));
+		if (it == ge_packets.end()) {
+			return;
+		} else {
+			it->second.swap(_packets);
+		}
+	} else {
+		assert(ge_packets[INVALID_STATION].empty());
+		ge_packets[INVALID_STATION].swap(_packets);
+	}
+}
 
 static void Load_STNS()
 {
@@ -299,6 +332,7 @@ static void Load_STNS()
 		for (CargoID i = 0; i < num_cargo; i++) {
 			GoodsEntry *ge = &st->goods[i];
 			SlObject(ge, GetGoodsDesc());
+			SwapPackets(ge);
 			if (IsSavegameVersionBefore(68)) {
 				SB(ge->acceptance_pickup, GoodsEntry::GES_ACCEPTANCE, 1, HasBit(_waiting_acceptance, 15));
 				if (GB(_waiting_acceptance, 0, 12) != 0) {
@@ -310,7 +344,10 @@ static void Load_STNS()
 					 * savegame versions. As the CargoPacketPool has more than
 					 * 16 million entries; it fits by an order of magnitude. */
 					assert(CargoPacket::CanAllocateItem());
-					ge->cargo.Append(new CargoPacket(GB(_waiting_acceptance, 0, 12), _cargo_days, source, _cargo_source_xy, _cargo_source_xy, _cargo_feeder_share));
+
+					/* Don't construct the packet with station here, because that'll fail with old savegames */
+					CargoPacket *cp = new CargoPacket(GB(_waiting_acceptance, 0, 12), _cargo_days, source, _cargo_source_xy, _cargo_source_xy, _cargo_feeder_share);
+					ge->cargo.Append(cp, INVALID_STATION);
 					SB(ge->acceptance_pickup, GoodsEntry::GES_PICKUP, 1, 1);
 				}
 			}
@@ -336,7 +373,9 @@ static void Ptrs_STNS()
 		if (!IsSavegameVersionBefore(68)) {
 			for (CargoID i = 0; i < NUM_CARGO; i++) {
 				GoodsEntry *ge = &st->goods[i];
+				SwapPackets(ge);
 				SlObject(ge, GetGoodsDesc());
+				SwapPackets(ge);
 			}
 		}
 		SlObject(st, _old_station_desc);
@@ -427,6 +466,7 @@ static void RealSave_STNN(BaseStation *bst)
 	if (!waypoint) {
 		Station *st = Station::From(bst);
 		for (CargoID i = 0; i < NUM_CARGO; i++) {
+			_num_dests = (uint32)st->goods[i].cargo.Packets()->MapSize();
 			_num_flows = 0;
 			for (FlowStatMap::const_iterator it(st->goods[i].flows.begin()); it != st->goods[i].flows.end(); ++it) {
 				_num_flows += (uint32)it->second.GetShares()->size();
@@ -445,6 +485,9 @@ static void RealSave_STNN(BaseStation *bst)
 					SlObject(&flow, _flow_desc);
 				}
 			}
+			for (StationCargoPacketMap::ConstMapIterator it(st->goods[i].cargo.Packets()->begin()); it != st->goods[i].cargo.Packets()->end(); ++it) {
+				SlObject(const_cast<StationCargoPacketMap::value_type *>(&(*it)), _cargo_list_desc);
+			}
 		}
 	}
 
@@ -498,6 +541,16 @@ static void Load_STNN()
 					}
 					prev_source = flow.source;
 				}
+				if (IsSavegameVersionBefore(183)) {
+					SwapPackets(&st->goods[i]);
+				} else {
+					StationCargoPair pair;
+					for (uint j = 0; j < _num_dests; ++j) {
+						SlObject(&pair, _cargo_list_desc);
+						const_cast<StationCargoPacketMap &>(*(st->goods[i].cargo.Packets()))[pair.first].swap(pair.second);
+						assert(pair.second.empty());
+					}
+				}
 			}
 		}
 
@@ -520,7 +573,16 @@ static void Ptrs_STNN()
 	FOR_ALL_STATIONS(st) {
 		for (CargoID i = 0; i < NUM_CARGO; i++) {
 			GoodsEntry *ge = &st->goods[i];
-			SlObject(ge, GetGoodsDesc());
+			if (IsSavegameVersionBefore(183)) {
+				SwapPackets(ge);
+				SlObject(ge, GetGoodsDesc());
+				SwapPackets(ge);
+			} else {
+				SlObject(ge, GetGoodsDesc());
+				for (StationCargoPacketMap::ConstMapIterator it = ge->cargo.Packets()->begin(); it != ge->cargo.Packets()->end(); ++it) {
+					SlObject(const_cast<StationCargoPair *>(&(*it)), _cargo_list_desc);
+				}
+			}
 		}
 		SlObject(st, _station_desc);
 	}
diff --git a/src/station.cpp b/src/station.cpp
index d7cd0ea2b..555c6369c 100644
--- a/src/station.cpp
+++ b/src/station.cpp
@@ -103,6 +103,7 @@ Station::~Station()
 		FOR_ALL_STATIONS(st) {
 			GoodsEntry *ge = &st->goods[c];
 			ge->flows.DeleteFlows(this->index);
+			ge->cargo.Reroute(UINT_MAX, &ge->cargo, this->index, st->index, ge);
 		}
 	}
 
diff --git a/src/station_cmd.cpp b/src/station_cmd.cpp
index 6ef992caa..d74c20668 100644
--- a/src/station_cmd.cpp
+++ b/src/station_cmd.cpp
@@ -3370,6 +3370,8 @@ void DeleteStaleLinks(Station *from)
 			if ((uint)(_date - edge.LastUpdate()) > LinkGraph::MIN_TIMEOUT_DISTANCE +
 					(DistanceManhattan(from->xy, to->xy) >> 2)) {
 				node.RemoveEdge(to->goods[c].node);
+				ge.flows.DeleteFlows(to->index);
+				ge.cargo.Reroute(UINT_MAX, &ge.cargo, to->index, from->index, &ge);
 			}
 		}
 		assert(_date >= lg->LastCompression());
@@ -3539,7 +3541,8 @@ static uint UpdateStationWaiting(Station *st, CargoID type, uint amount, SourceT
 	/* No new "real" cargo item yet. */
 	if (amount == 0) return 0;
 
-	ge.cargo.Append(new CargoPacket(st->index, st->xy, amount, source_type, source_id));
+	StationID next = ge.GetVia(st->index);
+	ge.cargo.Append(new CargoPacket(st->index, st->xy, amount, source_type, source_id), next);
 	LinkGraph *lg = NULL;
 	if (ge.link_graph == INVALID_LINK_GRAPH) {
 		if (LinkGraph::CanAllocateItem()) {
diff --git a/src/station_gui.cpp b/src/station_gui.cpp
index 1afabe0a2..e2e33b0d5 100644
--- a/src/station_gui.cpp
+++ b/src/station_gui.cpp
@@ -947,7 +947,7 @@ struct StationViewWindow : public Window {
 				this->cargo_rows[i] = (uint16)cargolist->size();
 
 				/* Add an entry for each distinct cargo source. */
-				const StationCargoList::List *packets = st->goods[i].cargo.Packets();
+				const StationCargoPacketMap *packets = st->goods[i].cargo.Packets();
 				for (StationCargoList::ConstIterator it(packets->begin()); it != packets->end(); it++) {
 					const CargoPacket *cp = *it;
 					if (cp->SourceStation() != station_id) {
diff --git a/src/station_type.h b/src/station_type.h
index b312bdd74..82ee0ae25 100644
--- a/src/station_type.h
+++ b/src/station_type.h
@@ -14,6 +14,7 @@
 
 #include "core/smallvec_type.hpp"
 #include "tilearea_type.h"
+#include <list>
 
 typedef uint16 StationID;
 typedef uint16 RoadStopID;
@@ -87,6 +88,9 @@ enum CatchmentArea {
 
 static const uint MAX_LENGTH_STATION_NAME_CHARS = 32; ///< The maximum length of a station name in characters including '\0'
 
+/** List of station IDs */
+typedef std::list<StationID> StationIDList;
+
 /** List of stations */
 typedef SmallVector<Station *, 2> StationList;
 
diff --git a/src/vehicle.cpp b/src/vehicle.cpp
index 50825d36d..8ccaf2eda 100644
--- a/src/vehicle.cpp
+++ b/src/vehicle.cpp
@@ -727,7 +727,7 @@ void Vehicle::PreDestructor()
 		st->loading_vehicles.remove(this);
 
 		HideFillingPercent(&this->fill_percent_te_id);
-		this->CancelReservation(st);
+		this->CancelReservation(INVALID_STATION, st);
 		delete this->cargo_payment;
 	}
 
@@ -2002,8 +2002,6 @@ void Vehicle::BeginLoading()
 		this->current_order.MakeLoading(false);
 	}
 
-	Station::Get(this->last_station_visited)->loading_vehicles.push_back(this);
-
 	if (this->last_loading_station != INVALID_STATION &&
 			this->last_loading_station != this->last_station_visited &&
 			((this->current_order.GetLoadType() & OLFB_NO_LOAD) == 0 ||
@@ -2024,16 +2022,18 @@ void Vehicle::BeginLoading()
 }
 
 /**
- * Return all reserved cargo packets to the station.
+ * Return all reserved cargo packets to the station and reset all packets
+ * staged for transfer.
  * @param st the station where the reserved packets should go.
  */
-void Vehicle::CancelReservation(Station *st)
+void Vehicle::CancelReservation(StationID next, Station *st)
 {
 	for (Vehicle *v = this; v != NULL; v = v->next) {
 		VehicleCargoList &cargo = v->cargo;
 		if (cargo.ActionCount(VehicleCargoList::MTA_LOAD) > 0) {
 			DEBUG(misc, 1, "cancelling cargo reservation");
-			cargo.Return(UINT_MAX, &st->goods[v->cargo_type].cargo);
+			cargo.Return(UINT_MAX, &st->goods[v->cargo_type].cargo, next);
+			cargo.SetTransferLoadPlace(st->xy);
 		}
 		cargo.KeepAll();
 	}
@@ -2071,7 +2071,7 @@ void Vehicle::LeaveStation()
 
 	this->current_order.MakeLeaveStation();
 	Station *st = Station::Get(this->last_station_visited);
-	this->CancelReservation(st);
+	this->CancelReservation(INVALID_STATION, st);
 	st->loading_vehicles.remove(this);
 
 	HideFillingPercent(&this->fill_percent_te_id);
diff --git a/src/vehicle_base.h b/src/vehicle_base.h
index 62fcb24ab..3873a0d35 100644
--- a/src/vehicle_base.h
+++ b/src/vehicle_base.h
@@ -247,7 +247,7 @@ public:
 	virtual ~Vehicle();
 
 	void BeginLoading();
-	void CancelReservation(Station *st);
+	void CancelReservation(StationID next, Station *st);
 	void LeaveStation();
 
 	GroundVehicleCache *GetGroundVehicleCache();