Solution For Vehicle Routing Problem (VRP) Using Travel Pattern

Abstract

Vehicle routing problem (VRP) is a well established optimization the field of location based applications like route planning, recommendation system for transportation and logistics in supply chain etc. It deals with delivering goods and shipments located at a source location to the remote locations, with overall objective of reduction of cost of distribution. Since fifties, when it was first proposed this problem exists in many different variations like VRPPD, LIFO, VRPTW, and CVRP. Many mathematical solutions evolved since then. These algorithms assign some weight to edges of digitized road network. Weights may be dependent on other factors like shortest distance, traffic condition etc., individually or a combination of these factors. Almost all the solutions use this road network graph to compute the shortest path and then do the optimization for minimizing the distribution cost. But it’s not necessary that the shortest path selected by this weighing scheme be the best path. Many factors influence the determination of the best path between any two given places. For example, security, lighting conditions, condition of the road etc. These are known by local drivers and local residents and so mostly these people drive through most optimal and best paths. We propose a framework in which spatial data mining is performed on location data captured from location devices for finding the frequently traveled paths between each pair source and destinations and are used while scheduling the vehicle trips.