Least Schedule Scheduling Scenario
I had a problem the other day which was interesting. This concerns the planning of a series of "tournaments". Below are the limitations:
- There are 7 teams named A, B, ..., G
- The tournament contains 3 teams, all teams in the tournament play 1 game against two other teams. That is, the tournament consists of 3 games.
- Each team has two tournaments
- Each team goes to four tournaments alongside the tournaments they host
- When the streak was over, all teams had to play all other teams twice.
Each movement is associated with a distance. The goal is to find a timetable so that the difference between the shortest and longest team is minimal.
Not exactly a traveling salesman problem, but an accompanying one. I'll be happy to remove this tag if it has any serious opinions.
Some examples of data:
create table d
( source varchar(20) not null
, destination varchar(20) not null
, distance int not null
, primary key (source, destination) );
insert into d (source, destination, distance)
select 'A', destination, distance
from (values ('B',204)
, ('C',31)
, ('D',185)
, ('E',213)
, ('F',142)
, ('G',165)
) T(destination, distance);
insert into d (source, destination, distance)
select 'B', destination, distance
from (values ('C',230)
, ('D',102)
, ('E',169)
, ('F',152)
, ('G',224)
) T(destination, distance);
insert into d (source, destination, distance)
select 'C', destination, distance
from (values ('D',200)
,('E',224)
,('F',157)
,('G',135)
) T(destination, distance);
insert into d (source, destination, distance)
select 'D', destination, distance
from (values ('E',68)
,('F',51)
,('G',123)
) T(destination, distance);
insert into d (source, destination, distance)
select 'E', destination, distance
from (values ('F',52)
, ('G',88)
) T(destination, distance);
insert into d (source, destination, distance)
select 'F', destination, distance
from (values ('G',80)
) T(destination, distance);
create view dv as
select source, destination, distance from d
union all
select destination, source, distance from d;
I started with the assumption that it would be easier to select 4 trips for each team and filter from there. Let's call this relationship team_travel. By cross-combining Team_travels with B team_travel etc. We get all possible combinations of team_travels. From there, we can exclude those that do not contain exactly 4 'A', 4 'B', etc. By ordering what is left with the difference between the largest and smallest travel distances, we can get the result.
This is inconvenient and can certainly be improved:
create or replace function cnt_occ(s varchar(28), c varchar(1))
returns int
return values length(s) - length(replace(s,c,null));
with t(s,d,n) as (
select source, destination, distance
from dv
), team_travel(s, d1,d2,d3,d4,n1,n2,n3,n4) as (
select t1.s, t1.d, t2.d, t3.d, t4.d, t1.n,t2.n,t3.n,t4.n
from t as t1
join t as t2
on t2.d > t1.d
and t1.s = t2.s
join t as t3
on t3.d > t2.d
and t1.s = t3.s
join t as t4
on t4.d > t3.d
and t1.s = t4.s
where t1.s not in (t1.d,t2.d,t3.d,t4.d)
)
select
a1.s||'->'||a1.d1||a1.d2||a1.d3||a1.d4,a1.n1+a1.n2+a1.n3+a1.n4
, a2.s||'->'||a2.d1||a2.d2||a2.d3||a2.d4,a2.n1+a2.n2+a2.n3+a2.n4
, a3.s||'->'||a3.d1||a3.d2||a3.d3||a3.d4,a3.n1+a3.n2+a3.n3+a3.n4
, a4.s||'->'||a4.d1||a4.d2||a4.d3||a4.d4,a4.n1+a4.n2+a4.n3+a4.n4
, a5.s||'->'||a5.d1||a5.d2||a5.d3||a5.d4,a5.n1+a5.n2+a5.n3+a5.n4
, a6.s||'->'||a6.d1||a6.d2||a6.d3||a6.d4,a6.n1+a6.n2+a6.n3+a6.n4
, a7.s||'->'||a7.d1||a7.d2||a7.d3||a7.d4,a7.n1+a7.n2+a7.n3+a7.n4
, greatest(a1.n1+a1.n2+a1.n3+a1.n4
, a2.n1+a2.n2+a2.n3+a2.n4
, a3.n1+a3.n2+a3.n3+a3.n4
, a4.n1+a4.n2+a4.n3+a4.n4
, a5.n1+a5.n2+a5.n3+a5.n4
, a6.n1+a6.n2+a6.n3+a6.n4
, a7.n1+a7.n2+a7.n3+a7.n4)
- least(a1.n1+a1.n2+a1.n3+a1.n4
, a2.n1+a2.n2+a2.n3+a2.n4
, a3.n1+a3.n2+a3.n3+a3.n4
, a4.n1+a4.n2+a4.n3+a4.n4
, a5.n1+a5.n2+a5.n3+a5.n4
, a6.n1+a6.n2+a6.n3+a6.n4
, a7.n1+a7.n2+a7.n3+a7.n4) as min_diff
from ( select * from team_travel where s = 'A' ) as a1
cross join ( select * from team_travel where s = 'B' ) as a2
cross join ( select * from team_travel where s = 'C' ) as a3
cross join ( select * from team_travel where s = 'D' ) as a4
cross join ( select * from team_travel where s = 'E' ) as a5
cross join ( select * from team_travel where s = 'F' ) as a6
cross join ( select * from team_travel where s = 'G' ) as a7
where cnt_occ(a1.d1||a1.d2||a1.d3||a1.d4
||a2.d1||a2.d2||a2.d3||a2.d4
||a3.d1||a3.d2||a3.d3||a3.d4
||a4.d1||a4.d2||a4.d3||a4.d4
||a5.d1||a5.d2||a5.d3||a5.d4
||a6.d1||a6.d2||a6.d3||a6.d4
||a7.d1||a7.d2||a7.d3||a7.d4, 'A') = 4
and cnt_occ(a1.d1||a1.d2||a1.d3||a1.d4
||a2.d1||a2.d2||a2.d3||a2.d4
||a3.d1||a3.d2||a3.d3||a3.d4
||a4.d1||a4.d2||a4.d3||a4.d4
||a5.d1||a5.d2||a5.d3||a5.d4
||a6.d1||a6.d2||a6.d3||a6.d4
||a7.d1||a7.d2||a7.d3||a7.d4, 'B') = 4
and cnt_occ(a1.d1||a1.d2||a1.d3||a1.d4
||a2.d1||a2.d2||a2.d3||a2.d4
||a3.d1||a3.d2||a3.d3||a3.d4
||a4.d1||a4.d2||a4.d3||a4.d4
||a5.d1||a5.d2||a5.d3||a5.d4
||a6.d1||a6.d2||a6.d3||a6.d4
||a7.d1||a7.d2||a7.d3||a7.d4, 'C') = 4
and cnt_occ(a1.d1||a1.d2||a1.d3||a1.d4
||a2.d1||a2.d2||a2.d3||a2.d4
||a3.d1||a3.d2||a3.d3||a3.d4
||a4.d1||a4.d2||a4.d3||a4.d4
||a5.d1||a5.d2||a5.d3||a5.d4
||a6.d1||a6.d2||a6.d3||a6.d4
||a7.d1||a7.d2||a7.d3||a7.d4, 'D') = 4
and cnt_occ(a1.d1||a1.d2||a1.d3||a1.d4
||a2.d1||a2.d2||a2.d3||a2.d4
||a3.d1||a3.d2||a3.d3||a3.d4
||a4.d1||a4.d2||a4.d3||a4.d4
||a5.d1||a5.d2||a5.d3||a5.d4
||a6.d1||a6.d2||a6.d3||a6.d4
||a7.d1||a7.d2||a7.d3||a7.d4, 'E') = 4
and cnt_occ(a1.d1||a1.d2||a1.d3||a1.d4
||a2.d1||a2.d2||a2.d3||a2.d4
||a3.d1||a3.d2||a3.d3||a3.d4
||a4.d1||a4.d2||a4.d3||a4.d4
||a5.d1||a5.d2||a5.d3||a5.d4
||a6.d1||a6.d2||a6.d3||a6.d4
||a7.d1||a7.d2||a7.d3||a7.d4, 'F') = 4
and cnt_occ(a1.d1||a1.d2||a1.d3||a1.d4
||a2.d1||a2.d2||a2.d3||a2.d4
||a3.d1||a3.d2||a3.d3||a3.d4
||a4.d1||a4.d2||a4.d3||a4.d4
||a5.d1||a5.d2||a5.d3||a5.d4
||a6.d1||a6.d2||a6.d3||a6.d4
||a7.d1||a7.d2||a7.d3||a7.d4, 'G') = 4
order by min_diff
fetch first 100 rows only
There must be something more elegant than this thought?
+3
source to share
No one has answered this question yet
Check out similar questions: