탄소배출을 고려한 이기종 기간차량경로 문제: 수학적 모형 및 알고리즘

Abstract

This study proposes a multi-period extension of heterogeneous fixed fleet vehicle routing with carbon emission, which is the problem of determining the routes of heterogeneous vehicles according to customer service combinations in each period of a planning horizon while satisfying customer demands and vehicle capacities. The objective is to minimize the sum of vehicle operation costs and carbon emission cost/benefit over the planning horizon, where the carbon emission cost/benefit is obtained from purchasing/selling the carbon emission right. To represent the problem mathematically, a mixed integer programming model is proposed. Then, a tabu search algorithm is developed that incorporates the characteristics of heterogeneous and period vehicle routing problems while considering the amount of carbon emission. Computational experiments were done on modified benchmark instances and randomly generated test instances, and the results show that the multi-period model proposed in this study gives better solutions than the existing single-period model in overall average. In particular, we show from the test results that the multi-period model reduces the amount of carbon emission more significantly than the single-period model without sacrificing the total cost.