做电台用啥什么网站,wordpress国内分享插件,wordpress框架文件上传,推动高质量发展的举措文章目录 前言一步步安装免费版主要模块介绍1. depot point2. customer point3. links4. vehicle type VRPTW 算例数据说明模型建立输出求解状态及结果 前言
VRPSolverEasy 是用于车辆路径问题#xff08;VRP#xff09;的最先进的分支切割和定价算法求解器1#xff0c;它的… 文章目录 前言一步步安装免费版主要模块介绍1. depot point2. customer point3. links4. vehicle type VRPTW 算例数据说明模型建立输出求解状态及结果 前言
VRPSolverEasy 是用于车辆路径问题VRP的最先进的分支切割和定价算法求解器1它的一大特点是即使没有运筹学背景的用户也可以直观地通过Python接口定义出VRP问题无需知道模型是如何建立为 MIP 问题以及底层进行的线性处理只需要通过配置好的方法向模型中添加高度抽象的VehicleType、Point衍生出depot、customer、links 即可。
VRPSolver将VRP问题进行了高度抽象尽管较大程度方便使用但代价是限制了VRPSolver只能建模常见的标准的VRP变体问题例如
车辆带容量限制客户点带时间窗车辆不同质多depot发车客户点指定车辆资质时间依赖…
VRPSolver的内核是分支切割定价算法其高效性在于对可行解最优界下界的优化上而在初始可行解的寻找方面效率较低因此由外部启发式求解器获得非常好的初始解上界时VRPSolver的求解性能可以得到改善。 目前的VRPSolver仍然是proof-of-concept的代码容易出现问题因此建议仅用于研究、教学、测试等非生产环境。 一步步安装免费版
VRPSolverEasy有两种安装模式一种是免费版本直接安装VRPSolverEasy库内嵌了COIN-OR CLP线性规划求解器以及下载Bapcod发行版即可。另一种是学术版本该版本使用了商业CPLEX MIP求解器由于CPLEX可以免费用于学术目的因此这个版本下的VRPSolverEasy也被称为学术版该版本提高了求解性能并提供了内置的基于MIP的启发式算法对寻找可行的初始解非常有用。
这里我们仅介绍安装免费版的 VRPSolverEasy操作系统默认为Windows。学术版的安装请参考 官方文档
1确认python版本及更新pip
VRPSolverEasy库要求python版本不小于 3.6因此在开始安装前先确认好python的版本并建议更新 pip 库
python -m pip install --upgrade pip2安装VRPSolverEasy库
VRPSolverEasy库的安装可以直接用pip安装
python -m pip install VRPSolverEasy3安装Bapcod依赖的环境
由于内嵌的 CLP 仅是线性规划求解器要用 BCP 求解MIP问题还需安装Bapcod由于Bapcod的底层是C因此要用Python接口使用就还需下载能对该库进行编译和管理的工具CMake该工具的官网下载地址为Download CMake具体的安装细节可以参考Windows 安装CMake。在cmd控制台输入 cmake --version 即可查看CMake的版本。
接着还需安装 Bapcod 依赖的python库
Boost库版本1.76 pip install boostLEMON 库版本 1.3.1 pip install lemon
4申请Bapcod并替换相应文件
尽管Bapcod是免费开源的库但是需要学术机构的电子邮箱才能下载Bapcod的源码在 BaPCod官方网站 填写相应信息并回车进行申请。系统会自动验证该邮箱并向该邮箱发送下载链接。
解压下载的文件例如为 bapcod-v0.82.5找到该文件夹下的 VRPSolverEasy 文件夹复制该文件夹下的 Windows 文件夹到 VRPSolverEasy 库下面的 lib 文件夹中替换 Windows 即可。
主要模块介绍 关于主要模块的介绍我们截取翻译自VRPSolverEasy的技术报告1。 导入VRPSolverEasy库并通过以下命令创建模型。
import VRPSolverEasy
model VRPSolverEasy.Model()VRPSolverEasy库模型由四组实体对象定义depot points、customer points、links、vehicle types。
1. depot point
depot 可以通过如下命令添加
model.add_depot(idid, name, service_time0.0, tw_begin0.0, tw_end0.0)添加 depot 方法的参数说明如下 2. customer point
customer 可以通过如下命令添加
model.add_customer(idid, id_customerid, name , demand0, penalty0.0, service_time0.0, tw_begin0.0, tw_end0.0, incompatible_vehicles[])添加 customer 方法的参数说明如下 不论是 depot point 还是 customer point都应该有一个唯一的点 id且每个 customer 都与一个或多个点相关联其中 id 与 id_customer 可以不同。
对于一些特殊的问题例如同一个客户点具有不同的时间窗且每个时间窗所兼容的车辆可能不同常见于时间依赖的VRPTW问题这类问题中客户点可能会被多辆车访问同时或者有时间前后约束这时候为了避免与子环路消除约束相冲突往往会创建虚拟点在这里如果我们要创建 customer point 的额外点可以通过以下命令添加
model.add_point(idid, id_customerid, name , demand0, penalty0.0, service_time0.0, tw_begin0.0, tw_end0.0, incompatible_vehicles[])3. links
link 可以通过如下命令添加
model.add_link(start_point_idid, end_point_idid, name, is_directedFalse, distance0.0, time0.0, fixed_cost0.0)添加 link 方法的参数说明如下 每一条 link 代表有向图G当中的一条弧如果 is_directedTrue则说明该弧具有方向只能从 start_point_id 到 end_point_id 方向如果 is_directedFalse则说明该弧是双向的若不设置该参数默认为双向的。
4. vehicle type
vehicle type 可以通过如下命令添加
model.add_vehicle_type(idid, start_point_id-1, end_point_id-1, name, capacity0, fixed_cost0.0, var_cost_dist0.0, var_cost_time0.0, max_number1, tw_begin0.0, tw_end0.0) 添加 vehicle type 方法的参数说明如下 当车辆的开始点和结束点都为 -1 时说明该车辆可以在任意节点处出发和返回任意节点处。
VRPTW 算例
数据说明
如下设置 7 个节点以第 1 个节点 Wisconsin, USA 为 depot point其余节点为 customer point除了 depot 其余节点都有大于0需求量车辆的时间窗为 [ 0 , 5000 ] [0, 5000] [0,5000]每辆车单位距离成本为 10节点与节点之间的距离通过欧式距离公式计算 compute_euclidean_distance。
import VRPSolverEasy as vrpse
import mathdef compute_euclidean_distance(x_i, x_j, y_i, y_j):compute the euclidean distance between 2 points from graphreturn round(math.sqrt((x_i - x_j)**2 (y_i - y_j)**2), 3)# Data
cost_per_distance 10
begin_time 0
end_time 5000
nb_point 7# Map with names and coordinates
coordinates {Wisconsin, USA: (44.50, -89.50), # depotWest Virginia, USA: (39.000000, -80.500000),Vermont, USA: (44.000000, -72.699997),Texas, the USA: (31.000000, -100.000000),South Dakota, the US: (44.500000, -100.000000),Rhode Island, the US: (41.742325, -71.742332),Oregon, the US: (44.000000, -120.500000)}# Demands of points
demands [0, 500, 300, 600, 658, 741, 436]模型建立
依次建立求解车辆路径网络流问题的要素车辆、节点、弧。要素的参数值可以自定义配置。
# Initialisation
model vrpse.Model()# Add vehicle type
model.add_vehicle_type(id1,start_point_id0,end_point_id0,nameVEH1,capacity1100,max_number6,var_cost_distcost_per_distance,tw_end5000)# Add depot
model.add_depot(id0, nameD1, tw_begin0, tw_end5000)coordinates_keys list(coordinates.keys())
# Add customers
for i in range(1, nb_point):model.add_customer(idi,namecoordinates_keys[i],demanddemands[i],tw_beginbegin_time,tw_endend_time)# Add links
coordinates_values list(coordinates.values())
for i in range(0, 7):for j in range(i 1, 7):dist compute_euclidean_distance(coordinates_values[i][0],coordinates_values[j][0],coordinates_values[i][1],coordinates_values[j][1])model.add_link(start_point_idi,end_point_idj,distancedist,timedist)输出求解状态及结果
当建立模型后通过以下命令即可实现求解求解的结果都会保存在 model 的属性当中。
# solve model
model.solve()打印模型信息可以通过以下命令默认将模型信息保存在 instance.json 文件中。
model.export()通过 model.status 可以返回模型的求解状态码
状态码说明0找到一个解并证明了最优性1求解过程被时间限制打断但找到了优于截断值的解2求解器证明不存在由于截断值的解3求解过程被时间限制打断且没找到由于截断值的解
判断求解状态码是一种输出结果的前置判断在该库中也可以用 model.solution.is_defined() 进行判断后者表示找到了可行解且解的信息会保存到模型的属性当中
if model.solution.is_defined():# 打印解的目标值及方案的全部信息print(model.solution)# 仅打印路线方案print(model.solution.routes)# 仅打印目标值print(model.solution.value) # 打印解的求解时间和上下界信息等print(model.statistics)打印解的目标值及方案的全部信息如下
Solution cost : 1479.6800000008684Route for vehicle 1:ID : 0 -- 2 -- 5 -- 0Name : D1 -- Vermont, USA -- Rhode Island, the US -- D1End time : 0.0 -- 16.807 -- 19.259 -- 37.230000000000004Load : 0.0 -- 300.0 -- 1041.0 -- 1041.0
Total cost : 372.29999999999995Route for vehicle 1:ID : 0 -- 1 -- 3 -- 0Name : D1 -- West Virginia, USA -- Texas, the USA -- D1End time : 0.0 -- 10.548 -- 31.625 -- 48.728Load : 0.0 -- 500.0 -- 1100.0 -- 1100.0
Total cost : 487.2800000000001Route for vehicle 1:ID : 0 -- 4 -- 6 -- 0Name : D1 -- South Dakota, the US -- Oregon, the US -- D1End time : 0.0 -- 10.5 -- 31.006 -- 62.010000000000005Load : 0.0 -- 658.0 -- 1094.0 -- 1094.0
Total cost : 620.1N. Errami, E. Queiroga, R. Sadykov, E. Uchoa. “VRPSolverEasy: a Python library for the exact solution of a rich vehicle routing problem”, Technical report HAL-04057985, 2023. ↩︎ ↩︎
