In this dissertation, the validity of the vehicle system handling multiple part types is to be verified, and the policy is to be advanced. In the circumstance where vehicle system handling only a single part type is generally used, this study is conducted from discussions on the need for a vehicle system handling multiple part types. The problem situation is approached as a vehicle routing problem, and dynamic vehicle routing problem with multiple types of demand that the demands occur in time according to a Poisson process is studied. The objective of this study is to minimize the sum of waiting time of demands. In addition, studies about vehicle routing problems so far generally address only one type of demand, but this study addresses the problem with multiple types of demand. Therefore, the vehicle scheduling policy should be established in consideration of the knapsack problem, one of the combinatorial optimization problems.
In this dissertation, the decision-making process of the dynamic vehicle routing problem is formulated by the Markov decision process (MDP). Based on the formulated model, dynamic programming (DP) determines vehicle scheduling policy, and the policies obtained are analyzed to provide insights for solving this problem.
본 학위 논문에서는 복수 유형의 부품 수요를 다루는 차량 시스템의 타당성을 검증하고, 그 정책을 고도화시키고자 한다. 일반적으로 단일 유형의 부품만을 다루는 차량 시스템이 사용되고 있는 상황에서, 복수 유형의 수요를 다루는 차량 시스템의 필요성에 대한 논의에서부터 본 연구는 진행된다. 문제 상황을 차량 경로 문제로 접근하여, 복수 유형의 수요를 가지며 수요가 푸아송 분포를 따라 발생하는 동적 차량 경로 문제를 연구한다. 본 연구에서는 수요의 대기 시간의 합을 최소화하는 것을 목적으로 하고 있다. 또한 복수 유형의 수요를 가지는 문제를 다루고 있기에 조합 최적화 문제의 하나인 배낭 문제를 고려하여 차량 스케줄링 정책을 수립하여야 한다.
본 학위 논문에서는 동적 차량 경로 문제의 의사 결정 과정을 마르코프 의사 결정 과정으로 수립한다. 수립된 모델을 기반으로 동적 계획법을 이용해 차량 스케줄링 정책을 결정하고, 얻어진 정책들을 분석하여 본 문제의 해결에 대한 아이디어를 제공한다.
