考虑工作量平衡的餐饮垃圾多行程收运路线优化

Multi-trip Food Waste Collection Routing Optimization with Workload Balance

城市餐饮垃圾的收运成本居高不下,严重阻碍了垃圾分类的推进。本文首先根据餐饮垃圾的产生及收运特点,划分不同的收运时段和频率,以均衡各个时段的收运量。其次,将城市餐饮垃圾的收运问题建模为带有时间窗的多行程车辆路径问题,并考虑驾驶员的工作量平衡约束。对于小规模问题,通过求解所建立的混合整数规划模型得到问题的最优解;对于大规模问题,针对多车多行程的问题特点,设计三维矩阵编码,提出混合自适应大邻域搜索算法。通过不同规模的算例验证了模型的正确性和算法的有效性。算例结果表明,增加不超过2%的收运成本能大幅度提高驾驶员之间的工作量平衡性。最后,采用大连市中山区的实例将本文所提算法与实际应用的优化算法进行比较发现,当使用不同的收运频率并考虑工作量平衡及城市路网的交通拥堵情况时,采用本文所提出的算法能降低14.3%的收运成本,减少12.7%的碳排放量,同时,将驾驶员之间的工作平衡性提升57.3%。

The high cost of food waste collection restricts the implementation of waste separation management in the cities.This study determined the time periods and collection frequencies to balance the workload of food waste collection for each time period based on the amount and distribution of the wasted food.The study then modeled the problem as multi-trip vehicle routing problem with time windows and considered the drivers'workload balance.The mixed integer programming model was solved to obtain the optimal solution for the small-size problems.The threedimensional matrix code and the hybrid adaptive large neighborhood search algorithm(HALNS)for multi-trip vehicle routing was used to solve the large-size problems.Five different numerical examples were used to test the mathematical model and the HALNS algorithm.It was found that when considering workload balance constraints,the imbalance of workload among different truck drivers could be improved significantly with less than 2%cost increases.Then,the proposed method was applied in a real case in Dalian of China.The solutions obtained by the HALNS were compared to the existing waste collection optimization tool.The results showed that the collection route obtained by HALNS could reduce collection costs by 14.3%,decrease carbon emissions by 12.7%and improve the balance of driver workloads by 57.3%.