Spatial Decision Support System for Vehicle Routing with Constraints: A Case Study of NUST Transportation

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.