자동 배차 및 주행경로 탐색 알고리즘 시뮬레이터를 제작한다. 그리고 택시와 고객간 최적의 비율을 제시한다.

1. 사용자가 배차를 요청하면 자동으로 주변의 차를 배차하고 목적지까지 주행하는 경로를 나타내는 알고리즘을 구상하고, 이를 테스트하는 시뮬레이터를 만든다
2. 차량의 수, 고객의 수, 합승여부 등의 조건이 바뀔 때 어떤 알고리즘이 효율적인지 결과를 보여준다.

• PyQt5의 Qtdesign 툴을 사용하여 UI를 만든다.
• 최단 경로는 다익스트라 알고리즘을 이용해 탐색한다.
• 자동차와 사용자가 움직이는 동선을 맵에 표시한다.
• BFS를 사용하여 사용자 근처의 자동차를 구한다.
• 맵 클래스를 통해 현재 상태를 파악한다.
• car과 customer 클래스를 만들어 알고리즘에 필요한 정보들을 저장한다.
• 여러가지 조건을 설정할 수 있도록 하고 어떤 조건일 때 가장 효율적인지 판단할 수 있도록 결과를 표시한다.
• 다음과 같은 조건을 가진 알고리즘을 시뮬레이션 할 수 있다. ◦ 합승 불가능 (1 : 1 배치) ◦ 합승 가능 (1 : N 배치, 먼저 탑승한 인원 먼저 처리) ◦ 합승 시 최단 경로 수정 (1 : N 배치, 목적지가 가까운 순으로 처리)
• 지도 상 경로의 가중치는 1로 일반화한다.
• 10개의 맵을 text파일로 생성해 읽어올 수 있다.
• 10개의 콜 시나리오를 만들고, 이를 바탕으로 테스트를 수행한다.
• 차량 총 이동거리, 고객의 평균 대기시간, 이동시간을 알고리즘별로 종합하여 화면에 표시한다.
• 고객 생성 시 근처 차량이 없을 때, 고객의 콜을 취소한다.

1. 맵 생성 함수 수정 여러 알고리즘에서 변수를 바꾸며 시뮬레이션을 수행할 때 고정된 환경을 만들 수 있도록 기존에 무작위로 생성되던 맵을 txt 파일로 만든 뒤 읽어오는 방식으로 수정했다.
2. 합승 알고리즘 추가 기존에는 합승 조건을 고려하지 않고 차량과 고객을 1 : 1 대응만을 처리하는 알고리즘만 존재했지만, 합승 조건을 고려하는 새로운 알고리즘이 추가됐다.
3. 시뮬레이션 결과 표시 기존에는 시간경과 버튼을 통해 차량과 사람이 어떤 식으로 움직이는지 나타냈다. 알고리즘이 추가되면서 알고리즘 별로 시뮬레이션 결과를 비교할 수 있도록 고객의 대기 시간, 목적지까지 걸린 시간, 차량의 이동 거리 등을 결과에 표시하도록 수정했다.
4. UI 수정 변경 전 UI는 변수 입력이 불가능하고 시간에 따른 변화를 관찰만 할 수 있었다. 변경 후 UI는 메인 윈도우와 서브 윈도우로 나뉘었다. 메인 윈도우는 여러가지 변수나 원하는 알고리즘을 입력할 수 있고, 시뮬레이션 과정 및 결과를 보여주는 서브 윈도우에는 한번에 시뮬레이션을 완료할 수 있도록 skip 버튼을 추가했다.

1. 고객 발생 처리 함수
2. 시간 경과 함수
3. BFS 함수
4. 고객 클래스 관리
5. 콜 시나리오 생성
6. 맵 생성