Journal Search Engine

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

Journal of Society of Korea Industrial and Systems Engineering Vol.41 No.4 pp.138-145
DOI : https://doi.org/10.11627/jkise.2018.41.4.138

Logistics Allocation and Monitoring System based on Map and GPS Information

Chulsoon Park^*†

, Larsson Bajracharya^**

^**School of Industrial Engineering and Naval Architecture, Changwon National University, Changwon
^**Dept of Information & Communication Engineering, Changwon National University, Changwon

^†Corresponding Author : cspark@changwon.ac.kr

Received 13/11/2018 Finally Revised 04/12/2018 Accepted 10/12/2018

Abstract

In the field of optimization, many studies have been performed on various types of Vehicle Routing Problem (VRP) for a long time. A variety of models have been derived to extend the basic VRP model, to consider multiple truck terminal, multiple pickup and delivery, and time windows characteristics. A lot of research has been performed to find better solutions in a reasonable time for these models with heuristic approaches. In this paper, by considering realtime traffic characteristics in Map Navigation environment, we proposed a method to manage realistic optimal path allocation for the logistics trucks and cargoes, which are dispersed, in order to realize the realistic cargo mixing allowance and time constraint enforcement which were required as the most important points for an online logistics brokerage service company. Then we developed a prototype system that can support above functionality together with delivery status monitoring on Map Navigation environment. First, through Map Navigation system, we derived information such as navigation-based travel time required for logistics allocation scheduling based on multiple terminal multiple pickup and delivery models with time constraints. Especially, the travel time can be actually obtained by using the Map Navigation system by reflecting the road situation and traffic. Second, we made a mathematical model for optimal path allocation using the derived information, and solved it using an optimization solver. Third, we constructed the prototype system to provide the proposed method together with realtime logistics monitoring by arranging the allocation results in the Map Navigation environment.

Key Words : Multiple Pickup and Delivery , Optimization Model , Logistics Allocation and Monitoring , Time Windows

Map과 GPS 기반의 혼적을 고려한 물류할당 및 모니터링 시스템

박철순^*†

, 랄손 바즈라차리야^**

^*창원대학교 산업조선해양공학부
^**창원대학교 정보통신공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

Changwon National University

1. 연구배경

온라인 물류중개서비스란 인터넷을 통해 화주와 화물 트럭간의 화물정보, 차량위치정보 및 운임정보를 실시간 으로 제공해주는 서비스를 의미한다. 이 서비스를 통해 차주에게는 풍부한 화물정보를 제공함으로써 공차운행 을 최대한 감소할 수 있도록 하고, 화주들에게는 운송수 단 조회 및 비교를 통해 물류운임비용을 최소화 할 수 있는 이점을 제공해 줄 수 있다. 현재 대기업계열의 중개 서비스 업체들이 온라인 운송계약 및 물류정보제공, 위 치추적기능 등의 서비스를 제공해 주면서 이 시장에 참 여하고 있다[3].

대기업계열의 화주들은 물류자회사와의 독점적 계약 을 통해 물류업무처리에 큰 어려움이 없지만 규모가 작 은 화주들은 JIT 제조시스템 운영 등의 이유로 고객이 원하는 시간구간 내에 화물입고와 같은 요구사항을 만족 시켜 주기 위하여 많은 노력을 기울이고 있다. 즉, 화주 는 요구사항을 충족하는 화물차량을 확보하기 위하여 노 력을 기울여야 하고, 화물트럭은 혼적 및 시간제약 등을 만족하는 화물을 갖고 있는 화주를 찾아야 하는 애로사 항이 발생하고 있다.

최근 온라인 물류중개서비스 업체인 N사는 현재 시장 에서 규모를 통한 우위를 점하고 있는 대규모 온라인 물 류중개서비스 업체들과의 경쟁에서 차별화를 통한 틈새 시장을 발굴하기 위해 화주와 화물트럭 모두에게 유리한 계약조건을 효율적으로 제시할 수 있는 방안을 찾고 있 다. 이 기업은 화물차량과 화주에 대해서 온라인상에서 의 정보제공을 통한 수동적인 중개서비스 대신에 중개기 업이 능동적으로 참여할 수 있는 중개서비스 제공 및 사 후고객관리에 관심을 가지고 있다. 이러한 능동적 중개 서비스를 통해 화물차량은 시간제약을 만족하는 혼적 가 능한 화물을 할당 받을 수 있고, 다른 지역으로 화물을 운송하여 갔다면 그곳에서 다시 화물차량의 원소재지까 지 공차로 와야 하는 경우가 있지만 중개서비스를 통해 서 미리 화물할당을 받을 수 있다면 공차비율을 줄이는 것이 가능해진다. 그리고 화주는 화물고객의 요구사항인 입고시점준수 등 물류시간제약을 만족하고, 다른 화주의 화물과의 혼적을 통해서 유리한 조건으로 화물운송계약 의 체결이 가능해진다. 또한 화주는 계약된 화물트럭이 목적지를 향해서 정상적으로 운행중임을 확인할 수 있는 서비스를 받을 수 있다.

따라서 온라인 물류중개서비스기업 N사에서는 물류 네트워킹을 통한 물류와 운송수단에 대한 시간제약을 만족하도록 실시간 Map Navigation 기반의 할당 및 추적 을 위한 시스템 개발의 필요성을 느끼고 있으며 이를 위해 협력관계에 있는 물류트럭에 부착할 수 있는 GPS 단말기의 도입을 추진중에 있다. 이 중개서비스기업에 서는 이러한 시스템 도입을 통해서 위치정보를 바탕으 로 이동 소요시간 등을 고려하여 할당을 할 수 있고, 실 시간으로 화물차량과 화물의 위치정보를 파악하여 제공 할 수 있다. 즉, ICT 환경에서 Web 기반의 물류중개서 비스시스템을 통해서 화주와 화물트럭이 함께 이득을 얻는 것이 가능해지고, 중개서비스기업은 틈새시장의 발굴을 통해서 경쟁력을 유지할 수 있을 것으로 기대하 고 있다.

온라인 물류중개서비스 차별화를 위해 위와 같은 할 당문제를 풀기 위해서는 분산되어 있는 다수의 차고지로 부터 출발할 수 있는 트럭들과 분산되어 있는 다수의 화 주들의 화물을 픽업 및 수송하여 적시에 입고할 수 있도 록 트럭과 화물에 대한 시간제약을 고려한 최적 매칭을 제공할 수 있는 알고리즘을 개발하는 것을 요구된다. 즉, 제약조건을 포함하고 있는 운송요구를 만족시키는 운송 경로를 개발하기 위해서는 최적의 트럭 운송경로를 도출 해야 한다. 화주의 각 운송요구는 트럭의 출발 차고지에 서 출발하여 화물을 픽업하고 픽업된 화물의 정해진 배 달지에 정해진 시간구간에 운송을 마친 후 최종차고지에 트럭을 반환하는 경로를 구성하는 작업으로 볼 수 있다. 따라서 이러한 상황을 반영할 수 있는 수리모델의 개발 이 필요하다.

따라서 본 논문의 문제는 다수 지점에 분산되어 있는 차고지의 트럭과 다수의 지점에 분산되어 있는 화주의 화 물들에 대해 시간제약을 고려하여 혼적이 가능한 매칭을 한 후 정해진 픽업 지점에서 픽업을 하고 정해진 입고지 에 운송을 한 후 트럭의 도착차고지에 할당하는 문제로 볼 수 있다. 이 문제는 위에서 언급된 일반적인 PDP(Pickup and Delivery Problem)와는 달리 분산되어 있는 다수의 트 럭을 고려해야 하는 문제로 볼 수 있는데 이와 같은 요구 에 대응할 수 있는 대안 중 한 가지는 완벽하지는 않지만 Ropke와 Pisinger[12]에 의해 제안된 시간제약을 갖는 다 수 픽업 및 배송 문제(Multi Depot Pickup and Delivery Problem with Time Windows; m-PDPTW) 모델인데 본 연 구에서는 이 모델을 확장하여 적용한다.

본 논문은 다음과 같이 구성되어 있다. 먼저 제 2장에 서는 시간제약을 갖는 PDP 문제를 포함한 VRP(Vehicle Routing Problem) 문제를 다루었던 연구에 대해 알아본다. 제 3장에서는 Map Navigation 환경에서 획득된 정보를 이용한 m-PDPTW 수리모델링에 대한 내용을 다루고, 제 4장에서는 프로토타입 시스템 구현 및 사례연구를 통해 검증 및 활용가능성을 보여주고 있다. 마지막으로 제 5장 에서는 결론 및 추후 연구에 대해 언급하고 있다.

2. 관련 연구

일반적으로 General Pickup and Delivery Problem(GPDP) 문제에서는 트럭 터미널에서 출발한 운송트럭이 고객들 을 방문해서 트럭의 적재용량을 고려하여 화물을 싣고 중간에 환적작업 없이 목적지에 수송을 한 후 빈차로 도 착 터미널에 도착하는 경로 스케줄링 문제를 다루고 있 다[13]. 즉, 각 운송트럭은 적재용량, 출발 터미널, 도착 터미널이 정해져 있고, 고객들은 운송 신청시 화물의 무 게, 픽업 지점, 배송 목적지 등의 정보를 지정 한다. 따 라서 트럭의 적재용량을 고려하여 다수 고객의 화물을 픽업하여 다수의 목적지에 배송을 할 수 있다. 이러한 GPDP는 세 가지의 카테고리로 구분할 수 있는데 첫째, 픽업 및 배송문제(PDP)에서는 각 화물은 단일 출발지와 단일 목적지를 가지고 있으며, 모든 트럭들은 단일 중앙 터미널에서 출발하고 배송완료 후에 다시 중앙터미널로 돌아와야 한다. 둘째, Dial-a-Ride Problem(DARP)에서는 손님의 호출에 의해 손님을 목적지까지 태워주는 형태의 PDP를 의미하며, 합승을 허용하지 않는다. 셋째, Vehicle Routing Problem(VRP)에서는 모든 화물의 출발지 또는 도착지가 차량 터미널과 동일한 위치해 있는 PDP 문제 를 다룬다. 이 GPDP 경로설정 문제에서는 시간제약(time windows)을 고려하고 있지 못하고 있다.

경로설정 스케쥴링에 시간제약을 고려하는 연구, 특 히 Xu et al.[16]에서는 양립할 수 없는 상황제약을 고려 하는 등 현실적인 제약조건을 추가하려는 시도가 있었 고, Sigurd et al.[14]에서는 고객요구에 대한 픽업 우선순 위 제약을 추가하는 시도가 있었다. Lee와 Yu[7]에서는 구역별 클러스터링을 통해 복수 물류센터를 단일 물류 센터 문제로 전환하여 풀려는 시도가 있었다. 하지만 이 들의 연구에서는 문제 사이즈가 커질 때 이들을 적절한 시간동안에 어떻게 해결할 것인가에 초점이 맞추어져 있다고 볼 수 있다. Ropke와 Pisinger[12]는 시간제약을 갖는 Pickup and Delivery 문제를 해결하기 위한 포괄적 인 휴리스틱 기법을 제안하고 있는데 제한된 수량의 트 럭을 이용해서 다수 고객의 화물운송에 대한 경로설정 문제를 다루고 있다.

그리고 시간제약을 갖는 다수 차고지 다수 픽업 및 입 고 문제에 대해서 문제 사이즈가 커짐에 따라 해결이 어 려워지므로 휴리스틱을 이용하여 적절한 시간동안에 해 를 찾는 방법에 초점이 맞추어져 많은 연구들이 수행되 어 왔다[1, 2, 5, 6, 8, 9, 10, 11]. 따라서 본 연구에서는 입고구간을 맞추기 위한 현실적인 해를 제시하기 위해서 Map Navigation 시스템을 이용한 데이터 수집, 이를 기 반으로 수리모델 작성 및 할당, 운송 중에 경로상의 트럭 에 대한 모니터링을 위한 Map Navigation 기반의 혼적을 허용하는 온라인 물류 할당 및 모니터링 시스템을 제안 하고자 한다.

3. Map 기반의 시간제약을 고려한 운송경로 할당 모델링

온라인 물류중개기업인 N사의 문제는 여러 곳에 분 산되어 있는 차고지의 트럭들과 여러 곳에 분산되어 있 는 화주의 화물들에 대해 시간제약을 준수하면서 혼적 을 허용하는 할당을 한 후 정해진 픽업 장소에서 화물 픽업 및 정해진 배송지에 적시에 입고를 하고 트럭의 최종차고지에 도착하기 위한 해를 찾는 것으로 정의될 수 있다. 이 문제는 위에서 언급된 일반적인 PDP와는 달리 다수의 트럭을 고려해야 하고, 고객이 요구하는 시간제약을 엄수해야 하고, 현실적인 혼적허용을 위해 분산되어 있는 트럭의 위치도 동시에 고려해야 하는 문 제로 볼 수 있다. 이와 같은 요구에 대응할 수 있는 대 안 중 한 가지는 완벽하지는 않지만 시간제약을 갖는 다수 차고지 픽업 및 배송 문제(Multi Depot Pickup and Delivery Problem with Time Windows) 모델이며 본 논문 에서는 이 모델을 기반으로 본 연구에서 고려해야 하는 추가사항들을 반영하여 확장 및 적용하였다[12]. 적시 입고를 위한 시간제약 준수를 위해 Map Navigation 기반 으로 현실적인 데이터를 수집하여 할당 모델링에 활용 하였다. 즉, 트럭 출발차고지, 화물 픽업지점 및 배달지 점, 트럭 도착차고지를 모두 포함하여 지점간의 이동시 간을 고려하면서 혼적이 이루어질 수 있는 할당계획을 작성할 수 있도록 했다. 본 연구에서 활용하는 수리모델 은 아래와 같다 :

N : 화물픽업 및 입고지점 집합
K : 물류트럭 집합
n : 픽업 및 입고지점 갯수, n = |N|
m : 물류트럭 대수, m = |K|
P : 픽업지점 집합, P = {1, 2, .., n}
D : 입고지점 집합, D = {n+1, .., 2n}
τ_k : 트럭 k의 출발차고지 집합, {τ_k}= {2n+1, …, 2n+m}
τ_k′ : 트럭 k의 도착차고지, {τ_k ′ } = {2n+m+1, …, 2n+2m}
l_i : 픽업 및 입고할 화물 무게, $\begin{array}{l} l_{i} \geq 0 \forall i \in P; l_{i} = - l_{i - n}, \forall i \in D; \\ l_{i} = 0 \forall i \in {τ_{k}} \cup {{τ^{'}}_{k}} \end{array}$
a_i : 픽업/입고지점 i에 대한 가장 빠른 착수시간
b_i : 픽업/입고지점 i에 대한 가장 느린 착수시간
s_i : 픽업/입고지점 i에 대한 상하차 서비스시간
t_ij : map 상의 i, j지점 간 이동 소요시간
C_k : 트럭 k의 적재용량 $x_{i j k} = {\begin{array}{l} 1, & \begin{array}{l} 트점 k 방문하 i 는경우바로 \\ 트점 j 방문하는경우 \end{array} \\ 0, & 그외경우 \end{array}$
S_ik : 트럭 k의 지점 i에서의 서비스 시작시간
L_ik : 지점 i 방문 후의 트럭 k의 무게

수리모형 ( $| K | \geq | N |$ case)

min \sum_{k \in K} \sum_{i \in N \cup τ_{k} \cup {τ^{'}}_{k}, i \neq j} \sum_{j \in N} t_{i j} x_{i j k} + \sum_{k \in K} (S {τ^{'}}_{k} - a_{τ_{k}})

(1)

subject to(11)

\begin{array}{l} \sum_{k \in K} \sum_{j \in N} x_{i j k} = 1, & \forall i \in P \end{array}

(2)

\begin{array}{l} \sum_{j \in P \cup D} x_{i j k} - \sum_{j \in P \cup D} x_{n + i, j, k} = 0, & \forall k \in K, \forall i \in P \end{array}

(3)

\begin{array}{l} \sum_{j \in P \cup^{​} {τ^{'}_{k}}} x_{τ^{'}_{k} j, k} = 1, & \forall k \in K \end{array}

(4)

\begin{array}{l} \sum_{j \in D \cup {{τ^{'}}_{k}}} x_{i, {τ^{'}}_{k}, k} = 1, & \forall k \in K \end{array}

(5)

\begin{array}{l} \sum_{i \in P \cup D {τ_{k}}} x_{i j k} - \sum_{j \in P \cup D \cup {{τ^{'}}_{k}}} x_{j i k} = 0, \\ \forall k \in K, \forall j \in P \cup D \end{array}

(6)

\begin{array}{l} S_{i k} + s_{i} + t_{i j} - S_{j k} - M (1 - x_{i j k}) \leq 0, \\ \forall k \in K, \forall i \in N, \forall j \in N \end{array}

(7)

\begin{array}{l} a_{i} \leq S_{i k} \leq b_{i}, & \forall k \in K, \forall i \in P \cup D \cup {τ_{k}} \cup {{τ^{'}}_{k}} \end{array}

(8)

\begin{array}{l} S_{i k} \leq S_{n + i, k,} & \forall k \in K, \forall i \in P \end{array}

(9)

\begin{array}{l} L_{i k} + l_{j} - L_{j k} - M (1 - x_{i j k}) \leq 0, \\ \forall k \in K, \forall i \in P \cup D \cup {τ_{k}} \cup {{τ^{'}}_{k}} \end{array}

(10)

\begin{array}{l} L_{i k} \leq C_{k}, \forall k \in K, \forall i \in P \cup D \cup {τ_{k}} \cup {{τ^{'}}_{k}}, \\ \forall k \in K, \forall i \in P \cup D \cup {τ_{k}} \cup {{τ^{'}}_{k}} \end{array}

(11)

L_{τ_{k} k} = L_{{τ^{'}}_{k} k} = 0, \forall k \in K

(12)

식 (1)은 목적함수(objective function)를 나타내고 있으 며 지점 간 이동시간의 합과 서비스 참여시간의 합을 최 소화하는 최적할당 솔루션을 찾는 것을 목적으로 한다. x_ijk는 이진변수이기 때문에 목적함수는 현재 트럭위치 에서 화물픽업지점까지의 소요시간, 픽업지점에서 입고 지점까지의 소요시간, 입고지점에서 최종차고지까지의 소요시간 등 Map상의 Route에 대한 이동시간의 합과 서 비스 참여시간의 합을 나타내고 있다. 식 (2)는 모든 화 물은 반드시 픽업되어야 함을 의미한다. 하나의 화물픽 업을 수행한 후에 다른 화물픽업을 다시 수행하는 것은 허용된다. 여기서 전제조건은 트럭이 모든 요구를 커버 할 수 있을 만큼 충분히 많아야 함을 전제로 하고 있는 데 중개서비스기업의 입장에서는 고객으로 등록되어 있 는 화물트럭들을 충분히 확보할 수 있을 것으로 가정하 였다. 만일 트럭의 숫자가 너무 적어서 모든 운송요구를 커버할 수 없을 경우에는 운송요구에 대한 backlog 개념 등을 통해 이를 모델에 반영해야 한다. 식 (3)은 동일 차 량 k가 화물픽업 i를 수행 했으면 반드시 해당 목적지까 지 수송되어야 함을 의미한다. 식 (4)와 식 (5)는 각 차량 k는 출발위치(τ_k)에서 픽업지점까지의 경로가 설정되어야 하고, 수송목적지에서 다시 최종차고지(τ_k ′ )경로가 설정되 어야 함을 의미한다. 즉, 식 (4), 식 (5)를 통해서 모든 트 럭 k는 차량차고지에서 출발해서 정해진 최종 도착지로 반환되도록 경로가 설정된다. 식 (6)은 각 트럭 k에 대해 서 차량출발지(τ_k)와 최종차고지(τ_k ′ )를 연결하는 경로가 구성되어야 함을 의미한다. 이때 할당 받지 못한 차량은 차량출발지와 최종차고지 사이에 가상경로가 직결됨에 유의한다. 여기서 식 (4)~식 (6)은 차량출발지에서 최종 차고지를 연결하는 경로가 만들어져야 함을 의미한다. 식 (7)은 x_ijk가 1일 때 즉, 트럭 k가 픽업장소 i에서 수송 목적지 j로 경로가 설정될 때 노드 j에서의 작업시작시간 (S_jk)은 노드 i에서의 시작시간(S_ik), 노드 i에서의 서비스 시간(s_i), 노드 i에서 노드 j까지의 이동시간(t_ij)을 모두 합한 것보다 커야 함을 의미한다. 식 (8)은 픽업, 운송, 최초출발지, 최종차고지 지점에 대한 시간제약(time windows) 을 나타낸다. 식 (7)과 식 (8)을 통해서 S_ik값은 운 행경로를 따라 정확하게 결정되어야 하고 운송요구 i에 대한 시간제약을 만족해야 함을 의미한다. 이 두 식은 또 한 sub-tours를 방지하는 역할을 수행하고 있다. 식 (9)는 각 k에 대해 픽업노드(i)를 거치고 난 후에 해당 화물의 목적지를 거쳐야 함을 의미한다. 식 (10)은 x_ijk가 1일 때 즉, 트럭 k가 노드 i에서 노드 j로 경로가 설정될 때 노드 j에서 상하차 작업을 마친 후 트럭 k의 현재 무게 합(L_jk) 은 노드 i에서의 작업을 마친 후 트럭의 적재화물 무게 합(L_ik)과 노드 j에서의 적재한 화물 무게(l_j)를 합한 것 보다 크거나 같아야 함을 의미한다. 식 (11)은 모든 노드 i에서 작업을 마친 후의 트럭 전체 무게는 트럭의 적재 용량보다 작아야 함을 의미한다. 식 (12)는 트럭 k의 출 발차고지에서 출발할 때와 최종차고지에 도착할 때 빈차 상태 이어야 함을 의미한다.

<Figure 1>은 3개의 화물 픽업을 3대의 트럭을 이용하 여 할당하는 방법을 보여주고 있다. 화물 1(P1)은 가장 가 까운 위치에 있는 1번 트럭 (τ₁)에 의해서 픽업되어 운송 작업을 수행한 후 1번 트럭의 최종차고지에 도착되도록 할당된다. 화물 2(P2)와 화물 3(P3)은 가장 가까운 위치에 있는 2번 트럭(τ₂)에 의해서 혼적으로 픽업되어 각각의 목적지에 배달된 후 2번 트럭의 차고지에 도착하도록 할 당된다. 한편 3번 트럭의 경우 할당을 받지 못하고 최종 차고지로 가상경로가 설정되고 있음을 보여주고 있다.

4. Map Navigation 기반 최적할당 및 모니터링 시스템 구축

4.1 사례연구

본 논문에서는 분산되어 있는 7대의 화물차량이 분산 되어 있는 5개 화주의 화물을 픽업하여 수송한 후 도착차 고지로 반환되는 예제를 이용한다. <Figure 2>에서 index 1~5는 픽업장소, index 6~10은 각 픽업화물에 대한 입고 장소, index 11~17은 화물트럭의 현재위치, index 18~24는 도착차고지에 대한 GPS 위도 및 경도좌표를 보여주고 있다.

<Figure 3>은 화물트럭 및 화물의 시간제약 정보, 각 지점의 화물의 무게, 상하차 소요시간, 트럭적재용량 정 보의 일부를 보여주고 있다. 첫 번째 행은 각 지점을 의 미하며 두 번째와 세 번째 행은 트럭의 출발가능 시간구 간/ 화물픽업가능 시간구간, 화물도착요구 시간구간을 나타내고 있다. 네 번째 행은 각 지점에서의 화물상차 및 하차무게 증감을 나타내고, 다섯 번째 행은 각 지점에서 의 상하차 서비스 시간을 의미하며 마지막 행은 7대의 트럭에 대한 적재용량을 의미한다.

아래 그림들은 <Figure 2>의 위치정보를 이용해서 Map Navigation상에서 측정한 두 지점간의 소요시간 및 이동거 리 측정결과를 보여주고 있다. 즉, <Figure 4>는 두 지점간 의 이동시간을 보여주고 있고 <Figure 5>는 두 지점간의 이동거리를 보여주고 있다. 이와 같은 측정정보를 3장에서 도입한 수리모형에 적용하면 <Figure 6>과 같은 수리모형 을 만들 수 있다. 라인 1~5는 목적함수의 일부인데 라인 3에서 이진변수 x020801은 1번 트럭에 의한 2번 지점에서 8번 지점까지의 운송할당 변수를 의미한다. 따라서 이 운송이 할당되면 171분이 소요됨을 의미한다. 라인 7~44는 제약식 의 일부를 보여주고 있다. 라인 26에서 S1101과 S0101은 각각 1번 트럭의 11번 지점과 1번 지점에서의 시작시간을 의미하므로 1번 지점에서의 서비스 시작시간은 11번 지점 에서의 서비스 시작시간과 서비스 수행시간을 합한 것보다 커야 함을 의미한다. 라인 34는 상차, 하차 지점에서 트럭 무게를 업데이트 하도록 설정하고 있다. 즉, L0101이 1번 지점에서의 1번 트럭의 화물무게를 의미하므로 라인 34는 1번 지점을 떠날 때의 최종 트럭 무게를 설정한다. 이제 CPLEX Optimizer[4]를 이용하여 풀면 <Figure 7>과 같은 할당 해를 얻을 수 있다.

<Figure 7>의 결과를 해석하면 트럭 2, 3, 5, 7이 할당되 었고, 트럭 1, 4, 6이 할당되지 않았음을 보여주고 있다. 트럭 2의 경우에는 노드 12 차고지에서 출발하여 2번 지점 에서 화물 픽업 후 혼적을 하지 않고 7번 지점에 입고한 후 19번 최종차고지로 향하는 경로가 구성됨을 확인할 수 있다. 한편 트럭 5의 경우에는 혼적이 발생하는데 15번 트 럭차고지에서 출발, 1번 및 4번 지점에서 화물픽업 작업을 수행한 후 9번과 6번 지점에서 입고작업을 한 후 22번 최 종차고지로 향하는 경로가 구성되었음을 알 수 있다.

4.2 시스템 구축

본 연구에서 제안하고 있는 방법론에 대한 실현가능성 을 보여주기 위해서 Tmap 환경에서 Map Navigation 기 반의 할당 및 모니터링 시스템을 구현하였다. 수요기업 에서는 스마트폰 환경에서 중개서비스시스템을 사용할 수 있도록 Web 환경에서 실행이 가능하도록 요구하였다. 이를 반영하기 위하여 Web 인터페이스를 제공하기 위한 Javascript와 HTML, 정보관리를 위한 SQL Server 2017, 백엔드 로직구현을 위한 C#, Navigation 환경을 위한 이용 하기 위한 Tmap API[15] 등의 도구를 사용하였다. 그리 고 최적할당 수리모형의 모델링 및 해결을 위해서 Visual C++와 CPLEX Optimizer[4]를 각각 사용하였다.

<Figure 8>은 두 지점간의 시간과 거리를 Map 상에서 구하는 알고리즘을 보여주고 있다. 라인 1~4는 출발지점 과 도착지점의 위도와 경도 자료를 입력받는다. 라인 5~6은 Tmap API 사용을 위한 환경설정을 수행하며 라인 7~10은 Route Layer와 Marker Layer의 생성 및 이들을 map에 할 당하는 작업을 수행하고 있다. 라인 13~17은 http 프로토콜 에 대한 파라미터 설정을 하고 있고 라인 18~23에서는 http 프로토콜 실행 및 실행결과 분석을 통해 두 지점간의 소요시간 및 거리에 대한 정보를 XML 파싱을 통해 얻고 있다. <Figure 9>에서는 두 지점간의 거리 및 이동 소요시 간을 측정한 결과를 보여주고 있다.

<Figure 10>은 Map 상에 할당결과를 표시하여 모니터 링을 수행하는 알고리즘을 보여주고 있다. 라인 1~5는 경 도, 위도, 네트워크 노드의 개수를 위한 변수설정을 수행 하고 있다. 라인 7~12는 할당된 경로상의 노드정보를 설 정하고 있으며 라인 14~17은 Tmap에 표시하기 위한 경 도, 위도 정보를 설정하고 있다. 라인 19~45에서는 Tmap 인스턴스를 생성하여 맵상에 Route와 Marker Layer를 생 성해서 추가하고 http 프로토콜 호출을 위한 환경변수 설 정, http 프로토콜 실행 및 실행결과를 MAP 상에 표시해 주고 있다. <Figure 11>은 할당된 결과를 Map에 표시한 결과를 보여주고 있으며 <Figure 12>에서는 수송중인 트 럭에 대한 모니터링 상황을 보여주고 있다.

6. 결론 및 추후연구

본 논문에서는 Map Navigation 상에서 다수차고지에 분산되어 있는 화물트럭과 다수지점에 분산되어 있는 화 주의 화물들에 대해 화물도착지의 고객이 요구하는 도착 시간제약을 만족시키면서 혼적이 가능한 매칭을 한 후 운송중인 화물에 대한 실시간 모니터링을 지원하는 온라 인 물류중개서비스 지원시스템을 제안하였다. 고객이 요 구하는 시간제약을 만족하면서 혼적을 제공하기 위해서 는 다수차고지에 분산되어 있는 화물트럭, 다수지점에 분산 되어 있는 화물 및 입고지점에 대한 Map Navigation 기 반의 실시간 소요시간을 반영한 할당을 위한 수리모형을 작성한 후 최적화 도구를 이용해서 해를 구하고, 이를 Tmap 환경에서 모니터링 할 수 있는 시스템을 구현하였다. 본 논문에서는 실현가능성을 보여주기 위해 구현한 프로 토타입 시스템 환경에서 샘플데이터를 이용하여 할당작 업 및 모니터링 방안을 제시하였다.

추후 연구과제로는 m-PDPTW 모형의 경우 VRP 계열 수리모형의 특징으로 인해 NP-Hard 특성을 보일 수 있 으므로 이를 극복하기 위한 메타휴리스틱 기법의 적용이 필요할 수 있다. 둘째, 현재는 화물의 시간제약과 적재무 게 제약만을 고려하고 있지만 향후 화물의 부피, 형상 등 의 특성을 할당 수리모형에 반영할 필요가 있다.

Acknowledgement

This research was supported by Changwon National University in 2017~2018.

Figure

<Figure 1>.

Pickup and Delivery Allocation(Cargo = 3, Vehicle = 3 case)

<Figure 2>.

GPS information of Node

<Figure 3>.

A Part of Characteristics of Cargo and Truck

<Figure 4>.

A Part of Map based Time between Nodes

<Figure 5>.

A Part of Map based Distance between Nodes

<Figure 6>.

A Part of Map based Mathematical Model

<Figure 7>.

A Part of CPLEX Optimizer Results

<Figure 8>.

A Part of Algorithm for Calculation of Map based Time and Distance between Nodes

<Figure 9>.

Snapshot of Time and Distance Calculation between two nodes

<Figure 10>.

Algorithm for Calculation of Multiple Pickup and Delivery on Map

<Figure 11>.

Snapshot of Allocation Result on Map

<Figure 12>.

Snapshot of Truck Monitoring Example

Table

Reference

Bent, R. and Van Hentenryck, P., A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows, Computers and Operations Research, 2006, Vol. 33, No. 4, pp. 875-893.
Dumas, Y., Desrosiers, J., and Soumis, F., The pickup and delivery problem with time windows, European Journal of Operational Research, 1991, Vol. 54, No. 1, pp. 7-22.
Ha, H.G. and Kim, Y.J., The strategies to stimulate online marketplaces for freight exchange services, [Sejong,Korea] : The Korea Transport Institute, 2003.
IBM, IBM ILOG CPLEX Interactive Optimizer 12.8. 0.0, https://www.ibm.com/analytics/cplex-optimizer.
Kang, C.S. and Lee, J.S., A Heuristic for Fleet Size and Mix Vehicle Routing Problem with Time Deadline, Journal of Society of Korea Industrial and Systems Engineering, 2005, Vol. 28, No. 2, pp. 8-17.
Lau, H.C. and Liang, Z., Pickup and delivery with time windows : algorithms and test case generation, Proceedings 13th IEEE International Conference on Tools with Artificial Intelligence, 2001, pp. 333-340.
Lee, S.C. and Yu, J.C., Improved VRP & GA-TSP Model for Multi-Logistics Center, Journal of the Korea Academia-Industrial Cooperation Society, 2007, Vol. 8, No. 5, pp. 1279-1288.
Li, H. and Lim, A., A metaheuristic for the pickup and delivery problem with time windows, Proceedings 13^th IEEE International Conference on Tools with Artificial Intelligence, 2001, pp. 160-170.
Moon, G.J. and Hur, J.H., Development of an efficient vehicle routing heuristic by 2 Step advanced calculation,Journal of the Korean Institute of Plant Engineering, 2007, Vol. 12, No. 2, pp. 5-15.
Moon, G.J. and Park, S.M., A Possible Heuristic for Variable Speed Vehicle Routing Problem with 4 Time Zone, Journal of society of Korea Industrial and Systems Engineering, 2012, Vol. 35, No. 4, pp. 171-178.
Nanry, W.P. and Barnes, J., Solving the pickup and delivery problem with time windows using reactive tabu search, Transportation Research Part B Methodological, February 2000, Vol. 34, No. 2, pp. 107-121.
Ropke, S. and Pisinger, D., An Adaptive Large Neighborhood Search Heuristic for the Pickup and DeliveryProblem with Time Windows, Transportation Science, 2006, Vol. 40, No. 4, pp. 455-472.
Savelsbergh, M.W.P. and Sol, M., The General Pickup and Delivery Problem, Transportation Science, 1995, Vol. 29, No. 1, pp. 17-29.
Sigurd, M.M., Pisinger, D., and Sig, M., The Pickup and Delivery Problem with Time Windows and Precedences, Transportation Science, 2004, Vol. 38, pp. 197-209.
SK Telecom, Tmap API, http://tmapapi.sktelecom/index.html.
Xu, H., Chen, Z.L., Rajagopal, S., and Arunapuram, S., Solving a Practical Pickup and Delivery Problem, Transportation Science, 2003, Vol. 37, No. 3, pp. 347-364.