NEARP / MCGRP
The Node, Edge, and Arc Routing Problem (NEARP) was defined by Prins and Bouchenoua in 2004 [1]. This problem generalizes the classical Capacitated Vehicle Routing Problem (VRP), the Capacitated Arc Routing Problem (CARP), and the General Routing Problem. The NEARP is also denoted the Mixed Capacitated General Routing Problem (MCGRP), and the Capacitated General Routing Problem on Mixed Graphs (CGRP(-m)). Two early papers discuss the CGRP [4,5]. The first mathematical formulation and exact method is proposed in [6]. An informal description of the problem is as follows: Given a mixed weighted (multi)graph, and a (possibly unconstrained) homogeneous fleet of vehicles, the goal is to find a minimum cost routing plan that services a given subset of required nodes, arcs, and edges under capacity constraints. The required items have given demand, and the vehicles have a given capacity. The traversal cost is given for edges and arcs and nodes have no traversal cost. The cost to be optimized is the total traversal cost, as the total service cost (the sum of the demands for the required items) is constant. Please note that the graph may not obey the triangle inequality, and there may be several nodes/edges between two given nodes. To determine the deadheading (traversal without service) costs between nodes for movement between required items, a NEARP solver must find the shortest path between all nodes. We refer to [1,2,4,5,6], and Documentation for details. Here you find information on four benchmarks for the NEARP, including instance definitions as well as best known (to our knowledge) upper and lower bounds for all instances. The four benchmarks are CBMix [1];  BHW and DI-NEARP [2]; and MGGDB/MGVAL [6]. In [2], the authors develop the first combinatorial lower bound procedure for the NEARP, and also define the BHW and DI-NEARP benchmarks. The first upper bounds for these two benchmarks are reported in [3]. The MGGDB/MGVAL benchmarks and an algorithm for solving these are defined in [6]. We encourage you to send information on new best known upper and lower bounds to us so the results we present here are as up to date as possible. See below for instructions. Also, if you have defined new NEARP / MCGRP benchmarks, please let us know. In case, we would appreciate of you could give us permission to publish definitions and best known bounds on these pages, or at least a pointer to this information.

The short URL to these pages that could also be used for citation is http://www.sintef.no/nearp .

Your detailed solutions will be checked by our solution checker. The format for solutions is documented  here. Please send your detailed solutions, new lower bounds, or other relevant information by email to top-request@sintef.no

 

References

[1]  Christian Prins and Samir Bouchenoua. A memetic algorithm solving the VRP, the CARP and general routing problems with nodes, edges and arcs. In W Hart, N Krasnogor, and J Smith, editors, Recent Advances in Memetic Algorithms, Studies in Fuzziness and Soft Computing, pages 65–85. Springer, 2004.

[2] Lukas Bach, Geir Hasle, Sanne Wøhlk: A Lower Bound for the Node, Edge, and Arc Routing Problem. Computers & Operations Research 40 (2013) 943–952.

[3] G. Hasle, O. Kloster, M. Smedsrud and K. Gaze, Experiments on the node, edge, and arc routing problem. Technical report A23265, SINTEF, May 2012. ISBN 978-82-14-05288-6 (444 KB).

[4] R. Pandi and B. Muralidharan (1995). A capacitated general routing problem on mixed networks. Computers & Operations Research, 22(5):465 – 478.

[5] J. C. A. Gutiérrez, D. Soler, and Antonio Hervás (2002). The capacitated general routing problem on mixed graphs. Revista Investigacion Operacional, 23(1):15 – 26, 2002.

[6] A. Bosco, D. Lagana, R. Musmanno, and F. Vocaturo. Modeling and solving the mixed capacitated general routing problem. Optimization Letters, October 2013, Volume 7, Issue 7, pp 1451-1469.

Published June 12, 2012