VRPSolverEasy：支持VRP问题快速建模的精确算法Python包

2024-01-18 03:28
文章标签 python 算法 问题 快速 支持 建模 精确 vrp vrpsolvereasy

本文主要是介绍VRPSolverEasy：支持VRP问题快速建模的精确算法Python包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 前言
  • 一步步安装免费版
  • 主要模块介绍
    • 1. depot point
    • 2. customer point
    • 3. links
    • 4. vehicle type
  • VRPTW 算例
    • 数据说明
    • 模型建立
    • 输出求解状态及结果

前言

VRPSolverEasy 是用于车辆路径问题（VRP）的最先进的分支切割和定价算法求解器1，它的一大特点是，即使没有运筹学背景的用户，也可以直观地通过Python接口定义出VRP问题，无需知道模型是如何建立为 MIP 问题以及底层进行的线性处理，只需要通过配置好的方法，向模型中添加高度抽象的VehicleType、Point（衍生出depot、customer）、links 即可。

VRPSolver将VRP问题进行了高度抽象，尽管较大程度方便使用，但代价是限制了VRPSolver只能建模常见的标准的VRP变体问题，例如：

  1. 车辆带容量限制；
  2. 客户点带时间窗；
  3. 车辆不同质；
  4. 多depot发车；
  5. 客户点指定车辆资质；
  6. 时间依赖…

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 pip

（2）安装VRPSolverEasy库

VRPSolverEasy库的安装可以直接用pip安装：

python -m pip install VRPSolverEasy

（3）安装Bapcod依赖的环境

由于内嵌的 CLP 仅是线性规划求解器，要用 B&C&P 求解MIP问题，还需安装Bapcod，由于Bapcod的底层是C++，因此要用Python接口使用，就还需下载能对该库进行编译和管理的工具CMake，该工具的官网下载地址为：Download CMake，具体的安装细节可以参考：Windows 安装CMake。在cmd控制台输入 cmake --version 即可查看CMake的版本。

接着还需安装 Bapcod 依赖的python库：

  1. Boost库版本1.76 pip install boost
  2. LEMON 库版本 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(id=<id>, name='', service_time=0.0, tw_begin=0.0, tw_end=0.0)

添加 depot 方法的参数说明如下：

Characterization of a depot point v

2. customer point

customer 可以通过如下命令添加：

model.add_customer(id=<id>, id_customer=<id>, name ='', demand=0, penalty=0.0, service_time=0.0, tw_begin=0.0, tw_end=0.0, incompatible_vehicles=[])

添加 customer 方法的参数说明如下：

Characterization of a customer point v
不论是 depot point 还是 customer point，都应该有一个唯一的点 id，且每个 customer 都与一个或多个点相关联，其中 id 与 id_customer 可以不同。

对于一些特殊的问题，例如同一个客户点具有不同的时间窗，且每个时间窗所兼容的车辆可能不同，常见于时间依赖的VRPTW问题，这类问题中，客户点可能会被多辆车访问（同时或者有时间前后约束），这时候为了避免与子环路消除约束相冲突，往往会创建虚拟点，在这里，如果我们要创建 customer point 的额外点，可以通过以下命令添加：

model.add_point(id=<id>, id_customer=<id>, name ='', demand=0, penalty=0.0, service_time=0.0, tw_begin=0.0, tw_end=0.0, incompatible_vehicles=[])

3. links

link 可以通过如下命令添加：

model.add_link(start_point_id=<id>, end_point_id=<id>, name='', is_directed=False, distance=0.0, time=0.0, fixed_cost=0.0)

添加 link 方法的参数说明如下：

Characterization of a link l
每一条 link 代表有向图G当中的一条弧，如果 is_directed=True，则说明该弧具有方向，只能从 start_point_id 到 end_point_id 方向；如果 is_directed=False，则说明该弧是双向的（若不设置该参数默认为双向的）。

4. vehicle type

vehicle type 可以通过如下命令添加：

model.add_vehicle_type(id=<id>, start_point_id=-1, end_point_id=-1, name='', capacity=0, fixed_cost=0.0, var_cost_dist=0.0, var_cost_time=0.0, max_number=1, tw_begin=0.0, tw_end=0.0)

添加 vehicle type 方法的参数说明如下：

Characterization of a vehicle type k
当车辆的开始点和结束点都为 -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 graph"""return 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),  # depot"West 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(id=1,start_point_id=0,end_point_id=0,name="VEH1",capacity=1100,max_number=6,var_cost_dist=cost_per_distance,tw_end=5000)# Add depot
model.add_depot(id=0, name="D1", tw_begin=0, tw_end=5000)coordinates_keys = list(coordinates.keys())
# Add customers
for i in range(1, nb_point):model.add_customer(id=i,name=coordinates_keys[i],demand=demands[i],tw_begin=begin_time,tw_end=end_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_id=i,end_point_id=j,distance=dist,time=dist)

输出求解状态及结果

当建立模型后，通过以下命令即可实现求解，求解的结果都会保存在 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.1

  1. N. 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. ↩︎ ↩︎

这篇关于VRPSolverEasy：支持VRP问题快速建模的精确算法Python包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/617974。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
python: 多模块(.py)中全局变量的导入

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别： 当你在一个模块（文件）中使用 global 声明变量时，这个变量只在该模块的全局命名空
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

在日常使用电脑的过程中，我们经常会遇到这样的情况：一不小心，桌面上的某个重要文件被删除了。这时，大多数人可能会感到惊慌失措，不知所措。 其实，不必过于担心，因为有很多方法可以帮助我们找回被删除的桌面文件。下面，就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件，并且还没有进行其他操作，那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【Python编程】Linux创建虚拟环境并配置与notebook相连接

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如，在当前目录下创建一个名为 myenv 的虚拟环境： python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行： source myenv/bin/activate 3.与notebook连接 在虚拟环境中，使用 pip 安装 Jupyter 和 ipykernel： pip instal
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2