물류 문제에서 메모리 추가에 의한 가변적인 이웃 탐색 강화

전문가 제언

○ 차량경로배정 문제(VRP)는 중앙차고지로부터 고객에게 주문한 물품의 배송을 위한 차량의 경로를 설정하는 문제로서 수송 및 유통과 물류 분야에서 발생하는 문제이다. VRP의 목적은 전체 경로 거리의 최소화이다. 이 문제의 최적 해는 조합최적화 또는 정수계획법을 이용하게 되는데 물품 배달 과정에서 발생하는 가변적인 상황 때문에 주로 경험적 방법론인 메타 휴리스틱 방법을 사용한다.

 

○ 가변적 이웃 탐색(Variable neighborhood search: VNS)방법은 조합최적화 문제에 대한 효과적이고 간단한 메타 휴리스틱 해결 방법이 하나이다. VNS는 현재 최적 해에 대한 이웃 해를 탐색하여 이동하는 방법을 사용한다. VNS는 또한 선형계획법, 정수계획법, 혼합 정수계획법 및 비선형계획법 등에서 메타 휴리스틱 방법으로 사용되기도 한다.

 

○ 경로우선 집단 사후전략(route-first cluster second)은 VRP에서 먼저 모든 차량경로를 확인하고 이 경로를 운행 가능한 집단으로 묶어서 이에 따라 경로를 배정하는 메타 휴리스틱 방법이다. 이때 경로들은 주어진 최적해 알고리즘을 사용하여 분리되고 분리된 집단으로부터 최적경로가 결정된다.

 

○ 이 논문은 계획된 주기 상에서 유연한 배달 날짜를 가진 경로를 설계하는 실제 문제를 다루었다. 해법은 경로우선 집단 사후전략을 채택하고 메모리 기반 Shaking 프로시저와 Skewed 프로시저를 사용한 VNS 방법을 사용한다.

 

○ 차량 경로배정 문제를 다룬 국내 연구는 물류 분야와 수송문제 및 OR에서의 최적해 문제에서 많은 연구가 수행되고 있고 물류 분야에서는 실제적인 차량 경로에 관한 많은 부분이 활용되고 있다. 비록 VRP문제가 NP-hard이긴 하지만 앞으로의 연구는 경로 배정문제 해법에 ICT를 융합한 소프트웨어 개발에 있다고 볼 수 있다. 물류분야에서 많은 기업이 해외에 진출하고 있음을 비춰볼 때 비용을 더욱 줄이면서 효율적인 패키지 개발도 경쟁력 향상을 위하여 추진되어야 할 것이다.

저자

Joaquin Pacheco , Irma Garcia , Ada Alvarez

자료유형

학술정보

원문언어

영어

기업산업분류

정보통신

연도

2014

권(호)

62()

잡지명

Knowledge-Based Systems

과학기술
표준분류

정보통신

페이지

28~37

분석자

김*기

분석물

• 물류 문제에서 메모리 추가에 의한 가변적인 이웃 탐색 강화.pdf [297,684 byte]

이미지변환중입니다.