考虑多行程与同时取送货的电动车路径问题研究

Solving an Electric Vehicle Routing Problem with Multi-Trip and Simultaneous Pickup and Delivery by Column Generation

针对城市物流配送中的电动车辆路径优化问题,考虑电动汽车的充电特性以及车辆多行程和需求点的双向货流,以最小化车辆成本、行驶成本和充电成本为目标,建立考虑多行程与同时取送货的电动车辆路径问题(EVRPMTSPD)模型,并采用列生成算法进行求解.为提高子问题求解速度,提出了基于蚁群算法的启发式寻路算法用以处理较大规模问题,数值实验验证了模型与算法的有效性,表明了考虑多行程和同时取送货能有效降低成本和提高效率.

In urban transportation,the company need to consider not only the demand from the depot to the customer,but also the needs of reverse logistic,which complicate the problem.In this paper,we introduce a rich Vehicle Routing Problem which considered both the challenge of electric vehicle and the reverse logistic.In order to solve the problem,we apply the column generation algorithm and an ant-colony-based shortest path algorithm to speed up the sub-problem.By a case study,we prove the feasibility of the problem and the algorithm.