Abstract: Currently, the national government is vigorously supporting the construction of modern logistics service system, especially for the agricultural and commercial products such as tea, fruit and seafood. Importance has been gradually attached to satisfying the differentiated requirements of different goods and lowering the loss during transportation. In this paper, the different needs of goods distribution conditions are considered. Some types of goods should avoid being transported with specific goods while they can be transported with most of other non-specified goods. Therefore, high-quality logistics services need the cooperation of route strategy, service strategy and vehicle charging strategy. The problem is formulated as an integer programming model. A two-phase Tabu Search-modified Clarke and Wright Savings heuristic(MCWTS)and a four-phase heuristic called IGALNS are proposed to solve the problem. Compared with the MIP solver of CPLEX on small-size instances, these heuristics can solve the problem within a shorter computing time and get reasonable solutions. Then, we systematically make a parameter analysis of this problem. The distribution distance of the classified transportation surpasses the reference model which does not take classified distribution into account. However, this model can avoid improper mixed transportation in a vehicle on condition that the transportation distance is slightly increased. If the potential cost caused by goods damage is calculated into the total cost, the cost of the unclassified transportation will be higher than the classified transportation. Thus, using classified goods distribution service strategy on the basis of the attributes of goods is not only beneficial to reducing the potential operating costs of enterprises, but also can help improve service quality and enhance the market competitiveness of enterprises. Furthermore, we conduct a series of experiments with a set of existing vehicle routing problem instances to evaluate and demonstrate the effectiveness of the two proposed algorithms

Key words: electric vehicles, cargo category, Clarke and Wright saving heuristic, adaptive large neighborhood search, battery swapping strategy

摘要： 电动汽车参与的物流配送服务需要统筹协调车辆路径、配送对象与换电策略。本文提出了考虑货物分类需求的电动汽车路径优化与换电策略问题,并建立了该问题的整数规划数学模型。其次,提出了基于禁忌搜索-改进节约算法的两阶段混合启发式算法MCWTS和一种四阶段启发式算法IGALNS。通过多组小规模算例验证了算法的有效性。随后,分别从运营成本、路径距离、换电策略以及混合运输线路等方面比较并分析了货物分类对运营策略的影响。实验结果表明,该模型可以在配送距离略有增加的情况下避免将不适宜混合运输的货物指派给同一车辆,达到降低货物运输损失提高顾客满意度的目的。最后,通过多组较大规模算例对两种启发式算法的有效性进行了比较。

关键词: 电动汽车, 货物分类, 节约算法, 自适应大邻域搜索, 换电策略