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

这篇具有很好参考价值的文章主要介绍了VRPSolverEasy:支持VRP问题快速建模的精确算法Python包。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

VRPSolverEasy 是用于车辆路径问题(VRP)的最先进的分支切割和定价算法求解器1,它的一大特点是,即使没有运筹学背景的用户,也可以直观地通过Python接口定义出VRP问题,无需知道模型是如何建立为 MIP 问题以及底层进行的线性处理,只需要通过配置好的方法,向模型中添加高度抽象的VehicleTypePoint(衍生出depotcustomer)、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 pointscustomer pointslinksvehicle types

1. depot point

depot 可以通过如下命令添加

model.add_depot(id=<id>, name='', service_time=0.0, tw_begin=0.0, tw_end=0.0)

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

VRPSolverEasy:支持VRP问题快速建模的精确算法Python包,车辆路径优化,算法,python

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 方法的参数说明如下:

VRPSolverEasy:支持VRP问题快速建模的精确算法Python包,车辆路径优化,算法,python
不论是 depot point 还是 customer point,都应该有一个唯一的点 id,且每个 customer 都与一个或多个点相关联,其中 idid_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 方法的参数说明如下:

VRPSolverEasy:支持VRP问题快速建模的精确算法Python包,车辆路径优化,算法,python
每一条 link 代表有向图G当中的一条弧,如果 is_directed=True,则说明该弧具有方向,只能从 start_point_idend_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 方法的参数说明如下:

VRPSolverEasy:支持VRP问题快速建模的精确算法Python包,车辆路径优化,算法,python
当车辆的开始点和结束点都为 -1 时,说明该车辆可以在任意节点处出发,和返回任意节点处。

VRPTW 算例

数据说明

如下设置 7 个节点,以第 1 个节点 Wisconsin, USAdepot point,其余节点为 customer point,除了 depot 其余节点都有大于0需求量,车辆的时间窗为 [ 0 , 5000 ] [0, 5000] [0,5000],每辆车单位距离成本为 10,节点与节点之间的距离通过欧式距离公式计算 compute_euclidean_distance

import VRPSolverEasy as vrpse
import math

def 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.6800000008684

Route for vehicle 1:
 ID : 0 --> 2 --> 5 --> 0
 Name : D1 --> Vermont, USA --> Rhode Island, the US --> D1
 End time : 0.0 --> 16.807 --> 19.259 --> 37.230000000000004
 Load : 0.0 --> 300.0 --> 1041.0 --> 1041.0
Total cost : 372.29999999999995

Route for vehicle 1:
 ID : 0 --> 1 --> 3 --> 0
 Name : D1 --> West Virginia, USA --> Texas, the USA --> D1
 End time : 0.0 --> 10.548 --> 31.625 --> 48.728
 Load : 0.0 --> 500.0 --> 1100.0 --> 1100.0
Total cost : 487.2800000000001

Route for vehicle 1:
 ID : 0 --> 4 --> 6 --> 0
 Name : D1 --> South Dakota, the US --> Oregon, the US --> D1
 End time : 0.0 --> 10.5 --> 31.006 --> 62.010000000000005
 Load : 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. ↩︎ ↩︎文章来源地址https://www.toymoban.com/news/detail-800513.html

到了这里,关于VRPSolverEasy:支持VRP问题快速建模的精确算法Python包的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 最优化:建模、算法与理论(典型优化问题

    4.1.1 基本形式和应用背景 再次说明一下,其实这本书很多的内容之前肯定大家都学过,但是我觉得这本书和我们之前学的东西的出发角度不一样,他更偏向数学,也多一个角度让我们去理解 线性规划问题的一般形式如下: min ⁡ x ∈ R n c T x s . t . A x = b G x ≤ e (4.1.1) min_{x{

    2024年02月09日
    浏览(250)
  • 数学建模软件及算法模型典型问题汇总

    一、 软件篇 编程 、MATLAB(物理建模)、python(数据分析)、R、其他(SPSS、Stata、Origin) 这里其实还有一个 Lingo 软件,不过我不推荐,有更好的替代方案,就是 Yalmip 工具箱+OPTI 工具箱+gurobi 求解器,Yalmip 是基于 matlab 的求解规划问题的高级建模语言,OPTI 提供众多 开源的规

    2024年04月17日
    浏览(52)
  • 模拟退火算法与遗传算法求解多目标优化问题的算法实现(数学建模)

    模拟退火算法是一种全局优化算法,解决的问题通常是找到一个最小化(或最大化)某个函数的全局最优解。它通过模拟物理退火的过程来搜索解空间,在开始时以一定的温度随机生成初始解,然后一步步降低温度,同时在当前解的周围随机搜索新的解,并根据一定概率接受

    2024年02月02日
    浏览(52)
  • 量子退火算法入门(3):整数分割问题的QUBO建模

    QUBO建模最重要的就是,把建模对象中的变量映射为binary(0/1 或者 -1/+1)的变量。我先从简单的问题开始说明,让大家有些直观感受。整数分割问题就是一个非常简单,并容易理解的例子。此文参考了日本NTT公司的量子计算指南文档[*1]。 整数分割问题定义: 判断能否将一个

    2024年02月01日
    浏览(35)
  • 量子退火算法入门(4):旅行商问题的QUBO建模「上篇」

    旅行商问题,是一个经典的组合优化问题,而且是著名NP问题之一。如下图所示 ,可以想象,有A,B,C,D,E 五个地点,我们想找到一条路径,从地点A出发,经过剩余四个地点,然后回到地点A,从所有可能路径中找到距离最短的一条路径。本章借用了文献[*1]的图表。 最简单

    2023年04月18日
    浏览(36)
  • 数学建模|通过模拟退火算法求解供货与选址问题:问题二(python代码实现)

    今天继续用模拟退火算法供货与选址问题的问题二,如果还没看过问题一的可以看我之前的博客 数学建模|通过模拟退火算法求解供应与选址问题:问题一(python代码实现)-CSDN博客 这里还是把题目放上来(题目来自数学建模老哥的视频): 那么我们可以分析一下,第一问和

    2024年01月16日
    浏览(55)
  • 数学建模十大算法04—图论算法(最短路径、最小生成树、最大流问题、二分图)

    一、最短路径问题 从图中的某个顶点出发,到达另一个顶点的 所经过的边的权重之和最小 的一条路径。 1.1 两个指定顶点之间的最短路径 问题如下:给出了一个连接若干个城镇的铁路网络,在这个网络的两个指定城镇间,求一条最短铁路线。 1.1.1 Dijkstra算法 迪杰斯特拉(D

    2024年02月02日
    浏览(70)
  • 集货运输优化:数学建模步骤,Python实现蚁群算法(解决最短路径问题), 蚁群算法解决旅行商问题(最优路径问题),节约里程算法

    目录 数学建模步骤 Python实现蚁群算法(解决最短路径问题)  蚁群算法解决旅行商问题(最优路径问题)

    2024年02月09日
    浏览(52)
  • 数学建模笔记——整数规划类问题之我见(匈牙利算法)

    目录 浅浅叙述匈牙利算法 基本思路 计算步骤 来一道简单例题 1.1 符号规定 1.2目标函数​编辑       1.3约束条件 ​编辑 1.4代码 题目复述 基本假设 问题分析 符号说明  模型的建立与求解 模型建立思路 模型建立的过程 建立0-1整数规划模型  运用匈牙利方法: 代码实现  

    2023年04月11日
    浏览(48)
  • 量子退火算法入门(5):旅行商问题的QUBO建模「下篇之Python实现」

    提示:上篇已经讲过了旅行商问题的QUBO建模,这里直接讲两种编程实现: 看过上篇的读者应该已经注意到,因为旅行商问题需要最终返回到初始点的。所以,下面👇的目标函数里,循环进行到 N N N 时,最后一个 x j , t + 1 x_{j,t+1} x j , t + 1 ​ 应该确定回到初始点的。 针对这

    2023年04月14日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包