최종보고서

전기컴퓨터공학부 정보컴퓨터공학전공

황보규민(201424559)

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

지도교수 : 조 환 규

1. 과제 목표

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

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

경로와 차량 대수를 고객수에 따라 테스트하여 최적화한다.

2. 설계 상세화 및 사용 기술, 수정사항

- GUI는 PyQt5의 Qtdesign 툴을 사용하여 베이스를 만든다.

- 알고리즘은 다익스트라를 선택하여 만든다.

- 자동차와 사용자가 움직이는 동선을 표시한다.

- 현재는 모든 자동차와 사용자간의 거리를 계산하고 자동차를 선택하지만, 4월에는 BFS를 사용하여 사용자근처의 자동차를 선택한다.

- 그리드맵에 위치정보를 struct로 넣을 수 없어 Label로 넣고 split으로 구분하여 정보를 업데이트한다.

- car과 person 딕셔너리를 만들어 현재 매칭중인 정보들을 추가한다.

- 최단경로는 다익스트라 알고리즘을 사용한다.

- 알고리즘은 총 3 개, 1) 합승 불가능 2) 합승 가능 3) 최단 경로의 합승가능 을 만든다.

- weight는 1로 일반화한다.

- 맵을 text파일로 총 10개를 받아와서 읽는다.

- 사용자 시나리오는 10개의 case를 만들어 실행한다.

- 차량 총 이동거리, 평균대기시간, 이동시간을 알고리즘별로 종합하여 표시한다.

- 고객 생성 시 근처 차량이 없을 때, 고객의 콜을 취소한다.

- ui 변경

[차량 300대 고정 분석결과]

[고객 500명 고정 분석결과]

main.py

import sys
from MainWindow import MainWindow
from PyQt5.QtWidgets import *

if __name__ == '__main__':
    app = QApplication(sys.argv)
    win = MainWindow()
    win.show()
    sys.exit(app.exec_())

mainwindow.py

import sys
from PyQt5.QtWidgets import *
from PyQt5.QtCore import *
from SubWindow import SubWindow
from PyQt5 import QtCore, QtGui, QtWidgets

class MainWindow(QMainWindow):
    def __init__(self):
        super().__init__()
        self.initUI()

    def initUI(self):
        self.setWindowTitle('Main Window')
        self.setGeometry(300,300,614, 300)

        self.centralwidget = QtWidgets.QWidget(self)
        self.centralwidget.setObjectName("centralwidget")
        self.gridLayoutWidget = QtWidgets.QWidget(self.centralwidget)
        self.gridLayoutWidget.setGeometry(QtCore.QRect(10, 10, 591, 221))
        self.gridLayoutWidget.setObjectName("gridLayoutWidget")
        self.gridLayout = QtWidgets.QGridLayout(self.gridLayoutWidget)
        self.gridLayout.setContentsMargins(0, 0, 0, 0)
        self.gridLayout.setObjectName("gridLayout")
        self.textEdit_algorithm = QtWidgets.QTextEdit(self.gridLayoutWidget)
        self.textEdit_algorithm.setObjectName("textEdit_algorithm")
        self.gridLayout.addWidget(self.textEdit_algorithm, 0, 1, 1, 1)
        self.textEdit_people = QtWidgets.QTextEdit(self.gridLayoutWidget)
        self.textEdit_people.setObjectName("textEdit_people")
        self.gridLayout.addWidget(self.textEdit_people, 1, 1, 1, 1)
        self.textEdit_car = QtWidgets.QTextEdit(self.gridLayoutWidget)
        self.textEdit_car.setObjectName("textEdit_car")
        self.gridLayout.addWidget(self.textEdit_car, 2, 1, 1, 1)
        self.textEdit_map = QtWidgets.QTextEdit(self.gridLayoutWidget)
        self.textEdit_map.setObjectName("textEdit_map")
        self.gridLayout.addWidget(self.textEdit_map, 3, 1, 1, 1)
        self.label_3 = QtWidgets.QLabel(self.gridLayoutWidget)
        self.label_3.setObjectName("label_3")
        self.gridLayout.addWidget(self.label_3, 2, 0, 1, 1)
        self.label_4 = QtWidgets.QLabel(self.gridLayoutWidget)
        self.label_4.setObjectName("label_4")
        self.gridLayout.addWidget(self.label_4, 3, 0, 1, 1)
        self.label = QtWidgets.QLabel(self.gridLayoutWidget)
        self.label.setObjectName("label")
        self.gridLayout.addWidget(self.label, 0, 0, 1, 1)
        self.label_2 = QtWidgets.QLabel(self.gridLayoutWidget)
        self.label_2.setObjectName("label_2")
        self.gridLayout.addWidget(self.label_2, 1, 0, 1, 1)
        self.pushButton = QtWidgets.QPushButton(self.gridLayoutWidget)
        self.pushButton.setObjectName("pushButton")
        self.pushButton.clicked.connect(self.onButtonClicked)
        self.gridLayout.addWidget(self.pushButton, 4, 1, 1, 1)
        self.setCentralWidget(self.centralwidget)
        self.menubar = QtWidgets.QMenuBar(self)
        self.menubar.setGeometry(QtCore.QRect(0, 0, 614, 26))
        self.menubar.setObjectName("menubar")
        self.setMenuBar(self.menubar)
        self.statusbar = QtWidgets.QStatusBar(self)
        self.statusbar.setObjectName("statusbar")
        self.setStatusBar(self.statusbar)

        self.textEdit_map.setPlaceholderText("1")
        self.textEdit_algorithm.setPlaceholderText("1")
        self.textEdit_people.setPlaceholderText("400")
        self.textEdit_car.setPlaceholderText("30")

        self.retranslateUi(self)
        QtCore.QMetaObject.connectSlotsByName(self)

    #그리드맵 ui로 전환
    def onButtonClicked(self):
        #알고리즘 번호 가져오기 1~4번까지
        a = self.textEdit_people.toPlainText()
        b = self.textEdit_car.toPlainText()
        c = self.textEdit_map.toPlainText()
        if self.textEdit_algorithm.toPlainText() == "1":
            win = SubWindow(a,b,c)
            r = win.showModal()
            if r:
                text = win.edit.text()
                self.label.setText(text)
        if self.textEdit_algorithm.toPlainText() == "2":
            print("2")
        if self.textEdit_algorithm.toPlainText() == "3":
            print("3")
        if self.textEdit_algorithm.toPlainText() == "4":
            print("4")


    def show(self):
        super().show()

    def retranslateUi(self, MainWindow):
        _translate = QtCore.QCoreApplication.translate
        MainWindow.setWindowTitle(_translate("MainWindow", "MainWindow"))
        self.label_3.setText(_translate("MainWindow", "차량 수"))
        self.label_4.setText(_translate("MainWindow", "맵 번호"))
        self.label.setText(_translate("MainWindow", "알고리즘 번호"))
        self.label_2.setText(_translate("MainWindow", "사람 수"))
        self.pushButton.setText(_translate("MainWindow", "OK"))

subwindow.py

import sys
import time
from ReadMap import *
from PyQt5.QtWidgets import *
from PyQt5 import QtCore, QtGui, QtWidgets
from create_car_and_customer import create_car_and_customer
from analyze import get_car_travel_length, get_customer_travel_time, get_customer_waiting_time
from analyze import get_car_travel_length, get_customer_travel_time_10, get_customer_waiting_time_10
from route_ver1 import *
from check_map_position_info import *

import random


class SubWindow(QDialog):
    def __init__(self, people_num, car_num, map_num):
        super().__init__()
        self.people_num = people_num
        self.car_num = car_num
        self.map_num = map_num

        readmap = Map(map_num)
        # 모든 맵의 state를 이차원 배열로 저장=> state 는 char로 저장!!

        self.map = readmap.getMap()
        # 비활성화된 맵x,y저장
        self.map2 = readmap.getDialbePoint()
        self.place = readmap.getPlace()

        self.car_list, self.customer_list = create_car_and_customer(int(self.car_num), int(self.people_num), self.map)

        self.initUI()

    def initUI(self):
        # 맵 설정.
        self.hour = 9
        self.min = 0
        self.second = 0
        self.dx = [0, 0, 1, -1]
        self.dy = [1, -1, 0, 0]
        self.mindist = 10

        # 고객 리스트에서 고객 번호 초기화
        self.cus_list_num = 0
        #대기중인 고객 list
        self.wait_cus_list =[]
        self.visited = []

        self.setObjectName("Dialog")
        self.resize(1045, 612)
        self.horizontalLayoutWidget = QtWidgets.QWidget(self)
        self.horizontalLayoutWidget.setGeometry(QtCore.QRect(10, 10, 921, 521))
        self.horizontalLayoutWidget.setObjectName("horizontalLayoutWidget")
        self.horizontalLayout = QtWidgets.QHBoxLayout(self.horizontalLayoutWidget)
        self.horizontalLayout.setContentsMargins(0, 0, 0, 0)
        self.horizontalLayout.setObjectName("horizontalLayout")
        self.gridLayout = QtWidgets.QGridLayout()
        self.gridLayout.setObjectName("gridLayout")
        self.horizontalLayout.addLayout(self.gridLayout)
        self.verticalLayout = QtWidgets.QVBoxLayout()
        self.verticalLayout.setObjectName("verticalLayout")
        self.label = QtWidgets.QLabel(self.horizontalLayoutWidget)
        self.label.setObjectName("label")
        self.verticalLayout.addWidget(self.label)
        self.label_2 = QtWidgets.QLabel(self.horizontalLayoutWidget)
        self.label_2.setObjectName("label_2")
        self.verticalLayout.addWidget(self.label_2)
        self.label_3 = QtWidgets.QLabel(self.horizontalLayoutWidget)
        self.label_3.setObjectName("label_3")
        self.verticalLayout.addWidget(self.label_3)
        self.label_4 = QtWidgets.QLabel(self.horizontalLayoutWidget)
        self.label_4.setObjectName("label_4")
        self.verticalLayout.addWidget(self.label_4)
        self.label_5 = QtWidgets.QLabel(self.horizontalLayoutWidget)
        self.label_5.setObjectName("label_5")
        self.verticalLayout.addWidget(self.label_5)


        self.pushButton = QtWidgets.QPushButton(self.horizontalLayoutWidget)
        self.pushButton.setObjectName("pushButton")
        self.pushButton.clicked.connect(self.plus1)
        self.verticalLayout.addWidget(self.pushButton)

        self.pushButton_2 = QtWidgets.QPushButton(self.horizontalLayoutWidget)
        self.pushButton_2.setObjectName("pushButton_2")
        self.pushButton_2.clicked.connect(self.plus2)
        self.verticalLayout.addWidget(self.pushButton_2)

        self.pushButton_3 = QtWidgets.QPushButton(self.horizontalLayoutWidget)
        self.pushButton_3.setObjectName("pushButton_3")
        self.pushButton_3.clicked.connect(self.plus3)
        self.verticalLayout.addWidget(self.pushButton_3)

        self.label_6 = QtWidgets.QLabel(self.horizontalLayoutWidget)
        self.label_6.setObjectName("label_6")
        self.verticalLayout.addWidget(self.label_6)

        self.label_7 = QtWidgets.QLabel(self.horizontalLayoutWidget)
        self.label_7.setObjectName("label_7")
        self.verticalLayout.addWidget(self.label_7)

        self.label_8 = QtWidgets.QLabel(self.horizontalLayoutWidget)
        self.label_8.setObjectName("label_8")
        self.verticalLayout.addWidget(self.label_8)

        self.label_9 = QtWidgets.QLabel(self.horizontalLayoutWidget)
        self.label_9.setObjectName("label_9")
        self.verticalLayout.addWidget(self.label_9)

        self.label_10 = QtWidgets.QLabel(self.horizontalLayoutWidget)
        self.label_10.setObjectName("label_10")
        self.verticalLayout.addWidget(self.label_10)

        self.label_11 = QtWidgets.QLabel(self.horizontalLayoutWidget)
        self.label_11.setObjectName("label_11")
        self.verticalLayout.addWidget(self.label_11)

        

        spacerItem = QtWidgets.QSpacerItem(20, 40, QtWidgets.QSizePolicy.Minimum, QtWidgets.QSizePolicy.Expanding)
        self.verticalLayout.addItem(spacerItem)
        self.horizontalLayout.addLayout(self.verticalLayout)

        self.retranslateUi(self)
        QtCore.QMetaObject.connectSlotsByName(self)

        self.buttons = {}
        self.create_map()

    # 시간, 고객 번호 초기화
    def reset_data(self):
        self.hour = 9
        self.min = 0
        self.second = 0
        self.cus_list_num = 0
        self.wait_cus_list.clear()
    # 차량 이동거리 초기화
    def reset_car_data(self):
        for i in range(len(self.car_list)):
            self.car_list[i].set_travel_length(0)

#10회 skip
    def plus3(self):
        scenario_num = 0

        self.reset_data()
        self.reset_car_data()

        for scenario_num in range(10):
            for i in range(28800):
                self.second += 1
                if self.second == 60:
                    self.min += 1
                    self.second = 0
                if self.min == 60:
                    self.hour += 1
                    self.min = 0
                
                #self.label.setText("시간 : " + repr(self.hour) + ":" + repr(self.min) + ":" + repr(self.second))
                # 고객 위치 표시 함수
                self.set_cus_position(scenario_num)
                # 차량 이동 함수
                self.moving_car(scenario_num)
            
            self.reset_data()

        # 시간 계산 및 표시
        self.calc_time_10()

# 1회 skip
    def plus2(self):
        scenario_num = 0

        self.reset_data()
        self.reset_car_data()


        for i in range(28800):
            self.second += 1
            if self.second == 60:
                self.min += 1
                self.second = 0
            if self.min == 60:
                self.hour += 1
                self.min = 0

            #self.label.setText("시간 : " + repr(self.hour) + ":" + repr(self.min) + ":" + repr(self.second))
            # 고객 위치 표시 함수
            self.set_cus_position(scenario_num)
            # 차량 이동 함수
            self.moving_car(scenario_num)
            # 시간 계산 및 표시
        self.calc_time(scenario_num)
    # 시간 + 1
    def plus1(self):
       
        self.second += 1
        if self.second == 60:
            self.min += 1
            self.second = 0
        if self.min == 60:
            self.hour += 1
            self.min = 0
        self.label.setText("시간 : " + repr(self.hour) + ":" + repr(self.min) + ":" + repr(self.second))

        # 고객 위치 표시 함수
        scenario_num = 0
        self.set_cus_position(scenario_num)
        # 차량 이동 함수
        self.moving_car(scenario_num)
        # 시간 계산 및 표시
        self.calc_time(scenario_num)
        print(self.customer_list[0][self.cus_list_num].get_time())

    def find_near_car(self, from_x, from_y):
        min_dist = 3
        carinf = []
        near_car_number_list = []

        # t점의 weight 와 state를 받아온다.
        def getmapinfo(x, y):
            return 1, int(self.map[x][y])

        # 재귀함수, count = weight합   xy = 현재 검색위치.
        def bfs(count, x, y):
            if (count > min_dist):
                return 0
            if self.map[x][y] == "3":
                carinf.append(str(x) + "," + str(y))
                return 1
            # 4방향 탐색. 위 아래 오른쪽 왼쪽
            for i in range(4):
                nx = x + self.dx[i]
                ny = y + self.dy[i]
                # nx,ny가 맵 안에 있고 방문 했던 곳이 아닐 때, 재귀로 방문.
                if nx >= 0 and nx < 15 and ny >= 0 and ny < 20:
                    if self.visited[nx][ny] == False:
                        # 벽일 때, continue
                        if self.map[nx][ny] == "0":
                            continue
                        self.visited[nx][ny] = True
                        if bfs(count + 1, nx, ny):
                            return 1
                        self.visited[nx][ny] = False

        bfs(0, from_x, from_y)
        # 중복제거. set사용
        carinf = list(set(carinf))
        # print(carinf)

        # 가까운 차량 번호 찾기
        if (len(carinf) > 0):
            # 찾은 차량 좌표 리스트에서 첫번째 차량의 번호를 찾음
            position_xy = carinf[0].split(',')
            position_x = int(position_xy[0])
            position_y = int(position_xy[1])
            for i in range(len(self.car_list)):
                if (position_x == self.car_list[i].get_position_x()
                        and position_y == self.car_list[i].get_position_y()
                        and self.car_list[i].get_state() == 1):
                    near_car_number_list.append(self.car_list[i].get_car_num())

            # 리스트인 이유: 같은 위치에 차량 여러대일수있음
            #print("가까운차 번호 리스트 ", near_car_number_list)
            
            return near_car_number_list
        else:
            dummy = []
            return dummy

    # 차량 위치 설정 함수
    def set_car_position(self):
        # 초기 차량 위치 생성
        for i in range(len(self.car_list)):
            self.car_here(self.car_list[i].get_position_x(), self.car_list[i].get_position_y())

    # 고객 위치 설정 함수
    def set_cus_position(self, scenario_num):
        call_list = []
        # 0번 고객 리스트 ui에 표시
        if self.cus_list_num < int(self.people_num) :
            self.a, self.b, self.c = self.customer_list[scenario_num][self.cus_list_num].get_time()
            # customer_list[시나리오][고객 번호]의 시간이 현재 시간과 같을 떄,
            if (    self.a == self.hour
                and self.b == self.min 
                and self.c == self.second ):
                cus_x, cus_y = self.customer_list[scenario_num][self.cus_list_num].get_start_position()
                #고객 grid에 표시.
                self.person_here(cus_x, cus_y)
                call_list = self.find_near_car(cus_x, cus_y)
                #근처 차량 존재2
                if len(call_list) != 0:
                    print("")
                    print("고객 번호", self.cus_list_num)
                    print("호출 시각", self.customer_list[scenario_num][self.cus_list_num].get_time())
                    print("고객 출발", self.customer_list[scenario_num][self.cus_list_num].get_start_position(),
                     "고객 도착", self.customer_list[scenario_num][self.cus_list_num].get_dest_position(),
                     "차량 위치",  self.car_list[call_list[0]].get_position_x(), self.car_list[call_list[0]].get_position_y())
                    print("가까운 차량 번호 ", call_list[0])
                   
                    route = find_route(self.place, self.car_list[call_list[0]].get_position_x(), self.car_list[call_list[0]].get_position_y(),
                                    cus_x, cus_y)
                    
                    del route[0]
                    #call_list[0] => 제일 가까운 차량 번호
                    self.car_list[call_list[0]].set_route(route)

                    self.car_list[call_list[0]].set_state(2)
                    #사람 한명만 받도록 설계, 추후 수정 필요.
                    dummy = []
                    dummy.append(self.customer_list[scenario_num][self.cus_list_num].get_cus_num())
                    self.car_list[call_list[0]].set_cus_num_list(dummy)
                #근처차량 없을 때, 고객 번호를 대기열에 추가.
                elif len(call_list) == 0:
                    self.empty(cus_x, cus_y)
                    self.wait_cus_list.append(self.cus_list_num)
                self.cus_list_num += 1

    # 맵 생성
    def create_map(self):
        temp2 = "border-color: rgb(0, 0, 0); border-width : 1.2px; border-style:inset;"
        for i in range(15):
            v = []
            for j in range(20):
                v.append(False)
                temp1 = ""
                if self.map[i][j] == "0":
                    temp1 = "background-color: rgb(222, 104, 104);"
                else:
                    temp1 = "background-color: rgb(200, 200, 200);"
                self.buttons[(i, j)] = QtWidgets.QLabel('%s' % self.map[i][j])
                self.buttons[(i, j)].setStyleSheet(temp1 + temp2)  # buttons의 색깔을 변환해준다.
                self.gridLayout.addWidget(self.buttons[(i, j)], i, j)
            self.visited.append(v)

        # 초기 차량 위치 표시
        self.set_car_position()

    # 맵 상태 변화
    # 활성화된 지역에 차나 사람이 없는 경우
    def empty(self, x, y):
        self.buttons[(x, y)].setStyleSheet("border-color: rgb(0, 0, 0); border-width : 1.2px; border-style:inset; background-color: rgb(200, 200, 200);")
        self.map[x][y] = "1"
        self.buttons[(x, y)].setText("%d" % 1)

    # 사람이 있을 때
    def person_here(self, x, y):
        self.buttons[(x, y)].setStyleSheet("border-color: rgb(0, 0, 0); border-width : 1.2px; border-style:inset; background-color: rgb(150, 255, 150);")
        self.map[x][y] = "2"
        self.buttons[(x, y)].setText("%d" % 2)

    # 차가 있을 때
    def car_here(self, x, y):
        self.buttons[(x, y)].setStyleSheet("border-color: rgb(0, 0, 0); border-width : 1.2px; border-style:inset; background-color: rgb(255, 255, 0);")
        self.map[x][y] = "3"
        self.buttons[(x, y)].setText("%d" % 3)

    # 사람을 태운 차가 있을 때
    def car_and_person_here(self, x, y):
        self.buttons[(x, y)].setStyleSheet("border-color: rgb(0, 0, 0); border-width : 1.2px; border-style:inset; background-color: rgb(0, 255, 150);")
        self.map[x][y] = "4"
        self.buttons[(x, y)].setText("%d" % 4)

    # 현재까지 서비스를 이용한 사람 및 차량의 이동거리 / 시간을 계산
    def calc_time(self, scenario_num):
        self.label_6.setText("차량 총 이동 거리 : " + repr(get_car_travel_length(self.car_list)))
        self.label_7.setText("고객 평균 대기 시간 : " + repr(get_customer_waiting_time(self.customer_list[scenario_num])))
        self.label_8.setText("고객 평균 이동 시간 : " + repr(get_customer_travel_time(self.customer_list[scenario_num])))

    def calc_time_10(self):
      
        self.label_9.setText("차량 총 이동 거리 : " + repr(get_car_travel_length(self.car_list)))
        self.label_10.setText("고객 평균 대기 시간 : " + repr(get_customer_waiting_time_10(self.customer_list)))
        self.label_11.setText("고객 평균 이동 시간 : " + repr(get_customer_travel_time_10(self.customer_list)))

    # 움직이는 차량 위치정보 그리드맵에 표시(움직이지 않는 차량 제외)
    def moving_car(self, scenario_num):

        for i in range(len(self.car_list)):
            #차량이 대기중이 아니고 움직이는 state일 때,
            if self.car_list[i].get_state() != 1:
                self.car_list[i].set_count(self.car_list[i].get_count() + 1)
                #이동경로 []로 받아옴.
                car_route = self.car_list[i].get_route()
                #이동경로가 남아 있을 때,
                if len(car_route) != 0:
                    temp_dest = car_route[0].split(',')
                    temp_x = int(temp_dest[0])
                    temp_y = int(temp_dest[1])
                    temp_state =0
                    pos_x = self.car_list[i].get_position_x()
                    pos_y = self.car_list[i].get_position_y()
                    self.car_list[i].set_position_x(temp_x)
                    self.car_list[i].set_position_y(temp_y)

                    cur_people_num = self.car_list[i]
                    for wait_cus in self.wait_cus_list:
                        #이동 하기 전, 주변에 대기중인 고객이 있다면
                        if abs(self.customer_list[0][wait_cus].get_start_position()[0]-pos_x) + abs(self.customer_list[0][wait_cus].get_start_position()[1]-pos_y) < 2:
                            #탑승 하는 사람 수가 조건 충족할 때,
                            if self.customer_list[0][wait_cus].get_people_num() <= self.car_list[i].get_people_num():
                                #목적지 거리가 근처일 때,
                                if abs(self.customer_list[0][wait_cus].get_dest_position()[0] - self.customer_list[0][self.car_list[i].get_cus_num_list()].get_dest_position()[0]) + abs(self.customer_list[0][wait_cus].get_dest_position()[1] - self.customer_list[0][self.car_list[i].get_cus_num_list()].get_dest_position()[1])<3:
                                    #사람 수 만큼 추가
                                    self.car_list[i].set_people_num(cur_people_num+self.customer_list[0][wait_cus].get_people_num())
                                    #차량 route 조정.
                                    temp_state =1
                                    print("근처 존재")


                    #움직이기 이전 현재 위치 list참조해서 초기화.
                    if check_map_position_info(pos_x, pos_y, self.car_list, self.customer_list[scenario_num]) == 0:
                        self.empty(pos_x, pos_y)
                    elif check_map_position_info(pos_x, pos_y, self.car_list,
                                                 self.customer_list[scenario_num]) == 1:
                        self.car_here(pos_x, pos_y)
                    elif check_map_position_info(pos_x, pos_y, self.car_list,
                                                 self.customer_list[scenario_num]) == 2:
                        self.person_here(pos_x, pos_y)

                    cus_num_list = self.car_list[i].get_cus_num_list()
                    cus_num = cus_num_list[0]

                    # 차가 고객에게 이동중
                    if self.car_list[i].get_state() == 2:
                        # waiting time cal
                        self.customer_list[scenario_num][cus_num].set_waiting_time(
                            self.customer_list[scenario_num][cus_num].get_waiting_time()
                            + self.car_list[i].get_count())
                        self.car_here(temp_x, temp_y)
                    # 차가 사람을 태우고 이동하는 경우
                    elif self.car_list[i].get_state() == 3:
                        # travel time
                        self.customer_list[scenario_num][cus_num].set_travel_time(
                            self.customer_list[scenario_num][cus_num].get_travel_time()
                            + self.car_list[i].get_count())
                        self.car_and_person_here(temp_x,temp_y)



                    del car_route[0]
                    self.car_list[i].set_route(car_route)
                    #self.car_list[i].set_count(0)
                    self.car_list[i].set_travel_length(self.car_list[i].get_travel_length() + 1)

                else :
                    if self.car_list[i].get_state() == 2:
                        cus_num_list = self.car_list[i].get_cus_num_list()
                        cus_num = cus_num_list[0]
                        start_x = self.car_list[i].get_position_x()
                        start_y = self.car_list[i].get_position_y()
                        dest_x, dest_y = self.customer_list[scenario_num][cus_num].get_dest_position()
                        new_route = find_route(self.place, start_x, start_y, dest_x, dest_y)
                        del new_route[0]
                        self.car_list[i].set_route(new_route)
                        self.car_list[i].set_state(3)
                        self.customer_list[scenario_num][cus_num].set_state(2)

                    elif self.car_list[i].get_state() == 3:
                        cus_num_list = self.car_list[i].get_cus_num_list()
                        cus_num = cus_num_list.pop(0)
                        dest_x, dest_y = self.customer_list[scenario_num][cus_num].get_dest_position()
                        self.car_list[i].set_state(1)
                        self.car_here(self.car_list[i].get_position_x(), self.car_list[i].get_position_y())
                        self.customer_list[scenario_num][cus_num].set_state(3)
                        # print(cus_num, "번 고객 도착 : ", dest_x, dest_y)
                        # print("")


    def retranslateUi(self, Dialog):
        _translate = QtCore.QCoreApplication.translate
        Dialog.setWindowTitle(_translate("Dialog", "Dialog"))
        self.label.setText(_translate("Dialog", "시간 : 9:0:0"))
        self.label_2.setText(_translate("Dialog", "알고리즘 : 다익스트라&bfs"))
        self.label_3.setText(_translate("Dialog", "사람 수 : " + self.people_num))
        self.label_4.setText(_translate("Dialog", "차량 수 : " + self.car_num))
        self.label_5.setText(_translate("Dialog", "맵 번호 : " + self.map_num))
        
        self.pushButton.setText(_translate("Dialog", "시간 + 1"))
        self.pushButton_2.setText(_translate("Dialog", "skip"))
        self.pushButton_3.setText(_translate("Dialog", "10 skip"))

        self.label_6.setText(_translate("Dialog", "차량 총 이동 거리 : 0"))
        self.label_7.setText(_translate("Dialog", "고객 평균 대기 시간 : 0"))
        self.label_8.setText(_translate("Dialog", "고객 평균 이동 시간 : 0"))

        self.label_9.setText(_translate("Dialog", "10회 분석 - 차량 총 이동 거리 : 0"))
        self.label_10.setText(_translate("Dialog", "10회 분석 - 고객 평균 대기 시간 : 0"))
        self.label_11.setText(_translate("Dialog", "10회 분석 - 고객 평균 이동 시간 : 0"))

    def showModal(self):
        return super().exec_()

analze.py

def get_customer_waiting_time(customers):

    avg_waiting_time = 0
    count = 0

    for i in range(len(customers)):
        if customers[i].get_state() == 3:
        # if customers[i].get_waiting_time() > 0 :
            avg_waiting_time += customers[i].get_waiting_time()
            count += 1

    if count != 0 :
        avg_waiting_time /= count
        return avg_waiting_time
    else :
        return 0


def get_customer_travel_time(customers):

    avg_travel_time = 0
    count = 0

    for i in range(len(customers)):
        if customers[i].get_state() == 3:
            avg_travel_time += customers[i].get_travel_time()
            count += 1


    if count != 0 :
        avg_travel_time /= count
        return avg_travel_time
    else :
        return 0


def get_car_travel_length(cars):

    car_travel_length = 0
    
    for i in range(len(cars)):
        car_travel_length += cars[i].get_travel_length()

    return car_travel_length



####################################
# 10회 계산



def get_customer_waiting_time_10(customers):
    
    avg_waiting_time_list =  []
    avg_waiting_time = 0

    for i in range(10):
       avg_waiting_time_list.append(get_customer_waiting_time(customers[i]))

    for i in range(10):
        avg_waiting_time += avg_waiting_time_list[i]

    avg_waiting_time /= len(avg_waiting_time_list)

    return avg_waiting_time


def get_customer_travel_time_10(customers):

    avg_travel_time_list =  []
    avg_travel_time = 0

    for i in range(10):
        avg_travel_time_list.append(get_customer_travel_time(customers[i]))

    for i in range(10):
        avg_travel_time += avg_travel_time_list[i]

    avg_travel_time /= len(avg_travel_time_list)

    return avg_travel_time






#차의 총 이동거리 사용 예제
#print(get_car_travel_length(cars))

#고객 평균 대시시간 사용 예제
#customers[2][3].set_waiting_time(450)
#print(get_customer_waiting_time(customers[2]))

car_class.py

import random

#차량 class (택시)
class Car:
    def __init__(self, car_num, position_x, position_y, people_num, state, cus_num_list):
        self.car_num = car_num        #차량 번호
        self.position_x = position_x  #차량 위치 x
        self.position_y = position_y  #차량 위치 y
        self.people_num = people_num  #차량 탑승 인원 (운전자 제외 최대 4명)
        self.state = state            #차량 상태  (차량 대기중 : 1 / 고객에게 이동 중 : 2 / 고객 탑승 중 : 3)
        self.cus_num_list = []        #차량 탑승 고객 번호 리스트
        self.dest_x = -1              #목적지 위치 x
        self.dest_y = -1              #목적지 위치 y
        self.route = []
        self.count = 0
        self.travel_length = 0        #차 이동 길이

    def get_car_num(self):
        return self.car_num

    def get_position_x(self):
        return self.position_x

    def get_position_y(self):
        return self.position_y

    def get_people_num(self):
        return self.people_num
    
    def get_state(self):
        return self.state

    def get_cus_num_list(self):
        return self.cus_num_list

    def get_dest_x(self):
        return self.dest_x

    def get_dest_y(self):
        return self.dest_y

    def get_route(self):
        return self.route

    def get_count(self):
        return self.count

    def get_travel_length(self):
        return self.travel_length

    # 차량 상태  / 차량 대기중 : 1 / 고객에게 이동 중 : 2 / 고객 탑승 중 : 3
    def set_state(self, state):
        self.state = state

    # 차량에 탑승한 인원
    def set_people_num(self, people_num):
        self.people_num = people_num

    # 차량위치 x
    def set_position_x(self, position_x):
        self.position_x = position_x

    # 차량위치 y
    def set_position_y(self, position_y):
        self.position_y = position_y

    # 차량에 탑승한 고객 정보 / list로 표현(여려명이 탑승한 경우가 있으므로)
    def set_cus_num_list(self, cus_num_list):
        self.cus_num_list = cus_num_list

    # 목적지위치 x
    def set_dest_x(self, dest_x):
        self.dest_x = dest_x

    # 목적지위치 y
    def set_dest_y(self, dest_y):
        self.dest_y = dest_y

    def set_route(self, route):
        self.route = route

    def set_count(self, count):
        self.count = count
    
    #차의 총 이동 길이
    def set_travel_length(self, travel_length):
        self.travel_length = travel_length



def create_car_list(total_car_num, map_info):
    
    cars = []

    map_block_list = []
    for x in range(len(map_info)):
        for y in range(len(map_info[0])):
            if(map_info[x][y] == "0"):
                map_block_list.append([x,y])

    #print(map_block_list)

    for car_num in range(total_car_num):
        position_x, position_y, people_num, state, cus_num_list = random_car(map_block_list)
        cars.append(Car(car_num, position_x, position_y, people_num, state, cus_num_list))
        

    # 결과출력 테스트용 함수
    result_out(cars)


    return cars

    
#랜덤한 차량 정보 생성
def random_car(map_block_list):
    position_x = random.randrange(0, 15)
    position_y = random.randrange(0, 20)
    people_num = 0
    state = 1
    cus_num_list = []

    # 맵에 없는 위치에 생성시 재생성(출발지, 도착지 모두 맵에 가능한 곳만 생성)
    check = 0
    while (check == 0):
        temp = 0
        for i in range(len(map_block_list)):
            if ((position_x == map_block_list[i][0]) and (position_y == map_block_list[i][1])):
                temp = 1
                
        if temp == 1:
            position_x = random.randrange(0, 15)
            position_y = random.randrange(0, 20)
    
        if temp == 0:
            check = 1

              
 
    return position_x, position_y, people_num, state, cus_num_list


#결과 출력 테스트
def result_out(cars):
    if __name__ == "__main__":
        i = 0
        print("car_num    position_x    position_y    people_num    state    cus_num_list")
        while i < len(cars) :
            print('%-11s%-14s%-14s%-14s%-12s%-12s' % (cars[i].get_car_num(), 
            cars[i].get_position_x(), cars[i].get_position_y(), cars[i].get_people_num(), cars[i].get_state(),
            cars[i].get_cus_num_list()))
            i += 1



# test

#map_info = [["0","0","0","0","0","0","0","0","0","0"],
#            ["0","0","0","0","0","0","0","0","0","0"],
#            ["0","0","0","0","0","0","0","0","0","0"],
#            ["0","0","0","0","0","0","0","0","0","0"],
#            ["0","0","0","0","0","0","0","0","0","0"],
#            ["0","0","0","0","0","0","0","0","0","0"],
#            ["0","0","0","0","0","0","0","0","0","0"],
#            ["0","0","0","0","0","0","0","0","0","0"],
#            ["0","0","0","0","0","0","0","0","0","0"],
#            ["0","0","0","0","0","0","0","0","0","0"],
#            ["0","0","0","0","0","0","0","0","0","0"]]

#car_list = create_car_list(30, map_info)




#사용 방법 
# 다른 py 파일에서 
# from car_class import create_car_list 
# create_car_list(30) 과 같이 원하는 차량 수를 입력해준다.

customer_class.py

import random

#고객 class
class Customer:
    def __init__(self, cus_num, start_x, start_y, dest_x, dest_y, share, people_num, hour, minute, second, state):
        self.cus_num = cus_num                  #고객 번호
        self.start_x = start_x                  #고객 출발 위치 x
        self.start_y = start_y                  #고객 출발 위치 y
        self.dest_x = dest_x                    #고객 도착 위치 x
        self.dest_y = dest_y                    #고객 도착 위치 y
        self.share = share                      #고객 합승 여부 (0, 1) 0 : 합승불가 1 : 합승 가능
        self.people_num = people_num            #고객 탑승 인원 (1 ~ 4)
        self.hour = hour                        #호출 시간
        self.minute = minute                    #호출 시간
        self.second = second                    #호출 시간
        self.state = state                      #고객 상태 (차량 대기중 : 1 / 차량 탑승 후 이동 중 : 2 / 도착 완료 : 3)
        self.waiting_time = 0                   #고객 대기 시간 (차량 호출 후 차에 탑승하기까지 시간)
        self.travel_time = 0                    #고객 이동 시간 (차에 타고 있는 시간 / 출발지에서 목적지까지 가는 시간)
        self.car_num = -1                       #고객이 탑승한 차량 번호
        
    def get_cus_num(self):
        return self.cus_num
    def get_start_position(self):
        return self.start_x, self.start_y
    def get_dest_position(self):
        return self.dest_x, self.dest_y
    
    def get_share(self):
        return self.share
    
    def get_people_num(self):
        return self.people_num

    def get_time(self):
        return self.hour, self.minute, self.second
    
    def get_state(self):
        return self.state

    def get_waiting_time(self):
        return self.waiting_time

    def get_car_num(self):
        return self.car_num
    
    def get_travel_time(self):
        return self.travel_time

    # 고객 생태  / 차량 대기중 : 1 / 차량 탑승 후 이동 중 : 2 / 도착 완료 : 3
    def set_state(self, state):
        self.state = state

    # 고객이 차량 호출 후 탑승까지 기다리는 대기시간
    def set_waiting_time(self, waiting_time):
        self.waiting_time = waiting_time

    # 고객이 차량 탑승 후 출발지에서 목적지까지 가는 시간
    def set_travel_time(self, travel_time):
        self.travel_time = travel_time

    # 고객이 탑승한 차량 번호
    def set_car_num(self, car_num):
        self.car_num = car_num

    # 고객 정렬 후 고객 번호 변경을 위해 필요
    def set_cus_num(self, cus_num):
        self.cus_num = cus_num
    
    def set_time(self, h, m, s):
        self.hour = h
        self.minute = m
        self.second = s



#고객 발생 시나리오
def create_call_scenario(total_cus_num, map_info):

    customers = []
    cus_num = 0
    state = 0

    map_block_list = []
    for x in range(len(map_info)):
        for y in range(len(map_info[0])):
            if(map_info[x][y] == "0"):
                map_block_list.append([x,y])


    # 랜덤 고객 생성
    for i in range(total_cus_num):
        hour = random.randrange(9, 17)
        minute = random.randrange(0, 60)
        second = random.randrange(0, 60)
        start_x, start_y, dest_x, dest_y, share, people_num = random_customer(map_block_list)
        customers.append(Customer(cus_num, start_x, start_y, dest_x, dest_y, share, people_num, hour, minute, second, state))
        cus_num += 1
    #end for

   
    #시간 기준으로 고객 정렬
    sorted_cus_list = sorted(customers, key= lambda x : (x.hour, x.minute, x.second))
    
    #같은 시각에 호출하는 고객 생성 x
    temp_check = 0
    while(temp_check == 0):
        temp = 0
        for i in range(total_cus_num-1):
            temp_h, temp_m, temp_s = sorted_cus_list[i].get_time()
            h, m, s = sorted_cus_list[i+1].get_time()
            if temp_h == h and temp_m == m and temp_s == s :
                temp = 1
                hour = random.randrange(9, 17)
                minute = random.randrange(0, 60)
                second = random.randrange(0, 60)
                sorted_cus_list[i+1].set_time(hour, minute, second)

        if temp == 0:
            temp_check = 1

    #시간 기준으로 고객 정렬
    sorted_cus_list = sorted(customers, key= lambda x : (x.hour, x.minute, x.second))

    #고객 번호 정렬
    for i in range(total_cus_num):
        sorted_cus_list[i].set_cus_num(i)



    #결과 출력 (테스트 / 확인용)  
    result_out(sorted_cus_list)
   
    
    return sorted_cus_list


#랜덤한 고객 정보 생성
def random_customer(map_block_list):
    start_x = random.randrange(0, 15)
    start_y = random.randrange(0, 20)
    dest_x = random.randrange(0, 15)
    dest_y = random.randrange(0, 20)
    share = random.randrange(2)

    
    check = 0
    while (check == 0):
        temp = 0
        for i in range(len(map_block_list)):
            if ((start_x == map_block_list[i][0]) and (start_y == map_block_list[i][1])):
                temp = 1
            if ((dest_x == map_block_list[i][0]) and (dest_y == map_block_list[i][1])):
                temp = 2
            if ((dest_x == start_x) and (dest_y == start_y)):
                temp = 3
                            
        if temp == 1:
            start_x = random.randrange(0, 15)
            start_y = random.randrange(0, 20)
        
        if temp == 2:
            dest_x = random.randrange(0, 15)
            dest_y = random.randrange(0, 20)
        
        if temp == 3:
            dest_x = random.randrange(0, 15)
            dest_y = random.randrange(0, 20)
    
        if temp == 0:
            check = 1

  

    #탑승인원 1명 70% / 2명 20% / 3명 10% 확률로 발생
    temp_people_num = random.randrange(1,11)
    if temp_people_num <= 7:
        people_num = 1
    elif 8 <= temp_people_num <= 9:
        people_num =2
    else:
        people_num =3

    return start_x, start_y, dest_x, dest_y, share, people_num

#결과 출력
def result_out(customers):
    if __name__ == "__main__":
        i = 0
        print("고객번호    출발지점    도착지점    합승여부    탑승인원    호출시각      현재상태")
        while i < len(customers) :
            print('%-12s%-12s%-12s%-12s%-12s%-14s%-12s' % (customers[i].get_cus_num(), customers[i].get_start_position(), 
            customers[i].get_dest_position(), customers[i].get_share(),
            customers[i].get_people_num(), customers[i].get_time(), customers[i].get_state()))
            i += 1
        
       


create_call_scenario(400, [[1,2],[3,4]])

#ex) 3번 고객의 호출시각
#print(customer_list[2].get_time())

check_map_position_info.py

# 특정 좌표를 입력하면 해당 좌표에 무엇이 있는지 알려준다.
# 아무것도 없는 경우 0
# 차량이 있는 경우 1
# 고객이 있는 경우 2
# ----------------------------------------------------------
# 사용 방법 ex)
# 다른 py 파일에서 
# from check_map_position_info import check_map_position_info 
# print(check_map_position_info(3,4, car_list, customer_list))
# ----------------------------------------------------------


# input: 좌표 x , 좌표 y, 차량 리스트, 대기중인 고객 리스트
def check_map_position_info(x, y, car_list, customer_list):
    map_state = 0

    # 검색한 위치에 차량이 있는경우
    for i in range(len(car_list)):
        car_x = car_list[i].get_position_x()
        car_y = car_list[i].get_position_y()

        if ((x == car_x) and (y == car_y)):
            map_state = 1

    # 검색한 위치에 대기중인 고객이 있는 경우
    for i in range(len(customer_list)):
        cus_x, cus_y = customer_list[i].get_start_position()

        if ((x == cus_x) and (y == cus_y)) and customer_list[i].get_state() == 1:
            map_state = 2


    #검색한 위치에 아무것도 없는 경우 : 0 / 차량이 있는 경우 : 1 / 대기중인 고객이 있는 경우 : 2
    return map_state

create_car_and_customer.py

from car_class import create_car_list 
from customer_class import create_call_scenario


# 순서대로 입력 (차량 수 , 고객 수 , 맵 정보) 
def create_car_and_customer(total_car_num, total_cus_num, map_info):
    customer_list = []
    car_list = create_car_list(total_car_num, map_info)

    # 각각 다른 고객 시나리오 몇개 생성할 것인지 설정
    for i in range(10):
        customer_list.append(create_call_scenario(total_cus_num, map_info))
    
    return car_list, customer_list


# 사용 방법
#create_car_and_customer(40, 400, 맵 정보)

ReadMap.py

class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def get_x(self):
        return self.x

    def get_y(self):
        return self.y

    def set_x(self,x):
        self.x=x

    def set_y(self,y):
        self.y=y

class Map() :
    def __init__(self, map_num) :
        self.map = []
        self.disable_point = []
        file = open('./' + map_num + ".txt")
        for x in range(15):
            line = file.readline().replace("n",'').split()
            for y in range(len(line)):
                #비활성화일때
                if int(line[y]) == 0:
                    #print(int(line[y]))
                    self.disable_point.append(Point(x,y))
            self.map.append(line)

        self.place = {}
        for i in range(len(self.map)) :
            for j in range(len(self.map[i])) :
                key1 = str(i) + "," + str(j)                        #first key
                state = self.map[i][j]
                if int(state) != 0 :
                    self.place[key1] = {}
                    for k in range(4):
                        if k == 0:
                            if i-1 >= 0:
                                key2 = str(i-1) + "," + str(j)    #second key
                                next_state = self.map[i-1][j]            #check node's state
                                if next_state != "0":
                                    self.place[key1][key2] = 1
                        elif k == 1:
                            if i+1 < len(self.map):
                                key2 = str(i+1) + "," + str(j)    #second key
                                next_state = self.map[i+1][j]            #check node's state
                                if next_state != "0":
                                    self.place[key1][key2] = 1
                        elif k == 2:
                            if j-1 >= 0:
                                key2 = str(i) + "," + str(j-1)    #second key
                                next_state = self.map[i][j-1]            #check node's state
                                if next_state != "0":
                                    self.place[key1][key2] = 1
                        elif k == 3:
                            if j+1 < len(self.map[i]):
                                key2 = str(i) + "," + str(j+1)    #second key
                                next_state = self.map[i][j+1]            #check node's state
                                if next_state != "0":
                                    self.place[key1][key2] = 1

    def getMap(self):
        return self.map

    #비활성화 된
    def getDialbePoint(self):
        return self.disable_point

    def getPlace(self):
        
        return self.place

route_ver1.py

import copy 

# start_x = 1
# start_y = 1
# dest_x = 2
# dest_y =3

# 길찾기
def find_route(place, start_x, start_y, dest_x, dest_y):
    start = str(start_x) + "," + str(start_y)
    dest = str(dest_x) + "," + str(dest_y)

    #dictionary  위치: 가중치
    #이 방식은 맵 정보를 다 저장해둘 필요가 있음
    # place = {
    #     "1,1" : {"1,2":5, "2,1":10},
    #     "1,2" : {"1,3":5 ,"2,1":3, "1,1":1},
    #     "1,3" : {"2,3":3 },
    #     "2,1" : {"2,2":9, "1,1":7,},
    #     "2,2" : {"2,3":3, "1,2":4},
    #     "2,3" : {"1,3":11, "2,2":4},
    # }

    routing = {} 
    for position in place.keys(): 
        routing[position]={"visited":0, "route":[], "shortest_dist":0} 

    # 새로운 위치 방문  
    def visit_place(visit): 
        routing[visit]["visited"] = 1 
        for to_go, between_dist in place[visit].items(): 
            dist = routing[visit]["shortest_dist"] + between_dist 
            if (routing[to_go]["shortest_dist"] >= dist) or not routing[to_go]["route"]: 
                routing[to_go]["shortest_dist"] = dist 
                routing[to_go]["route"] = copy.deepcopy(routing[visit]["route"]) 
                routing[to_go]["route"].append(visit) 

    
    #방문과정
    visit_place(start) 
    while 1 :
        min_dist = max(routing.values(), key=lambda x:x["shortest_dist"])["shortest_dist"] 
        to_visit = ""
        
        #name = key / search = values
        for name, search in routing.items():
            if 0 < search["shortest_dist"] <= min_dist and not search["visited"]: 
                min_dist = search["shortest_dist"] 
                to_visit = name
        if to_visit == "": 
            routing[dest]["route"].append(dest) 
            break 
        
        visit_place(to_visit)
    #
    # if __name__ == "__main__":
    #     print("출발지점 : ", start)
    #     print("도착지점 : ", dest)
    #     print("경로 : ", routing[dest]["route"] )
    #     print("소요시간 : ", routing[dest]["shortest_dist"])

    return routing[dest]["route"]

분석결과

[차량 300대 고정 분석결과]

[고객 500명 고정 분석결과]

#이동 가능한 지도 상의 모든 정보를 담는 place 생성
def setPlace(Ui_Dialog):
    place = {}
    for i in range(Ui_Dialog.size):
        for j in range(15):
            str_key1 = str(i) + "," + str(j)
            str_state = Ui_Dialog.buttons[(i,j)].text().strip('()').split(',')
            if int(str_state[1]) == 1:
                place[str_key1] = {}
                for k in range(Ui_Dialog.size):
                    if k == 0:
                        if i-1 >= 0:
                            str_key2 = str(i-1) + "," + str(j)
                            str_value = Ui_Dialog.buttons[(i-1,j)].text().strip('()').split(',')
                            if int(str_value[1]) == 1:
                                place[str_key1][str_key2] = str_value[0]
                    elif k == 1:
                        if i+1 < Ui_Dialog.size:
                            str_key2 = str(i+1) + "," + str(j)
                            str_value = Ui_Dialog.buttons[(i+1,j)].text().strip('()').split(',')
                            if int(str_value[1]) == 1:
                                place[str_key1][str_key2] = str_value[0]
                    elif k == 2:
                        if j-1 >= 0:
                            str_key2 = str(i) + "," + str(j-1)
                            str_value = Ui_Dialog.buttons[(i,j-1)].text().strip('()').split(',')
                            if int(str_value[1]) == 1:
                                place[str_key1][str_key2] = str_value[0]
                    elif k == 3:
                        if j+1 < Ui_Dialog.size:
                            str_key2 = str(i) + "," + str(j+1)
                            str_value = Ui_Dialog.buttons[(i,j+1)].text().strip('()').split(',')
                            if int(str_value[1]) == 1:
                                place[str_key1][str_key2] = str_value[0]
    print(place)
    return place

남은 것.

1. place에 기존의 위치정보를 변환하여 저장해야한다.

2. routing[dest]["route"].append(dest)가 실행될 때, 이전의 grid맵에 위치표시를 해주어야한다.

3. 택시(state == 3) -> 사용자(state == 2) 로 route_find 실행. 만났을 때, state == 4 로 표시

4. 택시 & 사용자(state == 4) -> 목적지. 완료하면 "고객번호"를 인덱스로(label에 고객번호를 표기해야됨) tableView의 상태를 "1"로 둔다.

import copy

start_x = 1
start_y = 1
dest_x = 2
dest_y = 3


# 길찾기
def find_route(start_x, start_y, dest_x, dest_y):
    start = str(start_x) + "," + str(start_y)
    dest = str(dest_x) + "," + str(dest_y)

    # dictionary  위치: 가중치
    # 이 방식은 맵 정보를 다 저장해둘 필요가 있음
    place = {
        "1,1": {"1,2": 5, "2,1": 10},
        "1,2": {"1,3": 5, "2,1": 3, "1,1": 1},
        "1,3": {"2,3": 3},
        "2,1": {"2,2": 9, "1,1": 7, },
        "2,2": {"2,3": 3, "1,2": 4},
        "2,3": {"1,3": 11, "2,2": 4},
    }

    routing = {}
    for position in place.keys():
        routing[position] = {"visited": 0, "route": [], "shortest_dist": 0}

        # 새로운 위치 방문

    def visit_place(visit):
        routing[visit]["visited"] = 1
        for to_go, between_dist in place[visit].items():
            dist = routing[visit]["shortest_dist"] + between_dist
            if (routing[to_go]["shortest_dist"] >= dist) or not routing[to_go]["route"]:
                routing[to_go]["shortest_dist"] = dist
                routing[to_go]["route"] = copy.deepcopy(routing[visit]["route"])
                routing[to_go]["route"].append(visit)

                # 방문과정

    visit_place(start)
    while 1:
        min_dist = max(routing.values(), key=lambda x: x["shortest_dist"])["shortest_dist"]
        to_visit = ""

        # name = key / search = values
        for name, search in routing.items():
            if 0 < search["shortest_dist"] <= min_dist and not search["visited"]:
                min_dist = search["shortest_dist"]
                to_visit = name
        if to_visit == "":
            routing[dest]["route"].append(dest)
            break

        visit_place(to_visit)

    if __name__ == "__main__":
        print("출발지점 : ", start)
        print("도착지점 : ", dest)
        print("경로 : ", routing[dest]["route"])
        print("소요시간 : ", routing[dest]["shortest_dist"])


find_route(start_x, start_y, dest_x, dest_y)

# -*- coding: utf-8 -*-

# Form implementation generated from reading ui file 'test.ui'
#
# Created by: PyQt5 UI code generator 5.13.0
#
# WARNING! All changes made in this file will be lost!


from PyQt5 import QtCore, QtGui, QtWidgets
import random
from PyQt5.QtWidgets import *
from PyQt5.QtCore import *
from pandas import DataFrame
from PyQt5.QtCore import pyqtSlot
from PyQt5.QtCore import Qt
from PyQt5.QtWidgets import (QWidget, QLCDNumber, QSlider,
QVBoxLayout, QApplication)
from PyQt5.QtWidgets import *
from PyQt5.QtGui import *

#ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
#맵에 Label을 각 좌표마다 넣어 해당 위치정보를 얻을려면 Text를 split으로 해서 알아야 한다. delemmiter = ','
#ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

# 고객 class
class Customer:
    def __init__(self, cus_num, start_x, start_y, dest_x, dest_y, share, people_num, hour, minute, second, state):
        self.cus_num = cus_num
        self.start_x = start_x
        self.start_y = start_y
        self.dest_x = dest_x
        self.dest_y = dest_y
        self.share = share
        self.people_num = people_num
        self.hour = hour
        self.minute = minute
        self.second = second
        self.state = state

    def get_cus_num(self):
        return self.cus_num

    def get_start_position(self):
        return int(float(self.start_x)), int(float(self.start_y))

    def get_dest_position(self):
        return self.dest_x, self.dest_y

    def get_share(self):
        return self.share

    def get_people_num(self):
        return self.people_num

    def get_time(self):
        return self.hour, self.minute, self.second

    def get_state(self):
        return self.state
# 고객 발생 시나리오
def call_scenario(Customer):
    customers = []
    cus_num = 0
    hour = 9
    minute = 0
    second = 0
    state = 0

    # 9시 ~ 5시 랜덤 고객 발생
    for i in range(28800):  # 8시간 = 28800초

        if second == 60:
            minute += 1
            second = 0

        if minute == 60:
            hour += 1
            minute = 0

        if hour == 13:
            hour = 1

        # 9am, 2pm 랜덤 고객 발생
        if (hour == 9 or hour == 2) and (random.randrange(1, 1001) <= 30):
            cus_num += 1
            start_x, start_y, dest_x, dest_y, share, people_num = random_customer()
            customers.append(
                Customer(cus_num, start_x, start_y, dest_x, dest_y, share, people_num, hour, minute, second, state))

        # 10am ~ 1pm, 3pm ~ 5pm 랜덤 고객 발생
        if (hour != 9 and hour != 2) and (random.randrange(1, 1001) <= 10):
            cus_num += 1
            start_x, start_y, dest_x, dest_y, share, people_num = random_customer()
            customers.append(
                Customer(cus_num, start_x, start_y, dest_x, dest_y, share, people_num, hour, minute, second, state))

        second += 1

    # end for

    # 결과 출력


    # 총 8시간 평균 432건
    # 1시간당 평균 36건 / 9시, 2시 시간당 평균 108건
    return customers
# 랜덤한 고객 정보 생성
def random_customer():
    start_x = random.randint(1, 13)
    start_y = random.randint(1, 11)
    dest_x = random.randint(1, 13)
    dest_y = random.randint(1, 11)
    share = random.randrange(2)

    # 탑승인원 1명 70% / 2명 20% / 3명 10% 확률로 발생
    temp_people_num = random.randrange(1, 11)
    if temp_people_num <= 7:
        people_num = 1
    elif 8 <= temp_people_num <= 9:
        people_num = 2
    else:
        people_num = 3

    return start_x, start_y, dest_x, dest_y, share, people_num
#데이터 UI QTableView에 표시모델 dataframe -> QTableView
class pandasModel(QAbstractTableModel):
    def __init__(self, data):
        QAbstractTableModel.__init__(self)
        self._data = data

    def rowCount(self, parent=None):
        return self._data.shape[0]

    def columnCount(self, parnet=None):
        return self._data.shape[1]

    def data(self, index, role=Qt.DisplayRole):
        if index.isValid():
            if role == Qt.DisplayRole:
                return str(self._data.iloc[index.row(), index.column()])
        return None

    def headerData(self, col, orientation, role):
        if orientation == Qt.Horizontal and role == Qt.DisplayRole:
            return self._data.columns[col]
        return None
class Ui_Dialog(QDialog):
    def setupUi(self):
        #맵 크기 설정 및 세팅

        self.size = 15
        self.hour = 9
        self.min = 0
        self.second = 0
        self.personlist = 0 # 사용자가 등록되어 있는 수 count
        self.customer_list = call_scenario(Customer)
        # UI 구성------------------------------------------------------------------------
        Dialog.setObjectName("Dialog")
        Dialog.resize(1401, 555)
        sizePolicy = QtWidgets.QSizePolicy(QtWidgets.QSizePolicy.Ignored, QtWidgets.QSizePolicy.Preferred)
        sizePolicy.setHorizontalStretch(0)
        sizePolicy.setVerticalStretch(0)
        sizePolicy.setHeightForWidth(Dialog.sizePolicy().hasHeightForWidth())
        Dialog.setSizePolicy(sizePolicy)
        self.horizontalLayoutWidget = QtWidgets.QWidget(Dialog)
        self.horizontalLayoutWidget.setGeometry(QtCore.QRect(10, 10, 1401, 531))
        self.horizontalLayoutWidget.setObjectName("horizontalLayoutWidget")
        self.horizontalLayout = QtWidgets.QHBoxLayout(self.horizontalLayoutWidget)
        self.horizontalLayout.setContentsMargins(0, 0, 0, 0)
        self.horizontalLayout.setObjectName("horizontalLayout")
        self.gridLayout = QtWidgets.QGridLayout()
        self.gridLayout.setObjectName("gridLayout")
        self.horizontalLayout.addLayout(self.gridLayout)
        self.verticalLayout = QtWidgets.QVBoxLayout()
        self.verticalLayout.setSizeConstraint(QtWidgets.QLayout.SetDefaultConstraint)
        self.verticalLayout.setObjectName("verticalLayout")
        self.gridLayout_2 = QtWidgets.QGridLayout()
        self.gridLayout_2.setObjectName("gridLayout_2")
        self.label = QtWidgets.QLabel(self.horizontalLayoutWidget)
        self.label.setObjectName("label")
        self.gridLayout_2.addWidget(self.label, 1, 0, 1, 1)
        self.pushButton = QtWidgets.QPushButton(self.horizontalLayoutWidget)
        self.pushButton.setObjectName("pushButton")

        self.gridLayout_2.addWidget(self.pushButton, 0, 1, 1, 1)
        self.label_2 = QtWidgets.QLabel(self.horizontalLayoutWidget)
        self.label_2.setObjectName("label_2")
        self.pushButton.clicked.connect(self.plus1)

        self.gridLayout_2.addWidget(self.label_2, 0, 0, 1, 1)
        self.verticalLayout.addLayout(self.gridLayout_2)
        self.tableView = QtWidgets.QTableView(self.horizontalLayoutWidget)
        self.tableView.setObjectName("tableView")
        #table header구성
        self.df = DataFrame({"고객번호":[],"출발x":[],"출발y":[],"도착x":[],"도착y":[],"합승여부":[],"탑승인원":[],"호출시각":[],"현재상태":[]})
        self.model1 = pandasModel(self.df)
        self.tableView.setModel(self.model1)
        header = self.tableView.horizontalHeader()
        # table header width 설정
        for i in range(9):
            header.setSectionResizeMode(i, QtWidgets.QHeaderView.ResizeToContents)

        self.verticalLayout.addWidget(self.tableView)
        self.horizontalLayout.addLayout(self.verticalLayout)
        self.retranslateUi()
        QtCore.QMetaObject.connectSlotsByName(self)
        # UI 구성------------------------------------------------------------------------

        #buttons은 label들의 list, 위치정보를 텍스트로 담고있다.
        self.buttons = {}
        self.create_map()

    # 지역 비활성화 state = 0
    def deactivate(self, x, y):
        self.buttons[(x, y)].setText("(%d,%d)" % (random.randint(1, 9), 0))
        self.buttons[(x, y)].setStyleSheet(
                "border-color: rgb(0, 0, 0); border-width : 1.2px; border-style:inset;background-color: rgb(222, 104, 104);")

    # 지역에 아무도 없을 때 state = 1
    def empty(self, x, y):
        temp = self.buttons[(x, y)].text().replace("(", "").replace(")", "").split(",")
        self.buttons[(x, y)].setText("(%d,%d)" % (int(temp[0]), 1))
        self.buttons[(x, y)].setStyleSheet(
            "border-color: rgb(0, 0, 0); border-width : 1.2px; border-style:inset;background-color: rgb(200, 200, 200);")

    # 지역에 사람이 있을 때 state = 2
    def person_here(self, x, y):
        self.buttons[(x, y)].setStyleSheet("border-color: rgb(0, 0, 0); border-width : 1.2px; border-style:inset; background-color: rgb(138, 139, 221);")
        temp = self.buttons[(x, y)].text().replace("(", "").replace(")", "").split(",")
        self.buttons[(x, y)].setText("(%d,%d)" % (int(temp[0]),2))

    # 지역에 자동차 있을 때 state = 3
    def car_here(self, x, y):
        self.buttons[(x, y)].setStyleSheet(
                "border-color: rgb(0, 0, 0); border-width : 1.2px; border-style:inset;background-color: rgb(204, 191, 255);")
        temp = self.buttons[(x, y)].text().replace("(", "").replace(")", "").split(",")
        self.buttons[(x, y)].setText("(%d,%d)" % (int(temp[0]), 3))

    #지역에 자동차가 사람을 태웠을 때 state = 4
    def carperson_here(self, x, y):
        self.buttons[(x, y)].setStyleSheet(
                "border-color: rgb(0, 0, 0); border-width : 1.2px; border-style:inset;background-color: rgb(164, 139, 255);")
        temp = self.buttons[(x, y)].text().replace("(", "").replace(")", "").split(",")
        self.buttons[(x, y)].setText("(%d,%d)" % (int(temp[0]), 4))

    def create_map(self):
        temp2 = "border-color: rgb(0, 0, 0); border-width : 1.2px; border-style:inset;"
        for i in range (self.size):
            for j in range (self.size):
                a=1
                temp1 =""
                if a == 0:
                    temp1 = "background-color: rgb(222, 104, 104);"
                else:
                    a=1
                    temp1 = "background-color: rgb(200, 200, 200);"
                self.buttons[(i,j)] = QtWidgets.QLabel('(%d,%d)' % (random.randint(1,9),a))
                self.buttons[(i,j)].setStyleSheet(temp1+temp2) #buttons의 색깔을 변환해준다.
                self.gridLayout.addWidget(self.buttons[(i,j)],i,j)
        #비활성화 위치
        self.deactivate(1, 1)
        self.deactivate(2, 5)
        self.deactivate(4, 5)
        self.deactivate(6, 2)
        self.deactivate(7, 9)

        #자동차 위치
        self.car_here(2, 2)
        self.car_here(3, 8)
        self.car_here(5, 4)

    #1초씩 버튼누를 때 마다 추가.
    def plus1(self):
        self.second += 1
        if self.second == 60:
            self.min += 1
            self.second = 0
        if self.min == 60:
            self.hour += 1
            self.min = 0
        self.label_2.setText("시간 : "+repr(self.hour) +":"+repr(self.min)+":"+repr(self.second))

        self.a,self.b,self.c=self.customer_list[self.personlist].get_time()

        #시간이 생성되어있던 call list와 같을 때
        if self.a == self.hour and self.b == self.min and self.c == self.second:
            d = self.customer_list[self.personlist]
            e, f =d.get_start_position()
            g, h =d.get_dest_position()

            #dataframe에 사용자 추가 및 table에 업데이트
            self.df.loc[self.personlist] = [d.get_cus_num(),e,f,g,h,d.get_share(),d.get_people_num(),repr(self.hour) +":"+repr(self.min)+":"+repr(self.second),d.get_state()]
            self.personlist+=1
            self.model1 = pandasModel(self.df)
            self.tableView.setModel(self.model1)
            #맵에 사용자 위치 표시
            self.person_here(e,f)
    def retranslateUi(self):
        _translate = QtCore.QCoreApplication.translate
        Dialog.setWindowTitle(_translate("Dialog", "Dialog"))
        self.label.setText(_translate("Dialog", "자동차수 : "))
        self.pushButton.setText(_translate("Dialog", "시간 + 1"))
        self.label_2.setText(_translate("Dialog", "시간 : "+repr(self.hour) +":"+repr(self.min)))



if __name__ == "__main__":
    import sys
    app = QtWidgets.QApplication(sys.argv)
    Dialog = QtWidgets.QDialog()
    ui = Ui_Dialog()
    ui.setupUi()
    Dialog.show()
    sys.exit(app.exec_())

시간버튼 누를 시, second 단위로 +1

import random


# 고객 class
class Customer:
    def __init__(self, cus_num, start_x, start_y, dest_x, dest_y, share, people_num, hour, minute, second, state):
        self.cus_num = cus_num
        self.start_x = start_x
        self.start_y = start_y
        self.dest_x = dest_x
        self.dest_y = dest_y
        self.share = share
        self.people_num = people_num
        self.hour = hour
        self.minute = minute
        self.second = second
        self.state = state

    def get_cus_num(self):
        return self.cus_num

    def get_start_position(self):
        return self.start_x, self.start_y

    def get_dest_position(self):
        return self.dest_x, self.dest_y

    def get_share(self):
        return self.share

    def get_people_num(self):
        return self.people_num

    def get_time(self):
        return self.hour, self.minute, self.second

    def get_state(self):
        return self.state


# 고객 발생 시나리오
def call_scenario(Customer):
    customers = []
    cus_num = 0
    hour = 9
    minute = 0
    second = 0
    state = 0

    # 9시 ~ 5시 랜덤 고객 발생
    for i in range(28800):  # 8시간 = 28800초

        if second == 60:
            minute += 1
            second = 0

        if minute == 60:
            hour += 1
            minute = 0

        if hour == 13:
            hour = 1

        # 9am, 2pm 랜덤 고객 발생
        if (hour == 9 or hour == 2) and (random.randrange(1, 1001) <= 30):
            cus_num += 1
            start_x, start_y, dest_x, dest_y, share, people_num = random_customer()
            customers.append(
                Customer(cus_num, start_x, start_y, dest_x, dest_y, share, people_num, hour, minute, second, state))

        # 10am ~ 1pm, 3pm ~ 5pm 랜덤 고객 발생
        if (hour != 9 and hour != 2) and (random.randrange(1, 1001) <= 10):
            cus_num += 1
            start_x, start_y, dest_x, dest_y, share, people_num = random_customer()
            customers.append(
                Customer(cus_num, start_x, start_y, dest_x, dest_y, share, people_num, hour, minute, second, state))

        second += 1

    # end for

    # 결과 출력
    result_out(customers)

    # 총 8시간 평균 432건
    # 1시간당 평균 36건 / 9시, 2시 시간당 평균 108건
    return customers


# 랜덤한 고객 정보 생성
def random_customer():
    start_x = random.randrange(1, 13)
    start_y = random.randrange(1, 11)
    dest_x = random.randrange(1, 13)
    dest_y = random.randrange(1, 11)
    share = random.randrange(2)

    # 탑승인원 1명 70% / 2명 20% / 3명 10% 확률로 발생
    temp_people_num = random.randrange(1, 11)
    if temp_people_num <= 7:
        people_num = 1
    elif 8 <= temp_people_num <= 9:
        people_num = 2
    else:
        people_num = 3

    return start_x, start_y, dest_x, dest_y, share, people_num


# 결과 출력
def result_out(customers):
    if __name__ == "__main__":
        i = 0
        print("고객번호    출발지점    도착지점    합승여부    탑승인원    호출시각      현재상태")
        while i < len(customers):
            print(
                '%-12s%-12s%-12s%-12s%-12s%-14s%-12s' % (customers[i].get_cus_num(), customers[i].get_start_position(),
                                                         customers[i].get_dest_position(), customers[i].get_share(),
                                                         customers[i].get_people_num(), customers[i].get_time(),
                                                         customers[i].get_state()))
            i += 1


# customer_list에 모든 고객 정보 저장(고객번호, 출발지점, 도착지점, 합승여부, 탑승인원, 호출시각, 현재상태(ex) 0 대기 / 1 탑승 중 / 2 완료))
customer_list = call_scenario(Customer)

# ex) 3번 고객의 호출시각
# print(customer_list[2].get_time())

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 역할분담

6.2 개발일정