Route optimization of ATM delivery vehicles

Abstract

The main objective of this study is optimizing routes of ATM delivery vehicles under some constraints. Since the problem is NP-hard, it is not possible to solve it in polynomial time and near optimum solutions through heuristic algorithms are found. The methodology developed involves construction of new heuristics based on the Savings and the Sweep Algorithms. Two new heuristics both manipulating and combining some general properties of these two algorithms and adding some new factors to the classical Savings algorithm are suggested. Then, initial tours such obtained are improved using 2-opt based algorithms. Two different versions of 2-opt algorithm are used and compared to each other. Then, a Switch based heuristic is developed and total cost of visiting an ATM one day before the suggested schedule is studied. In case it decreases total cost some ATMs are considered to be visited one day earlier. Instances are tested and results are reported for both the sample data retrieved from “www.branchandcut.org” and provided by a commercial bank (data provided by the bank is manipulated due to confidentiality issues). Trend analysis is tried to find the most suitable resulting algorithm for a spesific problem set. Algorithms are coded in SQL and executed on Intel(R) Core(TM)2 Duo CPU 2.40GHz computer.