{'fraction_non_alphanumeric': 0.016845180136319377, 'fraction_numerical': 0.005063291139240506, 'mean_word_length': 4.957656612529003, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Distribution Route Optimization of a Capacitated Vehicle Routing Problem by Sweep Algorithm

This paper presents the application of a sweep algorithm to optimize distribution route of a Capacitated Vehicle Routing Problem (CVRP). The objective of this research is to find a set of optimal routes that minimizes the number of vehicles required and total distance travelled for all vehicles to serve customers. The algorithm consists of two phases, a clustering phase and a route generation phase. Experimental results from its application to a real-world case of PT Eastern Pearl Flour Mills, Indonesia are presented. The obtained vehicle routes which are compared against the existing daily distribution routes showing that significant savings can be gained on the daily cost of transportation related expenses. The number of vehicle routes and vehicle used for delivery are reduced and therefore, the distance travelled and the utilization of the vehicles are also improved. The algorithm applied in this research would be suitable for solving practical vehicle routing optimization problems in other logistics companies.


Introduction
The vehicle routing problem (VRP) aims to determine a set of optimal vehicle routes through a number of customer locations in which each route originates and terminates at the same depot. The problem was firstly introduced by Dantzig and Ramser [1] as a generalized of travelling salesman problem (TSP) and since then several variants of VRP have been studied by researchers in different areas such as Operations Research, Computer Science, Decision Support Systems, and Artificial Intelligence. One of the basic versions of VRP is Capacitated Vehicle Routing Problem (CVRP) in which customers with known demand are visited by a homogeneous fleet of vehicles with limited capacity. The number of customers to serve in a route is considerably constrained by capacity limitation of vehicles. The simplest form of CVRP considers one depot, several customers with known demand and known locations to be served by vehicles with equal capacity. The objective is to find a solution that minimizes either the number of vehicles and/or total travelling cost (time or distance) for all vehicles to serve customers.
The object of study and observation is PT Eastern Pearl Flour Mills (EPFM). PT EPFM is the largest of Interflour's mills, located in Makassar on the west coast of the island of Sulawesi in Eastern part of Indonesia. It currently operates two flour mills, one sea-side and the other city-side mills joined by a conveyor system. The wheat flour-milling factory is one of the primary producers of flour in Indonesia with its products distributed across the nation. EPFM's flour product range supplies to all demands from 1kg consumer packs, 25kg and 50kg packs in the domestic market. The factory sells many different types of flour directly to large institutional buyers as well as small to medium sized enterprises (SMEs), while also utilizing a widespread distributor network (distributors, wholesalers, and retailers). Currently, a fleet of vehicles outsourced for distribution of a number of products to a set of customers according to 2 their requirements. The delivery is made on daily basis directly to dealers or to end consumers. In this study, the fleet for this delivery operation is considered homogeneous with each truck has a capacity of 15 tons. There are no time windows at the customers, but it is necessary to conform with the factory working hours. This research was carried out in Makassar city and data collected only for daily distribution of the company in this region.
There have been various types of algorithms developed as an attempt to solve the vehicle routing problems. Metaheuristics such as tabu search and simulated annealing have been applied to provide the best path comply with the needs of the customers to find the optimized routes for delivering the packets to the customers [2]. An integrated modelling and optimization framework for solving complex and practical VRP had also been proposed in [3]. Variants of the sweep algorithm have been proposed in [4] to find optimal tours for vehicles with given capacity constraints to distribute goods to customers within allocated time windows. This research applies a sweep algorithm as a solution method to find the most optimal set of routes that minimizes the number of vehicles required and total distance travelled for all vehicles to serve customers.

Solving CVRP using Sweep Algorithm
Sweep algorithm is a two-phase constructive algorithm consisting of two stages known as cluster-first, route-second [5]. Sweep algorithm is applied for clustering the given customer nodes. In the first phase the algorithm decomposes the problem by clustering customers based on their positions in polar coordinates. Location of the warehouse (depot) is the coordinate center (0,0) of the two-dimensional Cartesians plane (x, y). Polar coordinates (r, ) of each individual node are computed with respect to the coordinate center and the nodes are ordered according to polar angle. The criteria for clustering customers are the minimal polar angle and the capacity of the vehicle assigned to the cluster. Cluster formation begins with the least polar angle nodes and continues sweeping customer nodes by increasing polar angle. Sweeping is discontinued when the included next customer node would violate maximum limit of the vehicle capacity. The demands of all the selected customers in one cluster has to be less than or equal to the capacity of the vehicle assigned to the cluster. A new cluster is created by continuing the sweeping where the last one left off. The process of adding customer nodes into cluster is repeated until all customer nodes have been included. There are nine clusters formed based on the requirement that the total demand in one cluster must be less than the maximum truck capacity of 15 tons: Cluster 1 = (23), Cluster 2 = (12, 16, 3, 4   The next stage is to apply nearest neighbour algorithm. The location of customers in the clusters formed from the previous stage will be sequenced and scheduled for vehicle tours. A tour is built based on the traveling distance from the vehicle last-visited point (node) to the next point closest in the network. The procedure begins with the base depot node and then finding the node which is the closest to the last included node in the path. This procedure is repeated until all nodes have been added to the path. The first and the last nodes in the path are then connected to make a complete tour.

Experimental Studies
In order to implement the sweep algorithm, locations and demands information of customers are firstly defined. The number of vehicles and the existing distribution routes taken by vehicles to serve customers are also determined as well as the distance from depot to every distribution point. Distance matrix is prepared by using data obtained from the coordinates of the customer's address on Google maps. The procedure is performed by determining customer's locations which are points in a plane geometry with distances represents the traveling costs. The distance between coordinate (xi, yi) and (xj, yj) is then calculated. The polar coordinates of each customer are determined with respect to the location of the base depot and sorted by increasing polar angle. Capacity limitation of the vehicle assigned to the cluster is considered as constraint and sweep is terminated when including the next customer node would violate maximum limit of the vehicle capacity. Through this procedure the customers have been clustered by vehicles.
Application of sweep algorithm generated nine distribution routes. Table 2 shows the nine vehicle routes that have been generated by applying the sweep algorithm. Cluster 1 covers total demand of 7.8 tons even though vehicle capacity 15 tons. Total distance travelled to serve customers in a day by nine vehicles is 142,8 km. Total demands in this case are supplied by nine routes which correspond to the number of vehicles. Among the nine routes obtained, the fourth route serves customers with truck capacity exactly the same as the customers' demand. Figure 3 shows optimized routes taken using Google maps.  Computational results show that total demands can be fulfilled by nine clusters that is equal to the number of vehicles. The total distance travelled daily can be reduced from 255.84 km to 142.8 km. The number of vehicle fleets is also reduced from 14 vehicles to 9 vehicles. The obtained vehicle routes which are compared against the existing company's daily distribution routes indicating that, the daily cost of transportation related expenses may be reduced as there is a significant reduction in the total distance travelled and the number of vehicles used for the daily delivery of the company.

Conclusion
This paper presents an application of sweep algorithm to solve CVRP. The objective is to find a set of optimal vehicle routes with given capacity constraints to distribute products to customers. Case study from a wheat flour industry is taken and its distribution performance is evaluated with daily delivery points of 24 customers spread across the city. The optimized vehicle routes which are compared against the existing daily distribution routes indicating that significant savings can be gained on the daily cost of transportation related expenses. The sweep algorithm applied for generating vehicle routes is capable of obtaining shorter vehicle routes than the existing routes operated by the company. The total distance travelled for the fleet of vehicles to distribute flour products to customers can be reduced significantly and therefore the number of vehicles utilized also can be minimized to five vehicles only. The sweep algorithm applied in this paper provides better solutions in terms of the traveling distance, traveling time, the number of vehicles utilized, and the daily work capacity balances under the specified constraints considered in the work. The company's daily distribution and logistics performance may be improved and the algorithm used in this study can be applied to practical vehicle routing problems arising in many other logistics and distribution companies.