의료택시는 이런 상황입니다. 택시 몇 대가 있고, 어르신 여러 명이 각자 다른 마을에서 다른 병원으로 가야 합니다. 시간도 제각각(9시 예약, 10시 예약…).
여기서 "누가 누구를 태우고, 어떤 순서로 도느냐"를 정하는 게 배차입니다. 아무렇게나 정하면 택시가 빈 채로 이리저리 왔다갔다 하면서 기름·시간을 낭비하죠.
택시 주행은 딱 두 종류로 나뉩니다.
택시는 차고에서 어르신 집까지 빈 차(공차)로 갔다가, 집→병원은 손님을 태우고(실차) 갑니다. 우리가 줄일 수 있는 건 저 주황 점선(공차)뿐입니다.
택시 1대, 어르신 2명이 병원에 갔다 와야 합니다. A는 문막, B는 지정에 삽니다. 진료가 끝나면 집에 돌아가야 하죠.
회송(回送) = 손님을 내려준 택시가 빈 채로 돌아가는 것. 이 빈 주행이 공차의 가장 큰 원인입니다. 체이닝(chaining) = 그 빈 주행을 다른 운행과 사슬처럼 이어붙이는 것.
왜 좋은가? 원래라면 두 번의 빈 주행이 생깁니다 — ①A 내려주고 병원→빈차 복귀, ②B 태우러 다시 빈차로 병원行. 체이닝은 이 둘을 하나로 합쳐 없애버립니다.
| 체이닝 없음 | 체이닝 있음 | |
|---|---|---|
| A 하차 후 | 병원→A동네 빈차 복귀 | 그 자리서 대기 |
| B 태우기 | B동네→병원 빈차 이동 | 바로 B 승차 |
| 공차 | 2구간 낭비 | 0 (사슬로 연결) |
중요 — 이건 '합승'이 아닙니다. A가 내린 뒤에 B를 태웁니다. 차 안에 동시에 두 팀이 타지 않아요(정원=1). 어르신 입장에서 낯선 사람과 합승하는 불편이 전혀 없습니다. 단지 택시의 빈 시간·빈 거리를 이어붙이는 겁니다.
현실 조건도 반영합니다: ① 시각이 맞아야 함(A 하차 ≈ B 진료 종료) ② 같은/가까운 병원이어야 함 ③ 진료가 예정보다 늦어지면 그 사슬은 포기하고 다른 택시로 재배차(그래서 '진료완료' 신호로 확정). 못 맞추면 그냥 일반 배차 — 손해는 없습니다.
손님이 2명이면 눈으로도 풀립니다. 그런데 하루에 수십 명, 택시 여러 대가 되면?
"누구를 어느 택시에, 어떤 순서로" 배정하는 경우의 수가 폭발합니다.
| 손님 수 | 가능한 방문 순서의 수 |
|---|---|
| 3명 | 6가지 |
| 5명 | 120가지 |
| 10명 | 362만 가지 |
| 15명 | 1조 3천억 가지 |
여기에 "택시 여러 대", "시간 약속(9시 예약은 9시까지)", "왕복" 조건까지 붙으면 — 사람이 손으로 최선을 찾는 건 불가능합니다. 이걸 학문적으로 차량경로문제(VRP), 그중 병원 왕복형은 DARP라고 부릅니다.
구글이 만든 무료 최적화 엔진 OR-Tools가 있습니다. 이 폭발하는 경우의 수를 똑똑하게 탐색해서 좋은 답을 빠르게 찾아주는 도구예요. (전 세계 물류회사가 씁니다.)
우리가 할 일은 "문제를 설명해주는 것"뿐입니다. 마치 내비게이션에 목적지만 찍으면 경로는 내비가 계산하듯이요.
| 알려줄 것 | 의미 |
|---|---|
| ① 지점들 | 각 어르신 집·병원의 위치(좌표) |
| ② 시간 약속 | "이 어르신은 9시 예약" → 그 전에 도착 |
| ③ 정원 = 1 | 택시 1대에 1팀만 (억지 합승 금지) |
| ④ 비용 = 거리 | "총 이동거리가 짧을수록 좋다"고 알려줌 |
이 4가지만 넣으면 OR-Tools가 "몇 번 택시가, 누구를, 몇 시에, 어떤 순서로"를 스스로 계산해서 돌려줍니다. 빈차(공차)가 최소가 되도록요.
OR-Tools에게 "총 이동거리를 줄여라"라고만 시켰는데, 왜 공차가 줄어들까요?
총거리 = 실차 + 공차 입니다. 그런데 실차는 못 줄여요(손님은 무조건 집→병원 가야 하니까 고정). 그래서 총거리를 줄이라고 하면, OR-Tools가 건드릴 수 있는 건 공차뿐 → 자연스럽게 빈차 이동을 최소화하는 답(=회송 체이닝을 많이 쓰는 답)을 찾아냅니다.
만약 예약이 너무 많거나 시간이 촉박해서 OR-Tools가 제한시간 안에 최선을 못 찾으면 — 답이 아예 안 나오면 큰일이죠. 그래서 그리디(greedy)라는 간단한 백업 방법을 같이 넣었습니다.
즉 OR-Tools(최선) → 안 되면 그리디(항상 됨) 2단 구조라 서비스가 멈추지 않습니다.
배차 최적화가 어렵다는 건 차량 수천~수만 대 얘기입니다(예: 전국 택배). 우리 의료택시는?
솔직하게 — 딥러닝·자율주행·챗봇은 아닙니다. 우리가 쓰는 AI는 두 가지이고, 둘 다 정통 인공지능 기술입니다.
심사위원이 "이게 왜 AI냐" 물으면: "차량경로 최적화(DARP)는 인공지능·운영과학의 조합최적화 분야이고 구글 OR-Tools로 구현했으며, 귀가시각 예측은 데이터로 학습하는 머신러닝(scikit-learn)입니다." — 최적화 + 학습, 둘 다 있으니 과장 없이 'AI 활용'이 확실합니다.
optimizer.py)
📄 실제 구현 파일: ai_dispatch/app/services/optimizer.py (OR-Tools DARP + 그리디 폴백, DB 없이 순수함수라 단독 테스트 가능). 웹 데모(원주_AI배차_웹데모.html)는 이 원리를 브라우저에서 가볍게 재현한 버전입니다.