Global Journal of Computer Science and Technology, D: Neural & Artificial Intelligence, Volume 22 Issue 1

popped up. Some were utilizing route construction savings method and an insertion method to solve incapacitated TDVRP (time dependent with/without time windows), some had heuristic solutions [8-10], some metaheuristic algorithms [5-7] and others hyper heuristics [11].Figure 1. shows a generalized view of how a VRP is solved. Figure 1: General VRP Solving Method Many works of solving the VRP with the Time Window Constraint were inherited from the travelling salesman problem. The method used by the salesman to find the best and optimal route to deliver the goods to the respective customers from one or more depot and also take the goods from the customer back to the respective depots within the constraints set, has been extensively used in VRP, with the inclusion of extra constraints. Similar VRP variants have been mentioned below: • Vehicle Routing Problem with the Time Window Constraint [12] that has been set by customers, • Another modified VRP with the added constraint of using limited number of vehicles of varying holding capacity has been published as Mixed Fleet Vehicle Routing (MFVRP) [13], • Another paper which has VRP with an added constraint where customers can request for delivery or pickup with the requirement that in every single delivery route, all pickups and deliveries to the customers are completed. This is known as Vehicle Routing Problem with Backhauls (VRPB) [13]. This paper has five sections in total. Section 1 deals with the introduction while section 2 deals with the literature survey. Section 3 handles the mathematical model of the proposed system [ACO using K-Means Clustering Algorithm], section 4 will explain the approach to the solution, section 5 will have the results and case studies, with section 6 concluding the paper. II. L iterature S urvey One of the heuristic solutions mentioned was provided by Hideki Hashimoto, MutsunoriYagiura and ToshihideIbaraki [8]. In their paper they generalized VRPTW by making travelling costs and duration to be time-dependent functions. They used local search algorithm to find the routes of vehicles and using that, evaluated a neighbourhood solution. they proposed an algorithm that could efficiently pick optimal routes using data from previous dynamic programming recursion that were used to evaluate the present solution. they even included a filtering method that determines which spaces in the neighbourhood are not to be searched so as to avoid dead ends in improving the solution. they finally conclude with a local search algorithm that combines all their modifications. A metaheuristic solution was proposed by YiyoKuo[6]. In the research paper, the author has considered fuel consumption and carbon emission as the constraints to the Time-Dependent Vehicle Routing Problem (TDVRP). The paper has proposed an algorithm that determines a route that consumes less fuel and has the least carbon emissions. With this algorithm the author was able to provide an overall improvement of 22.69% in minimizing transportation Global Journal of Computer Science and Technology Volume XXII Issue I Version I 50 ( )D Year 2022 © 2022 Global Journals Vehicle Routing Problem with Time Window Constrain using KMeans Clustering to Obtain the Closest Customer