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

摘要： 降低城市生活垃圾分类清运成本是有效推进垃圾分类制度的关键。基于对城市生活垃圾分类清运现状的调研,本文研究了多车型多车厢车辆混合清运路径问题,构建了研究问题的混合整数规划数学模型,以优化清运车辆的装载以及行驶路径,从而极小化总清运成本。针对研究问题的特性,设计了适合垃圾分类清运问题的摧毁算子以及修复算子,提出了自适应大邻域搜索算法,以获得问题的近似最优解。参考我国各类城市生活垃圾的数量及相对比例,生成了不同规模以及服从不同分布规律的仿真算例,并进行了大量的算法测试以及结果分析。结果表明,混合车队清运模式较之当前的联合清运模式,能更有效地降低清运成本,而所提出的自适应大邻域搜索算法可在合理时间内获得高质量的近似最优解,满足实际清运需求。本研究丰富了垃圾清运系统的研究体系,为城市生活垃圾分类清运提供了有效的方法和技术支撑。

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