Logotipo NIPE


Seminários Brown Bag

A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem

Orador convidado

José Carlos Brandão (NIPE)


Sala -1.26 EEG UMinho & Online


Início08.11.2023 13:15Fim08.11.2023 14:15

Resumo do evento


José Carlos Soares Brandão is Associate Professor with Habilitation in the department of Management. He has Habilitation in Management from the University of Minho (2006), a Ph.D. in Management Science – Operational Research from Lancaster University, England (1994), a M.Sc. in Mathematical Methods for Economics and Management from ISEG (University of Lisbon, 1991), and a B.Sc. (honours) in Production Engineering – branch of Polymers from the University of Minho (5 years degree, 1982). He has been involved in several research projects in the field of Logistics. He has published several articles in leading international scientific journals and has presented his work at international conferences. He has also worked as Production Manager during about four years.


In this talk we will present an iterated local search algorithm for solving the multi-depot open vehicle routing problem. First of all, it is explained why the approximate algorithms are required to solve this problem. Therefore, the quest is to create approximate algorithms that are the best possible.

This distribution problem is a variant of the classical vehicle routing problem, which has the following two differences: there are several depots; the vehicles do not return to the depot after delivering the goods to the customers, i.e., the end of the route is not the starting point. The open vehicle routing problem with a single depot started to attract attention only two decades ago, but in spite of this, since then, have been published many algorithms for solving it. On the contrary, the number of existing papers for the multi-depot variant is quite scarce. In this paper, we present an iterated local search algorithm, in which the moves performed during the local search are recalled and this historical search information is then used to define the moves executed inside the perturbation procedures. Therefore, it is recorded the number of times that each customer is moved during the local search. Since this information is continuously updated and changes in each iteration, the search is driven to potentially better regions of the solution space, and increases the chance of avoiding cycling, even when using deterministic perturbations. The performance of this algorithm was tested using a large set of benchmark problems and was compared with other algorithms, and the results show that it is very competitive.

Key words: iterated local search; logistics; memory; multi-depot; transportation; vehicle routing.

To join the webinar, click on the link: https://videoconf-colibri.zoom.us/j/96069475973

Join the NIPE seminars on Google calendar: https://bit.ly/2LKkPyV