Delft University of Technology
Faculty Mechanical, Maritime and Materials Engineering
Transport Technology / Logistic Engineering



S. de Jongh Dynamic routing and balancing in material handling systems.
Masters thesis, Report 2001.LT.5558, Transport Technology, Logistic Engineering.


This graduation project has been conducted for and under supervision of Vanderlande Industries (VI), a creator of (large) Material Handling systems. These systems are designed to a certain capacity and in peak periods the overall occupancy will be high. The objective of this project is twofold:
  1. Application and development of network theory in the routing strategies of the system controls and simulation in networks similar to the VI systems (with special attention to balancing network flows, dynamic shortest path calculations in a network and re-routing);
  2. Implementation of promising methods in re-usable routing software for the Simulation department.
The VI systems that are of interest for this project are:
  1. Baggage handling systems (BHSs);
    A BHS handles all baggage flows in an airport. In this project, the number of bags that arrives at its destination too late is the most important Key Performance Indicator (KPI) of a BHS.
  2. Express parcel systems (EPSs);
    An EPS sorts large amounts of parcels. Used for example by postal companies. In this project, the batch time (the time the system takes to sort out one batch of parcels) is the most important KPI of an EPS.
Balancing is in this project regarded as distributing all unit flows over different available routes, in order to minimise queues and die-backs and improve overall system performance. Shortest path algorithms can be used in balancing methods, if the right arc properties are chosen for the algorithms.

Several balancing methods have been studied and none is found to be optimal for the VI systems. Therefor, two new methods are developed:
  1. Capacity Constrained Shortest Paths routing (CCSP).
    In the CCSP method, two sets of shortest paths are determined. The shortest travel time paths and the shortest travel time paths with capacity constraint. Units can be distributed over the paths according to their individual importance status.
    For the calculation of the paths, the actual arc travel times as well as the actual arc occupancy levels are kept up to date. The following parameters are available to tune the method:
    • Recalculation time; sets the time between two calculations of the two sets of shortest paths;
    • Number of arc trips; sets the number of trips used in the moving average arc travel time.
    • Maximum occupancy level; used in the shortest travel time path with capacity constraint. If the actual occupancy level of the arc is higher than the maximum level, then the arc cannot be used in any capacity constrained shortest travel time path.
  2. Capacity Constrained Shortest Paths with lowest Occupancy routing (CCSPO).
    The CCSPO method constructs the same two sets of paths as the CCSP method plus one additional set: the lowest average occupancy path. This gives one extra set of paths to distribute the units over. The same tuning parameters can be used as in the CCSP method.
Of both the CCSP and CCSPO methods, extra implementations are made, in which each individual arc can be assigned its own maximum occupancy level. These are called the ICCSP and ICCPO methods.

In order to test the balancing methods, two networks representing a BHS system and an EPS system are designed. The CCSP, ICCSP, CCSPO and ICCSPO methods are tested and compared with:
BHS results. SSP DSP CCSP ICCSP CCSPO ICCSPO
Late bags (#) 1007 32 5 79 10 19
Parameters:            
Maximum occupancy - - 0.75 0.75 or 1 0.75 0.75 or 1
Recalculation time (seconds) - 1 1 1 1 1
Arc trips (#) - 45 31 31 1 1
Table S.1: balancing method result for the BHS.

EPS results. SSP DSP CCSP ICCSP CCSPO ICCSPO
Batch time (sec) 3072 1952 1530 1700 1535 1578
Parameters:            
Maximum occupancy - - 0.65 0.65 or 1 0.65 0.65 or 1
Recalculation time (seconds) - 1 11 11 21 21
Arc trips (#) - 31 50 50 50 50
Table S.2: balancing method results for the EPS.

Table S.1 and S.2 show the parameter setting for which each method achieves its best performance based on the systems KPI (late bags in table S.1 for the BHS and batch time in table S.2 for the EPS) and the values of these KPI's.

Conclusions: Recommendations:

Reports on Logistic Engineering (in Dutch)
Modified: 2001.12.14; logistics@3mE.tudelft.nl , TU Delft / 3mE / TT / LT.