[논문]배송 네트워크에서 드론의 유용성 검증: 차량과 드론을 혼용한 배송 네트워크의 경로계획

정예림; 박태준; 민윤홍

doi:10.7737/jkorms.2016.41.3.075

배송 네트워크에서 드론의 유용성 검증: 차량과 드론을 혼용한 배송 네트워크의 경로계획
Usefulness of Drones in the Urban Delivery System: Solving the Vehicle and Drone Routing Problem with Time Window 원문보기

한국경영과학회지 = Journal of the Korean Operations Research and Management Science Society, v.41 no.3, 2016년, pp.75 - 96

정예림 (연세대학교 경영대학 경영학과) , 박태준 (연세대학교 경영대학 경영학과) , 민윤홍 (삼성전자 종합기술원)

Abstract ▼ AI-Helper

This paper investigates the usefulness of drones in an urban delivery system. We define the vehicle and drone routing problem with time window (VDRPTW) and present a model that can describe a dual mode delivery system consisting of drones and vehicles in the metropolitan area. Drones are relatively free from traffic congestion but have limited flight range and capacity. Vehicles are not free from traffic congestion, and the complexity of urban road network reduces the efficiency of vehicles. Using drones and vehicles together can reduce inefficiency of the urban delivery system because of their complementary cooperation. In this paper, we assume that drones operate in a point-to-point manner between the depot and customers, and that customers in the need of fast delivery are willing to pay additional charges. For the experiment datasets, we use instances of Solomon (1987), which are well known in the Vehicle Routing Problem society. Moreover, to mirror the urban logistics demand trend, customers who want fast delivery are added to the Solomon's instances. We propose a hybrid evolutionary algorithm for solving VDRPTW. The experiment results provide different useful insights according to the geographical distributions of customers. In the instances where customers are randomly located and in instances where some customers are randomly located while others form some clusters, the dual mode delivery system displays lower total cost and higher customer satisfaction. In instances with clustered customers, the dual mode delivery system exhibits narrow competition for the total cost with the delivery system that uses only vehicles. In this case, using drones and vehicles together can reduce the level of dissatisfaction of customers who take their cargo over the time-window. From the view point of strategic flexibility, the dual mode delivery system appears to be more interesting. In meeting the objective of maximizing customer satisfaction, the use of drones and vehicles incurs less cost and requires fewer resources.

주제어

질의응답

핵심어	질문	논문에서 추출한 답변
	VRPTW란 무엇인가?	VRPTW는 차량 일정계획 문제(Vehicle Routing Problem: VRP)에서 파생된 문제로서, 서비스를 받는 고객들이 희망하는 배송 시간대(Time Window)에 맞추어 서비스가 제공되어야 하는 제약이 추가된 차량 일정계획 문제이다. VRPTW는 많은 학자들에 의해 연구된 바 있다[3].
	택배 배송 네트워크에 드론을 사용했을 때, 비용적인 측면에서의 장점은 무엇인가?	‘수직 이착륙이 가능한 무인 비행체’로 정의되는 드론은 기계의 특성상 운반 가능한 배송품의 무게 제한과 운행거리 제한으로 인해 운행 반경이 좁은 택배 배송 네트워크에서 운용될 가능성이 높다. 택배 배송 네트워크에서 드론의 장점은 무인 비행이 가능하다는점, 도심지의 교통 혼잡을 피할 수 있다는 점, 차량보다 빠르다는 점, 그리고 단위 거리당 1개의 화물 운송비용이 차량보다 작다는 점을 들 수 있다[20] 비용적인 부분에서는 드론의 초기 구입비용이 1000달러 정도로 높기는 하지만, 배송 네트워크에서 드론의 운영비는 배송 건당 10～20센트로 매우 낮기 때문에 투자금의 회수율이 빠를 것으로 기대된다[21]. 드론 배송 서비스를 시범적으로 운용하는 아마존(Amazon)에서는 비용을 화물 1개 당 1달러로 계산하고 있다[41].
	배송 서비스에 드론을 사용하였을 때 얻을 수 있는 장점은 무엇인가?	도심지역의 복잡성과 교통 혼잡을 피할 수 있다는 점에서 드론을 이용한 배송 서비스가 주목을 받고 있다[5, 20, 21]. 드론은 차량과 달리 항공 네트워크를 이용하기 때문에 배송시간에 영향을 주는 도심지의 혼잡에서 상대적으로 자유롭고, 고객과 차고지 사이를 점대점 방식(Point to Point: P2P)으로 운행으로 때문에 한번 창고를 나간 후 다시 창고로 돌아오는 시간인 재보충주기가 짧아 당일에 발생하는 수요를 대처하기에 유리하다.

참고문헌 (50)

석상문, "네트워크 문제를 위한 새로운 진화 알고리즘에 대하여", 한국경영과학회지, 제32권, 제2호(2007), pp.109-121.

원문보기 상세보기
윤영수, "적응형 유전알고리즘의 실험적 비교", 한국경영과학회지, 제32권, 제4호(2007), pp.1-18.
이상헌, 이승원, "시간제약이 있는 차량경로문제에 대한 개미군집 시스템 해법", 한국경영과학회지, 제34권, 제1호(2009), pp.153-165.

원문보기 상세보기
"택배 서비스의 핵심 지표: 고객은 '당일 배송'을 원한다(?)", CLO 2015년 4월호 통권 59호, pp.71-73.
서울시, 2014년 서울시 차량통행속도 보고서, pp.11-13, 2015.
Agatz, N., P. Bouman, and M. Schmidt, "Optimization approaches for the traveling salesman problem with drone," ERIM Report Series Reference, No. ERS-2015-011-LIS., 2015.
Anand, N., H. Quak, R. van Duin, and L. Tavasszy, "City logistics modeling efforts: Trends and gaps-A review," Procedia-Social and Behavioral Sciences, Vol.39(2012), pp.101- 115.

상세보기
Berger, J. and M. Barkaoui, "A parallel hybrid genetic algorithm for the vehicle routing problem with time windows," Computers & Operations Research, Vol.31, No.12(2004), pp.2037-2053.

상세보기
Blanton, Jr, J.L. and R.L. Wainwright, "Multiple vehicle routing with time and capacity constraints using genetic algorithms," Proceedings of the 5th International Conference on Genetic Algorithms, pp.452-459, Morgan Kaufmann Publishers Inc. (1993, June).
Braysy, O. and M. Gendreau, "Tabu search heuristics for the vehicle routing problem with time windows," Vol.10, No.2(2002), pp.211-237.

상세보기
Braysy, O., "A reactive variable neighborhood search for the vehicle-routing problem with time windows," INFORMS Journal on Computing, Vol.15, No.4(2003), pp.347-368.

상세보기
Braysy, O., "Fast local searches for the vehicle routing problem with time windows," INFOR, Vol.40, No.4(2002), pp.319-330.

상세보기
Braysy, O., W. Dullaert, and M. Gendreau, "Evolutionary algorithms for the vehicle routing problem with time windows," Journal of Heuristics, Vol.10, No.6(2004), pp.587-611.

상세보기
Bryan, V., Drone delivery: DHL 'parcelcopter' flies to German isle http://www.reuters.com/article/us-deutsche-post-drones-idUSKCN0HJ1ED20140924, 2014.
Burke, E.K. and J.P. Newall, "A multistage evolutionary algorithm for the timetable problem," Evolutionary Computation, IEEE Transactions on, Vol.3, No.1(1999), pp.63-74.

상세보기
Carter, A.E. and C.T. Ragsdale, "A new approach to solving the multiple traveling salesperson problem using genetic algorithms," European Journal of Operational Research, Vol. 175, No.1(2006), pp.246-257.

상세보기
Chaovalitwongse, W., D. Kim, and P.M. Pardalos, "GRASP with a new local search scheme for vehicle routing problems with time windows," Journal of Combinatorial Optimization, Vol.7, No.2(2003), pp.179-207.
Chiang, W.C. and R.A. Russell, "A reactive tabu search metaheuristic for the vehicle routing problem with time windows," INFORMS Journal on Computing, Vol.9, No.4(1997), pp.417-430.

상세보기
Chiang, W.C. and R.A. Russell, "Simulated annealing metaheuristics for the vehicle routing problem with time windows," Annals of Operations Research, Vol.63, No.1(1996), pp.3- 27.

상세보기
Colin Lewis, Is package delivery using drones feasible? RobotEcnomics, 2014.(Lewis, 2014b).
Colin Lewis, The economics of Amazon's delivery drones, RobotEcnomics, 2014.(Lewis, 2014a).
Cordeau, J.F., M.M. Gendreau, and G. Laporte, "A tabu search heuristic for periodic and multi depot vehicle routing problems," Networks, Vol.30, No.2(1997), pp.105-119.

상세보기
Cordeau, J.F., G. Laporte, and A. Mercier, "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational Research Society, Vol.52, No.8(2001), pp.928-936.

상세보기
Czech, Z.J. and P. Czarnas, "Parallel Simulated Annealing for the Vehicle Routing Problem with Time Windows," PDP, 2002, p.0376 IEEE.
Davis, L., "Applying adaptive algorithms to epistatic domains," IJCAI, Vol.85(1985), pp.162- 164.
Falkenauer, E., Genetic algorithms and grouping problems, John Wiley & Sons, New York, 1998.
Glover, F., "Ejection chains, reference structures and alternating path methods for traveling salesman problems," Discrete Applied Mathematics, Vol.65, No.1(1996), pp.223-253.

상세보기
Ha, Q.M., Y. Deville, Q.D. Pham, and M.H. Ha, "Heuristic methods for the Traveling Salesman Problem with Drone," arXiv preprint arXiv:1509.08764., 2015.
Ha, Q.M., Y. Deville, Q.D. Pham, and M.H. Ha, "On the Min-cost Traveling Salesman Problem with Drone," arXiv preprint arXiv: 1512.01503., 2015.
Kilby, P., P. Prosser, and P. Shaw, "Guided local search for the vehicle routing problem with time windows," Meta-Heuristics, Springer, US, (1999), pp.473-486.
Laporte, G., Y. Nobert, and D. Arpin, "Optimal solutions to capacitated multi-depot vehicle routing problems," Universite de Montreal, Centre de recherche sur les transports, 1984.
Laporte, G., Y. Nobert, and S. Taillefer, "Solving a family of multi-depot vehicle routing and location-routing problems," Transportation Science, Vol.22, No.3(1988), pp.161-172.

상세보기
Lin, S., "Computer solutions of the traveling salesman problem," Bell System Technical Journal, Vol.44(1965), pp.2245-2269.

상세보기
Louis, S.J., X. Yin, and Z.Y. Yuan, "Multiple vehicle routing with time windows using genetic algorithms," Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on Vol.3(1999), IEEE.
Malmborg, C., "A genetic algorithm for service level based vehicle scheduling," European Journal of Operational Research, Vol.93, No.1(1996), pp.121-134.

상세보기
Murray, C.C. and A.G. Chu, "The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery," Transportation Research Part C: Emerging Technologies, Vol.54(2015), pp.86-109.

상세보기
Oliver, I.M., D.D. Smith, and J.R. Holland, "Study of permutation crossover operators on the traveling salesman problem," Genetic algorithms and their applications: proceedings of the second International Conference on Genetic Algorithms: July 28-31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA. Hillsdale, NJ: L. Erlhaum Associates, 1987.
Park, Y.B., "A hybrid genetic algorithm for the vehicle scheduling problem with due times and time deadlines," International Journal of Productions Economics, Vol.73, No.2(2001), pp.175-188.

상세보기
Renaud, J., F.F. Boctor, and G. Laporte, "An improved petal heuristic for the vehicle routing problem," Journal of the Operational Research Society, Vol.47, No.2(1996), pp.329- 336.

상세보기
Renaud, J., G. Laporte, and F.F. Boctor, "A tabu search heuristic for the multi-depot vehicle routing problem," Computers & Operations Research, Vol.23, No.3(1996), pp.229- 235.

상세보기
Rose, C., "Amazon's Jeff Bezos looks to the future," D. Mihailovich (Producer), (2013.), p.60.
Solomon, M.M., "Algorithms for the vehicle routing and scheduling problems with time window constraints," Operations research, Vol.35, No.2(1987), pp.254-265.

상세보기
Starkweather, T., S. McDaniel, K.E. Mathias, L.D. Whitley, and C. Whitley, "A Comparison of Genetic Sequencing Operators," In ICGA (1991, July) pp.69-76.
Syswerda, G., "Schedule optimization using genetic algorithms," Handbook of genetic algorithms, 1991.
Taillard, E., P. Badeau, M. Gendreau, F. Guertin, and J.Y. Potvin, "A tabu search heuristic for the vehicle routing problem with soft time windows," Transportation science, Vol.31, No.2(1997), pp.170-186.

상세보기
Tan, K.C., Y.H. Chew, and L.H. Lee, "A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows," Computational Optimization and Applications, Vol.34, No.1(2006), pp.115-151.

상세보기
Tang, L., J. Liu, A. Rong, and Z. Yang, "A multiple traveling salesman problem model for hot rolling schedule in Shanghai Baoshan Iron and Steel Complex," European Journal of Operational Research, Vol.124, No.2(2000), p.267.

상세보기
Taniguchi, E. and R.G. Thompson, "City Logistics Network Modelling and Intelligent Transport Systems," Emerald, United Kingdom, 2011.
Whitley, L.D., T. Starkweather, and D. Fuquay, "Scheduling problems and traveling salesmen: The genetic edge recombination operator," In ICGA, Vol.89(1989), pp.133-140.
Zhang, M., D. Jiang, and X. Tang, "Full load vehicle routing with multiple depots: New network flow based algorithm," Journal of Systems Science and Systems Engineering, Vol.6(2002), pp.216-220.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증