Title: The agricultural spraying vehicle routing problem with splittable edge demands

Speaker: Qian Wan

Summary: 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. We present a splittable agricultural chemical sprayed vehicle routing problem and formulate it as a mixed integer linear program. The main difference is that our problem allows us to split the demand on a single demand edge amongst robotics sprayers. We 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. We 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.

Biography: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.

WED 15 MARCH 16:00-17:00 (AEDT, Melbourne Time)

ZOOM MEETING ID: 873 1557 5255; PASSWORD: 778635