Abstract:
Vehicle Routing Problem is a combinatorial problem, the complexity of
VRP increases with the; number of vehicles, customers, delivery depots,
constraints like loading capacity and time duration of routes etc. To solve real
world VRP exact algorithms can solve small instances with very high
computational times. Practical solutions for VRPs are heuristics which give near
optimal solutions in polynomial time. The objective of this research was to develop·
Spatial Decision Support System SDSS for National University of Science and
Technology transport system, having easy to use interactive user interface. The
constrains of vehicle loading capacity and time duration of routes must be
followed. By using open source tools SDSS was developed and clustering heuristic
was used to solve VRP with constraints. Each vehicle was assigned to cluster of
passengers and all clusters were solved using Travelling Salesman Problem. The
SDSS developed returns map for each vehicle in such a way that each passenger
was picked up from his door step. If some vehicle violate time limit of route then
SDSS generates warning and allows decision maker to alter the route. The near
optimal routes were generated efficiently by this system. There is still room for
improvement as the accuracy of TSP reduces for sparse road network.
