Hande Kocbey
Dec 5, 2020 · 5 min read

Route Optimization with Trendyol Data (Clarke and Wright Algorithm And Sweep Algorithm)

With its intensive use in today’s global market, e-commerce sites have products with short life cycles, intense competition, and a certain amount of increase in customers’ orders, it has become obligatory for enterprises in the production sector to give importance to the distribution and collection systems and to allocate a certain budget. New habits such as mobile world, same-day distribution-delivery, and even daily grocery shopping online have led to the continuous development of logistics management. In order to keep up with this change and development in communication and transportation technologies, e-commerce sites also had to work. As a result of these events, Vehicle Routing Problem has become the most important part of logistics systems and many systems.

Operators in the manufacturing sector allocate between 30 percent and 60 percent of costs for distribution and collection. Since it covers the majority of the costs; Efficient use of the capacity and personnel of the distribution vehicles has gained importance. A tool to reduce the costs related to distribution and increase the quality of the service provided to customers; Finding the most suitable customer route to reach customers’ demands has become one of the most important issues in today’s technology. In cases where businesses do not plan a route in delivery works; It has been observed that customers are faced with problems such as dissatisfaction, not being able to use the resources effectively, increase in planning time and costs.

In order to offer a solution to the Vehicle Routing Problem, route optimization is performed with different methods. In this article, I will show the application of Sweeping and Saving Algorithms, one of the classical heuristic algorithms. The most real examples of the vehicle routing problem were encountered in Trendyol Express (TEX) processes. The number of branches and employees of TEX is increasing day by day, cargo companies having problems in capacity utilization during the event periods, and the number of orders and customers are constantly increasing; It suggested that route optimization could be beneficial.

For this reason, it was necessary to decide which of the Vehicle Routing Problem types it fits, depending on the business process. In this case, since each vehicle has a certain capacity and it is necessary to act within the capacities, it is considered as a Capacity Limited problem. Then a data model was created. Address information and order numbers have been taken independently from other customer information. The location information of the branches is taken in a way that does not give the exact point. The data model was created as follows.

Image for post
Image for post
  • Clarke and Wright Algorithm

Seeing the work of Dantzig and Ramser as a source of inspiration, Clarke and Wright developed this algorithm. This algorithm based on changing to find the best route combination among the route combinations in each iteration; It is one of the most preferred tour constructor algorithms among heuristic algorithms. In the scenario where there is no saving algorithm; The vehicle from the shipping company will return to the warehouse for each customer. According to the theory advocated by this algorithm, establishing a connection between customers without going to the warehouse creates savings for each customer. We can also measure whether there is savings by the difference between the two points connected or not. The following figure shows the purpose of the saving algorithm in its simplest form.

Image for post
Image for post
Image for post
Image for post

As a result of the Savings Algorithm outputs, with a capacity of 35 customers and 150 vehicles, the following route emerges.

  • Sweep Algorithm

Sweep algorithm was found by Gillett and Miller. Suppose polar coordinates are available for all points to be visited by vehicles. The visiting points are accepted as the Branch’s starting point and their angles to the Branch are calculated and listed. Then, by adding demand points to a route while these demand points are swept, the routes are arranged: starting from the origin (angle can be set to 0), the points are included in a cluster where they are swept up to a payload. If the tool capacity is full, it prevents the next point from being added to the set. This point becomes the starting point for the next route, and the process is complete when all points are swept away.

The simple description of the Sweep Algorithm is as follows.

Image for post
Image for post

As a result of the Sweeping Algorithm outputs with a capacity of 35 customers and 150 vehicles, the following route emerges.

Image for post
Image for post
Image for post
Image for post
Image for post
Image for post

Saving algorithm; Using a mathematical formula causes time complexity. Sweep algorithm; Time creates complexity during clustering. Therefore, the saving algorithm takes longer. Capacity constant: 150 while; I have observed in how long it reaches the optimum result in different number of customers. Saving; Having capacity controlled going and sweeping at each stage a. Checking the capacity only during clustering created capacity usage differences when looking at the%. However, 2 algorithms were tested by increasing the Capacity and how they behaved was observed. Changing the parameters has been helpful to achieve the best result.

Gains, losses and shortcomings of each technique have been observed. As a result of the findings, the effect of the number of customers to be served and the vehicle capacity in the formation of delivery costs were measured. Savings Algorithm; It has been observed that vehicles have benefits in terms of less distance and less fuel cost. Capacity uses are; It was measured by observing how many orders the vehicle took on each route and started its journey. It has been seen that the Saving Algorithm uses the capacity better with a rate of 93%

Image for post
Image for post

Trendyol Tech

Trendyol Tech Team

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store