关键词: 垃圾分类, 自适应大邻域搜索, 车辆路径问题, 多车型多车厢

Abstract: With the vigorous development of China’s economy, the steady progress of urbanization, and the rapid increase in the urban population, municipal solid waste (MSW) has also increased at an alarming rate. Due to incomplete classification, untimely collection and transportation, unreasonable utilization, and improper disposal, serious environmental pollution and economic losses have been incurred. Comprehensively implementing the classified waste recycling policy is an inevitable measure to handle this difficulty during the urban development. According to statistics, the costs of collection and transportation account for more than one half of the total waste treatment costs. In this context, optimally scheduling the vehicles to collect and transport MSWs so as to reduce the cost has important theoretical and practical significance for improving the efficiency of MSWs cleaning, environmental pollution reduction and the garbage classification policy implementation.
Based on the investigation into the current status of MSW classification and transportation in China, in this paper, a heterogeneous vehicle joint collection strategy by coupling single-carriage and homogeneous multi-carriage fleet for classified municipal solid waste collection is proposed. A general heterogeneous vehicle routing problem with multi-carriage (HVRP-MC) in the MSW joint collection and transportation is thus studied. Given a set of MSW storage nodes and a fleet of heterogeneous capacitated vehicles installing one or multi-carriage with each compartment can load only one type of MSW, the HVRP-MC is to determine the optimal assignment of MSW to vehicle and its route so that each vehicle used departs from and returns to the depot. Each type of MSW at each storage node is collected by one vehicle without exceeding the maximum capacity of the corresponding carriage. The objective of the problem is to minimize the total transportation costs and set up costs of vehicles. A hybrid heuristic based on greedy algorithm is applied to obtain an initial solution. Then, an adaptive large neighborhood search (ALNS) is proposed to further improve the initial solution to achieve near optimal solutions. Based on the feature of the HVRP-MC, we develop some problem specific destroy operators and repair operators to improve the performance of the classical ALNS.
Numerical experiments on various instances with different scale and proportion of type of MSW, as well as MSW storage nodes geographical distribution mode modified from Solomon’s data sets are generated to evaluate the performance of the proposed approaches. Computational results indicate that the proposed approach is very effective in solving the HVRP-MC,especially for those random clustered distribution instances with distinct residential distribution characteristics. In addition, the proposed method is good at achieving the optimal solution, and the computational time spent in solving the problem increases linearly with the size of the instance. Compared with the traditional single-carriage and homogeneous multi-carriage fleet for classified MSW collection strategies, the proposed heterogeneous vehicle joint collection demonstrates great advantage in reducing transportation costs.
The research provides a new strategy and effective approach for the logistics network construction of classified MSW cleaning, which has important theoretical significance and application value for the construction of the “Wild China” national policy. In this research, we use Euclidean distance as distance measure. However, in realistic transportation scenarios, we also need to consider the factors such as time windows and road conditions, which may be closer to reality, and which provide new research directions for future study.

Key words: waste classification, adaptive-large-neighborhood search, vehicle routing problem, multi-vehicle and multi-carriage