师欣欣，陈树国，马 弘，邓明荣

(1.浙江大学管理学院，浙江 杭州 310058；2．国网浙江省电力有限公司，浙江 杭州 310007;3.浙江大学工程师学院，浙江 杭州 310015)

1 引言

伴随着互联网经济的蓬勃发展，网上购物成为人们消费活动的重要组成部分，国内对快递的配送需求也呈现爆发式增长态势。2019年，中国快递服务企业业务量累计完成630亿余件，其中农村快递增速比城市高近10个百分点[1]。支线镇际的快递配送是影响配送整体效率和服务水平的重要环节，快递的大规模和高时效性特点为支线镇际配送问题提出新的要求和挑战。与此同时，随着新能源汽车在续航、充电时间等方面的表现日益提升，将电动汽车引入支线镇际快递配送成为可能，并将有助于物流行业绿色经济的发展。本文主要对电动汽车在城镇快递配送中的路径规划进行研究，并提出与之相适应的分支定价算法求解该问题。

本文以支线镇际快递配送系统为研究对象，给定运营周期内城镇之间的快递配送需求，要求结合电动车辆自身属性，决策车辆的行驶路径和充电地点及时长，在满足所有运输需求的前提下，最小化总运输成本。由于Kerivin等[2]证明了SPDPR问题(the Splittable Pickup and Delivery Problem with Reloads)的复杂度为NP-hard，本文的研究问题较SPDPR问题附加考虑了多种车型以及电动车辆的相关特性，使得SPDPR问题成为了本文研究问题的一个特例，因而本文研究问题的复杂度亦为NP-hard。

已有的与城际、镇际快递配送应用相关的研究，大多围绕启发式算法和智能优化算法展开。……