Issue |
RAIRO-Oper. Res.
Volume 58, Number 3, May-June 2024
|
|
---|---|---|
Page(s) | 2239 - 2259 | |
DOI | https://doi.org/10.1051/ro/2024084 | |
Published online | 10 June 2024 |
Turkish Cashier Problem with time windows and its solution by matheuristic algorithms
Industrial Engineering Department, Ozyegin University, Istanbul, Turkey
* Corresponding author: ahmad.bassaleh@ozu.edu.tr
Received:
7
October
2023
Accepted:
4
April
2024
Turkish Cashier Problem (TCP) is a new application area of the traveling salesman problem that was introduced to the literature recently. In this problem, the cashier can use public transportation or take a taxi where the cashier must visit multiple customer locations while minimizing the total transportation cost. In this study, we introduce a more realistic version of this problem where time has been integrated. This aspect is achieved by imposing time intervals within which the cashier must visit the customers. We name this problem as the TCP with time windows (TCPwTW). We develop several matheuristic algorithms to solve the TCPwTW: a modified version of the Simplify and Conquer (SAC) algorithm that was suggested for the TCP, simulated annealing (SA), original and modified versions of the migrating birds optimization (MBO) algorithm coupled with mathematical programming. We also tried to find the exact optimum using a Solver where for complex problems, only lower bounds were found. Numerical experimentation reveals that while for problems with loose time intervals, an exact solver can be considered. Once the time intervals tighten up, the best solutions can be obtained using matheuristics involving SA and MBO.
Mathematics Subject Classification: 90-05 / 90B06
Key words: TSP applications / matheuristics / metaheuristics / migrating birds optimization / simulated annealing
© The authors. Published by EDP Sciences, ROADEF, SMAI 2024
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.