Solving a vehicle routing problem by balancing the vehicles time utilization

Various vehicle routing problems (VRP) appear in the literature due to their important applications in the area of transportation and distribution. A VRP is characterized by the constraints that the involved factors must satisfy and by an optimality goal. In this paper, we develop a heuristic algorithm that (i) partitions suitably a distribution network into subnetworks. A single depot complies with every subnetwork, where a fleet of identical vehicles will start their itinerary. The nodes of the corresponding subnetwork are demand nodes that require a onetime visit by one only vehicle. (ii) Determine the routes of k vehicles, k=2,3,…, for every subnetwork so to minimize the visiting time of the corresponding demand nodes. Consequently the method computes the necessary vehicle number for each subnetwork so as to complete promptly the visiting requirement of all the demand nodes of the whole network. The main strategy of the algorithm for designing the vehicle routes consists of balancing the time utilization of the used vehicles. The paper is integrated by an application of the presented algorithm to the center of the city of Thessaloniki.