선물 배송 경로 최적화 경진대회: 산타와 루돌프의 워라벨 사수작전

[배경]

안녕하세요, 데이커 여러분 :)

월간데이콘 '선물 배송 경로 최적화 경진대회: 산타와 루돌프의 워라벨 사수작전'에 오신 것을 환영합니다!

크리스마스를 앞두고 산타와 루돌프는 엄청난 선물 물량에 골머리를 앓고 있습니다.

아이들에게 모든 선물을 정확히 전달하려면 엄청난 거리를 이동해야 하는데, 한 번에 운반할 수 있는 선물의 개수도 제한되어 있어 효율적인 경로를 찾는 것이 무엇보다 중요합니다.

산타와 루돌프는 이 문제를 해결하기 위해 데이콘에 의뢰했습니다. "어떻게 하면 우리의 업무량을 최소화하면서도 모든 아이들에게 선물을 나눠줄 수 있을까요?"

여러분의 기발한 아이디어와 최적화 알고리즘으로 산타의 크리스마스를 도와주세요!

[주제]

산타의 선물 배송을 위한 경로 최적화 알고리즘 개발

[설명]

산타는 크리스마스를 맞아 출발점(DEPOT)인 좌표 (0, 0)에서 출발하여, 모든 마을을 방문하며 어린이들에게 선물을 전달하고 다시 출발점(DEPOT)으로 돌아오려고 합니다.

배송 해야할 75개 마을의 위치는 0<X,Y≤100(km) 범위 내에 주어지며, 각 마을마다 어린이들에게 배송할 선물 개수가 정해져 있습니다.

하지만 루돌프가 이끄는 산타의 썰매는 한 번에 최대 25개의 선물만 운반할 수 있습니다. 선물이 부족할 경우, 다시 출발점으로 돌아가 선물을 채워야 합니다.

또한, 한 마을에는 어린이들에게 배송할 선물을 한 번에 모두 배송해야 합니다.

즉, 한 마을은 한 번씩만 방문할 수 있으며, 마을에 방문했을 때 모든 아이들에게 선물을 주지 못하면 선물을 받지 못해 우는 아이가 발생하므로 방문 시 일부에게만 나눠줄 수 없습니다.

마지막으로 산타와 루돌프는 지점과 지점 사이를 가장 짧은 직선 경로로 이동합니다.

여러분은 산타가 모든 마을을 방문하며 어린이들의 선물을 모두 배송하고 나눠줄 수 있도록 총 이동 거리를 최소화할 수 있는 최적 경로를 설계하는 알고리즘을 개발해야 합니다.

효율적인 경로 설계를 통해 산타와 루돌프가 크리스마스를 성공적으로 준비할 수 있도록 도와주세요! 

[주최 / 주관]

데이콘

[참가 대상]

데이커라면 누구나 참가 가능