비대칭차량경로문제의 경로분할모형에 관한 연구

• 영문명: A Route-Splitting Approach to the Capacitated Asymmetric Vehicle Routing Problem
• 발행기관: 한국생산관리학회
• 저자명: 강성민(Sungmin Kang)
• 간행물 정보: 『한국생산관리학회지』韓國生産管理學會誌 第18卷 第4號, 3~31쪽, 전체 29쪽
• 주제분류: 경제경영 > 경영학
• 파일형태: PDF
• 발행일자: 2007.12.30

국문 초록

  차량경로문제의 Set-Partitioning모형에 적용된 열생성과정에서 차량경로를 생성하는 하위문제는 순회외판원문제와 같은 조합구조를 가지므로 연산상의 어려움이 크다. 본 논문은 각 차량경로를 분할하여, 하위문제에서 분할된 부분경로를 생성하고 주문제에서 다시 결합하는 경로분할모형을 소개한다. 열생성이 용이해지는 반면 주문제는 복잡해진다. 실험예제로 모형의 LP하한값을 비교분석하였으며, 분지열생성을 통하여 최대 100개 수요지의 비대칭차량경로문제의 최적화실험을 수행하였다.

영문 초록

  The Capacitated Vehicle Routing Problem (VRP) is to determine a set of feasible vehicle routes. one for each vehicle. such that each customer is visited exactly once and the total distance travelled by the vehicles is minimized. A feasible route is defined as a simple circuit including the depot such that the total demand of the customers in the route does not exceed the vehicle capacity. We introduce a new modelling approach. termed route-splitting. for the VRP that allows us to address problems whose size is beyond the current computational range of the Set-Partitioning model. The route-splitting model splits each vehicle route into segments. and results in more tractable subproblems. Lifting much of the burden of solving combinatorially hard subproblems. the route-splitting approach puts more weight on the LP master problem Recent advances in solving LP problems bode well for our approach. The route-splitting model can deal with non-identical vehicles. Given the ability of the route-splitting model to address a wider range of applications and its good performance on asymmetric instances. we find the model promising and valuable for further research.

목차

요약
1. 서론
2. 경로분할모형
3. 해법 알고리듬
4. 실험 연산
5. 결론
참고문헌
Abstract
저자소개

키워드

비대칭차량경로문제 분지열생성 경로분할모형 Asymmetric Vehicle Routing Problem Branch-and-Price Route-Splitting