SpOC 2022: Delivery Scheduling Space Coders Solutions Overview
The Space Coders team participated in the Delivery Scheduling challenge during the SpOC 2022 competition, aiming to balance the delivery of materials to 12 processing stations using various optimization techniques like simulated annealing, mixed-integer linear programming, and heuristic evaluation. Their solutions involved fine-tuning time windows, station sequences, and asteroid assignments to maximize material deliveries efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
SpOC 2022: Delivery Scheduling 4th place solution (score -9.446) Space Coders Space Coders S bastien Goulet & Vincent Debout - CS Group Space Optimisation Competition (SpOC) Workshop ESTEC September 16th2022
SpOC 2022: Delivery Scheduling Space Coders Problem: deliver asteroids to stations Mission Analysis Delivery Scheduling 12 processing stations 340 asteroids to assign 3 types of materials Transfers consume variable amount Stations are processed successively 2 4 12 1 Objective: Deliver as much material as possible in a balanced way score = min ????????min (m0, m1, m2) 2
SpOC 2022: Delivery Scheduling Space Coders Problem analysis 12 stations 479 M. possible sequences Opportunity density increases with time Material 2 seemed is more affected by the opportunity choice. 3
SpOC 2022: Delivery Scheduling Space Coders Early attempts: Initial score 9.126 First promising sequences & shape of the time windows Beam search / deliveries Tracking stations windows spans to ensure targeted score Heuristic evaluation: cumulative and pending loss w.r.t. best deliveries Beam search / station sequence Greedy deliveries affectation up to targeted mass per station Simulated annealing / deliveries (+ Tabu search variant) Allow slight variations of time windows bounds Occasional stations swap and greedy refill Simulated annealing / station sequence Approximated raw density (as if all deliveries were independent) 4
SpOC 2022: Delivery Scheduling Space Coders Mixed Integer Linear Programming Optimization problem Expression of constraints as linear dependencies Linear programming Advanced solver for the integer version Mixed Integer Linear Programming Open-source solver: CBC Commercial solver: Gurobi (free trial version) Limited 2000 variables, 2000 constraints Credit: wikipedia 5
SpOC 2022: Delivery Scheduling Space Coders Mixed Integer Linear Programming The full problem may linearized : Each station s is given a time window : [Ss, Es]. The 1-day delay on station change gives the following constrains : 1 ? 2 or ? s1, s2, Es1+1 Ss2or Es2+1 Ss1(extra variable for the or-statement) 2 1 Every asteroid a can provide one stations s on one opportunity p, Ka,s,p a, aKa,s,p 1 Check opportunity time t is in window if selected Ss t + (1 Ka,s,p) Tmax t Ka,s,p Es 6
SpOC 2022: Delivery Scheduling Space Coders Mixed Integer Linear Programming The full problem is too wide to be efficiently solved (14k variables, 28k constrains) Need to reduce the problem Fixed window Fixed sequence 1000 variables 400 constrains Fixed window Variable sequence 10k variables 10k constraints Fixed sequence Variable window 3000 variables 6500 constraints 1 2 3 1 2 3 1 2 3 Converges very fast Very limited exploration Identify promising sequences More efficient Need to provide the sequence 7
SpOC 2022: Delivery Scheduling Space Coders Mixed Integer Linear Programming The small change window (2k variables, 2k constrains) Sequence is fixed. Stations windows may only move on a limited range. 1 2 3 Interesting trade-off very efficient may be run in several iterations Final score 9.446 8
