关键词: 车辆路径问题, 混合车队, 城市限行, 混合启发式算法

Abstract: In the past few years, the problem of environmental pollution in cities has become more and more serious, and the sustainable development of cities has received more and more attention. In order to alleviate the impact of urban logistics and distribution pollution on the urban environment, most city governments have implemented traffic restriction policies to limit pollution from the source. However, the long-term regional restriction leads to the obstruction of logistics transportation, which greatly reduces the efficiency of logistics operation and increases the cost of logistics transportation.
In order to address this, this paper sets up quantifiable regional access costs, so as to restrict the passage of trucks and at the same time more accurately measure the cost of transportation. At the same time, a mixed fleet is introduced to construct a mixed fleet routing optimization study considering the zone entry fee. This problem is an extension of the multi-vehicle fleet routing optimization problem. A distribution routing model is constructed with the objective of minimizing the sum of vehicle fixed cost, operation cost, zone entry fee and carbon emission cost to evaluate the optimal choice of urban distribution vehicles and distribution paths. The problem is described as follows: there are several distribution centers, and each distribution center has two types of transportation vehicles: traditional oil vehicles and electric vehicles. There are sufficient vehicles of each type in each yard. Different types of vehicles serve the customer points from each distribution center. Meanwhile, due to the battery limitation of electric vehicles, the trams will go to the charging station for recharge when they have insufficient power during the distribution process, and they will continue to perform the distribution task when they are fully charged. The total amount of customer demand in each sub-path does not exceed the vehicle load, and the vehicle returns to the nearest distribution center after completing the task. The innovation of the problem is to construct a new cost type to measure the cost of urban distribution more accurately under regional traffic restrictions.
According to the characteristics of the problem, a hybrid ant colony heuristic algorithm is designed for solving the problem, in which a decentralized search algorithm is used to optimize the initial solution and improve the solution performance of the ant colony algorithm. The steps of the algorithm are as follows: (1)The diversity initial solution is constructed by K-means clustering and improved scanning algorithm. (2)The optimal solution under the current clustering is solved using the improved ant colony algorithm. (3)Decompose the current optimal solution according to the decentralized search to generate new clusters for solving, and cycle sequentially until the stop condition is satisfied. In order to check the effectiveness of the algorithm, several MDVRP benchmark experiments are set up to let Gurobi, MACO and this paper’s algorithm be compared and analyzed, and the results show that this paper’s algorithm is significantly better than Gurobi, and can be used to solve this paper’s model.
Finally, combined with the case of an enterprise’s logistics and distribution network in the city, the simulation obtains the distribution routing results before and after considering the zone entry fee, and carries out a Fosensitivity analysis of the size of the restricted area and the zone entry fee. The experimental results show that: reasonable consideration and setting of zone entry fee in the city can greatly increase the utilization rate of EVs in the mixed fleet, and at the same time significantly reduce the carbon emissions; in cities with different restricted zones, the larger the restricted zone is, the more obvious is the impact of zone entry fee, and the more customer points and charging piles there are in the restricted zones, the more obvious is the impact of zone entry fee. The utilization of electric vehicles increases as the cost of regional access increases, and the total cost of zone entry fee increases and then decreases until all electric vehicles are used instead of oil vehicles.

Key words: vehicle routing problem, mixed fleet, traffic restrictions, hybrid heuristic algorithm