This seminar will take place on October 22 at 15h30, online via Zoom (link below)
https://videoconf-colibri.zoom.us/j/81758278875?pwd=aHk0VTRvaUtncjFDVnpGVk50VG1IZz09
Our seminars are free to attend and open to everyone. Please share with whomever may be interested.
Summary
Consider a depot and a partition of the set of nodes into subsets, called families. The objective of the family traveling salesman problem (FTSP) is to find the minimum cost route that starts and ends at the depot and visits a given number of nodes per family. The FTSP finds its practical application in the order picking problem in warehouses with chaotic storage, such as those of Amazon. We propose a new variant of the FTSP by introducing incompatibilities between the families, that is, incompatible families cannot be visited in the same route. Thus, the FTSP with incompatibility constraints (FTSP-IC) consists of determining the minimum cost set of routes that begins and ends at the depot; visits a given number of cities in each family; and does not visit incompatible nodes in the same route. We propose compact and non-compact formulations for the FTSP-IC, which model the incompatibility constraints for each family implicitly in the compatibility graph. We also present a new set of valid inequalities. To evaluate the different models, we used the benchmark instances for the FTSP and generated incompatibility matrices. The computational experiment shows that the non-compact models outperform the compact ones. As the exact methods are unable to address the largest sized instances, we developed two heuristic methods, namely an ant colony optimization algorithm and an iterated local search. Both heuristic algorithms are able to efficiently obtains solutions with a lower value than the branch-and-cut algorithm for most of the instances with an unknown optimal value.
Speaker's bio
Raquel Bernardino completed her PhD in 2019 in Statistics and Operations Research, specializing in Optimization, at the Faculdade de Ciências da Universidade de Lisboa. She has co-authored four papers in top journals of the Operations Research and Management Science field. Since then, she has been a Visiting Assistant Professor at the Faculdade de Ciências da Universidade de Lisboa, where she taught unit courses in the area of Statistics and, currently, she is a Visiting Assistant Professor at the Mathematics Department of Instituto Superior de Economia e Gestão, where she teaches Operations Research. Her research interests are the development of branch-and-cut algorithms and heuristic algorithms for routing problems.