배달아~ 배달 가는길 알려줘!(단호함)
서론
배민라이더스에서는 배달거리를 업소와 고객의 주소 정보를 이용해서 지구는 적당히(?) 둥글다는 계산으로 거리계산을 하고 있습니다. ~대충대충코드~
double theta = from.getLongitude() - to.getLongitude();
double dist = Math.sin(deg2rad(from.getLatitude())) * Math.sin(deg2rad(to.getLatitude()))
+ Math.cos(deg2rad(from.getLatitude())) * Math.cos(deg2rad(to.getLatitude())) * Math.cos(deg2rad(theta));
dist = Math.acos(dist);
dist = rad2deg(dist);
dist = dist * 60 * 1.1515;
dist = dist * 1.609344 * 1000;
return (long) dist;하지만 이런 경우가 많죠.
산,공원,강이 있는경우는 직선거리와 실제 거리는 큰 차이가 있습니다.
부디 이렇게라도 돌아가는 경로를 계산해보는건 어떨까 했습니다.
꼭 직접 구현 해야 하나요?
네비게이션 api를 사용하면 자동차,자전거,도보를 이용해서 실거리및 경로 안내를 받을 수 있습니다. 하지만, 거리계산은 실시간으로 주문전에 앱에서 요청이 들어오고 배민라이더스만 해도, 최고 분당 최고 12만회를 처리해야합니다. 비용문제와 SLA 문제로 사용할 수도 없습니다.
여기서 뜬금 없는 팀소개
저희 팀은 배민라이더스 주문을 고객에게 전달하기 까지 모든 과정을 처리하는 딜리버리플랫폼팀입니다. 지금 이야기들 들으시고 흥미가 있다면 지원 부탁드려요. https://www.woowahan.com/#/recruit/tech
요구 사항
- 라이더가 업소에서 고객에게 가는 실제와 유사한 경로와 거리계산
- 최대 분당 20만 request 처리
- 평균 응답시간 0.05s 이내
문제를 풀어보자!
첫번째 아이디어
모든 산,강과 갈수 없는 곳을 polygon 으로 그려 직선 우회로를 계산한다.
그걸 언제다 그려? 바로 포기!
두번째 아이디어
라이더가 실제 배달한 GPS좌표를 활용한다. 근 2년동안 라이더가 이동한 기록을 따로 보관만 하고 사용한적은 없었는데, 기록을 잘 정돈하면 실제 배달을 하는 지역에서의 배송 루트가 나오지 않을까 하는 막연한 기대를 해봤습니다. 하지만, 모두 WGS84 좌표일뿐 이걸 길찾기로 바로 사용할수 없습니다.
공간을 단순히
어렸을때 하던 전략시뮬에이션 게임에서 아이디어를 찾았습니다.
하나의 유닛은 6방향으로 이동할수 있고 모든 방향의 거리는 동일합니다. 이렇게 6방향으로 규격화 하면 아주 정확하지는 않지만, 공간에서 공간으로 이동하는 거리를 단순화 할수 있습니다. 실제 라이더가 이동한 거리만 이동할수 있는 계산기를 만들어볼수 있을것 같은 느낌(?)
이미 누군가 다 만들어 놓았음
https://www.redblobgames.com/grids/hexagons/#field-of-view 이미 라이브러리는 여러언어 기반으로 구현되어 있습니다. 이걸 가져다 쓰는걸로 했습니다. 하지만 가져다 쓴다지만 뭐가 뭔지 하나도 몰라서 배워 봤습니다.
hexagon grid
hexagon grid 는 두가지 형태의 좌표 시스템으로 표현할수 있습니다.
- Cube coordinates
- Offset coordinates
Cube coordinates 는 3축 좌표로 좌표마다의 거리 계산이나 범위계산 방향을 계산할때 유리합니다.
Offset coordinates 는 두개의 좌표로 가로나 세로 기준올 x축과 y축의 모델과 유사합니다. 실제 위경도 대입시 직각형태로 구역을 잘라 지도에 grid를 그리는데 유용합니다. 앞서 말한 두개의 좌표는 언제나 변환 가능합니다.
하나의 점은 하나의 offset 좌표로 매칭되고, 또 다른 cube 좌표도 가지게 됩니다. 용도에 맞게 자유롭게 변환하면서 사용됩니다.
https://www.redblobgames.com/grids/hexagons/implementation.html#cube-vs-axial hexagon grid 구현에 해당 링크에 있습니다.
좌표 변환
static public OffsetCoord qoffsetFromCube(Hex h)
{
int col = h.q;
int row = h.r + (int)((h.q + (h.q & 1)) / 2);
return new OffsetCoord(col, row);
}
static public Hex qoffsetToCube(OffsetCoord h)
{
int q = h.col;
int r = h.row - (int)((h.col + (h.col & 1)) / 2);
int s = -q - r;
return new Hex(q, r, s);
}편의 상 Cube는 Hex, Offset 은 Offset로 칭합니다. 다시 말씀드리지만 Hex와 Offset은 서로 변환 가능합니다.
위경도 좌표를 Hex(Cube) 좌표로 변환
위도를 y좌표, 경도로 x좌표로 생각하고, 각각의 hexagon grid에 포함시킬수 있습니다.
Layout
public FractionalHex pixelToHex(Point p)
{
Orientation M = orientation;
Point pt = new Point((p.x - origin.x) / size.x, (p.y - origin.y) / size.y);
double q = M.b0 * pt.x + M.b1 * pt.y;
double r = M.b2 * pt.x + M.b3 * pt.y;
return new FractionalHex(q, r, -q - r);
}
FractionalHex
public FractionalHex(double q, double r, double s) {
this.q = q;
this.r = r;
this.s = s;
if (Math.round(q + r + s) != 0) throw new IllegalArgumentException("q + r + s must be 0");
}
public final double q;
public final double r;
public final double s;
public Hex hexRound() {
int qi = (int) (Math.round(q));
int ri = (int) (Math.round(r));
int si = (int) (Math.round(s));
double q_diff = Math.abs(qi - q);
double r_diff = Math.abs(ri - r);
double s_diff = Math.abs(si - s);
if (q_diff > r_diff && q_diff > s_diff) {
qi = -ri - si;
} else if (r_diff > s_diff) {
ri = -qi - si;
} else {
si = -qi - ri;
}
return new Hex(qi, ri, si);
}사용법
Hex target = layout.pixelToHex(new Point(x, y).hexRound());이렇게 하면 특정 위경도가 어느 Hex 좌표에 해당하는지 알수 있고, Hex 좌표 안에 있는 모든 위경도좌표들은 같은 Hex좌표를 반환합니다. 그래서 hexagon grid를 사용하게 되면 polygon inboud 체크를 위해 polygon 데이터를 꺼내서 찾을 필요가 없습니다.
위도와 경도가 서로 거리가 다른 문제
여기서 문제가 됩니다. 위도와 경도는 서로 간격당 미터(meter)수치가 다릅니다. 위도는 지구가 둥글다고 가정하면 균일한 거리를 가리키지만 경도는 위도에 따른 거리가 다릅니다. http://www.longitudestore.com/how-big-is-one-gps-degree.html
우리는 근거리 배달이니까 지구는 둥글다고 쳐요!
위도에 따른 경도의 거리를 위도 마다 다르게 준다하면 계산식이 매우 복잡함으로, 서울에서 부산까지 배달을 하는 경우는 아니니 서울의 중앙을 잡고, 경도값에 대한 비율을 줍니다.
double rate = 110.574 / (111.320 * Math.cos(37.550396 * Math.PI / 180));
Point center = new Point(126.978955, 37.550396);
Layout layout = new Layout(Layout.pointy, new Point(rate * 0.0001, 0.0001), center);A Star 알고리즘
모든 구역을 hexagon grid로 전환가능하니. 이제 길찾기 알고리즘을 찾아봤습니다. https://www.redblobgames.com/pathfinding/a-star/introduction.html 해당링크는 4방향에 대한 길찾기인데, 6방향으로 고치면 됩니다.
A* 알고리즘 구현 핵심로직만 넣어봤습니다.
PriorityQueue<HexDepth> frontier = new PriorityQueue<>(10000, (o1, o2) -> o1.priority - o2.priority);
frontier.add(new HexDepth(nearStart, 0));
HashMap<Hex, Hex> cameFrom = new HashMap<>(2500);
HashMap<Hex, Integer> costSoFar = new HashMap<>(2500);
cameFrom.put(nearStart, null);
costSoFar.put(nearStart, 0);
HexDepth currentDepth;
while ((currentDepth = frontier.poll()) != null) {
Hex current = currentDepth.hex;
if (current.equals(nearGoal)) {
break;
}
// 6방향
List<Hex> neighbors = new ArrayList<>();
for (Hex direction : Hex.directions) {
Hex neighbor = current.add(direction);
neighbors.add(neighbor);
}
for (Hex next : neighbors) {
int nextHexCost = findHexCost(cacheCosts, bigHexCosts, next);
int newCost = costSoFar.get(current).intValue() + nextHexCost;
Integer nextCost = costSoFar.get(next);
if (nextCost == null || newCost < nextCost.intValue()) {
costSoFar.put(next, newCost);
int priority = newCost + heuristic(nearGoal, next);
frontier.add(new HexDepth(next, priority));
cameFrom.put(next, current);
}
}
}frontier queue 에 나중에 찾을 좌표를 담아두고, costSoFar를 갱신하면서 찾습니다. 이때 heuristic 함수를 써서 목표 지점에 가장 가까운 방향으로 우선순위를 두는데 진행방향이 A의 머리모양이 목표지점으로 향해 A* 알고리즘이라 합니다.(?? 그런가??)
실제 코드는 좀더 최적화 되어 있습니다.
이제 데이터를 모아 봅시다.
길찾기의 가장 중요한것은 어디가 막힌길인가 어디가 갈수 있는 길인가에 대한 데이터가 있어야 합니다. 먼저 계획으로 라이더가 많이 이동한 곳을 거리 비용이 낮은 곳이라 하고, 자주 가지 않는 지역은 비용이 높고, 한번도 가지 않는 길은 매우 높음이라 정합니다.
apache hive를 활용
- aws에는 관리형 하둡 클러스터를 손쉽게 제공합니다. 그래서 바로 emr을 할당받아서 hive를 올려봅니다.
- 라이더 이동경로는 kinesis stream을 통해 HDFS로 저장했다면 좋았을걸, 저장할 생각만하고, dynamodb에 넣었던게 매우 후회가 되네요. hive로 import하는데 5일 걸렸습니다. ㅠㅠㅠㅠ 잘못된 저장공간 선택 .
하지만 이동경로를 세세하게 남기지 못하고, 1분에 한번씩밖에 남기지 못했습니다. 아 정말 과거의 나를 반성합니다. 소중한 데이터를 버렸어요 ㅠㅠㅠㅠ 어쨌든 이거라도 씁니다.
가장 작은 hexagon 크기에 라이더 위치 count를 담는 table을 생성
drop table RiderFoot2;
CREATE TABLE `RiderFoot2`
(
count INT,
col INT,
`row` INT,
col_50x INT,
row_50x INT
);coord_udf는 위경도 좌표를 offset coord로 변환하는 custom function 입니다. 위에서 언급한 라이브러리로 만들었습니다. 모든 공간에 균일한 라이더가 배달을 수행하는것이 아니라 지역마나 count가 모두 다릅니다. 그래서 가장 작은 크기의 hexagon보다 100배가 큰 hexagon을 그려 전체를 그룹화 해서 count의 평균값으로 거리에 대한 cost를 산정해 볼까 합니다.
insert overwrite table RiderFoot2
select
count(*) as count,
x.road_coord.col as col,
x.road_coord.`row` as `row`,
x.big_coord.col as col_50x,
x.big_coord.`row` as row_50x
from (
select
latitude,
longitude,
coord_udf('SIMILAR_WGS84_SEOUL_0_5X', latitude, longitude) as road_coord, -- 우리가 정한 가장 작은 크기의 offset coord 좌표 반환
coord_udf('SIMILAR_WGS84_SEOUL_50X', latitude, longitude) as big_coord -- 모든 공간에 균일한 위치가 찍히는것이 아니기 때문에 커다란 hexagon 으로 다시 그려 group 을 만든다.
from (
select latitude, longitude from (
select
latitude,
longitude
from `tmp_baeminz_rider_footprint` -- 근무중 라이더 위치 정보
) dup
group by latitude, longitude -- 모든 라이더의 위치중 중복된 위치는 제거한다(대부분 같은 위치는 wifi 나 LTE기지국 위치임)
) coord
) x
group by x.big_coord.col, x.big_coord.`row`, x.road_coord.col, x.road_coord.`row`;큰 hexagon 구역당 최소/최대/총/평균 count 데이터를 구성합니다.
drop table RiderFoot3;
CREATE TABLE RiderFoot3
(
col_50x INT,
row_50x INT,
min_count INT,
max_count INT,
sum_count INT,
avg_count INT
);
insert overwrite table RiderFoot3
select
col_50x,
row_50x,
min(count) as min_count,
max(count) as max_count,
sum(count) as sum_count,
avg(count) as avg_count
from RiderFoot2
group by col_50x, row_50x;작은 hexagon 당 총 count 데이터를 구성합니다.
drop table RiderFoot4;
CREATE TABLE RiderFoot4
(
col INT,
`row` INT,
count INT
);
insert overwrite table RiderFoot4
select
col,
`row`,
sum(count) as `count`
from RiderFoot2
group by col, `row`;작은 hexagon의 총 count가 커다른 hexagon 구역에 얼마정도의 수치인지 알기 위해 join을 걸고, 큰 구역의 평균/총/최소/최대값을 참고 할수 있게 합니다.
drop table RiderFoot5;
CREATE TABLE RiderFoot5
(
col INT,
`row` INT,
cnt INT,
avg_count INT,
sum_count INT,
min_count INT,
max_count INT
);
insert overwrite table RiderFoot5
select a.col, a.`row`, sum(a.count) as cnt , avg(b.avg_count), sum(b.sum_count), sum(b.min_count), sum(b.max_count)
from RiderFoot2 as a join RiderFoot3 as b
on (a.col_50x = b.col_50x AND a.row_50x = b.row_50x)
group by col, `row`;마지막으로 a start 알고리즘에서 사용할 hexagon마다의 cost정보를 생성합니다. cost_udf라는 custom function을 사용해서. 구역의 평균값과, 최대값을 사용해서, 최적화된 cost를 생성합니다.(아휴~ 그냥 대충 넣어봤어요)
drop table HexCost;
create table HexCost AS
select 'SIMILAR_WGS84_SEOUL_0_5X' as layout, hex.q, hex.r, hex.s, col, `row`, cost from (
select col, `row`, cost_udf(cnt, avg_count, max_count) as cost, c_h_udf(col, `row`) as hex from RiderFoot5
) x;cost_udf function
public class HexCostUDF extends UDF {
public int evaluate(int cnt, int avg_count, int max_count) {
int cost = 50;
if (avg_count < cnt) {
// 1 ~ 10
cost = 1;
} else if (max_count == avg_count) {
// 최대 와 평균이 일치하면 한곳에 몰린곳이다.
cost = 50;
} else if (avg_count < 2) {
cost = 50;
} else {
cost = (int) Math.round((avg_count - cnt) * (24.0 / avg_count) + 1);
cost = Math.max(2, cost);
cost = Math.min(25, cost);
}
return cost;
}
}HexCost데이터를 받아와서 database로 변환합니다.
insert overwrite local directory '/tmp/HexCost' row format delimited fields terminated by ',' select * from HexCost;이제 적절한 데이터도 생성했으니 지도에 Hex마다 cost를 표시해봅니다.
모든 길이 나오지는 않지만 얼추 큰길은 나옵니다. 아지만 아래와 같이 GPS가 잡하지 않는 곳은 연결이 되지 않습니다.
찾아보니 군데군데 유실한곳이 많기도 하고 아직 라이더가 많이 움직이지 않는 신규지역같은곳은 사용하기가 어렵네요. 그래도 데이터가 존재하면 길찾기는 가능합니다.
세번째 아이디어 도로정보를 보강하자.
길찾기 구현은 다 되어 있지만 데이터를 보강하기로 했습니다. https://www.juso.go.kr/addrlink/devLayerRequestWrite.do 정부에서 도로명주소 데이터를 제공합니다. 신청을 하면 익일 데이터를 내려받을수 있습니다.
편의상 서울특별시 데이터를 참고하겠습니다.
데이터를 시각화
지리정보를 담은 파일을 제공합니다. 해당파정보를 읽을수 있는 툴을 준비합니다. https://qgis.org/ko/site/ 3.4.4버전을 사용해봅니다.
파일중 shx파일을 레이어에 등록하고, 좌표계는 GRS80으로 설정하면 다른 지도와 같이 볼수 있습니다.
데이터 입수
데이터를 시각적으로 확인했으니 서비스에 사용할수 있는 데이터로 변환을 합니다. 대량 파일은 아니라 손쉬은 spring batch를 사용했습니다. shapefile과 관련 dbasefile을 읽기 위해 geotools 라이브러리를 사용했습니다.
설명을 덧붙히면 모든 도로중 자동차 전용도로(전용도로라고 추정된) 도로는 제외하고, 선택된 도로를 WGS84좌표계로 변환후 line을 hex로 모두 변환해서 database에 기록하면 됩니다.
GeometryFactory gf = JTSFactoryFinder.getGeometryFactory();
.....
Set<Hex> hexSet = new HashSet<>();
try {
ShpFiles shpFiles = new ShpFiles(res);
String filename = res.getAbsolutePath();
log.debug("open filename", filename);
shapefileReader = new ShapefileReader(shpFiles, true, true, gf);
dbaseFileReader = new DbaseFileReader(shpFiles, true, Charset.forName("CP949"));
DbaseFileHeader header = dbaseFileReader.getHeader();
int numFields = header.getNumFields();
// 특정 도로는 제외(자동차전용도로)하기 위해 header정보를 얻습니다.
int WDR_RD_CD_FIELD = 0;
for (int iField = 0; iField < numFields; ++iField) {
String fieldName = header.getFieldName(iField);
if ("WDR_RD_CD".equals(fieldName)) {
WDR_RD_CD_FIELD = iField;
break;
}
}
while (shapefileReader.hasNext() && dbaseFileReader.hasNext()) {
ShapefileReader.Record record = shapefileReader.nextRecord();
String WDR_RD_CD = (String) dbaseFileReader.readRow().read(WDR_RD_CD_FIELD);
// 행자부도로는 제외
if ("1".equals(WDR_RD_CD)) {
continue;
}
Object shape = record.shape();
if (shape.getClass().isAssignableFrom(MultiLineString.class)) {
MultiLineString ob = (MultiLineString) shape;
Coordinate[] coordinates = ob.getCoordinates();
List<FractionalHex> path = new ArrayList<>();
for (Coordinate coordinate : coordinates) {
double x = coordinate.x;
double y = coordinate.y;
// WGS84 좌표계로 변환합니다.
double[] transmit = JTSTransformUtils.transmit(gf, x, y);
// 위도 경도
double latitude = transmit[0];
double longitude = transmit[1];
FractionalHex hex = lc.getLayout().pixelToHex(new Point(longitude, latitude));
path.add(hex);
}
// 도로 정보를 from to 직선라인 정보임으로 직선을 Hex로 모두 변환합니다.
FractionalHex prev = null;
for (FractionalHex cur : path) {
if (prev != null) {
ArrayList<Hex> hexes = FractionalHex.hexLinedraw(prev.hexRound(), cur.hexRound());
for (Hex hex : hexes) {
hexSet.add(hex);
}
}
prev = cur;
}
}
}
} catch (IOException e) {
throw new ItemStreamException(e);
}
도로 정보를 기반한 Hex Cost정보를 보여줍니다.
실제 도로를 많이 반영되었네요. 그래서 이전 라이더가 이동한 기록과, 도로 정보를 같이 섞어 봤습니다.
최종결과
최종결과는 실제 예상한 길과는 다른게 가운데 길을 찾아가는 최단 루트를 가리킵니다.
라이더가 이동하기에 완전 최적화된 루트는 아니지만, 도로와 라이더 위치기반으로 직선거리보다는 의미있는 루트를 찾았습니다.
기능은 구현했지만 서비스에 올라가기까지 더 많은 노력을 했습니다. 모든 내용을 하나의 글로 담기에는 너무 많네요. 다음에 소개할 이야기는 기능을 서비스로 올리기 까지 경험한 내용 을 공유하겠습니다.
참고자료