A Google Maps based novel approach to the optimization of multiple Traveling Salesman problem for limited distribution systems

Abstract

The Vehicle Routing Problem (VRP) is a complex combinatorial optimization problem that can be described as follows: given a fleet of vehicles with uniform capacity, a common depot, and several costumer demands; find the set of routes with overall minimum route cost which service all the demands. The multiple traveling salesman problem (mTSP) is a generalization of the well-known traveling salesman problem (TSP), where more than one salesman is allowed to be used in the solution. It is well-known that mTSP based algorithms can also be utilized in several VRPs by incorporating some additional constraints. There are several exact algorithms of the mTSP with relaxation of some constraints of the problem. These approaches have serious importance because the solution what is supplied is optimal. Furthermore, due to the combinatorial complexity of mTSP, it is necessary to apply some heuristic in the solution, especially in real-sized applications. The aim of this paper is to discuss how genetic algorithms can be applied to solve these problems. It reviews the previous approaches with their disadvantages and proposes a novel, interpretable representation based algorithm. In this work, the effectiveness of the developed novel algorithm which based on the proposed representation will be demonstrated by several examples. The paper pans out about the implemented software solutions, like a new tool for calculation of distance table (on real routes) based on Google Maps API and a user-friendly tool for the drawing of the vehicle round trips. Furthermore, it proposes a complete framework and methodology to solve real problems. The new algorithm, a novel tool, and the resulted routes provide economically effective solutions for logistics which is proved by a real application.