Faculty Mechanical, Maritime and Materials Engineering

Transport Technology / Logistic Engineering

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:

- 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);
- Implementation of promising methods in re-usable routing software for the Simulation department.

- 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. - 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.

Several balancing methods have been studied and none is found to be optimal for the VI systems. Therefor, two new methods are developed:

- 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.

- 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.

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:

- Static shortest path routing, in which all shortest travel time paths are constructed once (based on the free flow travel times) and all units are routed according to these calculations. This method does not balance, but serves as a benchmark;
- Dynamic shortest path routing, in which the shortest travel time paths are recalculated dynamically. (parameters: recalculation time and number of arc trips);

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 |

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.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:

- The application of network methods is possible for VI's systems;
- For the EPS, the CCSPO method is the best choice. The CCSP and CCSPO methods have almost the same results, but the CCSPO method shows greater stability in sensitivity analysis;
- Re-routing is possible with the developed routing method;
- For the BHS, the CCSP method shows the best performance.

- The developed lowest average occupancy path algorithm can only function in a-cyclic networks. The CCSPO method has to be adjusted to be useful in a BHS system;
- The developed automatic routing/balancing method should be applied in one of the new VI projects, together with the normal implementations.

Reports on Logistic Engineering (in Dutch)

Modified: 2001.12.14; logistics@3mE.tudelft.nl , TU Delft / 3mE / TT / LT.