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.

최적화 분야에서는 VRP(Vehicle Routing Problem)에 대한 많은 연구가 오래전부터 이루어져 왔다. 기본적인 VRP 모형을 확장하여, 단일차고지와 다수차고지 특성, Pickup and Delivery 특성, Time Windows 특성 등을 고려하여 다양한 모형들을 도출되고 있으며 이들에 대한 보다 나은 해를 구하는데 초점이 맞추어져 왔다. 이들 VRP 모형들은 노드 수의 증가에 따른 NP-Hard 특성을 가지고 있기 때문에 최적화에 초점을 맞추기 보다는 Genetic Algorithms, Tabu Search, Simulated Annealing 등의 메타휴리스틱 기법 등을 이용하여 적용할 수 있는 우수한 해를 도출하려 노력을 기울이고 있다. 본 연구에서는 시간제약을 가지는 Multi-Depot Pickup and Delivery 모형을 이용하여 3자물류 기업에서 물류 트럭의 할당 및 이들에 대한 운영 상황 모니터링을 지원할 수 있는 시스템 개발에 초점을 맞추고 있다. 본 연구에서는 먼저 수요기업의 요구사항을 반영하여 가장 중점을 두고자 하는 혼적이 가능하고 시간제약을 반영한 해를 도출하고자 했으며 도출된 해를 기반으로 물류를 트럭에 할당한 후 물류 트럭에 대한 GPS기반의 모니터링 시스템을 제안하고자 한다.