A Vehicle routing problem of demand responsive feeder service considering users' mode choice

Abstract

통신기술의 발달로 운영자와 이용자 사이의 소통이 가능해지면서, 수요대응형 대중교통 서비스가 확대되고 있다. 수요대응형 대중교통은 뛰어난 접근성으로 기존의 대중교통보다 더 고급 서비스를 제공하지만, 적은 재차인원과 높은 운영비용으로 인한 한계가 있다. 수요대응형 대중교통의 장점은 강화하고 단점을 극복하기 위한 대안으로 기존의 고속 대중교통과 공존하는, 접근 교통수단으로서의 수요대응형 대중교통 모형이 제시되었다. 관련 연구로 계획 차원에서 수요대응형 대중교통의 도입 여부나 한정된 환경에서 배차에 관한 연구들이 있었다. 최근의 모빌리티 산업의 또 다른 특징은 민간에 의해 주도되는 서비스가 많아지고 있다는 것이다. 다양한 서비스가 동시에 공급되면서 수단 간의 경쟁이 강화되고 있다. 따라서 대중교통 서비스의 운영적인 결정을 하는 과정에서 수단 간의 경쟁을 고려할 필요가 커지고 있다. 수요대응형 대중교통의 서비스를 위해선 다양한 수준의 운영 결정이 필요하다. 본 연구에서는 수요대응형 대중교통 서비스가 필요한 운영 결정을 승객들의 요청에 대한 응답 여부, 처리할 요청에 대한 배차 여부와 배차 차량 수, 각 차량의 경로 그리고 요금으로 나누었다. 이중에서 승객 효용에 직접적인 영향을 끼치며, 수요대응형 대중교통의 다른 운영을 결정하기 위해 필수적인 차량 경로 결정 문제에 집중하였다. 차량 경로는 이용자의 통행시간에 직접적인 영향을 주므로 경쟁 환경 하에서는 그에 따라 이용자의 해당 수단 선택 확률에 큰 변화를 준다. 따라서 본 연구에서는 경쟁환경 하에서 수요대응형 대중교통의 효과적인 경로를 설정하기 위해서는 수단선택 모형을 반영하는 것이 적합하다고 판단하였다. 복잡한 수단간 경쟁을 최적화 식에 반영하기 위해 문제상황을 좁힐 필요가 있었고, 다수의 승객들이 목적지를 공유하는 접근교통수단 서비스로 문제 상황을 설정하였다. 기존의 차량 경로 문제의 최적화 식에 수단선택 모형을 반영하기 위해 목적함수로 이용자의 선택에 의해 변화하는 값의 기대값을 이용하였다. 본 연구에서는 민간 운영자 입장에서 중요한 요소인 순이익과 공공 운영자 입장에서 중요한 요소인 총 통행시간 두가지 값을 적용하였다. 이용자의 수단 선택확률을 구하기 위해 이항로짓모형을 사용하였다. 구성된 최적화 문제를 풀기 위해 휴리스틱한 풀이법을 개발하였다. 초기해로 단순한 최단경로와 sweep-based clustering, away-first clustering 방법 3가지를 사용한다. 해를 개선하는 알고리즘을 구하기 위해 해석적 분석을 수행하여 4가지 해 개선 과정을 개발하였다. 실제 해는 3가지 초기해에 대해 4가지 해 개선 과정을 반복적으로 적용하여 변화가 없을 때 얻어진다. 구성된 문제와 풀이법을 검증하기 위해 테스트를 진행하였다. 테스트는 서울 근교의 동탄신도시의 교통 네트워크를 이용하여 임의로 발생시킨 수요에 대해 각 경로들의 이익 기대값들을 평가하였다. 평가 결과 단순 최단경로에 비해 해 개선 알고리즘을 적용한 결과 더 나은 결과를 얻을 수 있으므로 알고리즘의 타당성이 검증되었다. 초기해의 값에 따라 서로 다른 수요 분포에 대해 더 나은 해를 구할 수 있음이 확인되어, 다양한 초기해를 이용한 결과를 모두 합한 앙상블 모형이 가장 좋은 모형인 것으로 확인되었다. 구성된 문제와 알고리즘의 강건성을 평가하기 위해 수요와 차량의 대수를 바꾸어가며 민감도 검사를 진행하였다. 모든 경우에서 앙상블 모형이 최단거리 모형에 비해 월등히 나은 이익값을 보였으며, 이를 통해 각 환경별로 적합한 배차 전략을 구하는데 이 경로 결정 문제를 활용할 수 있음을 확인하였다. 다른 목적함수에 대한 확장성을 평가하기 위해 운영자의 순이익이 아닌 이용자들의 총 통행시간을 목적함수로 평가하였다. 평가 결과 운영자의 이익을 목적함수로 대입하였을 때에 비해 총 통행시간을 감소시키는 효과가 확인되었다. 연구 결과를 종합하면, 이용자의 선택확률을 반영한 목적함수의 기대값을 최대화 하는 최적화 문제 구성으로 현실의 경쟁상황을 반영한 최적화 문제를 구성할 수 있었으며, 해석적 분석을 바탕으로 그 풀이법을 개발하였다. 다양한 환경에 대한 테스트로 이를 검증하였으며, 그 결과를 이용하여 수요대응형 대중교통의 다른 결정문제에 활용할 수 있게 되었다.

As communication technology enables the communication between operators and users, demand-responsive public transportation services are expanding. Demand responsible transit (DRT) offers more advanced services than conventional public transport with better accessibility but has a limitation due to the low capacity and high operating costs. As an alternative to reinforcing the merits of the DRT and overcome the disadvantages, DRT that coexists with the existing high-speed public transport is proposed. As a related study, there were studies about the introduction of DRT at the planning level or dispatching in a limited environment. Another characteristic of the recent mobility industry is the increasing number of services driven by the private sector. The competition between transit modes is intensifying as various services are supplied at the same time. Therefore, there is a growing need to consider competition between modes in making operational decisions on public transport services. Various levels of operational decisions are needed for the DRT service. In this study, the operational decision requiring the DRT service was divided into the response of passengers' request, the allocation problem, the routing problem of each vehicle, and the pricing problem. Among these, it has a direct impact on passenger utility and focuses on the issue of vehicle routing, which is essential for determining other operational decisions of DRT service. The vehicle route has a direct impact on the user's travel time, so under competitive conditions, the vehicle route makes a large change in the probability of the user choosing the mode. Therefore, in this study, it was considered appropriate to reflect the mode choice model in order to establish an effective route of DRT in a competitive environment. It was necessary to narrow the problem situation in order to reflect the complex competition among the modes and set up the problem situation as a feeder service in which a large number of passengers share the destination. In order to reflect the mode choice model in the optimization formula of the existing vehicle route problem, the expected value of the value changed by the user's selection was used as the objective function. In this study, two values -net profit and total travel time- were applied. Both values were representing important factors for the private operator and the public operator each. To define the probability of the user's choice, the binary logit model was used. A heuristic solution method was developed to solve the formulated optimization problem. As the initial solution, the simple shortest route, sweep-based clustering, and away-first clustering are used. In order to find an algorithm that improves the solution, an analytical analysis was performed to develop four solution updating strategies. The solution was obtained when there was no change by repeatedly applying the four solution updating strategies for the three initial solutions. Numerical tests were conducted to verify the formulated problem and the solution method in the network of Dongtan district, planned city in suburban of Seoul. The profit expectations of each run were evaluated for randomly generated demand. As a result of the evaluation, the solution method was verified because better results could be obtained by applying the solution updating algorithm than the simple shortest route. It is confirmed that better solutions can be obtained for different demand distributions according to the initial solutions, and the ensemble model that combines the results using the various initial solutions is found to be the best model. Sensitivity tests were conducted to vary the demand and the number of vehicles to evaluate the robustness of the formulated problem and the solution method. In all cases, the ensemble model showed significantly better profits than the simple shortest route model, and it was confirmed that this vehicle routing problem considering user choice could be used to find a suitable allocation strategy for each environment. In order to evaluate the scalability of the problem to other objective functions, the total travel time of users was used as the objective function, not the net profit of the operator. As a result of the evaluation, it was found that the effect of reducing the total travel time was bigger than when the operator's profit was used as the objective function. It proves that the problem and the solution method can also cover the routing problem to reduce the total travel time. In conclusion, an optimization problem that reflects the competitive situation by constructing an optimization problem that maximizes the expected value of the objective function that reflects the user's choice probability was formulated. A solution method based on analytical analysis was developed. This has been verified by testing in various environments, and the results can be used for other decision-making problems in designing DRT service.