🖥️ IT, 컴퓨터/🚀 최적화30

• [공간 최적화] 구글의 RHIP(Receding Horizon Inverse Planning) 알고리즘 RHIP 알고리즘: 차량 경로 문제를 위한 혁신적인 최적화 기법RHIP(Receding Horizon Inverse Planning) 알고리즘은 차량 경로 문제(VRP)를 해결하기 위해 구글이 개발한 새로운 최적화 기법입니다. [1] 이 알고리즘은 기존의 VRP 해결 방법보다 16~24%의 성능 향상을 보였습니다.RHIP 알고리즘의 핵심 특징동적 계획법 기반: RHIP는 동적 계획법(Dynamic Programming)을 기반으로 하여 최적의 경로를 찾습니다. [1]실시간 최적화: 실시간으로 새로운 정보를 반영하여 경로를 지속적으로 최적화합니다. [1]역방향 계획: 목적지에서 출발지로 역방향으로 계획을 수립하여 최적의 경로를 찾습니다. [1]RHIP 알고리즘의 장점높은 성능: 기존 방식보다 16~24%의.. 🖥️ IT, 컴퓨터/🚀 최적화 2024. 6. 14.

• 

  [공간 최적화] 차량 경로 최적화 문제(VRP; Vehicle Routing Problem) VRP(Vehicle Routing Problem, 차량 경로 최적화 문제)는 여러 지점(고객 또는 물류 지점)에 물품을 배달하거나 서비스를 제공해야 할 때, 여러 대의 차량이 최소한의 비용으로 효율적인 경로를 계획하는 문제입니다. 이는 물류, 배달, 택배 서비스, 대중교통 계획 등 다양한 산업에서 매우 중요한 역할을 합니다.VRP의 주요 목표VRP의 목표는 여러 제약 조건을 고려하여 차량들이 최소한의 비용으로 모든 지점을 방문하는 최적 경로를 찾는 것입니다. 여기서 '비용'은 주로 총 이동 거리, 소요 시간, 연료 소비, 또는 운영비용으로 정의될 수 있습니다. 효율적인 경로 최적화를 통해 기업은 비용을 절감하고 서비스 품질을 향상시킬 수 있습니다.VRP 문제의 변형기본적인 VRP는 아래와 같이 여러 가.. 🖥️ IT, 컴퓨터/🚀 최적화 2024. 6. 14.

• 

  [최적화] p-median과 p-center의 차이, 예시 시각화 p-median과 p-center는 둘 다 위치 문제를 다루는 중요한 개념들입니다. 이들은 보통 시설 배치, 물류 관리, 공공 서비스 배치 등에서 사용되며, 최적의 위치를 찾아내는 데 활용됩니다. 이 두 개념의 주요 차이점을 설명하면 다음과 같습니다.p-median 문제목적: 주어진 고객 또는 수요 지점에 대한 총 이동 거리를 최소화하는 p개의 시설 위치를 찾는 것.적용 상황: 전체적인 고객 만족도를 최대화하고자 할 때 사용됩니다. 예를 들어, 여러 도시에 병원을 배치할 때, 전체 환자들의 평균 이동 거리를 최소화하려는 경우에 적합합니다.수학적 정의:n개의 수요 지점과 m개의 후보지 지점이 있다고 가정.p개의 후보지 지점을 선택하여 총 이동 거리를 최소화함.목적 함수는, 여기서는 지점 i에서 j까지의 거.. 🖥️ IT, 컴퓨터/🚀 최적화 2024. 5. 28.

• [최적화] Mini-sum과 Mini-max 문제 Mini-sum "Minisum"은 위치 문제의 한 유형으로, 최소화 문제의 한 형태입니다. 이 문제에서는 여러 지점 사이의 총 거리 또는 비용을 최소화하기 위해 최적의 위치를 찾아야 합니다. 이러한 유형의 문제는 다양한 분야에서 발견될 수 있으며, 물류, 도시 계획, 네트워크 디자인 등에서 특히 중요합니다. Minisum 문제의 핵심은 여러 지점(예: 고객 위치, 상점, 시설 등)을 고려하여 한 지점(예: 창고, 서비스 센터)의 최적 위치를 결정하는 것입니다. 이 최적 위치는 모든 지점으로부터의 거리나 비용의 합을 최소화하는 지점으로 정의됩니다. 예를 들어, 새로운 창고를 건설할 때, 여러 공급지점 또는 판매지점으로부터의 총 운송 비용을 최소화하기 위한 위치를 찾는 것이 minisum 문제의 전형적인 .. 🖥️ IT, 컴퓨터/🚀 최적화 2023. 12. 1.

• 

  [공간 최적화] P-center을 유전자 알고리즘으로 구현하기 import pandas as pd # 엑셀 파일 로드 (예: 'data.xlsx') df = pd.read_csv('whole.csv', encoding = 'utf-8') # 거리 데이터 예상 # - 'origin'과 'destination' 열에는 경위도 좌표가 있어야 함 # - 'distance_fin' 열에는 두 위치 사이의 거리가 있어야 함 print(df.head()) def p_center_heuristic(df, p): # 후보지와 고객의 unique id를 찾기 candidate_ids = df['Did'].unique() customer_ids = df['Oid'].unique() # 센터로 선택된 후보지들을 저장할 리스트 centers = [] # objective value 초기화.. 🖥️ IT, 컴퓨터/🚀 최적화 2023. 10. 21.

• 

  [공간 최적화] P-centdian을 유전자 알고리즘으로 구현하기 파이썬으로 Genetic Algorithm을 이용해 P-centdian을 구현한 코드 import pandas as pd # 엑셀 파일 로드 (예: 'data.xlsx') df = pd.read_csv('나의경로.csv', encoding = 'cp949') # 거리 데이터 예상 # - 'origin'과 'destination' 열에는 경위도 좌표가 있어야 함 # - 'distance_fin' 열에는 두 위치 사이의 거리가 있어야 함 print(df.head()) import pandas as pd import random import numpy as np def initialize_population(df, p, population_size): Dids = df['Did'].unique().tolist.. 🖥️ IT, 컴퓨터/🚀 최적화 2023. 10. 20.

• 

  [최적화] Docplex로 p-median 문제 풀기 아직 CPLEX를 설치하지 않은 분은 아래 글 참고! https://kimhongsi.tistory.com/entry/Python-Docplex-%ED%8C%A8%ED%82%A4%EC%A7%80-%EC%84%A4%EC%B9%98 [Cplex] IBM Cplex, 파이썬 DoCplex 패키지 설치 Install the IBM Cplex, Python DoCplex package 1. Cplex 설치 https://www.ibm.com/academic/topic/data-science 혹은 https://academic.ibm.com/a2mt/email-auth 에서 학교 메일로 가입 후 로그인, 평가판 설치 풀버전은 매우 비싸고 commu kimhongsi.tistory.com pip install doc.. 🖥️ IT, 컴퓨터/🚀 최적화 2023. 10. 13.

• 

  [CPLEX] 최적화 프로그램 CPLEX 사용 방법 https://kimhongsi.tistory.com/entry/Python-Docplex-%ED%8C%A8%ED%82%A4%EC%A7%80-%EC%84%A4%EC%B9%98 [Cplex] IBM Cplex, 파이썬 DoCplex 패키지 설치 Install the IBM Cplex, Python DoCplex package 1. Cplex 설치 https://www.ibm.com/academic/topic/data-science 혹은 https://academic.ibm.com/a2mt/email-auth 에서 학교 메일로 가입 후 로그인, 평가판 설치 풀버전은 매우 비싸고 commu kimhongsi.tistory.com 에서 CPLEX를 설치한 후 구동한다. 새로 만들기 > OPL 프로젝트 체크 후 .. 🖥️ IT, 컴퓨터/🚀 최적화 2023. 10. 12.

• [CPLEX] P-median 문제 코드 정리 CPLEX에서는 mod 파일과 dat 파일을 작성해야 한다. mod 파일은 내가 만드는 모델의 틀을 만드는 곳이고, dat 파일은 내가 모델에 넣을 데이터를 입력하는 곳이다. 모델 (mod) 파일 코드 // P-Median Probelm main{ //메인 블록 // Generating & Solving initial model thisOplModel.generate(); // OPL 모델을 만듦 if (cplex.solve()) { var ofile = new IloOplOutputFile("C:/Users/user/OneDrive - SNU/문서/cplex/P-Median-Problemanswer.txt"); //여기에 결과 저장 //대소문자 주의 ofile.close(); var obj = cple.. 🖥️ IT, 컴퓨터/🚀 최적화 2023. 10. 12.

• [최적화] 유전자 알고리즘 용어 정리 Genetic Algorithm (GA)에서 주로 사용되는 용어와 그 의미 Chromosome (염색체): 해의 한 예시나 데이터 구조를 나타내며, GA에서는 종종 문자열 또는 배열로 표현됩니다. Gene (유전자): 염색체의 개별 구성 요소로, 문제에 따라 다양한 데이터 타입을 가질 수 있습니다. Population (집단): 현재 해의 집합으로, GA의 각 세대마다 여러 개의 염색체로 구성됩니다. Selection (선택): 다음 세대의 부모 염색체를 선택하는 과정. 가장 흔한 방법 중 하나는 룰렛 휠 선택입니다. Crossover (교차): 두 개의 부모 염색체로부터 새로운 후손 염색체를 생성하는 과정. Mutation (돌연변이): 염색체의 일부를 무작위로 변경하여 다양성을 유지하는 과정. Fit.. 🖥️ IT, 컴퓨터/🚀 최적화 2023. 10. 11.

• [최적화] NP-hard 문제란 무엇일까? "NP-hard"는 계산 이론에서 문제의 난이도를 분류할 때 사용되는 용어 중 하나입니다. 그렇다면 NP-hard의 정의를 이해하기 위해 몇 가지 기본 용어와 개념을 알아보겠습니다: 결정 문제 (Decision Problem): 주어진 입력에 대해 "예" 또는 "아니오"로 답을 할 수 있는 문제입니다. P (Polynomial time): 모든 결정 문제들의 집합 중에서 다항 시간 안에 해결될 수 있는 문제들의 집합입니다. 다시 말해, 이 문제들은 크기가 (n)인 입력에 대해 (O(n^k))의 시간복잡도를 가지는 알고리즘으로 해결될 수 있습니다. NP (Nondeterministic Polynomial time): 모든 결정 문제들의 집합 중에서 주어진 "예"의 해답(증언, 증거)을 다항 시간 내에 검증.. 🖥️ IT, 컴퓨터/🚀 최적화 2023. 10. 11.

• [최적화] p-centdian greedy 휴리스틱 파이썬 코드 import pandas as pd def greedy_p_centdian(df, p, w): unique_Dids = df['Did'].unique() selected_combination = [] while len(selected_combination) < p: min_obj = float('inf') selected_Did = None for Did in unique_Dids: if Did in selected_combination: continue temp_combination = selected_combination + [Did] subset_df = df[df['Did'].isin(temp_combination)].copy() # Zmedian 계산 subset_df = subset_df.lo.. 🖥️ IT, 컴퓨터/🚀 최적화 2023. 9. 26.