Abstract
The Node, Edge, and Arc Routtng Problem (NEARP) was defined by Prins and Bouchenoua in
20011. This problem generalizes the classical Capacltated Vehicle Routing Problem (CVRP), the
Capacitated Arc Routing Problem (CARP), and the General Routing Problem. It captures
important aspects of real-life routing problems that were not adequately modeted in previous
Vehicle Routtng Problem (VRP) variants. The authors also proposed a memetic algorithm
procedure and defined a set of test instances called the CBMix benchmark. The NEARP
deflnition and investigation contribute to the development of rich VRPs. In this paper we present
the first lower bound procedure for the NEARP. It is a further development of tower bounds for
the CARP. We also define two novel sets of test instances to complement the CBMix benchmark.
The first ls 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 tower and best known
upper bounds for au instances or all three benchmarks. For three of the instances, the gap
between the upper and tower bound is closed. The average gap ls 25.1 %. As the tower bound
procedure ls based on a high quality tower bound procedure for the CARP, and there has been
limited work on approximate solution methods for the NEARP, we suspect that the main reason
for the rather large gaps is the quality of the upper bound. This fact, and the high Industrial
relevance of the NEARP, should motivate more research on approximate and exact methods for
this important problem.
Oppdragsgiver: The Research Council of Norway
20011. This problem generalizes the classical Capacltated Vehicle Routing Problem (CVRP), the
Capacitated Arc Routing Problem (CARP), and the General Routing Problem. It captures
important aspects of real-life routing problems that were not adequately modeted in previous
Vehicle Routtng Problem (VRP) variants. The authors also proposed a memetic algorithm
procedure and defined a set of test instances called the CBMix benchmark. The NEARP
deflnition and investigation contribute to the development of rich VRPs. In this paper we present
the first lower bound procedure for the NEARP. It is a further development of tower bounds for
the CARP. We also define two novel sets of test instances to complement the CBMix benchmark.
The first ls 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 tower and best known
upper bounds for au instances or all three benchmarks. For three of the instances, the gap
between the upper and tower bound is closed. The average gap ls 25.1 %. As the tower bound
procedure ls based on a high quality tower bound procedure for the CARP, and there has been
limited work on approximate solution methods for the NEARP, we suspect that the main reason
for the rather large gaps is the quality of the upper bound. This fact, and the high Industrial
relevance of the NEARP, should motivate more research on approximate and exact methods for
this important problem.
Oppdragsgiver: The Research Council of Norway