Accumulation Point Location on Tree Networks for Guaranteed Time Distribution

A guaranteed time distribution system is organized so that movement of items between any source-destination pair (serviced by the system) is completed within a guaranteed period of time (T). Various express mail services are examples of such distribution systems. The movement of items between source and destination consists of a combination of different modes of travel with varying speeds (i.e. trucks, airplanes etc.). Decisions have to be made regarding location of accumulation points (called local centers) at which changes in the mode of travel occur. All customers have to be allocated to these local centers so as to provide the best (minimum) time guarantee for travel between every source-destination pair. Accumulated flows between local centers pass through a global center in a centralized sorting system (CSS) and move directly between local centers in a decentralized sorting system (DSS). For tree structured distribution systems we provide polynomial time algorithms that locate a given number of local centers, allocate customers to local centers and provide the best possible time guarantee for both centralized and decentralized guaranteed time distribution systems.