Month: October 2021

Solving a capacitated VRP with the nearest neighbor heuristic in R

shibaprasadbLeave a comment

Google OR Tools have dedicated functions and packages for Python, C++, Java and C#. But there is nothing available for R. So, in this post, I aimed to tackle the Capacitated VRP in R, with the help of the nearest neighbor heuristic. The result obtained here is encouraging. That’s why I am sharing it in the blog post. The main aim here is to even better this approach with open-source collaboration. The Github link has also been shared at the end of this post.

Before proceeding further, let’s have a look at some of the details of the VRP function:

  1. The function will accept a list of vehicles with distinctive ids and capacities. It is assumed that the capacity of the vehicles are enough to meet the customer demand for the given day.
  2. The nearest neighbor heuristic is an example of a greedy algorithm. Which signifies that it will search for the local optimum solution. In order to find the best result, a user defined parameter (either can be the total time of iterations or the number of iterations) is introduced and through these iterations, the best solution can be obtained.
  3. In order to obtain the best solution, a cost function needs to be introduced. Here the cost function is designed with a simple assumption that the cost for each vehicle depends on the duration for which they have been hired. And if two vehicles are hired for the same duration then the cost will be more for the vehicle with more capacity.
  4. One advantage of this approach is both homogeneous and heterogenous fleets can be easily accomodated in the model without any effort.
  5. The model can be built by taking into account either distance or time, whatever the designer may like. For distance the Geodist can be used, for travel time OSRM package can be used or any model built for a specific problem statement can be utilised. In this example travel time has been computed considering the speed to be 9 km/hr.

The code is available here: https://github.com/shibaprasadb/Capacitated_VRP_with_nearest_neighbor

The clouds of our lives

shibaprasadbLeave a comment

A few days back, during a mere Uber ride, I was thinking about the clouds. Yes, the clouds. Have you ever wondered about them? Clouds are everywhere. They are ever-present. Be it the scorching May or the overcast August or even the wintry December. Whenever you’ll look at the sky, you’ll notice them. But there is a strange thing about them. We see the clouds, we notice the clouds but we only acknowledge their presence when it rains. At least most of the time this is the case.

I was thinking about the striking similarity between this phenomenon and another one in our mortal life. We come across so many people in our daily life. If you keep the count then it will be in lakhs. Among these lakhs, only very few touch us in a way that we can never forget about them. We often find something very unique, something very pure about them that always stays with us. Often we don’t meet these ‘clouds’ in our life ever again. But somehow we remember their essence in our life. Sometimes on a mundane day, these ‘clouds’ float around and we suddenly remember ‘that day’ or ‘that moment’ when once it rained.

At this point of time, I suddenly came back to reality by the murmuring voice of Mark Knopfler coming from my earphones:

“And you still refuse to be traced

Seems to me such a waste

And every victory has a taste that’s bittersweet

And it’s your face I’m looking for on every street”

I smiled a bit under my mask. I felt at peace.