本文主要是介绍如何写代码实现VRP问题中车辆容量限制及时间窗要求（python），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题研究背景
使用遗传模拟退火算法求解如下10个卸货点的VRPTW问题。为了使研究的问题更加有意义，本人将时间限理解为服务点一天的具体可以允许配送的时间。 如果不要求车辆从配送中心出发的时间是统一的并且为0时刻，那么就默认第一个配送节点是一定能赶到的。采取从配送中心出发的时间不为0时刻的策略，默认一定能达到第一个配送点，所以采用最早到达时间推算车辆出发的时间。
假设配送中心营业时间是早上七点至晚上七点，即配送中心也有最早和最晚时间窗要求，车辆配送货物应该满足这个发车即回到配送中心的最晚时间限制。卸货点１－１０的时间限制理解如下：卸货点１要求在下午１点至下午４点配送，卸货点１要求的服务时间是半个小时；卸货点２要求在下午４点至下午６点配送，卸货点２要求的服务时间是１个小时，以此类推其他的卸货点的配送及服务时间限制。算法中用到配送及服务时间是下午的情况，例如卸货点1可转成数字表示是[13,16]。
配送点的需求货物量如下：
配送点的达到时间窗及服务时间如下：
代码编码思路
取染色体，依次判断染色体的基因是否满足车辆载重量及时间窗限制条件，染色体基因片段如果不满足两者，则默认为一条路线，在中间插入配送中心节点0.
考虑是否可以写两个独立的函数，先判断车辆的载重量限制，再前面生成的解再次寻优判断是否满足时间窗限制。
编写代码过程中遇到的错误
从配送中心出发立即回到配送中心
chrom [10 1 5 2 3 6 4 9 7 8]
*******000******
*******000******
routes [[0, 0, 0]]当首次配送的需求点为卸货点10时，最早到达时间要求是下午5点，配送中心开门是上午七点，关门是下午七点，两点之间的路径长度是160公里，车辆每小时的车速是40公里/小时，所以最佳的方案是不考虑先去卸货点10完成配送任务，因为车辆返回时赶不上配送中心的关门时间。
一些其他的错误
opulation [[ 7 6 1 2 9 3 4 5 8 10][ 3 2 5 10 7 4 6 8 1 9][ 4 6 8 7 1 9 5 3 2 10][10 5 7 2 6 4 3 9 8 1][ 9 7 10 8 2 1 4 5 3 6][ 5 10 9 3 6 1 2 4 8 7][ 5 6 2 7 3 10 9 4 8 1][ 2 9 1 3 10 8 6 4 5 7][ 7 3 1 6 2 10 9 8 4 5][10 4 5 9 6 7 3 2 1 8][ 2 4 3 5 8 6 7 1 10 9][ 9 2 6 8 3 1 5 4 10 7][10 2 9 5 1 4 6 3 8 7][ 4 9 5 2 6 1 10 3 8 7][ 7 4 6 8 9 10 3 2 1 5][10 1 4 9 6 2 3 5 7 8][10 9 5 4 3 2 8 1 7 6][ 7 3 8 1 10 5 4 2 9 6][ 3 9 10 4 6 7 5 2 1 8][ 5 10 3 6 4 7 9 1 2 8][ 5 7 3 6 1 2 4 9 10 8][ 3 9 1 10 5 4 2 7 6 8][10 7 1 2 5 8 6 9 4 3][10 6 8 2 9 7 4 5 1 3][ 4 2 7 1 9 3 10 5 8 6][ 7 4 5 8 1 3 9 6 10 2][ 4 1 7 5 9 2 3 10 8 6][ 5 3 1 10 8 9 7 6 4 2][ 7 3 4 5 9 6 8 1 10 2][ 4 2 5 10 1 9 6 7 8 3][ 1 6 4 2 10 7 3 8 9 5][ 9 4 3 6 8 10 2 1 7 5][ 4 7 2 3 9 10 1 5 6 8][ 5 6 10 8 9 7 2 1 3 4][ 8 3 9 1 6 5 4 10 7 2][ 5 7 4 9 3 8 10 1 2 6][ 7 2 9 1 6 5 4 10 3 8][ 6 10 4 5 8 7 1 3 9 2][ 9 5 10 8 3 6 7 2 1 4][ 5 6 3 10 4 9 8 7 1 2][ 7 1 8 6 2 3 9 5 10 4][ 9 1 8 7 4 3 2 6 10 5][ 7 3 2 10 1 6 4 9 8 5][ 5 9 6 3 7 2 8 4 1 10][ 1 2 4 7 8 5 3 6 9 10][ 3 7 2 1 6 10 5 9 4 8][ 7 5 9 3 8 4 10 2 1 6][ 5 6 8 10 9 3 7 4 1 2][ 3 9 7 6 5 2 10 1 4 8][ 3 4 2 7 1 9 8 5 10 6]]
chrom [ 7 6 1 2 9 3 4 5 8 10]
*******000******
total_path_list [[0, 7, 6, 0], [0, 1, 2, 9, 0], [0, 3, 0], [0, 4, 5, 8, 0], [0, 10, 0]]
node 2
node 3
new_chrom [2, 3, 0, 9, 0, 0]
*******000******
total_path_list [[0, 0, 9, 0]]
new_chrom [9]
*******000******
total_path_list [[0, 9, 0]]
node 9
new_chrom [9]
routes [9]cannotbe_firstnode_served [4, 5, 7, 10]
*******000******
total_path_list [[0, 5, 1, 2, 0], [0, 10, 0], [0, 4, 6, 0], [0, 3, 0], [0, 7, 8, 0], [0, 9, 0]]
path_list [0, 5, 1, 2, 0]
path_list [0, 10, 0]
path_list [0, 4, 6, 0]
path_list [0, 3, 0]
path_list [0, 7, 8, 0]
path_list [0, 9, 0]
new_chrom [3, 9, 5, 10, 4, 7]
*******000******
total_path_list [[0, 10, 0], [0, 4, 0], [0, 5, 0], [0, 7, 0]]
total_path_list [[0, 2, 3, 0], [0, 4, 5, 0], [0, 6, 7, 0], [0, 8, 9, 0], [0, 10, 0], [0, 1, 0]]
path_list [0, 2, 3, 0]
path_list [0, 4, 5, 0]
path_list [0, 6, 7, 0]
path_list [0, 8, 9, 0]
path_list [0, 10, 0]
path_list [0, 1, 0]
feasible_node_list [2, 3, 6, 8, 9, 1]
not_feasible_node_list [4, 5, 7, 10]
new_chrom [2, 3, 6, 8, 9, 1, 4, 5, 7, 10]Process finished with exit code 0
函数代码
修改卸货点的时间窗，增加求得时间窗+车辆载重量约束限制的可行解概率。
车辆容量限制的代码见本博主的博文《【纠错】遗传算法求解VRP计算车辆容量限制的代码有bug》，时间窗要求的函数如下：
def time_window_restraint(total_path_list):# 先求解车辆容量限制，再计算时间窗限制，硬时间窗限制# 如果不要求车辆从配送中心出发的时间是统一的并且为0时刻，那么就默认第一个配送节点是一定能赶到的# 采取从配送中心出发的时间不为0时刻的策略，默认一定能达到第一个配送点，所以采用最早到达时间推算车辆出发的时间# 假设配送中心营业时间是早上七点至晚上七点# 先排除算例无解的场景，即配送中心开门时间都不能实现派车辆运输的场景print("total_path_list", total_path_list)not_feasible_node_list = []feasible_node_list = []feasible_path_list = []for i in range(len(total_path_list)):path_list = total_path_list[i]arrive_time = demand_time_window[0, path_list[1]]leave_time = arrive_time + demand_service_time[path_list[1]]if path_list[1] in cannotbe_firstnode_served:not_feasible_node_list.extend(path_list[1:-1])else:# 默认第一个服务点的时间窗一定是满足要求的if len(path_list) == 3:# 返回配送中心的时间back_center_time = leave_time + travel_time_graph[path_list[-2]][0]if back_center_time > dis_center_open_time[1]:not_feasible_node_list.append(path_list[-2])else:# 只有一个配送节点的场景feasible_node_list.append(path_list[-2])else:feasible_node_list.append(path_list[1])if len(path_list) == 4:before_node = path_list[1]cur_node = path_list[2]arrive_time = leave_time + travel_time_graph[before_node][cur_node]if (arrive_time < demand_time_window[0, cur_node]) or (arrive_time > demand_time_window[1, cur_node]):# 不可行解# 判断是否加入不可行解集合if before_node in feasible_node_list:feasible_node_list.remove(before_node)not_feasible_node_list.append(before_node)not_feasible_node_list.append(cur_node)else:not_feasible_node_list.append(cur_node)else:leave_time = arrive_time + demand_service_time[cur_node]# 返回配送中心的时间back_center_time = leave_time + travel_time_graph[cur_node][0]if back_center_time > dis_center_open_time[1]:# 判断是否加入不可行解集合if before_node in feasible_node_list:feasible_node_list.remove(before_node)not_feasible_node_list.append(before_node)not_feasible_node_list.append(cur_node)else:not_feasible_node_list.append(cur_node)else:# 判断是否加入可行解集合if before_node in not_feasible_node_list:not_feasible_node_list.append(cur_node)else:feasible_node_list.append(cur_node)else:remain_node_list = path_list[2:-1]for index in range(len(remain_node_list)):cur_node = remain_node_list[index]if len(remain_node_list) == 1:before_node = remain_node_list[0]else:before_node = remain_node_list[index-1]arrive_time = leave_time + travel_time_graph[before_node][cur_node]if (arrive_time < demand_time_window[0, cur_node]) or (arrive_time > demand_time_window[1, cur_node]):# 不可行解# 判断是否加入不可行解集合if before_node in feasible_node_list:feasible_node_list.remove(before_node)not_feasible_node_list.append(before_node)not_feasible_node_list.append(cur_node)else:not_feasible_node_list.append(cur_node)else:leave_time = arrive_time + demand_service_time[cur_node]if cur_node == path_list[-2]:# 返回配送中心的时间back_center_time = leave_time + travel_time_graph[path_list[-2]][0]if back_center_time > dis_center_open_time[1]:# 判断是否加入不可行解集合if before_node in feasible_node_list:feasible_node_list.remove(before_node)not_feasible_node_list.append(before_node)not_feasible_node_list.append(cur_node)else:# 判断是否加入可行解集合not_feasible_node_list.append(cur_node)else:# 判断是否加入可行解集合if before_node in not_feasible_node_list:not_feasible_node_list.append(cur_node)else:feasible_node_list.append(cur_node)else:# 判断是否加入可行解集合if before_node in not_feasible_node_list:not_feasible_node_list.append(cur_node)else:feasible_node_list.append(cur_node)new_chrom = []if len(feasible_node_list) > 0:for node in feasible_node_list:new_chrom.append(node)if len(not_feasible_node_list) > 0:for node in not_feasible_node_list:new_chrom.append(node)not_feasible_node_flag = Trueelse:not_feasible_node_flag = Falseprint("new_chrom", new_chrom)return not_feasible_node_flag, feasible_node_list, new_chrom
def get_feasible_route(chrom):# 先判断是否满足车辆最大载重量限制cur_chrom = copy.deepcopy(chrom)not_feasible_node_flag = Truecount = 0while not_feasible_node_flag:# 先用得到满足车辆载重量的函数切出可行解路径print("*******000******")total_path_list = vehicle_capacity_restraint(cur_chrom)# 再使用时间窗判断是否路径也是满足时间窗要求的not_feasible_node_flag, feasible_node_list, new_chrom = time_window_restraint(total_path_list)print("not_feasible_node_flag", not_feasible_node_flag)if not_feasible_node_flag:print("*******001******")cur_chrom = new_chromcount += 1else:print("*******003******")return vehicle_capacity_restraint(new_chrom)if (count > 1) and (cur_chrom == new_chrom):return vehicle_capacity_restraint(new_chrom) # 使用函数切出路线
算法迭代示意图
遗传算法迭代图如下：
连续两次运行程序，得到的目标值相同，下面图2比上图1在100代左右就寻找到了结果：
事不过三，连续三次，目标值开出来的都是478
这篇关于如何写代码实现VRP问题中车辆容量限制及时间窗要求（python）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
