1 |
1
차량 쉐어링(car sharing)에 제공되는 차량의 재배치를 스케쥴링하는 방법에 있어서,컴퓨팅 장치가, 복수의 스테이션들 중 적어도 하나의 오버플로 스테이션(overflow) 및 적어도 하나의 언더플로(underflow) 스테이션을 식별하는 단계;상기 컴퓨팅 장치가, 상기 오버플로 스테이션과 상기 언더플로 스테이션 사이의 거리에 기초로 상기 오버플로 스테이션에 속하는 재배치 차량과 상기 언더플로 스테이션 사이의 매칭 정보를 포함하는 차량 재배치 계획을 획득하는 단계; 및상기 컴퓨팅 장치가, 유전 알고리즘(genetic algorithm)을 이용하여 상기 차량 재배치 계획으로부터 차량 재배치를 스케쥴링하는 단계를 포함하고,상기 차량 재배치를 스케쥴링하는 단계는상기 컴퓨팅 장치가, 상기 매칭 정보 내 복수의 원소들을 지시하는 복수의 인덱스들을 서로 다른 순서로 포함하는 복수의 부모 염색체들을 해 집단에 포함시키는 단계;상기 컴퓨팅 장치가, 상기 해 집단에 포함된 복수의 부모 염색체들 중 적어도 일부를 기초로 교차 연산을 수행함으로써, 적어도 하나의 자식 염색체를 생성하는 단계;상기 컴퓨팅 장치가, 상기 적어도 하나의 자식 염색체 각각에 대응하여, 해당하는 자식 염색체 내 중복된 인덱스를 누락된 인덱스로 대치하는 단계; 및상기 컴퓨팅 장치가, 차량을 재배치하기 위한 동선 거리에 기초한 적합도 함수를 이용하여, 선택 연산을 수행하는 단계를 포함하는 스케쥴링 방법
|
2 |
2
제1항에 있어서,차량 재배치 스케쥴링은 상기 차량 재배치 계획에 포함된 복수의 매칭 페어들을 포함하는 염색체(chromosome)로 표현되고, 상기 염색체의 품질은 상기 복수의 매칭 페어들의 순서에 따라 정해지는 스케쥴링 방법
|
3 |
3
삭제
|
4 |
4
제1항에 있어서,상기 적어도 하나의 오버플로 스테이션(overflow) 및 적어도 하나의 언더플로(underflow) 스테이션을 식별하는 단계는상기 컴퓨팅 장치가, 복수의 스테이션들에 배치된 복수의 차량들의 현재 분포량에 대한 정보를 나타내는 현재 분포 정보를 획득하는 단계;상기 컴퓨팅 장치가, 미리 정해진 재배치 스킴(relocation scheme)을 기초로 상기 복수의 스테이션들 각각의 목표 분포량에 대한 정보를 나타내는 목표 분포 정보를 획득하는 단계;상기 컴퓨팅 장치가, 상기 현재 분포 정보 및 상기 목표 분포 정보를 이용하여 상기 복수의 스테이션들 각각에 대한 차량의 과부족 정보를 나타내는 현재 상황 정보를 추출하는 단계; 및상기 컴퓨팅 장치가, 상기 현재 상황 정보를 기초로 상기 복수의 스테이션들 중 적어도 하나의 오버플로 스테이션 및 적어도 하나의 언더플로 스테이션을 식별하는 단계를 포함하는 스케쥴링 방법
|
5 |
5
제4항에 있어서,상기 미리 정해진 재배치 스킴은 이븐 재배치 스킴(even relocation scheme), 사용율 기반 스킴(utilization-based scheme) 또는 모닝 포커스 스킴(morning-focused scheme) 중 적어도 어느 하나를 포함하는 스케쥴링 방법
|
6 |
6
제4항에 있어서,상기 목표 분포 정보를 획득하는 단계는상기 컴퓨팅 장치가, 상기 미리 정해진 재배치 스킴을 기초로 상기 복수의 스테이션들 각각의 재배치 가중치(relocation weight)를 획득하는 단계;상기 컴퓨팅 장치가, 상기 복수의 차량의 전체 차량 대수를 식별하는 단계; 및상기 컴퓨팅 장치가, 상기 각각의 스테이션의 재배치 가중치 및 상기 전체 차량 대수를 이용하여 상기 목표 분포 정보를 계산하는 단계를 포함하는 스케쥴링 방법
|
7 |
7
제4항에 있어서,상기 복수의 스테이션들 중 적어도 하나의 오버플로 스테이션 및 적어도 하나의 언더플로 스테이션을 식별하는 단계는상기 컴퓨팅 장치가, 상기 복수의 스테이션들 중 상기 현재 분포량이 상기 목표 분포량을 초과하는 적어도 하나의 스테이션을 상기 오버플로 스테이션으로 설정하는 단계; 및상기 컴퓨팅 장치가, 상기 복수의 스테이션들 중 상기 현재 분포량이 상기 목표 분포량보다 부족한 적어도 하나의 스테이션을 상기 언더플로 스테이션으로 설정하는 단계를 포함하는 스케쥴링 방법
|
8 |
8
제1항에 있어서,상기 차량 재배치를 스케쥴링하는 단계는상기 컴퓨팅 장치가, 적어도 하나의 오버플로 스테이션과 적어도 하나의 언더플로 스테이션을 이용하여 인덱스 테이블-상기 인덱스 테이블은 상기 매칭 정보에 대응함-을 생성하는 단계; 및상기 컴퓨팅 장치가, 상기 인덱스 테이블의 원소를 지시하는 정수 엘리먼트-상기 정수 엘리먼트는 상기 인덱스에 대응함-를 포함하는 복수의 벡터들-상기 벡터들은 상기 부모 염색체들에 대응함-을 생성하는 단계를 더 포함하는 스케쥴링 방법
|
9 |
9
제8항에 있어서,상기 복수의 벡터들 각각은 재배치 되어야 하는 차량들의 수만큼 정수 엘리먼트들을 포함하고, 정수 엘리먼트의 벡터 내의 위치는 상기 인덱스 테이블에 포함된 복수의 오버플로 스테이션들 중 어느 하나를 지시하며, 상기 정수 엘리먼트의 값은 상기 인덱스 테이블에 포함된 복수의 언더플로 스테이션들 중 어느 하나를 지시하는 스케쥴링 방법
|
10 |
10
제8항에 있어서,상기 인덱스 테이블을 생성하는 단계는상기 컴퓨팅 장치가, 정수 엘리먼트의 벡터 내의 위치와 오버플로 스테이션의 재배치 차량을 대응시키기 위하여 오버플로 스테이션의 초과 차량의 수만큼 해당 오버플로 스테이션을 상기 인덱스 테이블에 복사하는 단계; 및상기 컴퓨팅 장치가, 정수 엘리먼트들의 값과 언더플로 스테이션을 대응시키기 위하여 언더플로 스테이션을 부족 차량의 수만큼 해당 언더플로 스테이션을 상기 인덱스 테이블에 복사하는 단계를 포함하는 스케쥴링 방법
|