이진정수계획법 프로젝트 (트럭 배송 문제)

소개글

최우수 프로젝트로 A+ 받았습니다~

목차

1. 문제 설명
2. 문제 분석
3. 결과 제시 및 해 분석
4. References

본문내용

경희전자는 매일 8 곳의 소매상에 각 소매상이 요구하는 수량의 물품을 배달해야 한다. 물품은 물류창고에서 트럭을 이용하며 배달하며 배달을 위하여 대형트럭(적재적량 12톤) 2대, 중형트럭(적재적량 8톤) 2대, 소형트럭(적재적량 5톤) 2대를 보유하고 있다. 다음 표에는 물류창고와 고객들 사이의 운송시간(에서 까지의 소요시간은 에서 까지의 소요시간과 동일하다), 각 소매상에서의 수요, 각 소매상에 배달완료해야 하는 배달 마감시간이 기재되어 있다. 배달은 9:00 정각에 시작되며 대형트럭은 시간당 5만원, 중형트럭은 시간당 4만원, 소형트럭은 시간당 3만원의 운송비용이 소요된다. 목적하는 바는 각 소매상에 원하는 수요를 최소의 비용으로 시간에 늦지 않고 배달하기 위한 배달방법(어떤 종류의 트럭으로 어떤 경로를 통하여 배달할 것인지)을 결정하는 것이다. 이를 이진정수계획법을 이용하여 정식화하고 소프트웨어를 이용하여 해를 구하라.

<중 략>

이 문제의 목적함수는 상기 문제에 <목적하는 바는 각 소매상에 원하는 수요를 최소의 비용으로 시간에 늦지 않고 배달하기 위한 배달방법(어떤 종류의 트럭으로 어떤 경로를 통하여 배달할 것인지)을 결정하는 것이다.>라고 언급되어있듯, 비용 최소화 문제이므로 운송하는 데에 걸린 시간이 로 표기되어있으며, 해당 루트를 이용해서 트럭의 이동 여부인 가 0과 1로 표시되므로 목적함수 식은 다음과 같습니다.

<중 략>

단, 이 프로그램 또한 시간이 과하게 길어지거나 계산의 양의 한계로 인한 프로그램의 강제 종료 등의 문제점이 해 도출 과정에서 발생하였기 때문에 일괄적인 제약식 중에서 의미없는 제약식들을 제거하고 필요한 제약식만을 남겨 프로그래밍하였습니다. (이 중에서 이진 관련 제약식은 LiPs가 기본적으로 제공하는 기능인 변수 설정에서 제약식을 대신할 수 있었기 때문에 하단의 식의 수에는 포함되지 않았습니다.) 이 문제에 대한 약식으로 프로그램에 사용된 제약식은 총 164개이며, 결정변수는 216개가 사용되었습니다. Matrix Map은 다음과 같습니다.

참고 자료

김원태, 최경일, 이경식, 임현태(2005). 시간제약을 가진 이기종 차량경로문제에 관한 연구. 한국외국어대학교 산업정보시스템공학부 학술대회 논문.
장희정, 이경식, 최은정, 박성수(2005). 시간제약과 하역장 용량제약이 있는 차량경로문제에 대한 타부탐색 알고리즘. 한국경영과학회지.
최은정, 이태한, 박성수(2002). 복수 차량 유형에 대한 차량경로문제의 정수계획 해법. 한국경영과학회 학술대회논문집.
Hillier, Lieberman(2014). 경영과학. 김선교, 윤석훈 外 1명 역. 지필미디어.
Hillier, Lieberman(2007). Introduction to Operations Research. McGraw-Hill Korea
강금식(2014). Excel 경영과학. 박영사.
강금식(2012). 알기 쉬운 경영과학. 오래.
김충영, 이재영(2003). 선형계획법. 두남.
홍성필(2010). 경영과학 – 기초부터 심화까지. 율곡출판사.