Experiments on the Node, Edge, and Arc Routing Problem

The Node, Edge, and Arc Routing Problem (NEARP) was defined by Prins and Bouchenoua in 2004 along with the first benchmark called CBMix. The NEARP generalizes the classical Capacitated Vehicle Routing Problem (CVRP), the Capacitated Arc Routing Problem (CARP), and the General Routing Problem. It is also denoted the Mixed Capacitated General Routing Problem (MCGRP). The NEARP removes the strict and unwarranted dichotomy that previously existed in the literature between arc routing and node routing. In real applications, there are many cases where the pure node or arc routing models are not adequate. In fundamentally node-based routing applications such as newspaper delivery and communal waste management that have typically been modeled as arc routing problems in the literature, the number of points is often so large that demand aggregation is necessary. Aggregation heuristics will normally give a NEARP instance, possibly with side constraints. Hence, the NEARP is a scientifically challenging problem with high industrial relevance. In this report we present experiments with Spider, SINTEF’s industrial VRP solver, on the three NEARP benchmarks that have been published so far: CBMix, BHW, and DI-NEARP. Bach, Hasle, and Wøhlk have developed a combinatorial lower bound for the NEARP and defined the two latter benchmarks. Here, we present an experimental study with Spider on the three existing NEARP benchmarks. Upper and lower bounds are given for all instances. Three of the BHW instances have been solved to optimality. SINTEF has developed a web page for NEARP results on http://www.sintef.no/NEARP .

Oppdragsgiver: SINTEF