Posts Tagged routing problem

There are times when we wish Doraemon’s magical-anywhere-door really does exist. If so, we can reach our destination without having to travel miles in a long time. But, since Doraemon does not exist, fortunately there is something we can do to at least save the mileage and time we sacrificed to travel from one to another places. Especially in case of post men or delivery couriers who have to visit a lot of destinations in such limited amount of time and capability.

Recently, a research assistant from Systems Engineering, Modeling, and Simulation Laboratory from Industrial Engineering major, Universitas Indonesia is conducting a research about Vehicle Routing Problem with Time Windows to optimize distribution route and schedule. It was first inspired by Indonesia’s current logistic condition which is still not optimal. It is proven by the decreasing index of Indonesia’s logistic performance during the past five years. One of the reason is the high Indonesia’s logistic cost which can be considered as the highest logistic cost in the world. And the one that contributes almost half of the logistic cost is transportation cost.

On the other side, customer needs are rising annually. Moreover, the growing online shopping market create an increasing demand of same-day delivery service. Based on McKinsey survey, online retailers as the main originator of B2C shipments, have a large interest to reduce delivery time in order to foster the products sale. Therefore, we need a better planning of distribution route and schedule, especially for delivery service providers and courier companies.

The purpose of research conducted at SEMS Laboratory about Vehicle Routing Problem with Time Windows (VRPTW) is to find the most optimum distribution route with lowest total distance yet still manage to fulfill all demand and considering the constraints of vehicle capacity and customers’ time windows.

Since VRPTW belongs to NP-hard optimization problems, our researcher used heuristic method which is translated to Netbeans 8.1 software in C++ programming language. They also use local search to perform simple iterations to produce fairly accurate solutions. Local search methods which are used in this study are exchange, two-opt, and insert. They can be applied to customers in the same route (intra-route) and customers in different routes (inter-route). Basically, these methods perform some iterations of moves that determine the most optimum combination and sequence of customers to visit. This will be finalized by using Lin Kernighan Helsgaun algorithm. The iteration will stop once it can not generate a better solution.

Fig 1. Illustration of 2-opt intra-route move

The resulting improvements will ultimately result in reduced transportation costs. Thus, vehicle routing problem with time windows can be a solution for urban logistic problems. So, when you do not have any Doraemon’s magical door, make yourself sure that at least you have a well-planned distribution route and schedule!

This Research is Conducted by Vincencia Sydneyta and Dr. Komarudin