동적 차량경로 문제에 대한 분산 알고리즘

• 영문명: A Decentralized Coordination Algorithm for a Highly Dynamic Vehicle Routing Problem
• 발행기관: 한국산업경영시스템학회
• 저자명: 이반스 소와 옥포티(Evans Sowah Okpoti) 정인재(In-Jae Jeong)
• 간행물 정보: 『산업경영시스템학회지』제42권 제4호, 116~125쪽, 전체 10쪽
• 주제분류: 경제경영 > 경영학
• 파일형태: PDF
• 발행일자: 2019.12.30

영문 초록

The Dynamic Vehicle Routing Problem (DVRP) involves a combinatorial optimization problem where new customer demands become known over time, and old routes must be reconfigured to generate new routes while executing the current solution. We consider the high level of dynamism problem. An application of highly dynamic DVRP is the ambulance service where a patient contacts the service center, followed by an evaluation of case severity, and a visit by a practitioner/ ambulance is scheduled accordingly. This paper considers a variant of the DVRP and proposes a decentralized algorithm in which collaborators (Depot and Vehicle), both have only partial information about the entire system. The DVRP is modeled as a periodic re optimization of VRP using the proposed decentralized algorithm where collaborators exchange local information to achieve the best global objective for the current state of the system. We assume the existence of a dispatcher e.g., headquarter of the company who can communicate to vehicles in order to gather information and assigns the new visits to them. The effectiveness of the proposed decentralized coordination algorithm is further evaluated using benchmark data given in literature. The results show that the proposed method performed better than the compared algorithms which utilize the centralized coordination in 12 out of 21 benchmark problems.

목차

1. Introduction

2. Literature Review

3. Problem Description

4. Decentralized Architecture

5. Experimental Results

6. Conclusion

키워드

Decentralized Coordination Collaborative Decision-Making Dynamic Vehicle Routing