An open vehicle routing problem metaheuristic for examining wide solution neighborhoods

This paper examines a practical transportation model known as the open vehicle routing problem (OVRP). OVRP aims at designing the minimum cost set of routes originating from a central depot for satisfying customer demand. Vehicles do not need to return to the depot after completing their delivery services. In methodological terms, we propose an innovative local search metaheuristic which examines wide solution neighborhoods. To explore these wide neighborhoods within reasonable computational effort, local search moves are statically encoded into static move descriptor (SMD) entities. When a local search operator is applied to the candidate solution, only a limited solution part is modified. Therefore, to explore the next neighborhood only the tentative moves that refer to this affected solution part have to be re-evaluated, or in other words, only a subset of the SMD instances has to be updated, according to the modified solution state. The conducted search is efficiently performed by storing the SMD entities in Fibonacci heaps, which are special priority queue structures offering fast minimum retrievals, insertions and deletions. To diversify the search, we employ a tabu scheme and a penalization strategy, both compatible with the SMD design. The proposed metaheuristic was tested on well-known OVRP instances, for two objective configurations. The first one primarily aims at minimizing the number of routes and secondarily minimizing the routing cost, whereas the second one only aims at minimizing the cost of the generated route set. For both configurations, it managed to produce fine results improving several previously best-known solutions.