From Arc routing to Node routing problems

This work explains how to transform an Arc routing problem to an Node routing problem

1. From Arc routing to Node routing problems Aitor López Sánchez AGROBOTS*: Scalable, efficient and decentralized coordination of automated agricultural vehicle fleets

2. Agriculture Fleet Vehicle Routing Problem The Agricultural Fleet Vehicle Routing consists of determining the most efficient routes for agricultural robots to perform multiple tasks in the farming field.

3. Assad, A. A., & Golden, B. L. (1995). Arc routing methods and applications . Handboos in operations research and management science , 8, 375-483. Capacitated arc routing problem (CARP) S

4. Capacitated Vehicle Routing Problem (CVRP )

5. Transformation to a Node routing Problem Transformation into a CVRP with 3|R| +1 [ Pearn , Assad and Golden, 1987] Transformation into a CVRP with 2|R| +1 [Baldacci and Maniezzo , 2006] Transformation into a CVRP with 2|R| +1 [Baldacci and Maniezzo , 2006 // Longo, Poggi de Aragão and Uchoa , 2006 ] Belenguer , J. M., Benavent , E., & Irnich , S. (2015). Chapter 9: The capacitated arc routing problem: Exact algorithms. In Arc routing: Problems, methods, and applications (pp. 183-221). Society for Industrial and Applied Mathematics.

6. Pearn , Assad and Golden, 1987 Pearn , W. L., Assad, A., & Golden, B. L. (1987). Transforming arc routing into node routing problems. Computers & operations research , 14 (4), 285-288. Idea:     New set of nodes : New demand : New cost :      

7. Baldacci and Maniezzo , 2006 Baldacci, R., & Maniezzo , V. (2006). Exact methods based on node‐routing formulations for undirected arc‐routing problems. Networks , 47 (1), 52-60. Idea:     New set of nodes : New demand : New cost :      

8. Longo, Poggi de Aragão and Uchoa , 2006 Longo, H., De Aragao , M. P., & Uchoa , E. (2006). Solving capacitated arc routing problems using a transformation to the CVRP. Computers & Operations Research , 33 (6), 1823-1837. Idea:     New set of nodes : New demand : New cost :     New constraint :      

9. Example Longo et al. 2006 Baldacci and Maniezzo , 2006

10. Conclusions CARP is equivalent to CVRP CARP is more complex to solve than CVRP P earn et al. First approach Intuitive Baldacci et al. Less nodes Computational problems with the M. Longo et al. Less nodes It is not is a strict VRP.

11. From Arc routing into Node routing problems Aitor López Sánchez AGROBOTS*: Scalable, efficient and decentralized coordination of automated agricultural vehicle fleets