개요 정리

 

1. 과제의 목표

자동배차 주행경로 탐색 알고리즘 시뮬레이터

사용자가 배차를 요청하면 자동으로 주변의 차를 배차하고 목적지까지 주행하는 경로를 나타내는 알고리즘을 구상하고, 이를 테스트하는 시뮬레이터를 만든다.

2. 대상 문제 및 요구사항 분석

2-1) 대상문제

최근 다양한 분야에서 자동화가 이루어져 효율적인 작업이 가능해 졌다. 하지만 아직 배차 시스템은 단순히 가까운 위치의 차량에게 배차되는 단순한 알고리즘을 사용하고있다. 이런 단순한 알고리즘은 여러가지 상황을 고려하지 않음으로, 자원과 시간이 효율적으로 분배되지 않아 이를 보정하는 자동 배차 알고리즘을 개발한다.

2-2) 요구사항

1. 알고리즘은 배차 대기시간과 목적지까지 이동하는 시간을 최소화 한다.

   가까운 call이 일어난 경우 가까운 위치의 차량을 즉시 배차하여 대기시간을 최소화 한다.

2. 최대한 많은 사용자를 수용가능하게 한다.

  배차가능한 차량이 적을 경우 차량과 목적지까지의 거리 등을 계산하여 근처의 사용자에 대한 합승여부를 결정한다.

3. 기업입장에서의 소모비용 최소화.

   서비스에 들어가는 비용을 최소화 한다.

3. 현실적 제약사항 분석 및 대책

3-1) 제약사항

1. 파이썬 gui로 map구현

실제 지도를 사용하기 어려움.

2. 콜 시나리오 구현.

    알고리즘 테스트에서 사용자로 부터 직접적인 콜을 받을 수 없다.

3-2) 대책

1. 제약사항 1. 에 대한 대책

지도는 GUI로 만든 가상의 맵으로 제한한다.

2. 제약사항 2. 에 대한 대책

시나리오 call을 사용해 랜덤한 변수의 call을 생성한다.

4. 설계 문서

4-1) 기술소개

1. 인공지능 AI

  컴퓨터에서 인간과 같이 사고하고 생각하고 학습하고 판단하는 논리적인 방식을 사용하는 인간지능을 본 딴 고급 컴퓨터프로그램 사용.

2. 알고리즘

배차 요청시 사용자와 배차차량간의 거리 및 시간, 소모되는 자원, 수학적 방법론을 이용한 최적의 효율을 만들게 한다.

4-2) 개발환경

개발 언어 : Python.

개발 도구 : PyCharm.

대상 시스템 : 윈도우PC.

4-3) 주요 모듈

1. 배차엔진(NVD)

NVD(Nearest Vehicle Dispatch)는 가장 보편적으로 사용되는 알고리즘으로 직관적이며 원시적인 알고리즘이다. 배차 운영 시스템에 새로운 서비스가 요청되면, 요청된 승객의 위치에서 가장 가까운 차량을 찾아서 해당 차량의 운행계획을 갱신한다. 만약 가장 가까운 차량이 주어진 제약조건을 만족하지 않는다면 그 다음으로 가까운 차량을 찾는 방식이다. 이 방식의 장점은 승객의 서비스 대기시간을 최소화할 수 있으며, 알고리즘이 매우 단순하여 빠른 수행 속도(O(n2))를 보여준다. 하지만 승객의 기종점을 동시에 고려하지 않기 때문에 기존 승객의 목적지와의 거리가 먼 경우, 잦은 경로 우회가 발생된다. 이것을 보완하기 위해 합승시스템또한 적용하여 기종점까지의 거리를 계산한 뒤 근처의 승객에게 [그림-1]과 같이 합승을 제안한다. 합승 조건을 만족시키는 차량이 선택되고 새로운 승객이 차량 운행에 입력되는 경우 해당 차량은 실시간으로 기존의 운행 일정과 신규 승하차 일정을 최적화 한다. 최대 승차인원이 4명인 경우라고 가정할 때, 대부분의 개별 차량은 5~7개 내외의 승하차 운행일정을 포함하고 있기 때문에 이 문제는 제약조건이 포함된 PDP(Pickup and Delivery Problem) 형태의 문제로서 최적해가 도출될 수 있다.

 

[그림-1 shared-ride]

 

5. 추진체계 및 일정

6.1 역할분담

구성원	역할
황보규민	알고리즘 개발 파이썬 beautifulSoup과 selenium을 통한 멀티 프로세스로 데이터 재구성
정성훈	알고리즘 개발 파이썬 pyqt5 library를 통한 UI구현
이세철	알고리즘 개발 CALL 시나리오 개발

 

6.2 개발일정

월 진행 항목	2	3	4	5	6
착수보고서 작성
데이터 정제
중간보고서 작성
알고리즘 개발
알고리즘 최적화
최종보고서 작성
Test 및 보완
졸업과제 발표
결과물 제출/ SW등록