Strategic Location Problem for Last-mile Delivery with Relaying Drones

Abstract

본 논문의 목표는 트럭과 드론을 이용한 2단 물류 네트워크에서의 배송시간 단축을 위해 스테이션의 전략적 위치를 설정하는 것이다. 이를 위하여 본 논문에서는 드론 물류에서의 배송시간을 단축할 수 있는 `릴레이배송'이라는 운영방식을 제안한다. 이는 하나의 화물 트럭이 드론 스테이션을 순회하면서 화물을 하차하고, 이와 동시에 드론은 트럭이 하차가 종료된 스테이션으로부터 최종 소비자까지 라스트마일 배송을 하면서 트럭이 방문하는 스테이션을 순회하는 방식이다. 릴레이배송을 적용하여 배송시간을 단축하고자 하는 경우, 매 스테이션마다 트럭과 드론의 도착시간이 최대한 동기화되어야 한다. 본 논문에서는 이를 위해 주어진 배송지점의 분포 등의 환경에 따라 스테이션의 위치를 미리 전략적으로 구성하여 배송시간을 효과적으로 줄일 수 있는 문제를 제안하고, 이를 교차적 휴리스틱 알고리즘을 이용하여 해결한다. 또한 문제의 특성으로부터 드론이 빠른 경우와 느린 경우 각각에 적용할 수 있는 근사법을 제안하고, 이로부터 배송시간의 예측값, 상계와 하계를 구하여 알고리즘의 결과의 타당성을 검증한다. 이와 더불어 실제 배송지점이 주어졌을 때 드론의 스케쥴을 결정하는 혼합정수계획법 문제를 제안하며, 확률적으로 생성된 배송지점에서의 스케쥴링 결과와 앞서 분석한 결과를 비교하여 위치선정 전략의 타당성을 입증한다. 본 논문의 결과물은 2단 물류 네트워크에서의 트럭과 드론의 동기화의 중요성을 입증하고, 배송시간을 줄이는 위치선정 전략에 대한 직관적인 해법을 제공하여 2단 물류 네트워크 운영에서의 의사결정에 도움을 줄 것으로 기대된다.

Due to a competitive e-commerce environment, faster last-mile delivery using drones is taken into consideration as a challenging way of service provision. In this thesis, we propose a two-echelon distribution network for last-mile delivery with drones and a location problem involved in it. The objective is to minimize service time, the time required to finish one round of last-mile delivery. We introduce `relaying operation' as a collaborative operation method of a truck and drones; a truck picks all parcels up at the depot and delivers them to stations for transshipment in a specified sequence. Once the truck has delivered parcels to a station, drones deliver them from the station to their final destinations. After finishing all deliveries at one station, drones move to the next station following the same sequence as the truck. The service time of a proposed network is reduced strategically by locating intermediate stations. Our location problem is defined as a variant of continuous location-allocation problem. For minimal service time, arrivals and departures of the two types of vehicles may be synchronized at each station. We propose a heuristic algorithm that alternately solves location problem and allocation problem to achieve the synchronization. The performance of the proposed heuristic is satisfactory in solution quality and running time. We also identify the critical factor in a location decision and illustrate how the decision changes as parameters change. Moreover, we develop theoretical models for two extreme cases with fast and slow drones under uniform demand. We show the two models are well-aligned with heuristic results. Last, We validate the estimated service time from the heuristic algorithm by scheduling drones with realized demand.