[Project] 기숙사 택배실 문제 해결📦/정수계획법/선형계획법/최적화

안녕하세요, yejining입니다👩‍💻🍓

이번 포스팅은 제가 대학교 재학 시절 진행했던 프로젝트에 대해 적어볼 것입니다.

이름하여... 기숙사 택배실 문제 해결 프 로 젝 트📦🎉 (빠밤)

저에게 있어 이 프로젝트는 처음으로 실제 데이터를 활용해 문제를 해결한 정말 의미있는 프로젝트랍니다.

왜 이 문제를 해결했어야 했는지, 그리고 어떻게 문제 정의를 했었는지 정말 해결되었는지 하나씩 차근차근 적어가보도록 하겠습니다 :)

그럼 go go '∇' !!

---

1. Background

프로젝트 제목

우선 프로젝트 주제인 "기숙사 택배실 문제"에 대해 설명해볼 것입니다.

 

저희 대학교에서는 몇 년동안 기숙사 택배실 문제가 심각하게 발생되어 왔습니다.

이는 저희 대학교만의 특별한...(?) 기숙사와 택배 수령 방식에서 비롯됩니다.

 

여러분들은 보통 택배를 어떻게 수령하시나요?

아마 택배를 시킬 때 집주소를 적으면, 택배기사분께서 문 앞까지 가져다 주시는 person to person방식을 많이 이용하실텐데요.

저희 기숙사는 택배 수령 방식으로 이 방식을 사용할 수 없습니다...!

 

왜..?

 

왜냐하면 저희 대학교의 기숙사는 이렇게 생겼거든요...

기숙사 들어가려면 학생카드가 필요해서 택배기사분들이 들어갈 수가 없그등요...

 

높고 높은 우리 기숙사

 

여기다가 기숙사 특성상 남, 여가 구분되어있고 다른 성별은 그 기숙사 동에 들어갈 수 없습니다.

이거 말고도 행정적인 문제들이 여럿 겹쳐져 흔히 쓰는 person to person 방식은 사용할 수 없었습니다 ✂️

 

택배실 방식

 

그래서 저희 학교는 택배실 방법을 사용했습니다.

각각의 택배사들이 지정된 택배실에 택배를 놓아두면, 학생들이 그 택배실에 가서 택배를 찾아오는 방식으로요!

그런데 이 택배실에서 여러가지 문제점이 발생했습니다 🚨

 

2. Problem

택배실 문제들

 

우선 첫번째로 택배실이 작아 택배를 넣어둘 공간이 부족했다는 것 입니다.

특히 학기가 끝나고 시작되는 이사철에는 택배실 밖에까지 택배가 이리저리 놓여져 있었죠.

한번은 그 시기때 비가 왔었는데... 그 결과는 매우 처참했답니다...🥲

 

두번째는 택배사마다 택배를 높아둘 수 있는 공간이 지정되어 있는데, 이 공간이 적절히 배분되지 않았다는 것이죠.

이 문제 때문에 첫번째 문제도 발생했구요.

 

그래서 저희는 이렇게 문제정의를 했습니다.

각 택배사마다 배분되어야 하는 최적의 보관함 개수는 무엇일까?

 

3. Data collection

택배박스 & 보관함 크기

우선 택배사들이 사용하는 택배박스 사이즈와 보관함 크기를 측정했습니다.

택배박스의 가로*세로*높이와 보관함의 크기를 안다면 그 보관함에 얼마만큼의 택배가 놓여질 수 있는지 알 수 있으닌까요❗

 

두번째로 각 회사별로 보관함이 몇개씩 배분되어 있는지 확인해보았습니다.

자세한 데이터를 공개할 순 없지만, cj랑 우체국이 제일 많이 배분되어 있었던 것을 알 수 있었습니다.

 

세번째로 각 날짜별로 택배사에서 몇개의 택배가 배송되는지 확인해보았습니다.

이 데이터는 다행히도 택배실 안에 있던 택배 운송 정보에 기록되어 있었습니다.

(안그랬으면 다 세어야 했...)

개인정보보호를 위해 이름, 전화번호, 물품종류와 같은 개인정보 말고 오로지 개수만 기록했습니다.

 

 

4. Model definition

 

정수계획법

보관함 개수 배분 최적화를 위해서 저희는 정수계획법이라는 방식을 사용했습니다.

정수계획법 예시

선형계획법이란 최적화 문제의 일종으로 주어진 정수 조건을 만족시키면서 목적 함수를 최적화하는 문제입니다.

저희가 해결해야하는 문제와 제약조건들을 수식으로 나타낸 후 해결하는 것이죠.

그리고 보관함 개수는 정수로밖에 나눌 수 없기 때문에 선형계획법에서 정수해만 가지는 정수계획법 방법을 채택하였습니다.

 

변수 정의

저희가 구해야하는 각 택배사별 보관함 개수는 x로 두었습니다.

 

그래고 택배사마다 사용되지 않은 빈 공간을 나타내는 empty ratio라는 변수도 지정해두었습니다.

이 공간이 적으면 적을수록 최적의 개수로 분배된 것입니다.

 

전체 보관함 개수에서 각각의 택배사들이 배정된 보관함이 얼만큼의 비율인지를 나타내는 변수 입니다.

 

문제와 제약조건

저희가 해결해야하는 문제와 제약상황입니다.

해결해야하는 문제는 cpx를 다 더한 것들을 minimize 즉 최소화하는 것입니다.

이 식은 결국 사용되지 않는 빈공간을 최소화하는 식입니다.

어떤 택배사는 빈공간이 많은데 어떤 택배사는 빈공간 없이 꽉꽉 택배가 보관되어 있다면,

빈공간이 많은 택배사 공간을 사용하면 최적의 방법일 것입니다.

 

또한 제약식도 여러가지 사용했는데요,

우선 모든 택배사들의 보관함 개수가 전체 개수를 넘으면 안됩니다.

그리고 각각의 보관함 개수는 0보다 큰 정수여야합니다.

 

5. Conclusion

이전에 배분되었던 보관함 개수는 매우 비효율적이었습니다.

간단하게 회사별 칸 개수와 택배 개수만 비교해보아도 배분이 매우 비효율적이라는 것을 확인할 수 있습니다.

특히 쿠팡은 택배가 2번째로 많이 옴에도 불구하고 보관함 개수가 매우 적게 배분되었습니다.

 

실제로 이 문제에 대해 담당 행정실과 여러번 회의를 했습니다.

그 결과 택배보관함 추가배치, 학생들이 몰리는 시간대에 CCTV확인강화, 추가 택배실 증설 이 3가지 안건이 채택되게 되었답니다!

몇 년 동안이나 방치되었던 문제점을 데이터를 이용해 분석하고 해결하게 된 것입니다 👏🎉