Optimal routing with road network for scattered farm fields: Computational experiments with the branch-and-cut and 2-opt algorithms and case study on an agricultural corporation in Japan

Abstract

This study investigates optimal routing with a road network to minimize the total traveling distance among scattered farm fields for smart agriculture. Based on the case of an agricultural corporation in Japan, the shortest paths between all pairs of farm fields and their distances are obtained by utilizing road network data, and the optimal route is searched by addressing the traveling salesman problem (TSP) with an exact algorithm, which is implemented by the COIN-OR branch and cut (CBC) solver. The applicability of the TSP with the exact algorithm is verified by comparing its computational time and solution to those of the TSP with the 2-opt method, an approximation algorithm, through a computational experiment. Moreover, the effectiveness of the proposed approach is demonstrated through a case study on the agricultural corporation considered. The results of the computational experiment and case study show that the proposed approach can provide the optimal route for daily work within 7.5 seconds and can reduce 6.89% of the traveling distance from that of the route a worker creates empirically.

Keywords

• Smart agriculture
• Road network
• Traveling salesman problem (TSP)
• Exact algorithm
• Case study