Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.47 No.2 pp.168-175
DOI : https://doi.org/10.11627/jksie.2024.47.2.168

Parcel Locker Locations and Dynamic Vehicle Routing Problem with Traffic Congestion

Chaehyun Kim

, Gitae Kim†

Industrial and Management Engineering, Hanbat National University

^†Corresponding Author : gitaekim@hanbat.ac.kr

Received 07/06/2024 Finally Revised 14/06/2024 Accepted 14/06/2024

Abstract

Due to the complexity of urban area, the city vehicle routing problem has been a difficult problem. The problem has involved factors such as parking availability, road conditions, and traffic congestion, all of which increase transportation costs and delivery times. To resolve this problem, one effective solution can be the use of parcel lockers located near customer sites, where products are stored for customers to pick up. When a vehicle delivers products to a designated parcel locker, customers in the vicinity must pick up their products from that locker. Recently, identifying optimal locations for these parcel lockers has become an important research issue. This paper addresses the parcel locker location problem within the context of urban traffic congestion. By considering dynamic environmental factors, we propose a Markov decision process model to tackle the city vehicle routing problem. To ensure more real situations, we have used optimal paths for distances between two nodes. Numerical results demonstrate the viability of our model and solution strategy.

Key Words : City Vehicle Routing Problem , Parcel Locker , Markov Decision Process , Supply Chain Management , Location Problem

교통 체증을 고려한 물품 보관함 위치 및 동적 차량 경로 문제

김채현, 김기태†

국립한밭대학교 산업경영공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. 서 론

도시 간의 수송에서 수송 시간은 비교적 예측이 가능하지만 도시에 들어가서는 많은 변수가 있어서 예측이 어려워진다. 이러한 이유로 수요지의 최종 단계에서의 수송이 전체 수송에 많은 영향을 주기 때문에 라스트 마일 물류(Last Mile Logistics)에 대한 중요성이 커지고 있다. 라스트 마일 물류를 위한 도심에서의 차량 경로 문제(Vehicle Routing Problem, VRP)는 수요지의 위치와 도로는 정해져 있지만 많은 환경들이 변화하는 상황에 있다. 이러한 상황은 교통 체증, 도로 조건의 변화, 도심에서의 행사, 주차 공간의 변동 등이 포함된다. 따라서, 이러한 현실 상황을 고려하기 위해서는 결정론적(deterministic) 차량 경로 문제가 아닌 확률론적(stochastic) 차량 경로 문제와 함께 동적(dynamic) 차량 경로 문제 모형이 적합하다고 볼 수 있다[8].

도시 차량 경로 문제에서는 많은 불확실한 상황으로 계획했던 배송 시간을 맞추기 어려운 경우가 발생하고 수송 비용이 증가하기도 한다. 이러한 문제를 해결하기 위한 방법 중에 하나는 물품 보관함(Parcel locker)을 이용하는 것이다. 물품 보관함은 배송할 물품을 보관하는 창고와 같은 설비를 말하는데, 수요지들의 근처에 배치할 수 있다. 배송 차량은 물품을 최종 수요지에 배송하는 대신에 물품 보관함에 보관하고 수요자들이 자신의 물품을 직접 가져 간다. 따라서, 수요자들이 수고를 해야 하는 불편함이 있지만, 전체 수송비용과 시간을 줄일 수 있다.

물품 보관함에 대한 연구는 최근에 많이 이루어지고 있는데, 주로 물품 보관함을 어디에 위치시켜야 하는 지와 몇 개의 물품 보관함을 사용해야 하는지에 관한 연구들이다. 또한 이동식 물품 보관함을 이용하는 방안에 대해서도 연구되고 있다. 하지만, 물품 보관함을 이용할 때, 도심 차량 경로 문제에서 고려되어야 하는 확률적 부분과 동적 부분을 고려한 문제를 다루는 연구는 많지 않다. 본 연구는 도심에서의 확률적이며 동적으로 변하는 교통체증을 고려하고 물품 보관함을 이용하는 경우를 고려하는 동적 차량 경로 문제에 대한 모형을 개발하고 이에 대한 해법을 제시한다. 시간에 따라 교통상황이 변하는데, 변하는 교통상황에 따라 차량의 이동속도는 변하고 이를 고려하여 최적의 경로를 탐색하면서 물품 보관함의 최적 위치도 결정한다. 대부분의 연구에서는 두 지점을 연결한 도로는 고정된 것으로 보고 해당 도로에 대한 교통상황을 고려하였지만, 본 연구에서는 두 지점 사이를 이동하는 여러 경로들에 대한 교통상황을 모두 고려하여 가장 빠른 경로를 선택하여 이동하는 것으로 하고 이를 전체 동적 차량 경로 문제에서 고려한다. 이러한 부분은 문제를 좀 더 현실 문제에 가깝게 가정한 것이라고 볼 수 있고, 이는 전체 수송 비용과 시간을 줄일 수 있게 한다.

본 논문의 구성은 다음과 같다. 제2장에서는 차량 경로 문제와 확률적이고 동적인 상황을 고려한 차량 경로 문제에 대한 선행연구들과 물품 보관함의 이용에 대한 연구들을 살펴본다. 제3장에서는 본 논문에서 다루고 있는 문제의 정의 및 가정과 연구 방법 및 수리 모형이 제시되고, 제4장에서는 동적 차량 경로 문제를 푸는 해법에 대해 살펴본다. 제5장에서는 해법을 이용한 실험 결과를 보여주는데, 물품 보관함 이용을 고려한 결과, 목적지 사이의 최단 경로를 고려한 결과, 교통 체증을 고려한 결과 비교를 차례로 제시하며, 마지막으로 제6장에서 본 연구에 대한 결론을 제공한다.

2. 선행 연구

차량 경로 문제는 1950년대 후반에 처음으로 수리모형으로 모형화되었고, 1960년대에 해법이 제안된 후에 지금까지 많은 연구가 이루어지고 있다. 빈 패킹(Bin packing) 문제와 외판원 문제를 결합한 문제로 NP-hard로 알려져 있으면서 다양한 변형 모형이 제안되었다. 여러 조건이 추가된 모형들과 문제상황이 동적인 동적 차량 경로 문제와 무작위인 상황이 추가된 확률론적 차량 경로 문제에 대해서도 많은 모형과 해법이 연구되어 왔다[19].

결정론적 차량 경로 문제, 동적 차량 경로 문제, 확률론적 차량 경로 문제는 수요지, 차량, 네트워크 환경을 어떻게 가정하는지에 따라 구분될 수 있으며, 동적 차량 경로 문제는 실시간 통신을 위한 기술 지원이나 동적으로 공개된 정보를 사용하여 경로를 탐색한다[14]. 동적 차량 경로 문제의 역동성은 수요에 대한 변동과 네트워크에 대한 변동 등을 고려한 경우가 많이 있다. 차량이 한 지점에 도착하면 상황에 대한 동적인 변화와 이후의 모든 비용을 고려하여 다음 도착지를 연속적으로 결정해 나가면서 최종 경로를 정한다[4].

대부분의 차량 경로 문제는 창고와 고객 사이의 이동 시간이 결정적이고 일정하거나, 고객 사이의 거리가 동일하다고 가정한다. 실제 환경에서는 여러 가지 혼잡한 상황으로 인해 이동 시간이 가변적인 경우가 대부분이다. Chen et al.[5]은 시간 종속 차량 경로 문제(TDVRP)를 다루었으며, 이동 시간이 일정하지 않다고 가정하였다. 이를 이용해 전체 노선 시간, 차량 대수, 운송 비용에 미치는 영향을 판단하였다. 또한, 본 연구에 다루고자 하는 Markov decision process 모형을 적용한 동적 차량 경로 문제 연구는 많이 이루어져 왔다. Florio et al.[8]는 확률론적 수요가 있는 차량 경로 문제를 해결하기 위한 전략으로 실시간 고객의 요구를 반영하며, 2단계로 구성된 Markov Decision Process 모델을 제시하였다. Cimen and Soysal[6]은 확률론적 차량 속도를 고려하여 용량 제약 차량 경로 문제를 다루었다. 비용을 고려하는 대신 환경오염 물질 배출을 최소화하는 방향으로 모델을 제시하였다. Zhu et al.[22]은 확률론적 수요를 고려하는 단일 차량 경로 문제에 대한 Markov decision process 모형을 제안하였다. Kim et al.[9]는 교통 혼잡을 고려한 동적 차량 경로 문제를 다뤘는데, 본 연구에서도 적용한 Rollout Algorithm을 Markov decision process의 해법으로 제시하였다. Kim et al.[11]는 교통 정보를 실시간으로 수집하여 이용하는 최적 차량 경로 탐색을 다루었다.

교통체증 정보를 고려한 연구는 많이 이루어져 왔으며, 본 연구의 문제 상황에서 고려하려고 하는 픽업 지점(Pickup Point)/물품 보관함의 위치를 탐색하고, 이용하는 연구도 최근에 점점 증가하는 추세이다. Zhang et al.[20]은 도심의 셀프서비스 스테이션의 위치를 탐색하는 문제를 다뤘으며, 제안한 모델에 교통 혼잡을 고려하는 문제로 확장할 수 있을 것이라고 제시하였다. Zang et al.[18]은 도심 물류 배송에서 시간 창을 고려한 문제로 수요지 배송과 물품 보관함 배송을 함께 고려하여 외판원 문제(TSP)에 대해 혼합 선형 계획법을 이용한 모형을 제시하였고, Zhou et al.[21]는 픽업 지점의 위치 경로 문제에 대해 유전자 알고리즘을 적용한 모형을 제시하였다. Novoa et al.[13] 또한, Rollout Algorithm을 Markov decision process의 해법으로 제시하였는데, 확률적인 수요를 고려한 차량 경로 문제를 다뤘다. Kim[10]은 차량 경로 문제와 물품 보관함의 위치 문제를 하나의 모형에서 고려하는 수리모형을 개발하고 해법을 제시하였다. 픽업 지점 혹은 물품 보관함의 위치 및 개수를 고려하는 연구의 대부분은 결정론적/확률론적 수요를 고려한 연구가 주를 이루고 있다[17].

하지만 확률적인 교통체증과 무인 보관함 위치를 함께 고려한 연구는 거의 이루어지지 않았다. 또한, 차량 경로 문제에서 목적지 간의 경로는 고정되어 있는 경우가 대부분이며, 목적지 간의 이동 시간에 대해 탐색 시점마다 최단 경로를 계산하는 것도 거의 연구되지 않았다. 본 연구에서는 확률론적 차량 속도를 고려한 동적 차량 경로 문제를 다루며, 이동 시간 확률 분포를 추정한다. 차량 운송 비용을 최소화할 수 있도록 수요지와 물품 보관함의 이용을 함께 고려하여 경로를 탐색한 결과를 비교하였다.

3. 동적 차량 경로 문제 모형

3.1 문제 정의

차량은 물류센터에서 동시에 출발하여 수요지와 물품 보관함에 화물을 배송한다. 각 도로의 교통상황을 고려하여 다음 목적지(수요지 혹은 물품 보관함)를 결정한다. 각 도로의 시간별 평균 속도 데이터에 대한 확률 분포를 추정하여 이동 비용을 계산하며, 모든 도로 구간은 독립적이다. 다음 <Figure 1>은 가정한 수요지와 물품 보관함 후보지에 대한 대전시 도심의 배송 네트워크를 도식화한 것이다.

수요지 및 물품 보관함의 위치는 고정되어 있으며, 모든 보관함을 전부 사용하는 것은 아니라고 가정한다.

연구는 <Figure 2>와 같은 절차로 진행된다. 수집된 각 도로의 속도 데이터를 이용하여 시간대별로 속도 확률 분포의 모수를 추정한다. 추정된 확률 분포를 이용하여 이동 시간 확률 분포와 상태 전이 확률을 Markov Decision Process 모델에 적용하여 최적 정책을 도출한다. 계산 시간 감소를 위한 해결 방법론으로 Rollout Algorithm을 이용하여 완화된 최적 정책을 도출한다.

3.2 이동 시간 확률 분포 추정

확률 분포 추정을 위한 데이터는 대전 교통 빅데이터 플랫폼에서 대전시 도심 주요 도로 구간별 평균 속도 데이터를 수집하였다. 수집 기간은 2023년 12월 1일부터 2023년 12월 31일까지, 오전 9시부터 오후 9시까지, 5분 간격으로 수집하였다. 각 도로의 속도 확률 분포를 정규 분포를 가정하고, 각 도로의 5분 간격으로 분포의 평균과 표준 편차를 추정하였다. 추정된 모수와 도로의 실제 거리를 이용하여 이동 시간 분포를 추정하였으며, 난수가 분포의 신뢰구간 내에 존재할 확률을 계산하였다. 두 지점 간의 경로는 고정된 것이 아니며, 목적지 간의 모든 이용 가능한 도로에 대하여 최단 경로를 탐색하기 위해 Floyd-Warshall Algorithm을 적용하여, 목적지를 탐색하는 시점마다, 각 도로 구간의 시간대별로 최단 시간 매트릭스를 계산하여 최단 경로를 결정하게 된다. 그 과정은 다음의 <Figure 3>과 같다.

n이 현재 노드이고 n′이 다음 목적지 노드, x가 현재 노드와 다음 목적지 노드 사이를 구성하는 도로 구간일 때, 현재 노드에서 다음 목적지 노드까지 최단 시간 경로를 찾기 위해 다음과 같이 각 도로 구간의 이동 시간을 더하여 x′ 중 최소 이동 시간을 가지는 경로를 다음 목적지 노드까지 이동하기 위한 경로로 선택한다. 다음의 식은 다음 목적지 노드까지의 모든 가능한 경로에 따라 각 경로를 구성하는 도로 구간의 이동 시간을 더한 것을 나타낸 식이며, x′의 이동 시간 확률을 계산하기 위해서는 각 경로를 구성하는 도로 구간의 이동 시간 확률을 합한 것으로 한다.

\begin{array}{l} {x^{'}}_{1} = x_{11} + x_{21} + x_{31} + x_{41} \\ {x^{'}}_{2} = x_{11} + x_{22} + x_{32} + x_{41} \\ {x^{'}}_{3} = x_{11} + x_{22} + x_{33} + x_{42} \\ {x^{'}}_{4} = x_{12} + x_{23} + x_{34} + x_{42} \end{array}

위의 식은 다음 목적지 노드까지의 모든 가능한 경로에 따라 각 경로를 구성하는 도로 구간의 이동 시간을 더한 것을 나타낸 식이며, x′의 이동 시간 확률을 계산하기 위해서는 각 경로를 구성하는 도로 구간의 이동 시간 확률을 합한 것으로 한다.

3.3 Markov Decision Process 모형

모형은 추정된 이동 시간과 상태 전이 확률을 이용하여 구성되었고, 목적지가 수요지인지 혹은 물품 보관함 후보지인지에 따라 계산 조건이 달라진다.

문제 상황을 바탕으로 한 배송 네트워크를 G = (N, A )와 같이 나타내며, <Figure 1>과 같다. 각 지점(노드) 집합은 N = {0,1, ⋯, l} 으로 나타낸다. 이 중에서 0은 Depot로, 물류센터에 해당하고, 수요지는 N_c = {1, 2, ⋯, m} , 물품 보관함은 N_p = {m + 1, m + 1, ⋯, l } 와 같이 나타내며, N_c ⊆ N, N_p ⊆ N 과 같이 N 집합에 포함되어 있다. 각 지점(노드) 사이의 도로(아크) 집합은 A = {a ≡ (n, n′)|n, n′ ∈ N, n ≠ n′}와 같이 나타내며, 차량에 대한 집합은 V = {1, 2, ⋯, k} 로 나타낸다. 시간 t에서 각 아크 a의 상태 집합은 $\vec{S_{t}} = {S_{1} (t), S_{2} (t), \dots, S_{a} (t)}$ 이다. 현재 노드 n에서 다음 노드 n′를 탐색하기 위하여, 시간 t일 때, N 에서 현재 노드 n을 제외하고, 나머지 노드 집합 N_t = N ╲{n}에서 현재 노드 n의 접근 가능한 노드 집합 R_t ⊆ N_t에서 다음 노드 n′∈R_n을 선택한다. 또한, 물품 보관함의 이용을 고려하기 위해 물품 보관함 후보지의 선택은 수요지 노드 n_c의 접근 가능한 노드 집합 n_p∈ $R_{n_{c}}$ 에서 선택한다. 각 도로의 상태는 독립적인 것으로 가정하였다. 도로의 이동 시간 확률을 추정하기 위해 목적지 간의 경로를 구성하는 도로 구간 집합 A_nn′ = {a₁₁, a₁₂, ⋯, a_ij} 을 정의하였다. 이동 시간 확률 P (x′|n, t, $\vec{S_{t}}$ , n′)은 다음과 같다.

P (x^{'} | n, t, \vec{S_{t}}, n^{'}) = \sum_{a_{i j} \in A_{n n^{'}}} P (x_{i j} | a_{i j}, \vec{S_{t}})

목적지 사이를 구성하는 도로의 각 이동 시간 확률을 추정한 합으로 계산한다. 현재 확률 상태에서 다음 시간의 확률 상태로 전이될 확률을 나타내는 상태 전이 확률 $P (\vec{S^{'}} | t, \vec{s}, t + n)$ 은 다음과 같다.

P (\vec{S^{'}} | t, \vec{s}, t + n) = \prod_{a = 1}^{| A^{'} |} P (s_{a} (t + n)) = < \vec{s^{'}} >_{a} | s_{a} (t) = < \vec{s} >_{a})

현재 시간 t에서 다음 시간 t + n까지의 모든 a에 대하여, 아크 a의 t일 때의 상태 $< \vec{S} >_{a}$ 가 t + n일 때의 상태 $< \vec{S^{'}} >_{a}$ 가 될 확률을 모두 곱한 값이다.

시스템의 전체 상황은 Ω(n, t, $\vec{S_{t}}$ , N_t, k)로 정의되며, 다음 목적지 n′을 탐색하는 정책 π^* (Ω_t)은 다음과 같다.

π^{*} (Ω_{t}) \equiv a r g \underset{n^{'} \in R_{n}}{m a n} {w (n, t, {\vec{S}}_{t}, n^{'})}

시간 t일 때, 현재 노드 n에서 접근 가능한 노드에 대하여 다음 노드 n′로 전환하는 함수를 최소로 하는 다음 노드 n′이 t 시점에서의 최적 정책이 된다. 따라서, 최소 가치함수를 계산해야 하며, 다음과 같다.

υ^{*} (n, t, {\vec{S}}_{t}, N_{t}, k) = \underset{n^{'} \in R_{n}}{m i n} {w (n, t, {\vec{S}}_{t}, n^{'})}

모든 가능한 n′으로 전환하는 함수를 계산한다. 수요지와 물품 보관함 후보지에 따른 계산 조건을 고려한 식은 노드 n′이 수요지일 경우, 방문해야 할 노드에서 n′을 제거하고, 노드 n′이 물품 보관함 후보지일 경우, 물품 보관함 이용 비용 c_p와 n′과 수요지 사이의 거리 비용 c_l (n′, n_c)를 계산하고, n′ 및 n′에서 접근 가능한 수요지 노드 n_c를 제거한다. 식은 다음과 같다.

이러한 식을 이용하여 최소 가치함수와 다음 노드 전환에 대한 비용을 구하는 과정을 재귀적으로 반복하게 된다. <Figure 4>는 모델이 정책을 찾기 위한 과정을 도식화한 것이다.

방문해야 할 노드가 n₁, n₂, n₃, n₄일 때를 가정한다면, 모든 노드에 대하여 각 노드를 선택할 경우 나머지 노드에 대하여 선택해야 하는 모든 상황에 대하여 계산해야 한다. 이러한 모든 경우에 대하여 계산된 최소 가치함수를 선택해야 하므로 계산 시간이 상당히 증가한다.

4. Rollout Algorithm

4.1 Rollout Policy

계산 시간을 감소시키기 위한 근사해 동적 계획법(Approximate Dynamic Programming)에서, 최적의 최소 가치함수를 탐색하는 대신, 휴리스틱 최소 가치함수를 사용하였다. 차원의 저주를 피하기 위하여 휴리스틱 알고리즘으로 Rollout Algorithm을 채택하였다. Rollout Algorithm의 수식은 다음과 같다.

Rollout algorithm

1. Initialization

Current state Ω_t, let t = 0

2. While current state Ω_t ϵ Ω is not terminal state Do

3. For all possible next state Ω_t+1 (one step ahead) Do

\begin{matrix} π^{*} (Ω_{t}) = \arg min_{π (Ω_{t}) \in Ψ} {c (Ω_{t}, π (Ω_{t})) \\ + \sum_{\forall Ω_{t + 1}} P (Ω_{t + 1} | Ω_{t}, π (Ω_{t})) υ^{π_{H (Ω_{t + 1})}} (Ω_{t + 1}) \end{matrix}

4. Store π*(Ω_t)

5. Update current state by Ω_t+1 with π* (Ω_t) and a realization of

{\vec{s}}^{'}_{t}

6. t ← t+ 1

먼저, Step 1에서 알고리즘은 현재 상태를 초기화한다. Step 2에서 가능한 모든 정책에 대하여 반복한다. Step 3에서 가능한 다음 상태에 대해 정책을 탐색한다. Step 4에서 탐색한 최적 정책을 저장한다. Step 5에서 최적 정책에 대한 다음 상태로 현재 상태를 업데이트, Step 6에서 t를 업데이트하고 다시 알고리즘을 반복한다.[2]

경로 탐색 문제에서 주로 사용되는 탐색 방법으로 Nearest Neighbor Algorithm이 있다. 따라서, 결정 휴리스틱 규칙으로 채택하였다. Rollout Algorithm에서 정책을 찾기 위한 과정을 도식화한 것은 <Figure 5>와 같다.

마찬가지로 물류센터는 0이고, 방문해야 할 노드가 n₁, n₂, n₃, n₄일 때, 모든 노드에 대하여 각 노드를 선택할 경우 나머지 노드에 대해서는 가장 가까운 거리 순으로 다음 노드를 선택하는 경로로 정책을 찾는다. 모든 경우에 대하여 계산된 최소 가치함수를 선택하는 것이 아닌 가능한 다음 노드에 대하여 각 노드의 Nearest Neighbor Algorithm에 의한 최소 가치함수를 선택하는 것이다.

5. 실험 결과

모형은 Python으로 구현하였으며, 정책 반복을 위해 MDPtoolbox solver를 사용하였다. 실험 결과 경로는 <Figure 6>, <Figure 7>, <Figure 8>, <Figure 9>와 같다. <Figure 6>, <Figure 7>, <Figure 8>, <Figure 9>의 차량별 운송 경로는 <Table 1>과 같으며, 전체 운송 비용의 결과는 <Table 2>와 같다. 물품 보관함 이용을 고려하지 않는 경우, 차량이 모든 수요지에 배송을 마치고 돌아오는 경로 는 Figure 6과 같은 네트워크를 구성하며, 전체 운송 거리 는 82,769.57m이다. 전체 운송 비용은 698,679.65로 가장 많이 들었고, 물품 보관함을 이용하는 경우, 각 차량마다 한 개의 물품 보관함을 이용하는 결과로 <Figure 7>과 같이 나타나며, 전체 운송 거리는 79,373.95m로 거리가 감소하였다. 전체 운송 비용은 638,416.92로 물품 보관함을 이용하지 않는 경로보다 8.62% 감소하였다. 교통체증을 고려하여 목적지 간 최단 경로를 계산한 경우, 같은 목적지가 주어졌음에도 불구하고, 교통체증을 고려한 다른 경로를 이용했기 때문에 <Figure 8>과 같이 <Figure 6>과는 다른 경로를 나타내는 것을 확인할 수 있다. 전체 운송 거리는 98,636.01m이며, 전체 운송 비용은 602,104.68로 교통 체증을 고려하지 않는 경로보다 13.82% 감소하였다. 교통 체증을 고려하여 목적지 간 최단 경로를 계산하면서 물품 보관함의 이용을 모두 고려하는 경우, 각 차량마다 한 개의 물품 보관함을 이용하는 것은 <Figure 7>과 같으나, 다른 물품 보관함을 이용하는 결과를 <Figure 9>에서 확인할 수 있다. 전체 운송 거리는 94,112.71m이며, 전체 운송 비용은 546,518.55로 교통 체증과 물품 보관함을 고려하지 않은 경로보다 14.39% 감소로, 가장 많은 감소 결과를 보였다.

물품 보관함 이용을 고려한 경로는 이용하지 않는 경로에 비해 거리상으로도 비용상으로도 감소하는 것으로 나타났다. 만일 물품 보관함의 후보지들이 변경되면 최적해도 바뀔 것이다. 이것과 동일하게, 수요지들이 변경되면 최적해가 바뀌는 것과 같은 결과라고 볼 수 있다. 본 논문에서 제안한 수리모형은 물품 보관함의 후보지들의 위치와 수요지들의 위치가 변경되어도 물품 보관함을 사용하는 것이 유리하면 사용하는 것으로 최적해를 제시해 주고 불리할 경우에는 수요지들만을 방문하는 최적해를 제공할 것이다. 확률적인 교통 체증 상황을 고려한 경로는 거리상으로는 교통 체증을 고려하지 않는 경로에 비해서 증가했지만, 이는 교통 체증을 피하기 위해 교통 체증이 없는 도로로 우회했기 때문에 거리가 더 길어져도 비용적인 측면에서 실질적으로 감소했기 때문이다. 따라서, 물품 보관함의 이용은 교통 체증을 고려하는 것과 상관없이 거리 감소하는 것으로 나타나며, 물품 보관함 이용 고려에 상관없이 교통 체증을 고려할 경우, 거리는 증가하지만 비용은 감소하는 것으로 나타나고 현실 문제에 가까운 경향을 보인다.

6. 결 론

본 연구는 시간에 따라 확률적으로 변하는 교통체증 상황과 물품 보관함을 고려한 도시 차량 경로 문제를 동적 차량 경로 문제로 모형화하고 해법을 제시하였다. 이 모형을 통해서 최적의 동적 차량 경로와 물품 보관함의 위치를 찾을 수 있다. 또한 두 지점 간의 경로는 정해져 있는 것으로 가정하는데, 본 연구에서는 두 지점 간에 여러 경로를 고려하고 해당 경로들의 교통상황도 고려한 최단 거리를 찾아 전체 동적 차량 경로 문제에 적용하여 좀 더 현실적인 차량 경로 문제를 구현하였다. 본 논문은 동적이면서 확률적인 교통상황을 반영하기 위해 Markov decision process(MDP)를 이용한 모형을 개발하였으며, 계산량을 줄이기 위한 해법으로 Rollout algorithm을 사용하였다. 교통상황에 대한 네트워크의 구성을 위해 도심에서의 실제 교통 데이터를 수집하여 도로별, 시간별 차량 이동 시간에 대한 확률분포를 추정하고 이 확률 분포들을 이용하여 동적 차량 경로 문제에 적용하였다.

실험 결과는 물품 보관함을 이용하지 않는 경우, 물품 보관함을 이용하는 경우, 도로 구간의 교통 체증을 고려한 경우, 교통 체증과 물품 보관함 이용을 함께 고려한 경우의 네 가지 결과를 비교하여 물품 보관함 이용이 운송 비용을 감소시킬 수 있으며, 교통 체증을 고려하면 더 큰 비용을 감소시킬 수 있다는 결과를 도출하였다. 또한, 실제 도로 환경을 반영하는 복잡한 문제에서 해결 방안을 탐색하는 모형을 개발하는 것에 기초를 제공할 것으로 기대된다. 향후에 확률적인 수요나 도로 간의 교통 체증 상관성 등, 다양한 환경을 반영하여 최적 경로를 탐색하는 문제로 확장할 수 있고, 대규모 실제 사례를 적용하여, 모형에 대한 성능을 일반적으로 입증하는 연구가 필요할 것으로 보인다.

Figure

<Figure 1>.

City Distribution Network

<Figure 2>.

Solution Procedure

<Figure 3>.

Road Segments between Two Sites

<Figure 4>.

States Considered in Markov Decision Process

<Figure 5>.

States Considered in Rollout Algorithm

<Figure 6>.

Routes without Considering the use of Parcel Lockers

<Figure 7>.

Routes Considering the Use of Parcel Lockers

<Figure 8>.

Routes considering Traffic Congestion

<Figure 9>.

Routes considering both Traffic Congestion and the use of Parcel Lockers

Table

<Table 1>.

Optimal Routes of Vehicles

	Path
Without considering the use of Parcel Lockers	Vehicle 1 [0-40-2-35-48-13-38-21-53-19-3-0]Vehicle 2 [0-11-9-17-26-33-7-43-5-0]
Considering the use of Parcel Lockers	Vehicle 1 [0-40-2-35-48-13-38-21-53-56-0]Vehicle 2 [0-11-9-25-26-33-7-43-5-0]
Considering Traffic Congestion	Vehicle 1 [0-19-53-21-2-35-48-38-13-40-3-0]Vehicle 2 [0-11-5-43-7-9-17-26-33-0]
Considering both Traffic Congestion and the use of Parcel Lockers	Vehicle 1 [0-40-38-13-48-35-2-21-53-56-0]Vehicle 2 [0-11-33-7-9-17-26-46-5-0]

<Table 2>.

Total Transportation Costs & Distances

	Total Transportation Distnace (m)	Total Transportation Cost (₩)
Without considering the use of Parcel Lockers	82,769.57	698,679.65
Considering the use of Parcel Lockers	79,373.95	638,416.92
Considering the use of Parcel Lockers	98,636.01	602,104.68
Considering both Traffic Congestion and the use of Parcel Lockers	94,112.71	546,518.55

Reference

Arfananda, M. G., Nasution, S. M., and Setianingsih, C., Selection of Bandung City Travel Route Using the Floyd-Warshall Algorithm, International Journal of Integrated Engineering, 2020, Vol. 12, No. 7, pp. 90-97.
Bertsekas, D. P., Rollout Algorithms for Discrete Optimization: A Survey, in Handbook of Combinatorial Optimization, 2010.
Boysen, N., Fedtke, S., and Schwerdfeger, S., Last-mile delivery concepts: A survey from an operational research perspective, IEEE Transactions on Intelligent Transportation Systems, 2016, Vol. 17, No.8.
Braekers, K., Ramaekers, K., and Nieuwenhuyse, I. V., The vehicle routing problem: State of the art classification and review, Computers & Industrial Engineering, 2016, Vol. 99, pp. 300-313.
Chen, H. K., Hsueh, C. F., and Chang, M. S., The real-time time-dependent vehicle routing problem, Transportation Research Part E, 2006, Vol. 42, pp. 383-408.
Cimen, M. and Soysal, M., Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm, Transportation Research Part D, 2017, Vol. 54, No. 1, pp. 82-98.
Esuabana, Micah, I., Ikpang, Nkereuwem, I., and Okon, Jackson, E., Shortest Transportation Route Network in Nigeria Using Floyd-Warshall’s Algorithm, Mathematical Theory and Modeling, 2015, Vol. 5, No. 8.
Florio, A. M., Hartl, R. F., and Minner, S., Optimal a priori tour and restocking policy for the single-vehicle routing problem with stochastic demands, European Journal of Operational Research, 2020, Vol. 285, No. 1, pp. 172-182.
Kim, G., Ong, Y. S., Cheong, T., and Tan, P. S., Solving the Dynamic Vehicle Routing Problem Under Traffic Congestion, IEEE Transactions on Intelligent Transportation Systems, 2016, Vol. 17, No.8.
Kim, G., Optimization for Vehicle Routing Problem with Locations of Parcel Lockers, Journal of Korean Society of Industrial and Systems Engineering, 2022, Vol. 45, No. 4, pp. 134-141.
Kim, S., Lewis, M. E., and White, C. C., Optimal Vehicle Routing With Real-Time Traffic Information, IEEE Transactions on Intelligent Transportation Systems, 2005, Vol. 6, No. 2.
Magzhan, K. and Jani, H. M., A Review And Evaluations Of Shortest Path Algorithms, International Journal of Scientific & Technology Research, 2013, Vol. 2, No. 6.
Novoa, C., and Storer, R., An approximate dynamic programming approach for the vehicle routing problem with stochastic demands, European Journal of Operational Research, 2009, Vol. 196, pp. 509-515.
Pillac, V., Gendreau, M., Gueret, C., and Medaglia, A. L., A review of dynamic vehicle routing problems, European Journal of Operational Research, 2013, Vol. 225, No. 1, pp. 1-11.
Risald, Mirino, A. E., and Suyoto, Best Routes Selection Using Dijkstra and Floyd-Warshall Algorithm, International Conference on Information & Communicati-on Technology and System, 2017.
Sakharov, V., Chernyi, S., Saburov, S., and Chertkov, A., Automatization Search for the Shortest Routes in the Transport Network Using the Floyd-warshall Algorithm, Transportation Research Procedia, 2021, Vol. 54, pp. 1-11.
Wu, Y., and Qiu, X., GRASP-based request allocation and MDP-based vehicle routing in home pick-up service with service continuity consideration, Intelligent Transport Systems, 2023, Vol. 18, No. 2.
Zang, X., Jiang, L., Liang, C., and Fang, X., Coordinated home and locker deliveries: An exact approach for the urban delivery problem with conflicting time windows, Transportation Research Part E, 2023, Vol. 177, 103228.
Zhang, J., and Woensel, T. V., Dynamic Vehicle Routing with random requests: A literature review, International Journal of Production Economics, 2023, Vol. 256, 108751.
Zhang, W., Xu, M., and Wang, S., Joint location and pricing optimization of self-service in urban logistics considering customers’ choice behavior, Transportation Research Part E, 2023, Vol. 174, 103128.
Zhou, L., Wang, X., Ni, L., and Lin, Y., Location-Routing Problem with Simultaneous Home Delivery and Customer’s Pickup for City Distribution of Online Shopping Purchases, Sustainability, 2016, Vol. 8, 828.
Zhu, L., Rousseau, L. M., Rei, W., and Li, B., Paired cooperative reoptimization strategy for the vehicle routing problem with stochastic demands, Computer & Operations Research, 2014, Vol. 50, No. 1, pp. 1-13.