城市生活垃圾收运路线优化的数学模型与算法

Mathematical Model and Algorithm for Route Optimization of Municipal Domestic Waste Collection and Transportation

给出了城市生活垃圾收运路线优化问题的一般描述,考虑时间窗、车容量等约束,以收运路线总行程最短为目标,建立了该优化问题的数学模型。设计了求解该问题的单一组合邻域搜索算法,随机邻域搜索算法和变邻域搜索算法三种类型的邻域搜索算法。通过对多组算例的求解实验,结果表明变邻域搜索算法的优化效果明显优于其余类型的邻域搜索算法。

This paper provides a general description of the problem of route optimization for municipal domestic waste collection and transportation. With the consideration of constraint such as time window, vehicle capacity and etc. , a mathematical model for the optimization problem which minimize the total travel distance is presented. Three types of neighborhood search algorithm which are single combinational neighborhood search, stochastic neighborhood search and variable neighborhood search（VNS） are designed to solve the problem. The results of computational tests show VNS algorithm has a significant superiority compared with other algorithms.