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

distances and 24.61% improvement in fuel consumption. [11] has used a two-phase method that includes Genetic Algorithms along with Random Search incorporating simulated annealing concepts to solve the time dependent vehicle routing problem (TDVRP). This is a hyper heuristic solution. Paper [14] has taken into consideration the problems of carbon pollution and environmental issues. Electric vehicles were considered to reduce the various problems mentioned but it brought along with it the issue of charging locations and battery capacity. To tackle these problems, a new variant in the classical VRPTW was brought about which integrated the ideas of multiple charging points that also have the facility of swapping batteries. The authors proposed a mixed integer programming model to tackle the issue using the improved ant colony optimization (ACO) algorithm with hybridised insertion heuristics and enhanced local search. Another reference has been taken from [15] which is quite close in similarity with this paper’s solution. The problem that the paper addressed was that deliverance of perishable goods within a given time frame was a daunting task and if unexpected events took place, the extremely important goods would not reach their destination, leading to a molehill of problems and difficulties. The authors Yao Wu, Bin Zheng and Xueliang Zhou have proposed a working model where the idea of disruption management has been employed to create a disruption recovery model with a different type split delivery that is used for inter-route recourse based on a previous TDVRPTW. It takes into account the nature of perishable goods and dynamic travel route choice in urban road networks. The, a tabu search algorithm is brought up to create a solution for the initial routing problem. This will be further extended to create the disruption recovery plan. [16] Researchers have also used a novel ant colony optimization algorithm based on improved brainstorm optimization (IBSO-ACO) to solve VRP with soft time windows. According to this paper, the classical ant colony algorithm has been modified to efficiently solve the local optimum problem. Their research has given proof that it can achieve a lower routing cost at a high convergence rate than the classical ant colony (ACO) and the stimulated annealing ant colony algorithms. Looking into other heuristic strategies involved, [17] has the space-filling curve with optimal partitioning as a solution while another has three-phase heuristics which has been developed by grouping a heuristic- based clustering algorithm solving VRP [18]. Summary of other important state-of-art modern heuristics is available in [19,20]. In this paper, we will be solving the Vehicle Routing Problem with Time Windows constraint using the modified Ant Colony Optimization with K-Means Clustering. Ants use pheromones to leave behind a trail for its comrades so as to use the optimal path fixed to reach the food source. There has been several research based on this behaviour of ants, such as [21], which was the first paper to be published on this topic. Papers [22-27] have various hybrid versions of ACO in varied fields. Using this behaviour of ants and with the help of previous research work based on a somewhat similar problem, this paper aims to solve VRPTW using the K- Means Clustering algorithm to find the most optimal path to the customer. III. M athematical M odel of P roposed S ystem This part will use certain terms and elements from [28]. It is a case study based on VRPTW regarding fresh food distribution centres. There will be two subsets of service nodes: pickup set _ and delivery set _ . The values of these terms are | _ | = and | _ | = respectively. Now, starting depot node is set to 0 and end depot is set to ( + + 1) . A node will be replicated if it needs both delivery and pickup. Each vehicle has its set capacity and operation cost. If there is an order between pickup node and delivery node, then there will be a set which contains pairs of ( , ) . Looking at the objective function that minimizes total travelling cost, equation 1 is as follows ∑ ∈ ∑ , ∈ (1) Here, refers to the number of clusters and refers to the centroid of clusters. Equation 2 makes sure that each node is served by at least one vehicle ∑ ∈ ∑ ∈ 1 ≥ 1 ∀ ∈ \{0, + + 1} (2) Equation 3 showcases the constraint where the same vehicle must pick and order from node and deliver it to node . ∑ ∈ 2 − ∑ ∈ 2 = 0 ∀ ∈ , ∀( , ) ∈ (3) A vehicle must pass starting and ending depots at least once and this is shown by equations 4, and 5. ∑ ∈ 1 0 ≤ 1, ∀ ∈ (4) ∑ ∈ 2 , + +1 ≤ 1, ∀ ∈ (5) If a vehicle reaches a node, it must leave it as well. This is shown in equation 6. Global Journal of Computer Science and Technology Volume XXII Issue I Version I 51 ( )D Year 2022 © 2022 Global Journals Vehicle Routing Problem with Time Window Constrain using KMeans Clustering to Obtain the Closest Customer