Node, Edge, Arc Routing and Turn Penalties: Multiple Problems–One Neighborhood Extension

Node, Edge, Arc Routing and Turn Penalties: Multiple Problems–One Neighborhood Extension

0.00 Avg rating0 Votes
Article ID: iaor20173085
Volume: 65
Issue: 4
Start Page Number: 992
End Page Number: 1010
Publication Date: Aug 2017
Journal: Operations Research
Authors:
Keywords: combinatorial optimization, decision, graphs, heuristics, programming: dynamic, vehicle routing & scheduling
Abstract:

This article explores a structural neighborhood decomposition for arc routing problems, in which the decisions about traversal orientations during services are made optimally as part of neighbor evaluation procedures. Using memory structures, bidirectional dynamic programming, and lower bounds, we show that a large neighborhood involving classical moves on the sequences of services along with optimal orientation decisions can be searched in amortized O(1) time per move evaluation instead of O(n) as in previous works. Because of its generality and now‐reduced complexity, this approach can be efficiently applied to several variants of arc routing problems, extended into large neighborhoods such as ejection chains, and integrated into two classical metaheuristics. Our computational experiments lead to solutions of high quality on the main benchmark sets for the capacitated arc routing problem (CARP), the mixed capacitated general routing problem (MCGRP), the periodic CARP, the multidepot CARP, and the min‐max k‐vehicles windy rural postman problem, with a total of 1,528 instances. We also report sensitivity analyses for new MCGRP instances with turn penalties, which are uncommonly challenging yet critical for many practical applications. The e‐companion is available at https://doi.org/10.1287/opre.2017.1595

Reviews

Required fields are marked *. Your email address will not be published.