물류센터 내에서의 다수 로봇 경로 최적화
저자
발행사항
서울 : 서울대학교 대학원, 2020
학위논문사항
학위논문(석사)-- 서울대학교 대학원 : 산업공학과 2020. 2
발행연도
2020
작성언어
한국어
주제어
DDC
670.42 판사항(22)
발행국(도시)
서울
기타서명
Multi-agent route optimization for robotic mobile fulfillment systems
형태사항
vi, 56장 : 삽화, 표 ; 26 cm
일반주기명
참고문헌 수록
UCI식별코드
I804:11032-000000160369
소장기관
본 논문은 물류센터 내 물류시스템 중 하나인 RMFS의 운영환경을 염두에 두고 충돌 없이 다수의 에이전트가 출발지에서 목적지까지 이동할 수 있는 이동계획을 찾는 문제를 다룬다. RMFS에서 사용되는 로봇은 물리적 크기를 가질 뿐만 아니라, 이동계획이 주어졌을 때 해당 계획을 부정확하게 수행할 수도 있다는 점에서 해당 특성들을 단순화하는 가정을 적용한 기존의 다수 에이전트 경로찾기문제(Multi-Agent Path Finding Problem)을 해결하기 위한 기법들의 직접적인 적용이 힘들다. 본 논문에서는 로봇의 물리적 크기와 로봇이 이동계획을 부정확하게 수행할 불확실성을 고려하여 꼭짓점에서 시간 간격을 둔 다수 에이전트 경로찾기문제를 제안하고, 이에 대한 정수최적화 모형을 제시한다. 제시된 정수최적화 모형은 결정변수와 제약식의 개수가 많기 때문에, 이를 해결하기 위하여 라그랑지안 완화기법에 기반을 둔 휴리스틱 알고리즘과, 충돌기반탐색(Conflict Based Search)의 변형, 그리고 라그랑지안 완화절차를 이용한 충돌 기반 분지한계 알고리즘을 제안한다. 실험을 통해 제안된 알고리즘이 에이전트의 수가 많거나, 부과한 시간 간격이 클 때도 제한된 시간 안에 좋은 품질의 가능해를 찾는데 효과적임을 확인하였다.
더보기The Robotic Mobile Fulfillment System (RMFS) is a robotized material handling system where multiple robots transport movable shelves to and from stocking points and workstations in a warehouse. In this paper, we deal with the problem of finding collision-free routes for multiple robots to move from their starting points to destinations in a RMFS, which is defined as a generalization of the multi-agent path finding problem (MAPFP). In RMFSs, collisions among moving robots may occur due to the physical volume of robots and the inexact execution of planned routes by robots in terms of the planned timing of passing through points on the routes, which makes it difficult to directly apply the existing algorithms for MAPFP that assume the exact execution of planned routes by agents with no physical volume. Therefore, we defined the problem as a multi-agent path finding problem with the prespecified time spacing at points to address the possible sources of collisions among robots, and propose an integer optimization model for the problem. Since the proposed integer optimization model has a large number of decision variables and constraints, we propose heuristic and exact algorithms based on the Lagrangian relaxation technique and the conflict based search. Experimental results show that the proposed algorithms are effective in finding good quality solutions within a limited time even when the number of robots or the time spacing are large.
더보기분석정보
서지정보 내보내기(Export)
닫기소장기관 정보
닫기권호소장정보
닫기오류접수
닫기오류 접수 확인
닫기음성서비스 신청
닫기음성서비스 신청 확인
닫기이용약관
닫기학술연구정보서비스 이용약관 (2017년 1월 1일 ~ 현재 적용)
학술연구정보서비스(이하 RISS)는 정보주체의 자유와 권리 보호를 위해 「개인정보 보호법」 및 관계 법령이 정한 바를 준수하여, 적법하게 개인정보를 처리하고 안전하게 관리하고 있습니다. 이에 「개인정보 보호법」 제30조에 따라 정보주체에게 개인정보 처리에 관한 절차 및 기준을 안내하고, 이와 관련한 고충을 신속하고 원활하게 처리할 수 있도록 하기 위하여 다음과 같이 개인정보 처리방침을 수립·공개합니다.
주요 개인정보 처리 표시(라벨링)
목 차
3년
또는 회원탈퇴시까지5년
(「전자상거래 등에서의 소비자보호에 관한3년
(「전자상거래 등에서의 소비자보호에 관한2년
이상(개인정보보호위원회 : 개인정보의 안전성 확보조치 기준)개인정보파일의 명칭 | 운영근거 / 처리목적 | 개인정보파일에 기록되는 개인정보의 항목 | 보유기간 | |
---|---|---|---|---|
학술연구정보서비스 이용자 가입정보 파일 | 한국교육학술정보원법 | 필수 | ID, 비밀번호, 성명, 생년월일, 신분(직업구분), 이메일, 소속분야, 웹진메일 수신동의 여부 | 3년 또는 탈퇴시 |
선택 | 소속기관명, 소속도서관명, 학과/부서명, 학번/직원번호, 휴대전화, 주소 |
구분 | 담당자 | 연락처 |
---|---|---|
KERIS 개인정보 보호책임자 | 정보보호본부 김태우 | - 이메일 : lsy@keris.or.kr - 전화번호 : 053-714-0439 - 팩스번호 : 053-714-0195 |
KERIS 개인정보 보호담당자 | 개인정보보호부 이상엽 | |
RISS 개인정보 보호책임자 | 대학학술본부 장금연 | - 이메일 : giltizen@keris.or.kr - 전화번호 : 053-714-0149 - 팩스번호 : 053-714-0194 |
RISS 개인정보 보호담당자 | 학술진흥부 길원진 |
자동로그아웃 안내
닫기인증오류 안내
닫기귀하께서는 휴면계정 전환 후 1년동안 회원정보 수집 및 이용에 대한
재동의를 하지 않으신 관계로 개인정보가 삭제되었습니다.
(참조 : RISS 이용약관 및 개인정보처리방침)
신규회원으로 가입하여 이용 부탁 드리며, 추가 문의는 고객센터로 연락 바랍니다.
- 기존 아이디 재사용 불가
휴면계정 안내
RISS는 [표준개인정보 보호지침]에 따라 2년을 주기로 개인정보 수집·이용에 관하여 (재)동의를 받고 있으며, (재)동의를 하지 않을 경우, 휴면계정으로 전환됩니다.
(※ 휴면계정은 원문이용 및 복사/대출 서비스를 이용할 수 없습니다.)
휴면계정으로 전환된 후 1년간 회원정보 수집·이용에 대한 재동의를 하지 않을 경우, RISS에서 자동탈퇴 및 개인정보가 삭제처리 됩니다.
고객센터 1599-3122
ARS번호+1번(회원가입 및 정보수정)