|
Network Service Scheduling & Routing |
|---|
Abstract
Real-life vehicle routing problems generally have both routing and scheduling aspects to consider. Although this fact is well acknowledged, few heuristic methods exist which address both these complicated aspects simultaneously. We present a graph theoretic heuristic to determine an efficient service route through a transportation network that requires a subset of its edges to be serviced, each a specified (potentially different) number of times. The times at which each of these edges are to be serviced should additionally be as evenly spaced through the scheduling time window as possible, thus introducing a scheduling consideration to the problem. Our heuristic is based on the tabu-search method in conjunction with various well-known graph theoretic algorithms, such as those of Floyd (for determining shortest routes) and Frederickson (for solving the rural postman problem). This heuristic forms the backbone of a decision support system which prompts the user for certain parameters from the physical situation (such as the service frequencies and travel times for each network link as well as bounds in terms of acceptability of results) after which a service routing schedule is suggested as output. We apply the decision support system to a special case study where a service routing schedule is sought for the south western region of the South African railway system by SPOORNET (the semi-privatised South African national railways authority and service provider) as part of their cost savings effort in order to remain a lucrative company.
An electronic version of the complete paper may be obtained here: [pdf].
Affiliations
1
Department of Industrial Engineering, Stellenbosch University, Private Bag X1, Matieland, 7602, Republic of South Africa.