Scientific Program > Talks by Speaker > Poikonen Stefan

The mothership and drone routing problem is a collaborative transportation model between a mothership (e.g., a ship, plane, or other large vehicle that can move by Euclidean distances) and a drone. We show that by combining second order cone programming with the branch-and-bound algorithm, we can find optimal solutions. Additionally, we show fast heuristics that use second order cone programming. We show that the second order cone program can be modified for other constraints. We then consider the case where there exist several polygonal obstacles (e.g., dry land, shallow waters, political boundaries) that restrict the motion of the mothership. These obstacles inject non-convexity into the feasible domain, which complicates the problem significantly. Our proposed solution method first finds a feasible solution. Afterwards, a sequential second order cone program is applied. This second order cone program contains a new set of constraints. Critically, we circumscribe the launch and landing locations of the drone from the previous iteration's solution with a circle of maximal radius, such that the circle does not intersect with any obstacle. The launch and landing locations of the current iteration are constrained within these circles. Thus, we are able to ensure that the chosen launch and landing locations do not intersect with land, but we are able to preserve the form of a second order cone program. We show that the sequential second order cone program tends to drift towards some local optimum.