Multi-agent System for the decentralized dynamic vehicle routing problem

Abstract

The Dynamic Vehicle Routing Problem (DVRP) describes a combinatorial optimization problem where new customer orders appear over time, and new routes must be reconfigured while executing the current solution. An abundant literature on DVRP is available. However, most of these papers assume a centralized approach in their solution methods. This paper presents a Multi-Agent system approach to model and solve the DVRP. This research considers a common variant of the DVRP, decentralized in nature, in which the agents (Depot and Vehicle), both have only partial information about the entire system. This approach involves separating the arc-flow formulation of the Capacitated Vehicle Routing Problem (CVRP) into a Linear Assignment Problem (LAP) with an associated Travelling Salesman Problem (TSP). One particular feature of this heuristic is that, it will always find a feasible solution if one exists, which may not be guaranteed in a general decentralized approach. The effectiveness of the proposed heuristic is further evaluated using a set of benchmark data found in literature. The results shows that the proposed method performed better than the Genetic Algorithm based method which is centralized in 9 out of 21 benchmark problems.|동적 차량 경로 문제는 시간이 지남에 따라 새로운 고객이 발생하고 이를 기존의 차량 경로에 반영해야 하는 문제이다. 많은 기존의 문헌들이 동적 차량 경로 문제에 대해 중앙 통제 식 해법을 적용하고 있다. 본 연구에서는 동적 차량 경로 문제에 대한 에이전트 기반 해법을 제시한다. 에이전트기반 해법에서는 디포와 차량으로 구성된 에이전트가 전체 문제에 대한 부분적인 정보만을 가지고 문제를 해결하는 상황을 가정한다. 제안된 에이전트 기반 해법은 용량제한이 있는 차량 경로 문제의 호-흐름 제약을 완화한 선형할당 문제와 TSP 문제를 에이전트간에 반복적으로 풀어 정보를 교환함으로써 최적화된 해를 찾도록 한다. 제안된 방법의 중요한 특성 중 하나는 기존의 분산화된 접근방식과 달리 알고리즘의 실행 과정에서도 항상 가능해를 보장한다는 점이다. 제안된 방법의 효율성을 입증하기 위하여 벤치마크 문제를 풀어서 대표적인 중앙통제식 접근방식인 유전자 알고리즘과 비교하였다. 그 결과 21문제 중 9문제에서 제안된 방법이 좋은 해를 찾았다.; 동적 차량 경로 문제는 시간이 지남에 따라 새로운 고객이 발생하고 이를 기존의 차량 경로에 반영해야 하는 문제이다. 많은 기존의 문헌들이 동적 차량 경로 문제에 대해 중앙 통제 식 해법을 적용하고 있다. 본 연구에서는 동적 차량 경로 문제에 대한 에이전트 기반 해법을 제시한다. 에이전트기반 해법에서는 디포와 차량으로 구성된 에이전트가 전체 문제에 대한 부분적인 정보만을 가지고 문제를 해결하는 상황을 가정한다. 제안된 에이전트 기반 해법은 용량제한이 있는 차량 경로 문제의 호-흐름 제약을 완화한 선형할당 문제와 TSP 문제를 에이전트간에 반복적으로 풀어 정보를 교환함으로써 최적화된 해를 찾도록 한다. 제안된 방법의 중요한 특성 중 하나는 기존의 분산화된 접근방식과 달리 알고리즘의 실행 과정에서도 항상 가능해를 보장한다는 점이다. 제안된 방법의 효율성을 입증하기 위하여 벤치마크 문제를 풀어서 대표적인 중앙통제식 접근방식인 유전자 알고리즘과 비교하였다. 그 결과 21문제 중 9문제에서 제안된 방법이 좋은 해를 찾았다.