커플링 에이전트들의 상호작용을 이용한 다수차량 이동경로문제

Abstract

본 연구는 차량이동경로 문제에서 단일 디포에이전트를 다수의 분산된 차량에이전트들이 공유하고 있는 분산 환경하에서 서비스 시간을 고려하는 용량 제약 차량 이동경로 결정문제(Capacitated vehicle routing problem with service time; CVRPST)를 다루기로 한다. 분산 환경하의 차량에이전트들은 지역적 목적함수와 capa를 가지고 있다. 또한 이런 분산 환경에서 어떤 차량에이전트들도 전체 시스템의 완전 정보를 알 수 없고, 부분정보만 알고 있다고 가정한다. 각 분산 차량에이전트들과 디포에이전트는 독립적인 의사결정 권한을 가진다. 본 연구는 분산된 차량에이전트들간의 최소한의 부분정보 공유 및 교환을 통해서 최적해에 가까운 귀환경로(return arc)에 대한 고려가 없는 전체 차량 이동경로를 찾기 위한 분산 환경하의 의사결정 방법론을 제시 하려고 한다. 제안된 분산 에이전트 알고리듬은 Lagrangian Relaxation 방법을 이용한 Cooperative Interaction via Coupling Agent를 기초로 하고 있다. 제안된 해법은 CVRPST해법인 유전 알고리듬으로 해결된 해와 비교한다. 실험 결과 제안된 해법의 해가 유전 알고리듬으로 해결된 솔루션의 해에 근접함을 보여주었다.