Over the last two decades, the establishment of a separate market for courier, express and parcel shipments has caused the classic packaged goods trade to develop into what is known as CEP services. By far the largest segment in the CEP market is parcel services specialising in the transport of small parcels which weight up to 31.5 kg. Due to the delivery times guaranteed to customers by the parcel service providers (e.g. 24-hour delivery inside Germany), parcel services have developed highly effective transport networks to ensure that parcels reach the recipient within the required period.

These transport networks connect the physical depot sites with the transhipment centers. Within these networks, transport is typically arranged in such a way that parcels can be collected from customers within the depot areas for the so-called pre-carriage stage. Parcels are then clustered into larger loads and transported between depots for the so-called main carriage. After this, parcels are delivered to customers within the depot areas for post-carriage. The pre-carriage and post-carriage stages are also referred to as "local transit" since they generally occur simultaneously between 7 am and 4 pm in the various depot areas.

Within the transportation networks, organising and planning local transit is a key optimisation focus for parcel service providers. Local transit incurs annual costs of several hundred million euros to CEP services. Germany is divided into approx. 100 depot areas. Several dozen runs have to be made in each of these areas every day, with up to 200 parcels being delivered and collected on each run.


Figure 1: Development of parcel numbers and turnover in the CEP sector in Germany  (Source: http://www.biek.de/download/gutachten/biek_studie_2008.pdf).


The planning problem in terms of local transit in the individual depot areas can be described as follows: For any given depot, runs have to be calculated for a specific vehicle fleet so as to cover the individual requirements of a given number of customers. A separate route is calculated for each vehicle, starting and finishing and the same depot. What is more, each customer has to be visited at least once. The aim is to minimise a given criterion, such as the total distance covered by the fleet or the number of vehicles required. A number of ancillary factors also have to be taken into account.

However, no local transit planning support systems are available on the market which fully address these wide-ranging ancillary factors and ensure that the solutions arrived at can actually be implemented effectively. In practice, therefore, planning is carried out in such a way that the individual depot areas are subdivided into a number of districts. Planning for the individual districts is then generally done manually by the drivers.  This approach fails to produce optimum solutions, however, since no balance is achieved between the runs carried out in the various districts. It makes much more sense to group all assignments for an entire depot area into a single pool and then plan them all simultaneously.

The goal of this project is to develop potential solutions to increase efficiency in local transit. In addition to analysing the methods currently used to plan local transit, the project particularly aims to develop algorithms that help planners organise local runs effectively.



Figure 2: CEP service transportation networks.