K-medoids 알고리즘은 K-means와 유사하지만, 평균값 대신 중앙값을 사용한다는 점에서 차이가 있습니다.
이 알고리즘은 평균값을 해석하기 어려운 실도로 거리 기반의 클러스터링에도 잘 맞기 때문에, 실도로거리를 이용한 문제 해결에 적합합니다.
고객의 위치가 100개로 주어지고, 각 고객의 위/경도 정보를 알고 있는 상황에서, 직선거리가 아닌 실도로 거리를 기반으로 최적의 창고 3개의 위치를 선정하려면, K-medoids 알고리즘을 사용하는 것이 좋습니다. 실도로 거리와 같은 복잡한 거리 계산을 반영하기 위해 Distance Matrix를 활용할 수 있습니다.
저자는 이를 해결하기 위해 다음과 같은 방법을 고려했습니다.
1.
실도로거리 Distance Matrix 사용: 고객 위치 간의 실도로거리를 미리 계산한 Distance Matrix를 사용합니다. 이는 두 지점 간의 실제 거리를 반영하며, 실도로 기반의 최적화 문제를 해결하는 데 매우 유용합니다.
2.
K-medoids 알고리즘 적용: K-medoids 알고리즘을 적용하여 100개의 고객을 3개의 클러스터로 나누고, 각 클러스터의 중앙값(medoid)을 계산합니다. 이 중앙값이 각 클러스터에서 가장 중앙에 위치한 고객의 좌표가 되며, 이를 창고의 위치로 선정할 수 있습니다.
3.
반복적 클러스터링 과정: K-medoids는 반복적으로 클러스터의 중앙값을 업데이트하며, 각 클러스터에 속한 고객들과의 거리를 최소화하는 지점을 찾습니다. 최종적으로, 창고의 위치는 각 클러스터 내에서 실도로 거리가 최소화되는 고객의 위치로 결정됩니다.
전체 소스
import pandas as pd
import folium
from sklearn_extra.cluster import KMedoids
def main():
#Warehouse 갯수
k = 3
restaurantDf, distance = makeInput()
locList = [[0]*2 for i in range(len(restaurantDf))]
for idx, row in restaurantDf.iterrows():
locList[idx][0] = float(row['LAT'])
locList[idx][1] = float(row['LON'])
# fit model
kmed = KMedoids(n_clusters=k, random_state=123, method='pam').fit(distance)
map = folium.Map(location=[37.5666805, 126.9784147])
for i in range(len(restaurantDf)):
color = ""
if kmed.labels_[i] == 0:
color = "red"
if kmed.labels_[i] == 1:
color = "blue"
if kmed.labels_[i] == 2:
color = "orange"
folium.Marker([locList[i][0], locList[i][1]], icon = folium.Icon(color=color)).add_to(map)
#Warehouse Locations
for element in kmed.cluster_centers_:
folium.Marker([element[0], element[1]], icon=folium.Icon(color='gray',icon='star')).add_to(map)
map.save('kmedoidsResult.html')
def makeInput():
restaurant = [
['LOC_0001', '고양시', '37.6699528060', '126.8554585712'],
['LOC_0002', '과천시', '37.4277514160', '126.9920513446'],
['LOC_0003', '광주시', '37.4992915278', '127.3027287142'],
['LOC_0004', '김포시', '37.6598939546', '126.6656656950'],
['LOC_0005', '남양주시', '37.7496438017', '127.2086783633'],
['LOC_0006', '동두천시', '37.9052438433', '127.0526923103'],
['LOC_0007', '부천시', '37.5035236772', '126.7620258315'],
['LOC_0008', '성남시', '37.3589256866', '127.1230193698'],
['LOC_0009', '수원시', '37.3062283022', '127.0006673650'],
['LOC_0010', '시흥시', '37.3859529890', '126.8401627128'],
['LOC_0011', '안산시', '37.3584852392', '126.8220989209'],
['LOC_0012', '양주시', '37.7811156739', '127.0295140877'],
['LOC_0013', '양평군', '37.5352268162', '127.4671754909'],
['LOC_0014', '여주시', '37.2145722794', '127.5802137871'],
['LOC_0015', '연천군', '37.9897043024', '126.9206352812'],
['LOC_0016', '오산시', '37.1868046144', '127.0120339544'],
['LOC_0017', '용인시', '37.3274739465', '127.1737784768'],
['LOC_0018', '의왕시', '37.3497876203', '126.9626000497'],
['LOC_0019', '의정부시', '37.7455788063', '127.0904425858']]
distance = [[0,44784.3,74560,32631.5,55296.2,46753,31203.5,56457.4,58562.6,48237.5,51124.4,33118.1,78764.3,114745.9,48463,82583.7,64622.3,53900.4,36256.1],
[41823,0,45724.8,44851.3,48580.7,61251.7,32540.5,19359.6,16173.2,19458,25182.1,47418.1,55697.8,74934.2,84333.5,33050.7,29790.8,10581.3,44332.3],
[67795.4,46009.3,0,82506.9,53828.4,73134.6,74944.1,33983.9,44586.2,61224.3,62939.1,58028.4,29167.5,55087.3,89307.3,55334.9,27610.7,48728,52147.3],
[30541.5,46052.8,81582.5,0,71945.3,61221.8,25771.8,58698.8,62707.4,42805.9,45692.7,49767.1,95413.4,110692.6,61016.3,77152,66863.7,56551.3,52905.2],
[43956.7,49818.8,53515.3,69649.8,0,29060.1,68221.8,55504,69485.4,64621,81245.2,24306.6,50346.6,89372.9,49910.8,83520.1,61663.2,67034,18761],
[40201.7,60105.7,72345.1,62090.3,28870.3,0,71094.8,74333.8,75957.4,88128.8,91015.7,16218.1,76549.3,112530.9,21480,102349.8,80493,71295.2,20959],
[30438,32943.1,68261.6,27305.2,71841.8,64769.9,0,49894.9,40199.6,20298.1,21136.3,49663.7,75562.9,101784.4,73082.1,54644.3,58059.8,34043.5,52801.8],
[49064,19222.2,34616,62199.4,54558.8,73865,50284.9,0,16668.7,36565.1,38279.9,58758.8,53822.9,62771.8,90037.7,27417.4,10927.8,21793.5,54252.8],
[57477.4,15683.9,44878.6,64610.3,69215,88521.2,40398.6,16540.7,0,28228,24210.1,73415,68479.1,63246.7,99987.9,17135.5,19634.3,7322.3,59417.1],
[50178.1,19426.1,60472.9,47045.2,65485,84510,19770.5,36374,23417.3,0,4458.6,69403.8,78829.8,88018.3,92822.2,36087.1,44538.9,17907.4,61039.6],
[50934.8,26024,62795.9,47801.9,81888.7,85266.6,20527.2,38696.9,24379.1,4561.5,0,70160.4,81152.8,84321.3,93578.9,31326.4,41190.5,22468.5,73298.5],
[25104.8,45008.9,57248.2,50797.9,27868.7,16240.6,49370,59237,60860.6,66404,69290.9,0,61452.5,97434,29232.6,87253,65396.1,56198.4,8957.9],
[70718.9,57180.1,29105.8,96412,50366.6,76058.1,76352.3,54843.2,68824.6,78869.6,80584.4,60951.9,0,45886.1,92230.8,82859.3,56673.6,66373.3,53425.6],
[110980.1,74188.9,54608.5,111320.6,89373.2,116319.3,103123.7,62335.8,68070.4,92296.5,88081.4,101213.1,45159.9,0,132492,73078.7,55962.7,73257.8,95332],
[55484.2,86376.2,88533.5,61493.1,49710.9,21518.7,72795.3,90522.2,100154.4,89829.4,92716.2,29241.7,92737.7,128719.3,0,124175.6,96681.4,95492.2,37998.3],
[82074.9,32566.6,55048.2,78942,83274.9,102581.1,54730.3,26710.3,17278,36034.3,31195.9,87475,82539,67820,116893.2,0,29803.9,24205,81593.8],
[54121,27770.5,28016.7,66692,62276,81582.2,56705.3,10891.8,19786,42985.5,41591.6,66476,56762.4,56172.5,97754.9,30534.7,0,25994.8,60594.9],
[60511.4,10480.5,47568.4,57378.5,66661.3,85967.5,33166.8,20557,7057.1,19447,22152.4,70861.3,65925.3,69385.1,91749,24192.5,26236,0,54571.5],
[26891.8,44796.6,54983.5,52584.9,21662.1,20914.4,51156.9,54739.3,58574.9,68190.9,71077.8,8950.7,53761.7,95169.3,38232.1,82755.3,63131.4,53912.6,0]]
restaurantDf = pd.DataFrame(restaurant, columns = ['ID', 'CITY', 'LAT', 'LON'])
return restaurantDf, distance
if __name__ == '__main__':
main()
Python
복사
결과는 아래와 같습니다.
Keyword: Logistics Optimization, 물류 최적화, 파이썬, Python, 선형계획법, Linear Programming, Google OR Tools
