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

Vehicle Routing Problem with Time Window Constrain using KMeans Clustering to Obtain the Closest Customer Jai Keerthy Chowlur Revanna ∗ , Nushwan Yousif B.Al-Nakash † , PhD ∗ Information Systems Engineering and Management Harrisburg University of Science and Technology Email: jchowlur@my.harrisburgu.edu , nal-nakash@harrisburgu.edu Abstract- In this paper, the problem statement is solving the Vehicle Routing Problem with Time Window constraint using the Ant Colony Algorithm with K-Means Clustering. In this problem, the vehicles must start at a common depot, pickup from various warehouses, deliver to the respective nodes within the time window defined by the customer and return back to the depot. The objectives defined are to reduce number of vehicles employed, the total logistics cost and to reduce carbon emissions. The mathematical model described in this paper has considered multiple pickup and multiple delivery points. The proposed solution of this paper aims to provide better and more efficient solution while minimizing areas of conflict so as to provide the best output on a large scale. I. I ntroduction 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/transport- cost (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 endeavour. 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 K-Means Clustering (ACO-K-Means) 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 Ahn et al. with this, several research and studies T Global Journal of Computer Science and Technology Volume XXII Issue I Version I 49 ( )D Year 2022 © 2022 Global Journals