Track: Logistics Management

Abstract

Routing of vehicles is a common application in logistics. Given rising complexity when the number of nodes is increasing, exact solutions are hard to find and researchers turn their attention more to heuristics or metaheuristics for large-scale problems. These approaches are usually based on certain assumptions and satisfying the assumptions is often the key to effective and efficient implementation of the approach. One typical assumption in routing problems is called triangular inequality which states that the sum of distances between two connecting arcs should be larger or at least the same with the distance between the outer nodes of those arcs. In Euclidean setting, this assumption will not be violated. However, in real-life applications, we depend on external tool such as Google Maps to obtain distances between locations. In so doing, it is possible to violate the inequality assumption. This paper aims to rectify that problem by proposing a simple algorithm that can adjust and validate the triangular inequality assumption on a given dataset of distances. The algorithm will be tested on a case study in a distributor company and sensitivity analysis will be outlined to find the relationship between the number of nodes and algorithm complexity.