VRP问题

一、关于vrp问题

车辆路径问题，可以看成旅行商问题的推广

有N辆车，都从原点出发，每辆车访问一些点后回到原点，要求所有的点都要被访问到，求最短的车辆行驶距离或最少需要的车辆数

Thinking：有哪些应用领域，适用于VRP问题

快递公司，给司机分配送货线路 拼车软件，为司机分配接送乘客的路线

常见的限制要求： 车辆具有可携带的最大重量或数量

司机需要在指定时间窗口内访问某位置 点的访问顺序等

二、VRP问题的流程：

使用RoutingModel进行路径规划管理

1）设置城市个数，车辆数，起点下标

2）设置距离回调函数 distance_callback

3）设置初始可行解算法 PATH_CHEAPEST_ARC，从start节点开始，找到CHEAPEST的路径

4）在初始可行解的基础上进行优化（使用local search） search_parameters.local_search_metaheuristic = (     routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH) #搜索时间限制 search_parameters.time_limit.seconds = 120

三、指定城市的旅行商问题

Step1，数据预处理

1）所有城市的位置（经度、维度）

2）城市之间的距离矩阵 针对常用的功能，可以封装为自己的工具包 from cylearn import common_tools

# 读取，写入指定的pickle result = common_tools.load_pickle(‘result.pkl’) common_tools.save_pickle(result, ‘result.pkl’)

# 计算两点之间的距离 dist = common_tools.compute_distance(longitude1, latitude1, longitude2, latitude2)

Step2，根据指定的城市，计算TSP，得到路径route 创建tsp类

1）def __init__(self, city_names=None): 类初始化 __init__，定义常用的变量

2）def create_data_model(self): 初始化data，得到data字典，记录distance_matrix，num_vehicles，depot等数据

3）def get_solution(self, routing, solution): 返回路径(这里为index list，比如[0, 1, 2]) 以及 总距离

4）def work(self):

# 定义路由，比如10个节点，1辆车 manager = RoutingIndexManager(10, 1, starts_ends)

# 创建 Routing Model. routing = pywrapcp.RoutingModel(manager)

# 计算两点之间的距离 def distance_callback(from_index, to_index):    

# 将路由变量Index转化为 距离矩阵ditance_matrix的节点index    

from_node = manager.IndexToNode(from_index)    

to_node = manager.IndexToNode(to_index)    

return data[‘distance_matrix’][from_node][to_node]

Step3，可视化交互

1）选择指定的城市 // 表单提交

// checkbox使用

2）画出车辆行驶路径（基于百度地图API） 基于 map_line1.html 进行改写

今天的文章VRP问题分享到此就结束了，感谢您的阅读。