SpOC 2022: Delivery Scheduling Space Coders Solutions Overview
S
p
O
C
2
0
2
2
:
D
e
l
i
v
e
r
y
S
c
h
e
d
u
l
i
n
g
4
t
h
p
l
a
c
e
s
o
l
u
t
i
o
n
(
s
c
o
r
e
-
9
.
4
4
6
)
S
p
a
c
e
C
o
d
e
r
s
S
é
b
a
s
t
i
e
n
G
o
u
l
e
t
&
V
i
n
c
e
n
t
D
e
b
o
u
t
-
C
S
G
r
o
u
p
Space Optimisation Competition (SpOC) Workshop
ESTEC – September 16
th
2022
S
p
O
C
2
0
2
2
:
D
e
l
i
v
e
r
y
S
c
h
e
d
u
l
i
n
g
S
p
a
c
e
C
o
d
e
r
s
Problem:
deliver asteroids to stations
12 processing stations
340 asteroids to assign
3 types of materials
Transfers consume variable amount
Stations are processed successively
2
S
p
O
C
2
0
2
2
:
D
e
l
i
v
e
r
y
S
c
h
e
d
u
l
i
n
g
S
p
a
c
e
C
o
d
e
r
s
Problem analysis
12 stations
479 M. possible sequences
Opportunity density increases with time
Material 2 seemed is more affected
by the opportunity choice.
3
S
p
O
C
2
0
2
2
:
D
e
l
i
v
e
r
y
S
c
h
e
d
u
l
i
n
g
S
p
a
c
e
C
o
d
e
r
s
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
S
p
O
C
2
0
2
2
:
D
e
l
i
v
e
r
y
S
c
h
e
d
u
l
i
n
g
S
p
a
c
e
C
o
d
e
r
s
Mixed Integer Linear Programming
Credit: wikipedia
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
5
S
p
O
C
2
0
2
2
:
D
e
l
i
v
e
r
y
S
c
h
e
d
u
l
i
n
g
S
p
a
c
e
C
o
d
e
r
s
Mixed Integer Linear Programming
1
2
2
1
or
?
?
6
S
p
O
C
2
0
2
2
:
D
e
l
i
v
e
r
y
S
c
h
e
d
u
l
i
n
g
S
p
a
c
e
C
o
d
e
r
s
Mixed Integer Linear Programming
The full problem is too wide to be efficiently solved (14k variables, 28k constrains)
Need to reduce the problem
Fixed sequence
Variable window
3000 variables
6500 constraints
Fixed window
Variable sequence
10k variables
10k constraints
Fixed window
Fixed sequence
1000 variables
400 constrains
1
2
3
1
2
3
1
2
3
More efficient
Need to provide the sequence
Identify promising sequences
Converges very fast
Very limited exploration
7
S
p
O
C
2
0
2
2
:
D
e
l
i
v
e
r
y
S
c
h
e
d
u
l
i
n
g
S
p
a
c
e
C
o
d
e
r
s
Mixed Integer Linear Programming
The small change window (2k variables, 2k constrains)
Sequence is fixed. Stations windows may only move on a limited range.
Interesting trade-off
very efficient
may be run in several iterations
Final score 9.446
8
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
