Open-Source Implementation of Slack Induction by String Removals for Routing and Orienteering Problems
摘要
Vehicle routing problems aim to efficiently serve customer requests while respecting constraints such as vehicle capacities and delivery time windows. When it is not possible to fulfill all requests, orienteering problems are considered, where only a subset of locations is visited to maximize the total collected scores. This paper presents an open-source implementation of the slack induction by string removals (SISRs) heuristic [9] for three representative variants of the vehicle routing problem. Our implementations match the solution quality of the original solver, and their runtimes scale better with increasing instance sizes. We propose an SISRs extension to solve three variants of the orienteering problem, with specific modifications to address their unique requirements. The developed solver achieves strong performance compared to the current state of the art, computing 49 new best-known solutions and delivering about 85 % of the best-known solutions [38] across all considered variants of the orienteering problem. Overall, we provide an efficient open-source solver for a variety of routing problems [39], as the availability of such implementations is very limited.