|
On a routing & scheduling problem concerning multiple edge traversals in graphs |
|---|
GW Groves1, J le Roux2 & JH van Vuuren3
Abstract
Practical vehicle routing problems generally have both routing and scheduling aspects to consider. However, few heuristic methods exist which address both these complicated aspects simultaneously. We present heuristics to determine an efficient circular traversal of a weighted graph that requires a subset of its edges to be traversed, each a specified (potentially different) number of times. Consecutive time instances at which the same edge has to be traversed should additionally be spaced through a scheduling time window as evenly as possible, thus introducing a scheduling consideration to the problem. We present a route construction heuristic for the problem, based on well-known graph theoretic algorithms, as well as a route improvement heuristic, that accepts the solution generated by the construction heuristic as input and attempts to improve it in an iterative fashion. We apply the heuristics to various randomly generated problem instances, and interpret these test results.
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.