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

José Brandão

European Journal of Operational Research, 2020, vol. 284, issue 2, 559-571

Abstract: The problem studied in this paper is the multi-depot open vehicle routing problem, which has the following two differences in relation to the classical vehicle routing problem: 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. There are many practical applications for this problem, however the great majority of the studies have only addressed the open vehicle routing problem with a single depot. 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.

Keywords: Transportation; Iterated local search; Memory; Multi-depot; Vehicle routing (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720300278
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:284:y:2020:i:2:p:559-571

DOI: 10.1016/j.ejor.2020.01.008

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().