비대칭차량경로문제의 경로분할모형에 관한 연구
A Route-Splitting Approach to the Capacitated Asymmetric Vehicle Routing Problem
1
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
차량경로문제의 Set-Partitioning모형에 적용된 열생성과정에서 차량경로를 생성하는 하위문제는 순회외판원문제와 같은 조합구조를 가지므로 연산상의 어려움이 크다. 본 논문은 각 차량경로를 분할하여, 하위문제에서 분할된 부분경로를 생성하고 주문제에서 다시 결합하는 경로분할모형을 소개한다. 열생성이 용이해지는 반면 주문제는 복잡해진다. 실험예제로 모형의 LP하한값을 비교분석하였으며, 분지열생성을 통하여 최대 100개 수요지의 비대칭차량경로문제의 최적화실험을 수행하였다.
Abstract
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.
참고문헌 (23)
- "가동준비비용 및 시간이 작업순서에 종속하는 생산일정계획의 연속시간 모형", 15(3), pp.61~87 (2005)
- "A Set-Partitioning-Based Exact Algorithm for the Vehicle Routing Problem", pp.731~749 (1989)
- "Routing and Scheduling of Vehicles and Crews The State of the Art", pp.63~211 (1983)
- "Vehicle Routing Problem with Elementary Shortest Path Based Column Generation", 33, pp.2972~2990 (2006)
- "Exact Algorithms for the Vehicle Routing Problem Based on Spanning Tree and Shortest Path Relaxations", pp.255~282 (1981)
- "Algorithms and Codes for Dense Assignment Problems: The State of the Art", 100, pp.17~48 (2000)
- "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows", pp.342~354 (1992)
- "Performance of Various Computers Using Standard Linear Equations Software University of Tennessee", k(xville) (1988)
- "A Branch-and-Bound Algorithm for the Capacitated Vehicle Routing Problem on Direct Graphs", pp.846~859 (1994)
- "Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees", pp.626~642 (1994)
- "A New Exact Algorithm for the Vehicle Routing Problem Based on Q-paths and K-shortest Paths Relaxations", 61, pp.21~43 (1995)
- "Progress in Linear Programming-based Algorithms for Integer Programming : An Exposition", 12(1), pp.2~23 (2000)
- "Lotsizing and Scheduling on Parallel Machines with Sequence-Dependent Setup Costs", 45(2), pp.273~289 (1999)
- "An Exact Algorithm for the Asymmetrical Capacitated Vehicle Routing Problem", (bert), pp.33~46 (1986)
- "Exact Algorithms for the Vehicle Routing Problem Annals of Discrete Mathematics", (bert), pp.147~184 (1987)
- "An Overview of Exact and Approximate Algorithms European Journal of Operations Research", pp.345~358 (1992)
- "Optimization Theory for Large Systems" (1970), Macmillan Company
- "A Matching Based Exact Algorithm for Capacitated Vehicle Routing Problems", 7, pp.1~9 (1995)
- "The Age of Optimization", pp.5~13 (1994)
- "Multi-resource Routing with Flexible Tasks: An Application in Drayage Operations", 38, pp.555~568 (2006)
- "Models, Relaxations and Exact Approaches for the Capacitated Vehicle Routing Problem", 123, pp.487~512 (2002)
- "An Exact Algorithm for the Vehicle Routing Problem with Bachhauls", 31(4), pp.372~385 (1997)
- "VRPLIB: A Vehicle Routing Problem Library" (2000)