# I. Introduction
ransportation is one of the primary requisites of civilization and this fact continues to be true even today. In today's world of quick and safe deliveries, there has been a need for better service, reduction of vehicles used, maximizing profit, reduction in travel time variation and reduction of overall travel cost. To define these problems together, the term Vehicle Routing Problems was coined. This problem deals with the supply chain of an organization. Transportation is the backbone of the logistics of any organization and it takes up about 40 to 50 % of the total logistics cost, as stated in https://www.cogoport.com/blogs/transportcost (accessed on 11 October, 2021). This includes international and domestic transport, customs, all modes of transport such as air, water, land and so on. It can be inferred that transportation cost is a major and important factor in the supply chain of an organization, so its cost optimization becomes a necessity. The logistics branch of the organization must work on the management of transportation, deliver within customer provided time frames, competing with other organizations for better service and service rates effectively, handling unpredictable events and so on.
The world is witnessing the digital growth spurt and along with its influence on almost every sphere of life and nature. Integration of logistics and e-business will be a fruitful endeavor. This incorporation will lead to improvement in customer service, tracking, deliverance, time effectiveness as well as reduction in the overall cost.
Looking at the technical aspects of the Vehicle Routing Problem (VRP), there are initially p vehicles located at a depot that must deliver different amounts of supplies to q customers. Now, the VRP will aim to find the optimal route that a group of vehicles serve a group of users. This way a standard solution is obtained which contains all the routes that start and end at the depot, with the constraint that the goods are delivered within or before the time range set by the customer, capacity limit and the working time of the drivers are also considered. This paper will discuss how the Ant Colony Optimization with KMeans Clustering (ACO-KMeans) has been employed to minimize costs when delivering goods from depot to the customer within or before the time frame constraint set. The mathematical model defined in this paper will tackle and solve the problems related to distribution, e-logistics, retail networks and so on.
Dantzig and Ramser [1] were the first ones to introduce the Vehicle Routing Problem in 1959. Their solution was based on Linear programming. It was a truck dispatching problem that dealt with the delivery of gasoline at gas stations. Later, [2] Clarke and Wright came up with the savings method and it was termed as the Clarke-Wright algorithm. Their practical methodology gave better results than the Ramser-Dantzig algorithm. This was because the latter algorithm simply linked the customer pairs that were close to each other, which means that only distance constraint was considered, while the former not only considered the distance constraint, but they also reduced the distance rather than linking the two customers to different routes. Fast forward to 1992, Daskin and Malandraki came up with the time dependent vehicle routing problem (TDVRP) [3]. Then another solution was introduced by Ichoua et al. [4] which had a step function along with a piecewise linear function of time distribution which was fulfilling the FIFO (first in first out) principle, which was defined by T Jai Keerthy Chowlur Revanna * , Nushwan Yousif B.Al-Nakash ? , PhD Ahn et al. with this, several researches and studies popped up. Some were utilizing route construction savings method and an insertion method to solve incapacitated TDVRP(with/without time windows), some had heuristic solutions [8][9][10], some metaheuristic algorithms [5][6][7] and others hyper heuristics [11].
Figure 1. given below is 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 KMeans 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. Literature Survey
One of the heuristic solutions mentioned was provided by Hideki Hashimoto, Mutsunori Yagiura and Toshihide Ibaraki [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 neighborhood 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 neighborhood 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 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 heuristicbased 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 KMeans 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 researches based on this behaviour of ants, such as [21], which was the first paper to be published on this topic. Papers [22][23][24][25][26][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 KMeans Clustering algorithm to find the most optimal path to the customer.
# III. Mathematical Model of Proposed System
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, the equation is as follows
?????? ? ?? ??? ? ?? ,????? ?? ?? ???? ?? ???? ?? ??(1)
Here, ?? refers to the number of clusters and ?? refers to the centroid of clusters.
The next equation 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],
? ?? ??? 2 ?? ???? ?? = ? ????? 2 ?? ???? ?? ??? ? ??\{0, ?? + ?? + 1}, ?? ? ??, ?? ? ??, ?? ? ??(6)
Equations ( 7) and ( 8) have integrated time constraints, subtour elimination and load constraints.
???? ?? ?? + (?? ???? + ?? ?? ) ? ????????(1 ? ?? ???? ?? ) ? ???? ?? ?? , ??? ? ??, ?? ? ?? 1 , ?? ? ?? 2(7)???? ?? ?? + ?? ?? ? ????????(1 ? ?? ???? ?? ) ? ???? ?? ?? , ??? ? ??, ?? ? ?? 1 , ?? ? ?? 2 , ?? ? ??(8)
Now, if there is an order placed between two nodes and the pickup node must be visited before the delivery node, then equation (9) shows it.
???? ?? ?? ? ?? ???? (?? ?? + ?? ???? ) + ???? ?? ?? , ??? ? ??, ?? ? ??_??, ?? ? ??_??(9)
Equation (10) shows time constraint while (11) shows capacity bound constraint.
?? ?? ? ???? ?? ?? ? ð??"ð??" ?? , ??? ? ??\{0, ?? + ?? + 1}, ?? ? ??(10)(?? ?? + ?? ?? , ?? ?? ) ? ???? ?? ?? ? (0, ?? ?? ), ??? ? ??, ?? ? ??(11)
Now showcasing the constraint of limiting number of vehicles used and maximum working duration in equations ( 12) and (13).
? ????? ? ????? ?? 0?? ?? ? ??(12)?? ?????? ? ???? ??+??+1 ?? ? ???? 0 ?? , ??? ? ??(13)
This mathematical model is a small-scale solution.
# Approach to the Solution
In this paper, the Vehicle Routing Problem with Time Window constraint has been resolved using a modified version of the Ant Colony Optimization using KMeans Clustering. Marco Dorigo was the first person to introduce Ant Colony Optimization, in the 90s, in his Ph.D. thesis. The solution algorithm is based on the behaviour of ants, the way they live in colonies and search for food. While an ant goes around, searching for food, it leaves behind pheromones that act as a beacon. It acts as a communication mechanism and each time the ant leaves a pheromone trail, it tells the other ants about the quality and quantity of food the former ant had been carrying. This way, there are several set paths that the ants use based on the number of pheromones released in a path. The shortest and fastest route is chosen for maximum traffic.
Ant Colony Optimization (ACO) algorithm is a probabilistic technique based on the above phenomenon to find the optimal path. With the inclusion of KMeans Clustering, this modified approach has solved the constraints of the MPMDVRPTWHF, which has resulted in shorter time consumption, delivery within the time window and lower transportation costsalong with the inclusion of multiple pickup and delivery nodes wherein a pickup point might or might not have multiple delivery locations. The flowchart below showcases the solution setup. In the graph ?? = (??, ??), each arc (??, ??) has been assigned a variable called pheromone trail ?? ???? . The probabilities of better solution is directly proportional to the pheromone intensity. This means that when an ant wants to go to another node from its current node, it will choose the one with the maximum pheromone intensity. to make this work, a fixed quantity of pheromone is allocated to every arc. To decide which node to proceed to (node ??), the ????? ant will use the pheromone trail ?? ???? which is showcased below:
?? ???? ?? = [?? ???? ] ?? [?? ???? ] ?? ?? ???? ?? ?? ?? [?? ???? ] ?? [?? ???? ] ?? , ??ð??"ð??" ?????? ?? ?? (14)
Initially, all probabilities are set to 1. ?? = 1 ?? ???? is a heuristic value, pheromone concentration on the edge when the ant travels from node ?? to nodev??is denoted by ?? ???? and relative influence of the pheromone concentration and the heuristic value is shown by ??and ??.
If we go into the specifics, then ?? ???? denotes how much favourable is the next node ?? while ?? ???? implies how much better is the next node relatively.
# b) Solution Construction
In this scenario, the solution is generated when an artificial ant takes vehicles from the vehicle set and constructs a path, starting from the warehouse or depot, by choosing those nodes that satisfy the set of constraints. The ant continues to build the route until the limit of route length has been reached or when the time window constraint has been disobeyed. so, in forming the route, the ant will check each node whether it fulfils all the constraints and if it finds such a node, it will append it to the route, update the variables and go for the next node, using the updated variables. These changes in each iteration are all recorded in a solution set, which will then be used for finding the best solution from the set. When determining the optimal route for the best solution, pheromone update is used which includes pheromone deposition and pheromone evaporation. + ??? ? 0 and ?? is a constant. In each iteration, ?? number of ants find
?? ?????? = ? ?? ??=1 ?? ??
# ??
of average total distance. Then pheromone is updated by the elitist and best ants.
After the evaporation process, only the best and the elitist ants can update the pheromone deposits on the optimal path chosen, which is given by the equation
?? ???? = ?? ???? + ? ?? ???? * + ? ?? ?1 ??=1 ?? ???? ?? (16)
Where,
??? ???? ?? = { ?? ? ?? ?? ?? ??ð??"ð??" ????? ???????? ?????? ?????????????? ???? ???????? (??, ??)0 0 ????????????????? (17)??? ???? * = { ?? ???? ??ð??"ð??" ???????? ???????? ??ð??"ð??" ???????????????? ???? (??, ??)0 ?????????????????(18)
Looking at equations 17 and 18, it can be concluded that there are two types of pheromone depositions that are deposited on the trails during the pheromone update process. First, if ?? elitist ants have travelled a path, that path will be updated as the best solution so far (????), in accordance with the ACO+KMeans Clustering algorithm. ??? ???? * denotes the pheromone update by the elitist ants. Second, out of the ?? ants available, only (?? ? 1) best ants, in the current iteration, can deposit pheromone on the path they have traversed. The term ???? ???? ?? is used to denote the pheromone quantity laid down on the trails that have been traversed by them and the amount of pheromone that have been deposited by the ants are determined by their solution quality ?? ?? and rank ?? and the value is equal to ???? ???? ?? . To summarize, the elitist ants need to increase the probability of the best-solution so far after each iteration as the values that are updated will act as reference values for the next iteration. The ranking methodology has been employed in [17] so as to reduce pheromone deposition on those routes that have relatively lesser favourability.
# Case Study a) Dataset Used
The dataset has been obtained from consulting firms Horizon Consulting Inc. and EATEAM Inc. and their clients from students CPT work and it has been preprocessed to Solomon-100 standard test set which have 20 problem cases. The pre-processed real world dataset from above firms includes x-y location coordinates, service time, demand by customers, due dates and ready time. This section will be in comparison with [30] as it has used the same data set. This comparison will help in proving that the proposed solution from this paper is the better method of solving the (MPMDVRPTWHF) as it gives better cost reduction with lesser percentage of carbon emissions, along with optimized fuel consumptions and lesser vehicles used.
# b) Parameters Defined
The parameters defined in this paper are derived from [30] as this paper is in comparison with the latter. Similar to [30] the delivery vehicle used is a refrigerator car and the set of pre-defined parameters are given below.
# Parameters
# c) Result Analysis
The entire result section has used the Pareto optimal principle for obtaining the solution. The Pareto Principle states that 80 percent of a project's benefit comes from 20 percent of the work. The optimal version of it makes the sub objectives suppressed so as to efficiently solve the main objective. Due to this there is very little scope of conflict of objectives from the sub objectives and a noiseless solution id obtained.
Referring to [30], this paper the objectives chosen will be carbon emission reduction, total cost, time frame and customer satisfaction.
Using several test cases of 25,50,75 and 100 customers in three different scenarios, the proposed ACO algorithm with KMeans clustering provides a better solution in comparison. The results are arranged in the Pareto optimal solution format. 25) test table is used here for obtaining the most optimal path with better results of the constraints set. This solution has used the Pareto optimal approach and figure 3 has shown the comparison between [3] and this paper. It is clearly visible from the graph that the proposed algorithm of ACO+KMeans [PS_KPSO] clustering has better output in terms of carbon emission, customer satisfaction and total transportation cost. This part has used the c101(50) test table. 5 trucks have been employed with respective paths (0, 43, 42, 41, 40, 44, 46, 45, 48, 50, 49, 47,0), (0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1,0), (0, 20, 24, 25, 27, 29, 30, 28, 26, 23, 22, 21,0), (0, 32, 33, 31, 35, 37, 38, 39, 36, 34,0) and (0, 13,17,18,19,15,16,14,12,0). The end are 33.43 for carbon emissions, 5942.72 cost and 100 percent customer satisfaction. Figure 5 shows the comparison between [30] and this paper results while figure 6 displays the routes taken by the 5 trucks. The c101(75) dataset has been used in this part. The number of vehicles used is 8 with the most optimal paths chosen respectively: (0, 43, 42, 41, 40, 44, 46, 45, 48, 51, 50, 52, 49, 47, 0), (0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1, 75, 0), (0, 32, 33, 31, 35, 37, 38, 39, 36, 34, 0), (0, 67, 65, 63, 62, 74, 72, 61, 64, 68, 66, 69, 0), (0, 20,24,25,27,29,30,28,26,23,22,21,0), (0, 57, 55, 54, 53, 56, 58, 60, 59, 0), (0, 13,17,18,19,15,16,14,12,0) and (0, 71, 70, 73, 0)
The final results of carbon emissions, total cost and customer satisfaction are 54.96, 10639.71 and 100 percent respectively. Figures 7 and 8 showcase the comparison between [30] and this paper and the route distribution of the vehicles.
# Global Journal of Computer Science and Technology
Volume XXII Issue I Version I This section has used the c101 (100) dataset. Now looking [30], there are better results in terms of carbon emission, cost and customer satisfaction (69.03, 13561.41 and 100 percent). Instead of 23 vehicles, 10 vehicles have been employed and the most optimal paths are chosen: (0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1, 75, 0), (0, 43, 42, 41, 40, 44, 46, 45, 48, 51, 50, 52, 49, 47, 0), (0, 20,24,25,27,29,30,28,26,23,22,21,0), (0, 67, 65, 63, 62, 74, 72, 61, 64, 68, 66, 69, 0), (0, 90, 87, 86, 83, 82, 84, 85, 88, 89, 91, 0), (0, 57, 55, 54, 53, 56, 58, 60, 59, 0), (0, 98, 96, 95, 94, 92, 93, 97, 100, 99, 0), (0, 32, 33, 31, 35, 37, 38, 39, 36, 34, 0), (0, 13,17,18,19,15,16,14,12 Looking at all the results above, it is easily discernible that the ACO+KMeans clustering algorithm has performed way better than the improved Ant Colony algorithm and the normal Ant Colony Algorithm. With lesser number of vehicles employed, lesser carbon emission levels noted and better cost management, the proposed system has shown its effectiveness and viability for usage in the real-world logistics problems. The proposed algorithm PS_KPSO has provided about 10.37%, 46.9%, 61.98% and 78.81% reduction in total costs for 25, 50, 75 and 100 customers while there are about 46.61% , 53.27% and 61.16% reduction in total carbon emissions for 50, 75 and 100 customers, when compared with [30]. Along with the aforementioned improvements, there is 100% customer satisfaction in all the cases. The proposed algorithm (ACO+KMeans Clustering) has outperformed the Modified Ant Colony Algorithm and the original Ant Colony algorithm. Table 2 compares the results of the proposed algorithm and modified ant colony algorithm.
# Global Journal of Computer Science and Technology
Volume XXII Issue I Version I In the Solomon-100 dataset, there are three formats of destination grouping. One is a cluster format (C), one is a random format (R) and one is a randomclustered format (RC). These three formats have been used for 25, 50, 75 and 100 customers. So other than C101, there are C201, R211, R201 and RC201. The comparison between the proposed algorithm (ACO+KMeans algorithm) and modified Ant Colony algorithm [30] have been given in Table 4. The data from Table 4 helps in evaluating the effectiveness of the proposed algorithm. Even with increase in the number of customers, be it clustered, random or both, there is barely any increase in the number of vehicles employed. With an average of 2.625 vehicles per case, this greatly affects the total travel, storage, damage and fuel costs while reducing the carbon footprint by a great extent, ultimately helping not only the economy of the organisation but also trying to improve the environmental condition of the Earth. It can be assumed from the results data that there is a high probability of increase in number of customers. As the number of vehicles employed is less, there is scope of increasing customer reach and maybe there is a chance of increasing the speed of delivery. With the new electronic vehicle usage, there will be even more cuts in the carbon footprint value and better customer coverage.
# Conclusion
This paper discusses the vehicle routing problem with time window constraint (VRPTW) along with added constraints of number of vehicles, logistics cost, overall carbon emission rate along with multiple pickup and delivery points faced by firms EATEAM and Horizon Consulting Inc. in their logistical operations. A meta heuristic Ant Colony Algorithm with KMeans Clustering was employed to solve the problem statement. Looking at the literature survey in this paper, it is observable that Vehicle Routing Problem has had several approaches with varying results, which in turn leads to the fact that VRP with added constraints is a difficult problem to solve.
The solution provided in this paper has been compared with [30], which has a similar problem statement, and the results of the proposed Ant colony Algorithm with KMeans Clustering has performed far better and has provided very less scope of improvement in the discussed problem areas.
In future researches on similar topics, it's a hope that this paper will be a good leverage for the researchers and this solution can be further modified for more improvements.
2![Figure 2: Flow of the proposed solution a) Parameter initialization Looking at the research done in [28], the following parameters are set as follows: Number of ants ?? = 22, ?? = 2, ?? = 5, ?? = 0.80, ?? = 80, ?????????????? ???????? ?? = 3.](image-2.png "Figure 2 :")
![](image-3.png "(")
3![Figure 3: c101(25) comparison with [30] (ACOMO) and ACO+KMeans Clustering (PS_KPSO) PS_KPSO algorithm has given total cost as 3138.07, lower carbon emission of 19.50 and 100 percent customer satisfaction in all cases. The trucks used is 3 with respective optimal travel paths (0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1,0), (0, 13, 17, 18, 19, 15, 16, 14, 12,0) and [(0, 20, 24, 25, 23, 22, 21, 0).](image-4.png "Figure 3 :")
4![Figure 4: c101(25) vehicle distribution route ii. 50 Customers This part has used the c101(50) test table. 5 trucks have been employed with respective paths (0, 43, 42, 41, 40, 44, 46, 45, 48, 50, 49, 47,0), (0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1,0), (0, 20, 24, 25, 27, 29, 30, 28, 26, 23, 22, 21,0), (0, 32, 33, 31, 35, 37, 38, 39, 36, 34,0) and (0,](image-5.png "Figure 4 :")
5![Figure 5: c101(50) comparison with [30] (ACOMO) and ACO+KMeans Clustering (PS_KPSO)](image-6.png "Figure 5 :")
6![Figure 6: c101(50) vehicle distribution route iii. 75 Customers The c101(75) dataset has been used in this part. The number of vehicles used is 8 with the most optimal paths chosen respectively: (0, 43, 42, 41, 40, 44, 46, 45, 48, 51, 50, 52, 49, 47, 0), (0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1, 75, 0), (0, 32, 33, 31, 35, 37, 38, 39, 36, 34, 0), (0, 67, 65, 63, 62, 74, 72, 61, 64, 68, 66, 69, 0), (0, 20, 24, 25, 27, 29, 30, 28, 26, 23, 22, 21, 0), (0, 57, 55, 54, 53, 56, 58, 60, 59, 0), (0, 13, 17, 18, 19, 15, 16, 14, 12, 0) and (0, 71, 70, 73, 0)The final results of carbon emissions, total cost and customer satisfaction are 54.96, 10639.71 and 100 percent respectively. Figures7 and 8showcase the comparison between[30] and this paper and the route distribution of the vehicles.](image-7.png "Figure 6 :")
7![Figure 7: c101(75) comparison with [30] (ACOMO) and ACO+KMeans Clustering (PS_KPSO)](image-8.png "Figure 7 :")
8![Figure 8: c101(75) vehicle distribution route iv. 100 Customers This section has used the c101 (100) dataset. Now looking [30], there are better results in terms of carbon emission, cost and customer satisfaction (69.03, 13561.41 and 100 percent). Instead of 23 vehicles, 10 vehicles have been employed and the most optimal paths are chosen: (0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1, 75, 0), (0, 43, 42, 41, 40, 44, 46, 45, 48, 51, 50, 52, 49, 47, 0), (0, 20, 24, 25, 27, 29, 30, 28, 26, 23, 22, 21, 0), (0, 67, 65, 63, 62, 74, 72, 61, 64, 68, 66, 69, 0), (0, 90, 87, 86, 83, 82, 84, 85, 88, 89, 91, 0), (0, 57, 55, 54, 53, 56, 58, 60, 59, 0), (0, 98, 96, 95, 94, 92, 93, 97, 100, 99, 0), (0, 32, 33, 31, 35, 37, 38, 39, 36, 34, 0), (0, 13, 17, 18, 19, 15, 16, 14, 12, 0), (0, 81, 78, 76, 71, 70, 73, 77, 79, 80, 0). Figures 9 and 10 showcase the comparison](image-9.png "Figure 8 :")
![, 0), (0, 81, 78, 76, 71, 70, 73, 77, 79, 80, 0). Figures9 and 10showcase the comparison between[30] and this paper and the route distribution of the vehicles.Global Journal of Computer Science and TechnologyVolume XXII Issue I Version I](image-10.png "")
9![Figure 9: c101(100) comparison with [30] (ACOMO) and ACO+KMeans Clustering (PS_KPSO)](image-11.png "Figure 9 :")
10![Figure 10: c101(100) vehicle distribution route a. ComparisonLooking at all the results above, it is easily discernible that the ACO+KMeans clustering algorithm has performed way better than the improved Ant Colony algorithm and the normal Ant Colony Algorithm. With lesser number of vehicles employed, lesser carbon emission levels noted and better cost management, the proposed system has shown its effectiveness and viability for usage in the real-world logistics problems. The proposed algorithm PS_KPSO has provided about 10.37%, 46.9%, 61.98% and 78.81% reduction in total costs for 25, 50, 75 and 100 customers while there are about 46.61% , 53.27% and 61.16% reduction in total carbon emissions for 50, 75 and 100 customers, when compared with[30]. Along with the aforementioned improvements, there is 100% customer satisfaction in all the cases. The proposed algorithm (ACO+KMeans](image-12.png "Figure 10 :")
13![Figure 13: c201(75) vehicle distribution route](image-13.png "Figure 13 :")
14![Figure 14: c201(100) vehicle distribution route](image-14.png "Figure 14 :")
11![Figure 11: c201(25) vehicle distribution route Figure 12: c201(50) vehicle distribution route](image-15.png "Figure 11 :")
1517![Figure 15: r201(25) vehicle distribution route Figure 16: r201(50) vehicle distribution route](image-16.png "Figure 15 :Figure 17 :")
19![Figure 19: r211(25) vehicle distribution route Figure 20: r211(50) vehicle distribution route](image-17.png "Figure 19 :")
21![Figure 21: r211(75) vehicle distribution route Figure 22: r211(100) vehicle distribution route](image-18.png "Figure 21 :")
23![Figure 23: rc201(25) vehicle distribution route Figure 24: rc201(50) vehicle distribution route](image-19.png "Figure 23 :")
25![Figure 25: rc201(75) vehicle distribution route Figure 26: rc201(100) vehicle distribution route](image-20.png "Figure 25 :")
![](image-21.png "")
Pheromone update is used to elevate the pheromonevalues either increase or decrease at a constant ratevalues that are found on good solution paths and[29].decrease those that are on bad solution paths. InThe pheromone evaporation equation is givenpheromone deposition and evaporation, pheromoneas such,?? ???? = ?? ???? ? ?? ?????? ??+ ???,?(??, ??) ? ??(15)Where trail persistence 1 ? ?? ? 0 of theevaporation factor 1 ? ??? ?? ??????Year 2022)D??© 2022 Global Journals
2ACOMOPS_KPSOPIDNUM_CUSTC (CNY)CECSNVC (CNY)CECSNVC101_25253481.3119.7398.453138.07082319.50420315 1003C101_50509583.753.7599.2115942.71764833.43172956 1005C101_757520195.2794.8799.471710639.7098954.95890959 1008C101_10010031202.27129.8799.62313561.4071469.03832969 10010b. Results with other test cases
4PS_KACOACOMOPIDNUM_CUST TOT_VEHNVCCECSNVCCECSC_201_2525252215.54314.8641003613.8122.28100C_201_5050252444.96119.7345 10061232.842.46100C_201_7575253511.0926.2824 10092177.3458.81100C_201_100100253591.55727.9907 100132221.7199.08100r_201_2525252543.69321.8306 1005946.3945.17100r_201_50502521039.3932.3543 10061404.8269.75100r_201_75752531368.5844.4869 10072482.7598.4100r_201_1001002541995.1962.9339 100132931.63111.02100r_211_2525251375.43213.1144 100240024.11100r_211_50502521391.4239.8279 100760044.87100r_211_75752521199.9935.7638 1007873.4172.94100r_211_1001002531867.2855.0745 10091080.6484.49100r_c201_2525252454.04619.9274 1004847.1831.43100r_c201_5050253974.70336.1249 10081554.4780100r_c201_75752541623.555.0429 100102186.5121.39100r_c201_1001002541927.4761.4963 100112959.41139.2100
*
The truck dispatching problem
GBDantzig
JHRamser
Management Science
6
1
1959
*
Scheduling of vehicles from a central depot to a number of delivery points
GClarke
JWWright
Operations Research
12
4
1964
*
Time dependent vehicle routing problems: formulations, properties and heuristic algorithms
Malandraki C
Daskin M S
Transportation Science
26
3
1992
*
Vehicle dispatching with time-dependent travel times
Ichoua S
MGendreau
Potvin J Y
European Journal of Operational Research
144
2
2003
*
A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food
Osvald A
Stirn L Z
Journal of Food Engineering
85
2
2008
*
Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem
YKuo
Computers & Industrial Engineering
59
1
2010
*
An ant colony algorithm hybridized with insertion heuristics for the time de pendent vehicle routing problem with time windows
Balseiro S R
RamonetLoiseau I
Computers & Operations Research
38
6
2011
*
An iterated local search algorithm for the timedependent vehicle routing problem with time windows
Hashimoto H
Yagiura M
Ibaraki T
Discrete Optimization
5
2
2008
*
The time dependent vehicle routing problem with time windows: benchmark problems, an efficient solution algorithm, and solution characteristics
Figliozzi M A
Transportation
*
Vehicle routing under time-dependent travel times: the impact of congestion avoidance
HansEKok A L
Schutten J
Computers & Operations Research
39
5
2012
*
Two phase algorithm for solving VRPTW problem
Minocha B
Tripathi S
International Journal of Artificial Intelligence and Expert Systems
4
1
2013
*
Approximative Solutions to the Bicriterion Vehicle Routing Problem with Time Windows
JMüller
European Journal of Operational Research
202
2010
*
A Survey on the Vehicle Routing Problem and Its Variants
SNKumar
RPanneerselvam
Intelligent Information Management
4
2012
*
The Electric Vehicle Routing Problem With Time Windows and Multiple Recharging Options
HMao
JShi
YZhou
GZhang
10.1109/ACCESS.2020.3003000
IEEE Access
8
2020
*
A Disruption Recovery Model for Time-Dependent Vehicle Routing Problem With Time Windows in Delivering Perishable Goods
YWu
BZheng
XZhou
10.1109/ACCESS.2020.3032018
IEEE Access
8
2020
*
Brainstorming-Based Ant Colony Optimization for Vehicle Routing With Soft Time Windows
LWu
ZHe
YChen
DWu
JCui
10.1109/ACCESS.2019.2894681
IEEE Access
7
19643-19652, 2019
*
The space filling curve with optimal partitioning heuristic for the vehicle routing problem
RLBowerman
PHCalamai
Eur. J .Oper. Res
76
1994
*
A cluster-based optimization approach for the multi depot heterogeneous fleet vehicle routing problem with time windows
RDondo
Cerda
Eur. J. Oper. Res
176
2007
*
A guide to vehicle routing heuristics
.FCordeau
MGendreau
GLaporte
.YPotvinand
FSemet
J. Oper. Res. Soc
53
2002
*
An artificial ee colony algorithm for the capacitated vehicle routing problem
WYSzeto
YWu
SCHo
Eur
*
Oper. Res
215
2011
*
Applying the ant system to the vehicle routing problem
BBullnheimer
RFHartl
CStrauss
Meta-Heuristics: advances and Trends in Local Search or Optimization
*
SVoss
SMartello
IHOsman
CRoucairol
2012
Kluver Academic Publishers
Boston, MA, USA
*
Ant colony optimization for capacitated vehicle routing problem
WFTan
LSLee
ZAMajid
HVSeow
J. Comput. Sci
8
2012
*
Savings Ants for the vehicle routing problem
KDoerner
MGronalt
RFHartl
MReimann
CStrauss
MStummer
Lect. Notes Comput. Sci
2002, 2279
*
An Improved ACO for the multi-depot vehicle routing problem with time windows
YMa
Han
KKang
FYan
Proceedings of the Tenth International Conference on Management Science and Engineering Management
Xu
AHajiyev
SNickel
MGen
the Tenth International Conference on Management Science and Engineering ManagementSingapore
Springer
2018
*
A new hybrid ant colony optimization algorithm for the vehicle routing problem
XZhang
LTang
Pattern Recognit. Lett
30
2009
*
An ant colony algorithm for the capacitated vehicle routing. Electron. Notes Discret. ath
SMazzeo
ILoiseau
2004
18
*
An improved ant colony optimization for vehicle routing problem
BYu
ZZYang
BZYao
Eur. . Oper. Res
196
2009
*
An Improved ACO for the multi-depot vehicle routing problem with time windows
YMa
.;Han
KKang
FYan
Proceedings of the Tenth International Conference on Management Science and Engineering Management
the Tenth International Conference on Management Science and Engineering Management
*
,Xu
AHajiyev
SNickel
MGen
2018
Springer
Singapore
*
An improved ant system for the vehicle routing problem
BBullnheimer
RFHartl
CStrauss
Ann. Oper. Res
89
1999
*
Cold Chain Logistics Path Optimization via Improved Multi-Objective Ant Colony Algorithm
BZhao
HGui
HLi
JXue
doi: 10.1109/ ACCESS.2020.3013951
IEEE Access
8
2020