Planet: A Brief Overview
For a more detailed report on our project, please see our paper here.The Problem:
Given a bunch of tasks, each with some scheduling criteria, what's the best order in which to complete them, with respect to both time and space?
Tasks come with a duration and a deadline. Additionally, there are time windows that limit the time during which a task can be scheduled. Tasks also have a priority value, can be optional or mandatory, and have a location with associated travel times to and from other tasks.
The Solution:
We ultimately implemented five different categories of algorithms: Brute Force, Pulse, an Integer Program, a number of Greedy Algorithms, and Variable Neighborhood Search (VNS). Of those, Brute Force, Pulse, and the Integer Program produce optimal solutions given sufficient time.
The Algorithms:
Brute force tries and compares every possible solution, and it chooses the best one.
Pulse recursively tries every possible solution. However, given partial solutions, it checks to see whether or not a solution based off this one is worth further consideration. If it isn't, Pulse saves itself some time by not checking solutions based off that one.
The Integer Program uses an integer program solver called the Gurobi Optimizer to solve the problem. We describe the schedule using constraint functions, and the Gurobi Optimizer outputs the best possible solution.
Greedy algorithms organize the tasks by some order: deadline, value, or some combination of value and availability. Then, they add tasks to the schedule in that order (if possible). This quickly gives us a solution, and in our experience it performed extremely well given its speed.
Variable Neighborhood Search is a non-optimal algorithm. It uses a Greedy Algorithm's solution to begin, and it explores neighborhoods of this solution - similar schedules - until it improves the schedule. It uses a number of iterative improvement methods to continue exploring the solution set until it reaches a given time limit.
The Results:
The Integer Program got the most average optional value of all the algorithms. This measures how many optional tasks it was able to schedule.
The GUI:
We created a graphical user interface (GUI) to debug our code and also to help visualize our schedules. Each task is represented as a block on a given day. When you mouseover a task, it highlights on its day and on the map, and the route for that day appears on the map.
The Conclusion:
We spent a lot of time on this project and are proud of it! The previous description hardly does the project justice, so if you're interested we would encourage you to check out our paper and code.