주메뉴 바로가기 본문 바로가기 하단 바로가기

고객지원

기술문의

VRP 관련 질문입니다.

  • 정봉주
  • 2009.12.23
  • 조회수 1,645
현재 한국과학기술원 산업공학과에 재학중입니다.

가장 일반적인 행태의 VRP 관련 해서 C나 Java에서 Cplex을 연동하여 문제를 풀고자 하는데 subtour elimination을 어떻게 적용 시켜서 풀어야 할 지 답이 안나오네요.

이런 부탁이 무리인 것은 알지만 혹시나 C나 Java와 Cplex를 연동하여 VRP 풀기 위한 관련 example이나 source를 알려주시면 진심 감사하겠습니다. 만약 그런게 어려우시다면 subtour elimination을 cplex에서 어떻게 적용 할지라도 가르쳐 주셨으면 합니다.

진심 부탁드립니다.

댓글 2

  • 유환주2009-12-24
    실제 산업현장에서 사용할 VRP 문제라면 Column Generation Approach를 고려해 볼만합니다.
    Column Generation에서 후보(subtour)의 생성은 dual price를 사용하여 생성합니다. 필요없는 후보를 삭제하는 것은 통상적으로 후보 pool의 갯수를 정해서 그 갯수를 초과하면 dual price 낮은 것을 제거합니다 --> 상당한 코딩 스킬이 필요하여 쉽지 않은 작업입니다. Column Generation 예제는 cutstock.java를 참조하세요.
    그냥 MIP 모델이라면 적당한 휴리스틱으로 subtour를 제거할 수 밖에 없습니다.
    아이콘삭제
  • 이보헌2009-12-24
    LP/MIP 로 모델링 하신 후,
    cplex API를 사용해 풀이 하실 수 있습니다.

    cplex 사용방법은 모델 도출 후 생각해 볼수 있겠습니다.
    아이콘삭제

댓글 입력