A Lower Bound for the Node, Edge, and ArcRouting Problem

Abstract

The Node, Edge, and Arc Routing Problem (NEARP) was defined by Prins and Bouchenoua in 2004. They also proposed a memetic algorithm procedure and defined a set of test instances: the so-called CBMix benchmark. The NEARP generalizes the classical CVRP, the CARP, and the General Routing Problem. It captures important aspects of real-life routing problems that were not adequately modelled in previous VRP variants. Hence, its definition and investigation contribute to the development of rich VRPs. In this paper we present the first lower bound for the NEARP. It is a further development of lower bounds for the CARP. We also define two novel sets of test instances to complement the CBMix benchmark. The first is based on well-known CARP instances; the second consists of real life cases of newspaper delivery routing. We provide numerical results in the form of lower and best known upper bounds for all instances of all three benchmarks. For two of the instances, the gap is closed