| 1 |
1
운송 수단과 드론을 사용한 병렬 배송의 택배 위치 클러스터링을 이용한 운송 수단 및 드론의 스케줄링 최적화 방법에 있어서, 고객의 위치 데이터를 입력하고, 상기 고객의 위치 데이터 중에서 운송 수단 및 드론이 배송 가능한 배송 위치 데이터를 획득하며, 디포(depot)에서 상기 배송 위치 데이터까지의 거리 및 소요시간을 산출하는 택배 준비 단계; 상기 배송 위치 데이터 간의 상대적인 거리 비율과 클러스터의 중심점 간의 거리를 기반으로 복수의 배송 위치 데이터를 클러스터링하는 클러스터링 단계;각 클러스터의 중심점에 설치된 드론 정거장을 기준으로, 상기 드론 정거장에서 상기 배송 위치 데이터까지 상기 운송 수단 및 상기 드론의 병렬 택배를 위한 RGSO(Routing Group Search Optimization) 스케줄링 해를 획득하는 RGSO 스케줄링 단계; 및모든 클러스터에서 상기 RGSO 스케줄링 해를 획득하여 RGSO 스케줄링을 완료하는 스케줄링 처리 단계를 포함하는 운송 수단 및 드론의 스케줄링 최적화 방법
|
| 2 |
2
제1항에 있어서,상기 택배 준비 단계는상기 고객의 위치 데이터(x, y)와 상기 운송 수단 및 상기 드론의 속도를 입력하는 단계;상기 드론의 배달 가능한 중량 노드 및 상기 드론의 배달 가능한 범위를 입력하는 단계;상기 고객의 위치 데이터 중에서 상기 운송 수단 및 상기 드론이 배송 가능한 배송 위치를 나타내는 상기 배송 위치 데이터를 획득하는 단계; 상기 배송 위치 데이터 중에서, 상기 디포를 포함한 모든 고객 위치 간의 상기 운송 수단의 직각거리와 소요시간을 산출하고, 상기 디포에서 모든 고객 위치 간의 상기 드론의 직선거리와 소요시간을 산출하는 단계; 및상기 운송 수단과 상기 드론의 소요시간으로 총 소요시간(Makespan)의 평가함수를 정의하는 단계를 포함하는 운송 수단 및 드론의 스케줄링 최적화 방법
|
| 3 |
3
제2항에 있어서,상기 배송 위치 데이터를 획득하는 단계는상기 고객의 위치 데이터 중에서, 배달물의 중량 초과로 인해 상기 드론이 배달 불가능한 배송 위치 및 상기 디포에서 상기 드론으로 배달 가능한 배송 위치를 확인하여 상기 배송 위치 데이터를 획득하는, 운송 수단 및 드론의 스케줄링 최적화 방법
|
| 4 |
4
제1항에 있어서,상기 클러스터링 단계는클러스터 수 k를 결정하는 단계;상기 배송 위치 데이터 각각의 상대적인 거리 비율을 계산하는 단계;최소값의 상대적인 거리 비율 값을 나타내는 배송 위치 데이터를 선택하며, 기 결정된 중심데이터와의 거리를 고려한 k개의 중심데이터들을 결정하는 단계; 상기 중심데이터에 가까운 상기 배송 위치 데이터를 할당하여 데이터 클러스터링하는 단계; 및복수의 클러스터 각각의 중심점에 드론 정거장(Drone Station; DS)을 위치시키는 단계를 포함하는, 운송 수단 및 드론의 스케줄링 최적화 방법
|
| 5 |
5
제4항에 있어서,상기 k개의 중심데이터들을 결정하는 단계는첫 번째 중심데이터를 선택하고, 상기 첫 번째 중심데이터에서 최소값의 상대적인 거리 비율 값을 나타내는 배송 위치 데이터를 선택하며, 상기 첫 번째 중심데이터로부터 거리와 상기 최소의 상대적인 거리 비율 값을 동시에 고려하여 두 번째 중심데이터를 선택하는 것을 특징으로 하는, 운송 수단 및 드론의 스케줄링 최적화 방법
|
| 6 |
6
제5항에 있어서,상기 데이터 클러스터링하는 단계는선택된 k개의 중심데이터를 중심으로 상기 배송 위치 데이터를 클러스터링하여 클러스터링 세분화 해를 생성하는, 운송 수단 및 드론의 스케줄링 최적화 방법
|
| 7 |
7
제1항에 있어서,상기 RGSO 스케줄링 단계는상기 배송 위치 데이터 중에서 상기 운송 수단 및 상기 드론의 각 경로에 대한 초기 해를 생성하며, 상기 초기 해의 인구(Population)를 생성하고, 총 소요시간(Makespan)을 산출하는 단계; 초기 해의 프로듀서(producer)에 대한 프로듀싱 과정, 스크라운징 과정, 레인징 과정 및 파인딩 과정을 수행하는 단계;수행 결과에 따른 모든 해들의 평가값을 산출하여 최소값의 총 소요시간(Makespan)을 나타내는 해를 상기 프로듀서에 업데이트하는 단계; 및업데이트 결과에 따라 상기 운송 수단과 상기 드론을 사용한 병렬 배송을 위한 최적 해를 획득하는 단계를 포함하는, 운송 수단 및 드론의 스케줄링 최적화 방법
|
| 8 |
8
제7항에 있어서, 상기 수행하는 단계는운송 수단의 기준 확률 및 드론의 기준 확률을 기준으로 상기 프로듀서(producer)에서 이웃 해들을 탐색하여 새로운 프로듀서(new producer)로 업데이트하는 상기 프로듀싱 과정을 수행하는, 운송 수단 및 드론의 스케줄링 최적화 방법
|
| 9 |
9
제8항에 있어서, 상기 수행하는 단계는상기 새로운 프로듀서를 제외한 약 60%를 이전 스크라운저(previous scrounger)로 선택하며, 상기 새로운 프로듀서에 따라 해를 탐색하여 새로운 스크라운저(new scrounger)로 업데이트하는 상기 스크라운징 과정 및 상기 새로운 프로듀서를 제외한 약 10%를 이전 레인저(previous ranger)로 선택하며, 무작위 이웃 해의 다양한 해를 탐색하여 새로운 레인저(new ranger)로 업데이트하는 상기 레인징 과정을 수행하는, 운송 수단 및 드론의 스케줄링 최적화 방법
|
| 10 |
10
제9항에 있어서, 상기 수행하는 단계는상기 새로운 프로듀서를 제외한 약 30%를 이전 파인더(previous finder)로 선택하며, 라우팅(routing)에 적합한 메커니즘을 통하여 해를 탐색하여 새로운 파인더(new finder)로 업데이트하는 상기 파인딩 과정을 수행하는 것을 특징으로 하는, 운송 수단 및 드론의 스케줄링 최적화 방법
|
| 11 |
11
제7항에 있어서, 상기 프로듀서에 업데이트하는 단계는상기 프로듀싱 과정, 상기 스크라운징 과정, 상기 레인징 과정 및 상기 파인딩 과정에서의 모든 N개의 해에 대한 총 소요시간(Makespan)을 산출하며, 그 중 최소 평가값을 나타내는 새로운 프로듀서를 선택하며, 상기 프로듀서와 상기 새로운 프로듀서를 비교하여 상기 프로듀서를 업데이트하는, 운송 수단 및 드론의 스케줄링 최적화 방법
|
| 12 |
12
제11항에 있어서, 상기 최적 해를 획득하는 단계는일정 세대 동안 상기 프로듀서의 변화가 없는 기 설정된 종료 조건에 부합할 때, 상기 RGSO 스케줄링 최적화 방법을 종료하여 병렬 배송을 위한 상기 최적 해를 도출하는, 운송 수단 및 드론의 스케줄링 최적화 방법
|
| 13 |
13
운송 수단과 드론을 사용한 병렬 배송의 택배 위치 클러스터링을 이용한 운송 수단 및 드론의 스케줄링 최적화 시스템에 있어서, 고객의 위치 데이터를 입력하고, 상기 고객의 위치 데이터 중에서 운송 수단 및 드론이 배송 가능한 배송 위치 데이터를 획득하며, 디포(depot)에서 상기 배송 위치 데이터까지의 거리 및 소요시간을 산출하는 택배 준비부; 상기 배송 위치 데이터 간의 상대적인 거리 비율과 클러스터의 중심점 간의 거리를 기반으로 복수의 배송 위치 데이터를 클러스터링하는 클러스터링부;각 클러스터의 중심점에 설치된 드론 정거장을 기준으로, 상기 드론 정거장에서 상기 배송 위치 데이터까지 상기 운송 수단 및 상기 드론의 병렬 택배를 위한 RGSO(Routing Group Search Optimization) 스케줄링 해를 획득하는 RGSO 스케줄링부; 및모든 클러스터에서 상기 RGSO 스케줄링 해를 획득하여 RGSO 스케줄링을 완료하는 스케줄링 처리부를 포함하는 운송 수단 및 드론의 스케줄링 최적화 시스템
|
| 14 |
14
제13항에 있어서,상기 택배 준비부는상기 고객의 위치 데이터(x, y)와 상기 운송 수단 및 상기 드론의 속도를 입력하고, 상기 드론의 배달 가능한 중량 노드 및 상기 드론의 배달 가능한 범위를 입력하는 입력부;상기 고객의 위치 데이터 중에서 상기 운송 수단 및 상기 드론이 배송 가능한 배송 위치를 나타내는 상기 배송 위치 데이터를 획득하는 데이터 획득부;상기 배송 위치 데이터 중에서, 상기 디포를 포함한 모든 고객 위치 간의 상기 운송 수단의 직각거리와 소요시간을 산출하고, 상기 디포에서 모든 고객 위치 간의 상기 드론의 직선거리와 소요시간을 산출하는 산출부; 및상기 운송 수단과 상기 드론의 소요시간으로 총 소요시간(Makespan)의 평가함수를 정의하는 처리부를 포함하는 운송 수단 및 드론의 스케줄링 최적화 시스템
|
| 15 |
15
제13항에 있어서,상기 클러스터링부는클러스터 수 k를 결정하는 선택부;상기 배송 위치 데이터 각각의 상대적인 거리 비율을 계산하는 계산부;최소값의 상대적인 거리 비율 값을 나타내는 배송 위치 데이터를 선택하며, 기 결정된 중심데이터와의 거리를 고려한 k개의 중심데이터들을 결정하는 중심데이터 결정부; 상기 중심데이터에 가까운 상기 배송 위치 데이터를 할당하여 데이터 클러스터링하는 데이터 클러스터부; 및복수의 클러스터 각각의 중심점에 드론 정거장(Drone Station; DS)을 위치시키는 DS 형성부를 포함하는, 운송 수단 및 드론의 스케줄링 최적화 시스템
|
| 16 |
16
제13항에 있어서,상기 RGSO 스케줄링부는상기 배송 위치 데이터 중에서 상기 운송 수단 및 상기 드론의 각 경로에 대한 초기 해를 생성하며, 상기 초기 해의 인구(Population)를 생성하고, 총 소요시간(Makespan)을 산출하는 초기 해 생성부; 초기 해의 프로듀서(producer)에 대한 프로듀싱 과정, 스크라운징 과정, 레인징 과정 및 파인딩 과정을 수행하는 수행부;수행 결과에 따른 모든 해들의 평가값을 산출하여 최소값의 총 소요시간(Makespan)을 나타내는 해를 상기 프로듀서에 업데이트하는 프로듀서 처리부; 및업데이트 결과에 따라 상기 운송 수단과 상기 드론을 사용한 병렬 배송을 위한 최적 해를 획득하는 최적 해 획득부를 포함하는, 운송 수단 및 드론의 스케줄링 최적화 시스템
|
