The Node Edge Arc Routing Problem - applications and heuristics

In the VRP literature, the Arc Routing Problem is often advocated as an adequate model for routing applications such as newspaper delivery and garbage collection. We argue that a better model is the Node Edge Arc Routing Problem (NEARP), combining demand on nodes, edges, and arcs in a transportation network. We describe how we have extended a node based VRP solver to enable modeling and resolution of the NEARP, and network based heuristics for aggregating node-based demand into demands on arcs and edges. Experimental results on standard benchmarks and industrial cases are presented.