Abstract:
The problems encountered by courier companies in directing their eets
along road networks to visit customers, which are geographically distributed,
are common problems which are encountered frequently. These problems are by
no means isolated to courier companies. Any set of vehicles which is involved in
delivery, collection or a combination of both delivery and collection encounter a
variation of the vehicle routing problem (VRP). Several variations of the vehicle
routing problem exist. The algorithmic solutions to the individual variants of
the vehicle routing problem seek to optimise the routes assigned to a eet of
vehicles in visiting an array of nodes (which represent points of delivery or collection
or from another perspective, a set of customers). The optimal solution
of a VRP instance is the shortest, quickest or cheapest set of routes assigned
to a eet of vehicles which satis es all customer demand without contravening
any of the instance-speci c constraints. The vehicle routing problem has been
identi ed as an non-determinant polynomial-time (NP) hard problem. This
classi cation gives an indication of the computational complexity of the problem.
Problems of this class require an inordinate amount of time to be solved
to optimality for large problem instances. To overcome such obstacles, heuristic
and metaheuristic search algorithms are often utilised to arrive at near-optimal
or satisfactory solutions in less time.
