Turkish cashier problem with time windows and its solution by Migrating bird optimization algorithm

Abstract

A new application of the traveling salesman problem referred to as the Turkish cashier problem (TCP) was recently introduced in literature. The problem revolved around a cashier that must visit several locations and return to his office. To complete his visits, he can use taxis or public transportation and the objective is to minimize the total transportation cost. To make this problem more practical, we took time into consideration by adding a soft time interval for each location obligating the cashier to make his visit within. If he fails to visit within the adequate time, a penalty must be paid. We name this problem as the TCP with time windows (TCPwTW). A metaheuristic algorithm known as the Migrating Birds Optimization (MBO) algorithm coupled with mathematical programming was developed to solve TCPwTW. We attempted to find the exact optimum using an exact solver where for complex problems, optimal solutions cannot be found. The quantitative study reveals that for problems having a loose time interval, the Solver serves as the best approach. On the other hand, for problems having tight time intervals, the best solutions can be obtained by the matheuristic.