Predictive Vehicle Routing Problem

Play with an interactive demo

For my final year Computer Science project with EPI-USE, I worked with my team on creating a system that can generate semi-optimal randomised flight plans in an anti-poaching effort. These flight plans would be used to plan drone flights to survey wildlife.

I applied the vehicle routing problem to the system – treating the drone as the vehicle and all points to visit as customers. To create a more advanced system that can attempt to intercept animals along a calculated path, I devised an algorithm to accomplish this.

This algorithm uses an exhaustive search to find an optimal path for a vehicle moving at constant velocity to intercept targets moving along paths at a constant velocity.

Only feasible routes are found – all routes conform to the maximum route distance the vehicle can travel.

Due to the search being exhaustive, the algorithm produces guaranteed optimal results. The trade-off is that the it becomes very slow once more than only a few points are added.

Demonstration of the algorithm working with simple straight lines.
Also demonstrates how the flight distance affects the generated routes.

This algorithm works by trying every combination of interceptions and keeping track of the route that covers the most points while taking the least distance. As the vehicle moves from point to point, time elapses and new interception points for other points are calculated vs if the vehicle were to go straight to that interception point.

Intercepting a straight line is relatively simple using some vectors. However, animals do not move in a straight line so it was necessary to intercept a point along a multi-ling path. This is accomplished by attempting to intercept each straight line; if the interception point is not on the line, then the next line segment is tested until a valid interception point is found.

If the end of the line is reached without finding a valid interception, the point is unreachable.

Demonstration of multiple points following multi-line paths
Demonstration of multiple routes generated from multi-line paths (in this case the total route was too long – creating two separate routes)

As a proposed heuristic for a polynomial-time algorithm that could work on significantly more points, it makes sense that points moving towards the depot should be intercepted last. This is because as time elapses, the points moving away from the depot create a larger surface area to cover. Reaching those points first reduces the effect of the points moving away.

I hope to work on a heuristic-based version of this algorithm in future.