基于电动汽车的带时间窗的路径优化(Python&Matlab代码实现）

1 概述

(1）本文结合电动汽车的特点构建了以总配送成本最小为目标的带有惩罚函数的基于电动汽车的带时间窗的车辆路径优化问题（VRPTW ）模型。
(2)对求解车辆路径优化问题的各种方法进行比较之后，本文采用遗传算法，设计了适合求解本文模型的染色体编码方式和遗传算子。算例分析结果验证了模型及算法的有效性。

2 数学模型描述

2.1 有容量约束的路径问题模型

问题描述
某配送中心为各个已知客户点进行配送服务。配送中心的每辆配送车辆都有装载能力的限制。安排科学合理的车辆行驶路线，使一定数量的配送车辆从配送中心出发，完成配送任务后返回配送中心。路线规划的目标是配送成本最小。

2.2 带时间窗的车辆路径问题基本模型

(1)带时间窗车辆路径问题的描述

带时间窗的车辆路径优化问题(Vehicle Routing Problems with Time Windows，VRPTW)是以上文所述的经典的车辆路径优化问题为基础。在此基础上，新增了每个客户点都有物流配送时间的限制。我们称客户点的时间限制为时间窗。

3 算例及代码实现

3.1算例介绍

某物流配送中心为25个客户点提供配送服务，每个客户的货物需求量、时间窗不同。配送中心拥有3辆同一类型的电动汽车，其续驶里程dis为160km，额定载重量Q为5t。假设电动汽车进入充电站就选择充满电，充电时间为0.4h;假设电动汽车从配送中心出发的时间为0h，且在配送过程中的行驶速度恒定为40 km/ h。电动汽车的行驶成本为10元/km，惩罚成本系数epu为20元/h，lpu为30元/h。算例的其他数据在表5.1中列出。表3.1中的第一列数据代表配送中心、客户点及充电站的编号，0代表配送中心，1,2,3,…,25代表客户点,26,27代表充电站;第二列和第三列分别表示配送中心、客户点、充电站的X坐标和坐标，
本文假定客户之间的距离为欧氏距离;表中第四列表示客户点的货物需求量;第五、六列分别表示客户要求的服务时间窗;第七列表示客户点需要服务的时间。如何安排车辆才能使得总费用最小。

                                             表3.1客户需求信息

 

图3.2表示的是算例中配送中心、客户点及充电站的位置分布，其中圆圈“O”表示配送中心，圆点表示客户点，三角“△”代表充电站。

           

 

                        图3.2配送中心、客户点及充电站的位置分布

3.2 Python代码

if __name__ == "__main__" ：    genes = getRandomGenes(geneNum) # 初始种群    # 迭代    for i in tqdm(range(generationNum)):        updateChooseProb(genes)        sumProb = getSumProb(genes)        chosenGenes = choose(deepcopy(genes))   # 选择        crossedGenes = cross(chosenGenes)   # 交叉        genes = mergeGenes(genes, crossedGenes) # 复制交叉至子代种群        genes = vary(genes) # under construction    # sort genes with respect to chooseProb    key = lambda gene: gene.fit    genes.sort(reverse=True, key=key)   # 以fit对种群排序    print('\r\n')    print('data:', genes[0].data)    print('fit:', genes[0].fit)    genes[0].plot() # 画出来

3.3 Matlab代码实现

代码写得差不多了，就是有少许有问题，也不想继续调试了。

3.4 结果

  

Python代码为问题，完美：

100%|██████████| 3000/3000 [01:21<00:00, 36.65it/s]


data: [0, 13, 27, 5, 6, 2, 22, 23, 25, 21, 0, 7, 19, 11, 10, 8, 18, 0, 1, 20, 9, 3, 12, 26, 4, 15, 14, 16, 17, 24, 0]
fit: 9.991184414431451e-08

4 代码实现