摘要：针对日益严峻的城市汽车尾气污染问题和日趋严格的城市限行措施，本文首次将城市分区域、分车型等限行因素引入到车辆路径问题，并以碳排放、运输等费用总成本最小为目标，构建了基于城市道路限行的多能源多车型混合车辆路径优化模型。针对该模型是NP难问题，本文提出了一种变邻域搜索算法(VNS-TR)求解该模型。最后，通过算例和基准测试集验证了模型及算法的有效性。

关键词：车辆路径问题；多能源；多车型；城市道路限行；碳排放；变邻域搜索

The Multi-energy Heterogeneous Feet Vehicle Routing Optimization under urban Traffic Restriction

Abstract: In the paper, considering the increasingly heavy vehicle emission pollution and strict traffic restriction regulations in urban areas, various traffic restriction factors, such as the traffic restriction regions differed by the energy types and carrying capacity of vehicles, are initially introduced to vehicle routing problem. Regarding minimizing cost of carbon emission and transportation as objectives, the multi-energy heterogeneous feet vehicle routing problem under traffic restriction is proposed. Since the proposed problem is NP-hard, a variable neighborhood search algorithm (VNS-TR) is developed to solve it. Finally, the results of a numerical example and benchmark instances demonstrate the effectiveness of the model and algorithms.

Key words: Vehicle routing problem; Multi-energy vehicle; Heterogeneous Vehicles; Carbon Emission; Urban Traffic Restriction; Variable neighborhood search

引言

城市配送是保障和改善民生的重要领域，是保障城市经济社会正常运行的基础支撑，也是电商物流“最后一公里”的关键。城市物流车辆的配送路径是否合理、车辆结构配置是否高效，不仅直接关系到城市物流企业的物流成本、配送效率及服务水平，也直接影响城市道路拥堵、城市环境污染等民生问题。此外，随着城市规模的不断增大，以及电子商务消费经济向产品和服务的个性化发展，城市配送和交付需求呈现出较强的动态性和多样性，大规模的城市车辆配送路径优化也变得越来越复杂。因此，深入探讨和研究城市车辆路径优化问题具有重要的理论意义和现实价值。

近年来，虽然我国城市物流的专业化水平、配送效率等得到不断提升，但城市道路拥堵仍较严峻，城市配送车辆“通行难”等问题依然较为突出。为缓解日益严峻的交通拥堵压力，上海、北京、天津等城市相继推出分区域、分车型等措施来限制城市配送车辆通行，传统的车辆路径优化方法已不能满足城市限行措施下的新要求。因此，研究当前限行措施下的城市车辆配送路径优化问题显得非常重要。此外，为改善日益严峻的城市车辆尾气污染问题，越来越多的电动汽车、混合动力汽车等新能源汽车被应用到城市物流配送中，但由于受电池续航能力不足、充/换电配套设施不健全等因素限制，未来较长一段时间，新能源车和传统能源车将同时并存应用于城市配送，如何高效配置低碳背景下的配送车辆结构也已成为政府、行业、学者等共同关注的热点。