[논문 리뷰] Introduction to The Dynamic Pickup and Delivery Problem Benchmark - ICAPS 2021 Competition

Introduction to The Dynamic Pickup and Delivery Problem Benchmark

Introduction to The Dynamic Pickup and Delivery Problem Benchmark -- ICAPS 2021 Competition

ICAPS는 International Conference on Automated Planning and Scheduling 컨퍼런스로 플래닝과 스케쥴링을 다룹니다.
물류 환경에서 라우팅과 스케쥴링 문제 해결을 위한 데이터 세트 정의와 시뮬레이터 제작을 목적으로 다루었습니다.

 

관련 자료

깃허브에는 논문에 기술된 데이터 세트와 시뮬레이터를 포함합니다.

https://github.com/huawei-noah/xingtian

Abstract

화웨이의 DPDP 대회를 위한 데이터세트와 시뮬레이션에 대한 설명입니다.

Dynamic Pickup and Delivery Problem은 동적 상태의 물품 픽업 후 배달 라우팅 문제를 다룹니다 VRP(Vehicle Routing Problem)에 시간 제약사항, 차량의 용량 제약사항이 추가되었으며, 실시간으로 변동되는 오더를 처리한다는 점에서 이를 Dynamic 문제라 부릅니다. 오더가 계속 추가되지 않는 상황은 반대로 Static이라 부릅니다.

 

지금까지는 DPDP 문제를 푸는 연구자들은 주로 복잡한 실제 세상 문제의 복잡성을 반영하지 못한 가상의 데이터를 사용해왔습니다. 이에 연구자들이 실제 데이터를 활용하여 성과를 낼 수 있는 대회를 개최하였습니다. 이 논문은 대회에 사용된 시뮬레이터와 데이터 소개합니다. 실제 화웨이 공장의 픽업앤 딜리버리 데이터를 소개하고 스케쥴링과 플래닝을 평가할 수 있는 화웨이의 시뮬레이터를 소개합니다.

Introduction

화웨이 공장

화웨이에서는 불확실한 고객 요구사항과 제조 프로세스때문에 사전에 딜리버리 요구사항을 완전히 결정하지 못했습니다. 실제 화웨이 공장에서는 Delivery Order가 무작위로 생성되고 이 오더를 처리하기 위해 차량들에게 주기적으로 스케쥴링되고 있습니다. 이때 Deliver order의 정보는 집품 공장, 배달할 공장, 화물의 수, 시간 요구사항이 담겨있습니다.

실제 현실에서는 알고리즘의 작은 향상으로도 큰 효율을 낼 수 있기에, 향상된 차량 라우팅과 오더 배분 최적화 알고리즘이 필요했습니다. 그래서 이 대회를 개최하였으며 이를 위해 데이터 세트와 알고리즘 평가를 위한 시뮬레이터를 공개하였습니다.

 

화웨이의 데이터세트는 다음과 같은 특징을 보입니다. 

• 30일 기간 동안의 데이터 세트. 하루당 2000 - 5000 오더, 100 - 200 차량.
• 차량의 적재량을 초과하여 여러 차량으로 분배해야하는 데이터도 존재. 

시뮬레이터는 다음과 같은 특성을 가집니다.

• 계획 기간(하루치 혹은 기타)에 대한 알고리즘 퍼포먼스 측정.
• 하루 = 144개의 인터벌, 1개의 인터벌 = 10분.

Benchmark description

Introduction to DPDP

알고리즘은 다음의 기능을 수행해야합니다.
1. 화물을 시작 공장에서 목표 공장까지 옮기는 Task가 있을 때, 이를 수행할 차량 선택하는 것.
2. 차량의 경로를 선택하는 것.

DPDP Formulation and Evaluation

DPDP는 input, output, constraint, objective로 구성됩니다.

INPUT

• 로드 네트워크 G(유향 그래프)
  • F는 Node(Factory) 집합 $\{F_i | i = 1, ... ,M \}$
  • A는 Arc 집합 - $A = \{(i,j) | i,j \in M \}$
    • 여기서 arc는 i와 j사이의 $d_{ij}$거리(음이 아닌 값)와 소요시간 $t_{ij}$와 관련있는 값.
      $$ G = (F,A) $$
• Order Set O
  • 주문 집합 O
    $$ O = \{ o_i| i = 1, ... , N\} $$
  • Order는 픽업노드, 딜리버리노드 ,화물의 양, 생성시간, 배달 종료 시간으로 구성됨.
    $$ o_i = (F_p^i, F_d^i,q^i, t^i_e,t^i_l) $$
    • $F_p^i$는 픽업 노드, $F_d^i$는 딜리버리 노드
    • $q^i$는 화물의 양으로 다음과 같다. $q^i = (q^i_{standard}, q^i_{small},q^i_{box})$
    • $t^i_e,t^i_l$는 각각 오더별 생성시간과 목표 소요 시간이다. 화물 전달 소요시간에는 차량 이동시간, 도킹 접근 시간, 로딩/언로딩 시간, Dock Queuing time이 포함된다.
    • 화물의 크기는 Standard 팔레트 == 2 small 팔레트, 1 small 팔레트 == 2 Box와 같다.
• 차량 V
  • 차량은 동일한 종류이다. 각 차량 $v_k$는 loading capacity와 운전수의 work shift(근무 시간)와 관련됨.
    $$ V = \{ v_k | k = 1,...,K\} $$
• 공장 노드 M
  • 각 공장은 유한한 수의 로딩, 언로딩을 수행하는 화물 도크와 근무 시간 제한 존재.
  • 모든 도크가 사용된다면, 다른 화물들은 빌 때까지 기다려야함.
  • 로딩 언로딩 운영은 반드시 근무 시간에 수행되어야함.
    $$ \{F_i = 1, ... , M \} $$
• Docking approaching time
  • 공장 도착부터 도크를 할당받을 때까지 걸린 시간.
• Loading and unloading time
  • q는 스탠다드 화물의 양
  • Loading time $t_p = w \times q$
  • Unloading time $t_d = w \times q$ , $w = 180 second/standard \ pallet,$

Ouput

• 오더 할당 계획 & 각 차량의 route
  • $v_k$ 차량에 대한 Route 플랜
    $$ \Pi_k =\{ n^k_1,n^k_2,n^k_3,..., n^k_{l_k} \} $$
  • $n^k_i$ k차량이 방문해야할 i번째 공장.

Constraints

DPDP문제에 대한 제약사항입니다.

• 모든 Order는 수행할 것.
• 목표 완료 시간 충족할 것. 만약 그렇지 못하면 패널티 비용이 발생.
• 오더 분할. 오더 분할은 로딩 capacity를 초과할 경우에만 수행가능.
  • Smallest unit of order는 분할이 되지 않는다.
• 차량의 로딩 capacity.
  • 화물은 차량의 최대 용량Q를 초과할 수 없다.
• 운전수의 근무 시간
  • 예) 8:30 ~ 12:00, 13:30 ~ 18:00
• Last In First Out 로딩 제약사항
  • o1($F_p^1, \ F_d^1$) 오더와 o2 오더($F_p^2, \ F_d^2$)를 순서대로 받았을 때, 반드시 route 플랜은 $\{F_p^1, F_p^2,F_d^2, F_d^1\}$순으로 수행해야함.
  • $\{F_p^1, F_p^2,F_d^1, F_d^2\}$는 LIFO 제약사항을 어긴것이다.
• 한정된 공장의 화물 도크 수
  • 예로, F1 노드의 화물 도크가 3개고 차량 4대가 도착했으면, 마지막 차량은 하나의 도크가 가능 상태로 바뀔때까지 대기해야한다.
• 로딩, 언로딩 업무는 먼저 온 차량이 할 수 있도록 한다.
  • 혹시나 동시에 여러대가 도착하고 도크가 1개밖에 없다면, 이때는 무작위 차량에 도크를 할당한다. 실제 현실에서는 일어날 일이 거의 없지만, 시뮬레이션에서는 존재할 수도 있다.

Objectives

최적화하고자하는 목적함수는 Total timeout of Order 최소화와 차량 평균 이동 거리 최소화입니다.

• Total timeout of order
  • $a_d^i$는 도착 시간, $t_l^i$는 목표 완료 시간이다. N은 총 오더의 수이다.
    $$ f_1 = \sum_{i=1}^N\max(0, a^i_d - t^i_l) $$
• 차량의 평균 이동 거리
  • 만약 $v_k$가 $\Pi_k = \{ n^k_1,n^k_2,n^k_3,... n^k_{l_k} \}$ route plan을 가졌다면,
  • d는 i와 i+1 까지의 거리
  • k는 $v_k$차량
    $$ f_2 = \frac{1}{K}\sum_{k=1}^K \sum {i=1}^{l_k-1}d{n_l^k, n^k_{i+1}} $$
• Overall objective
  • 여기서 $\lambda$는 꽤 큰 양의 상수입니다. 화웨이는 $f_1$최적화를 원합니다.
    $$ \min f= \lambda \times f_1 + f_2 $$

Utilization of the Benchmark

데이터 세트에 관하여

데이터 세트는 오더, 차량, Route map, 공장 정보를 포함됩니다.

• 오더 - 오더에 대한 정보
  
• 차량 - 차량 용량에 대한 정보와 운용시간 정보
  
• Route map - 거리와 이동 시간 정보
  
• 공장 정보- 도크 갯수 등
  

시뮬레이터에 관하여

시뮬레이터에서 하루는 10분씩 144개의 인터벌로 구성되어있으며, 각 인터벌은 10분입니다.

• 시뮬레이터의 플로우 차트
  

  

• 스케줄링 알고리즘과 시뮬레이터의 상호작용 방식
  1. 시뮬레이터가 차량, 오더 데이터를 내놓는다.
  2. 알고리즘이 동작하며 오더 분배 결과를 내놓는다.
  3. 그 결과가 나오게 되면, 시뮬레이터가 검증작용을 하고 통과가 되면 다음 라운드때 시뮬레이팅한다.
• 오더 할당
  • 차량 v가 공장 f에 도착했을 때, v에 대한 픽업 앤 딜리버리 리스트가 즉각적으로 생성된다.
  • 알고리즘은 픽업 앤 딜리버리 리스트에 없는 품목만 차량을 바꾸어 재할당할 수 있다.
  • 알고리즘은 차량의 수용량이 초과하지 않는다면, 오더를 분할할 수 없다는 것에 유의해야한다.
  • 알고리즘은 오더 방출 시기를 제어할 수 있다. 만약 A오더가 t1시간에 생성되었다면, 알고리즘은 t2≤ t1 + 4h에 한하여 지연시킬 수 있다.
  • 이동거리와 이동시간은 오로지 행렬 테이블에서만 얻을 수 있다. 위도로 계산하면 안된다.
  • 시뮬레이터가 차량 상태를 t1 시간에 알고리즘에 전달하고, t2시간에 알고리즘이 할당 결과를 시뮬레이터가 전달한다고 할 때 그 시간이 오래 걸렸다면, t2시간 때 차량의 상태가 엄청나게 달라질 수도 있다.

Related works

DPDP는 VRP의 변형 문제로서 NP 하드 문제입니다. DPDP는 VRP과 대비하여 차량 용량 문제, LIFO 제약, Time window 제약(시간 제약), 용량 분할 조건 같은 추가적인 복잡성이 있습니다.
일반적으로 DPDP를 풀기 위해 다음의 2가지 방식을 많이 사용합니다. Exact methods(Exact Algorithm) 과 Heuristic methods 입니다.

대표적인 Exact Methods는 다음의 것이 있습니다.

• Brute Force 알고리즘: 모든 가능한 해를 열거하고, 최적의 해를 찾습니다.
• Backtracking 알고리즘: 가능한 해를 탐색하는 과정에서 조건을 만족하지 않는 해를 제외하고, 최적의 해를 찾습니다.
• Branch and Bound 알고리즘: 상한과 하한을 이용하여 해공간을 축소하면서 최적해를 찾습니다.
• Dynamic Programming : 작은 문제를 풀어 큰 문제를 해결하는 방식으로, 중복되는 부분 문제를 피함으로써 최적해를 찾습니다.

Exact Methods는 알고리즘들은 모든 가능한 해를 고려하고, 그 중 최적의 해를 결정하게 됩니다.이는 많은 시간 소요되며 큰 데이터는 처리하기 힘듭니다. Heuristic methods는 문제를 빠르게 해결하는데 초점을 맞추며, 정확한 최적해 대신 근사해를 찾습니다.

다른 시도들도 존재하는데, 미래의 오더 분포를 예측하는 방식으로 풀어 여러 서브 문제를 생성하여 최적화를 시도하기도 하고 강화학습, 딥러닝 적용하여 DPDP를 푸는 방식을 시도하기도 합니다.

 

강화학습에서는 Upper level 에이전트, Lower level 에이전트로 나누어 문제를 해결하는데, Upper-level는 주어진 정적 문제에 대해 lower-level에 오더 release를 결정하고, Lower level에서는 오더 할당과 차량 라우팅 계획하는 역할을 수행합니다.

DPDP 대회 요약

대회 참가자들은 휴리스틱, 딥러닝, 강화학습 등 많은 알고리즘들을 사용하였습니다. 하지만 우수한 퍼포먼스를 보인 상위 3팀은 휴리스틱 메서드로 문제를 해결하였습니다.

• 1위 - Variable Neighborhood Search Method
  • 여러 차량의 경로 계획 간 노드 순서를 지속적으로 교환
  • 하나의 경로 계획에서 주문 순서를 계속 교환하여 최적화
• 2위 - 임계값 체크 관점에서 알고리즘 개발
  • 배송 시간과 차량 용량의 임계값에 도달했는지 확인하여 주문을 할당
• 3위 - 도킹 시간에 대한 추가 최적화 목표 설정
  • 미할당 주문의 급한 순위를 기반으로 특정 규칙을 생성하여 스케쥴링 진행

수상자의 발표 내용은 다음 유튜브를 참고하세요.
https://www.youtube.com/watch?v=SL-iBAQTJKM