The Agricultural Spraying Vehicle Routing Problem with Splittable Edge Demands

Abstract: 
The capacitated arc routing problem (CARP) is to find a set of least-cost routes for a fleet of identical vehicles of limited capacity that must service the demand of a subset of edges in a network. Qian presented a splittable agricultural chemical sprayed vehicle routing problem and formulate it as a mixed integer linear program. The main difference is that her team's problem allows them to split the demand on a single demand edge amongst robotics sprayers. They use theoretical insights about the optimal solution structure to improve the formulation and provide two different formulations of the splittable capacitated arc routing problem (SCARP), a basic spray formulation and a high-edge demand formulation. The solution methods consist of lazy constraints, symmetry elimination constraints, and a heuristic repair method. Computational experiments on a set of valuable data based on the properties of real-world orchards reveal that the proposed methods can solve the SCARP with different properties. They also report computational results on classical benchmark sets from previous CARP literature. The tested results indicated that the SCARP model could provide cheaper solutions in some instances when compared with the CARP literature. Besides, the heuristic repair method significantly improves the quality of the solution by decreasing the upper bound when solving large-scale problems.

Bio: 
Ms Qian Wan is a second-year PhD student in the School of Mathematics at Monash University. She is supervised by Professor Andreas Ernst, Dr Rodolfo Garcıa-Flores, and Dr Simon Bowly. She has a great interest in operations research and discrete optimization. Her recent work is focused on developing effective techniques for solving agricultural arc routing problems.

Видео The Agricultural Spraying Vehicle Routing Problem with Splittable Edge Demands канала OPTIMA ARC