단일 허브를 이용한 시간 제약이 존재하는수거 및 배달 차량 경로 문제
Pick Up and Delivery Vehicle Routing Problem Under Time Window Using Single Hub
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
After Dantzig and Rasmer introduced Vehicle Routing Problem in 1959, this field has been studied with numerous approaches so far. Classical Vehicle Routing Problem can be described as a problem of multiple number of homogeneous vehicles sharing a same starting node and having their own routes to meet the needs of demand nodes. After satisfying all the needs, they go back to the starting node. In order to apply the real world problem, this problem had been developed with additional constraints and pick up & delivery model is one of them. To enhance the effectiveness of pick up & delivery, hub became a popular concept, which often helps reducing the overall cost and improving the quality of service. Lots of studies have suggested heuristic methods to realize this problem because it often becomes a NP-hard problem. However, because of this characteristic, there are not many studies solving this problem optimally. If the problem can be solved in polynomial time, optimal solution is the best option. Therefore, this study proposes a new mathematical model to solve this problem optimally, verified by a real world problem. The main improvements of this study compared to real world case are firstly, make drivers visit every nodes once except hub, secondly, make drivers visit every nodes at the right time, and thirdly, make drivers start and end their journey at their own homes.
Abstract
After Dantzig and Rasmer introduced Vehicle Routing Problem in 1959, this field has been studied with numerous approaches so far. Classical Vehicle Routing Problem can be described as a problem of multiple number of homogeneous vehicles sharing a same starting node and having their own routes to meet the needs of demand nodes. After satisfying all the needs, they go back to the starting node. In order to apply the real world problem, this problem had been developed with additional constraints and pick up & delivery model is one of them. To enhance the effectiveness of pick up & delivery, hub became a popular concept, which often helps reducing the overall cost and improving the quality of service. Lots of studies have suggested heuristic methods to realize this problem because it often becomes a NP-hard problem. However, because of this characteristic, there are not many studies solving this problem optimally. If the problem can be solved in polynomial time, optimal solution is the best option. Therefore, this study proposes a new mathematical model to solve this problem optimally, verified by a real world problem. The main improvements of this study compared to real world case are firstly, make drivers visit every nodes once except hub, secondly, make drivers visit every nodes at the right time, and thirdly, make drivers start and end their journey at their own homes.
참고문헌 (13)
- Cetiner, S., "Hubbing and routing in postal delivery systems", Annals of Operations Research, 181(1), pp.109~124 (2010)
- Dantzig, G. B., "The Truck Dispatching Problem", Management Science, 6(1), pp.80~91 (1959)
- Ebery, J., "Solving large single allocation p-hub problems with two or three hubs", European Journal of Operational Research, 128(2), pp.447~458 (2001)
- "Google map"[URL]
- 황인태, "여행경로 추천 서비스를 위한 최적화 수리모형", 한국산업경영시스템학회지, 40(3), pp.99~106 (2017), 한국산업경영시스템학회
- 진정민, "미래형 무인항공기 배송 시스템의 운영개념 설계", 한국생산관리학회지, 28(4), pp.417~431 (2017), 한국생산관리학회[DOI]
- 강충상, "고객의 납기마감시간이 존재하는 이기종 차량경로문제의 발견적 해법", 한국산업경영시스템학회지, 28(2), pp.8~17 (2005), 한국산업경영시스템학회
- Kartal, Z., "Single allocation p-hub median location and routing problem with simultaneous pick-up and delivery", Transportation Research Part E, 108, pp.141~159 (2017)
- Koc, C., "Thirty years of heterogeneous vehicle routing", European Journal of Operational Research, 249(1), pp.1~21 (2016)
- 문기주, "4개 시간구간에 의한 가변속도 차량경로해법", 한국산업경영시스템학회지, 35(4), pp.171~178 (2012), 한국산업경영시스템학회[DOI]
- Nagy, G., "The Many-to-Many Location-Routing Problem", TOP, 6(2), pp.261~275 (1998)
- Sohn, J. H., "A linear program for the twohub location problem", European Journal of Operational Research, 100(3), pp.617~622 (1997)
- Wasner, M., "An integrated multi-depot hub-location vehicle routing model for network planning of parcel service", International Journal of Production Economics, 90(3), pp.403~419 (2004)