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
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 u...
| Main Authors: | , , |
|---|---|
| 格式: | Article |
| 語言: | English |
| 出版: |
Elsevier
2024-08-01
|
| 叢編: | Smart Agricultural Technology |
| 主題: | |
| 在線閱讀: | http://www.sciencedirect.com/science/article/pii/S2772375524000558 |
| _version_ | 1827149162885414912 |
|---|---|
| author | Takuma Nemoto Naoki Niitsuma Norihiro Kamamichi |
| author_facet | Takuma Nemoto Naoki Niitsuma Norihiro Kamamichi |
| author_sort | Takuma Nemoto |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-24T11:37:41Z |
| format | Article |
| id | doaj.art-cafc703acdc84c51b8c39320ca453958 |
| institution | Directory Open Access Journal |
| issn | 2772-3755 |
| language | English |
| last_indexed | 2025-03-20T21:13:48Z |
| publishDate | 2024-08-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Smart Agricultural Technology |
| spelling | doaj.art-cafc703acdc84c51b8c39320ca4539582024-08-13T06:26:39ZengElsevierSmart Agricultural Technology2772-37552024-08-018100450Optimal 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 JapanTakuma Nemoto0Naoki Niitsuma1Norihiro Kamamichi2Corresponding author.; Department of Robotics and Mechatronics, School of Science and Technology for Future Life, Tokyo Denki University, 5 Senju Asahi-cho, Adachi-ku, Tokyo 120-8551, JapanDepartment of Robotics and Mechatronics, School of Science and Technology for Future Life, Tokyo Denki University, 5 Senju Asahi-cho, Adachi-ku, Tokyo 120-8551, JapanDepartment of Robotics and Mechatronics, School of Science and Technology for Future Life, Tokyo Denki University, 5 Senju Asahi-cho, Adachi-ku, Tokyo 120-8551, JapanThis 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.http://www.sciencedirect.com/science/article/pii/S2772375524000558Smart agricultureRoad networkTraveling salesman problem (TSP)Exact algorithmCase study |
| spellingShingle | Takuma Nemoto Naoki Niitsuma Norihiro Kamamichi 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 Smart Agricultural Technology Smart agriculture Road network Traveling salesman problem (TSP) Exact algorithm Case study |
| title | 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 |
| title_full | 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 |
| title_fullStr | 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 |
| title_full_unstemmed | 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 |
| title_short | 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 |
| title_sort | 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 |
| topic | Smart agriculture Road network Traveling salesman problem (TSP) Exact algorithm Case study |
| url | http://www.sciencedirect.com/science/article/pii/S2772375524000558 |
| work_keys_str_mv | AT takumanemoto optimalroutingwithroadnetworkforscatteredfarmfieldscomputationalexperimentswiththebranchandcutand2optalgorithmsandcasestudyonanagriculturalcorporationinjapan AT naokiniitsuma optimalroutingwithroadnetworkforscatteredfarmfieldscomputationalexperimentswiththebranchandcutand2optalgorithmsandcasestudyonanagriculturalcorporationinjapan AT norihirokamamichi optimalroutingwithroadnetworkforscatteredfarmfieldscomputationalexperimentswiththebranchandcutand2optalgorithmsandcasestudyonanagriculturalcorporationinjapan |