Supported versions: latest (3.7) 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev

Vehicle Routing Functions - Category ¶

Warning

可能服务器崩溃

这些功能可能会导致服务器崩溃

Warning

实验功能

它们不是当前版本的正式版本。
它们可能不会正式成为下一个版本的一部分：
- 这些函数可能不使用 ANY-INTEGER 和 ANY-NUMERICAL
- 名称可能会改变。
- 签名可能会改变。
- 功能可能会改变。
- pgTap 测试可能丢失。
- 可能需要 c/c++编码。
- 可能缺乏文档。
- 文档（如果有）可能需要重写。
- 可能需要自动生成文档示例。
- 可能需要社区的大量反馈。
- 可能取决于 pgRouting 的拟议功能
- 可能依赖于 pgRouting 的已弃用函数

取货和送货问题
- pgr_pickDeliver - 实验 - 使用成本矩阵的取货&送货
- pgr_pickDeliverEuclidean - 实验 - 使用欧几里得距离的取货&送货
分配问题
- pgr_vrpOneDepot - Experimental - 从单个仓库分发订单

介绍 ¶

车辆路径问题 VRP 是 NP-hard 优化问题，它推广了旅行商问题 (TSP)。

VRP 的目标是最小化总路由成本。
VRP 问题有多种变体，

pgRouting 并不尝试实现所有变体。

特征 ¶

容量车辆路径问题 CVRP 其中车辆的货物承载能力有限。
具有时间窗口的车辆路由问题 VRPTW，其中位置具有车辆必须访问的时间窗口。
取货和送货的车辆路径问题 VRPPD ，其中大量货物需要从某些取货地点移动到其他送货地点。

局限性

一个位置没有多个时间窗口。
使用的车辆越少越好。
总持续时间越短越好。
等待时间越短越好。

取货 & 送货 ¶

问题： CVRPPDTW 具有时间窗口的有能力分拣和送货车辆路径问题

时间是相对于 0 的
车辆
- 有开始和结束服务持续时间。
- 有开始和结束地点的开放和关闭时间。
- 具有容量。
订单
- 有提货和送货地点。
- 有提货和送货地点的开放和关闭时间。
- 有取货和送货持续时间的服务时间。
- 有将货物从取货地点移动到交货地点的需求请求。
基于时间的计算：
- 客户之间的旅行时间为 $d i s t a n c e / s p e e d$
- 取货和送货订单对由同一辆车完成。
- 送货前会进行取货。

参数 ¶

取货 & 送货 ¶

用于 pgr_pickDeliverEuclidean - 实验

列	类型	描述
Orders SQL	`TEXT`	Orders SQL 如下所述。
Vehicles SQL	`TEXT`	Vehicles SQL 如下所述。

用于 pgr_pickDeliver - 实验

列	类型	描述
Orders SQL	`TEXT`	Orders SQL 如下所述。
Vehicles SQL	`TEXT`	Vehicles SQL 如下所述。
Matrix SQL	`TEXT`	Matrix SQL 如下所述。

取货-送货可选参数 ¶

列	类型	默认	描述
`factor`	`NUMERIC`	1	旅行时间乘数。请参阅因素处理
`max_cycles`	`INTEGER`	10	执行优化的最大周期数。
`initial_sol`	`INTEGER`	4	要使用的初始解决方案。 `1` 每辆卡车一份订单 `2` 提前订单。 `3` 推迟订单。 `4` 优化插入。 `5` 推迟订单，允许在后面插入更多订单 `6` 提前订单，允许在前面插入更多订单

列

类型

默认

描述

factor

NUMERIC

旅行时间乘数。请参阅因素处理

max_cycles

INTEGER

执行优化的最大周期数。

initial_sol

INTEGER

要使用的初始解决方案。

1 每辆卡车一份订单
2 提前订单。
3 推迟订单。
4 优化插入。
5 推迟订单，允许在后面插入更多订单
6 提前订单，允许在前面插入更多订单

内部查询 ¶

订单 SQL ¶

两种实现中订单 SQL 的公共列：

列	类型	描述
`id`	ANY-INTEGER	提货-交货订单对的标识符。
`demand`	ANY-NUMERICAL	订单中的单位数量
`p_open`	ANY-NUMERICAL	相对于0的时间，提货地点开放。
`p_close`	ANY-NUMERICAL	提货地点关闭的时间（相对于 0）。
[`p_service`]	ANY-NUMERICAL	在取货地点装载的持续时间。缺失时：使用 0 个时间单位
`d_open`	ANY-NUMERICAL	交货地点开放的时间（相对于 0）。
`d_close`	ANY-NUMERICAL	交货地点关闭的时间（相对于 0）。
[`d_service`]	ANY-NUMERICAL	在交货地点卸货的持续时间。缺失时：使用 0 个时间单位

其中：

ANY-INTEGER:: SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

对于 pgr_pickDeliver - 实验，需要位置的取货和送货标识符：

列	类型	描述
`p_node_id`	ANY-INTEGER	取货的节点标识符必须与 Matrix SQL 中的顶点标识符匹配。
`d_node_id`	ANY-INTEGER	送货的节点标识符必须与 Matrix SQL 中的顶点标识符匹配。

其中：

ANY-INTEGER:: SMALLINT, INTEGER, BIGINT

对于 pgr_pickDeliverEuclidean - 实验，这需要位置的 $(x, y)$ 值：

列	类型	描述
`p_x`	ANY-NUMERICAL	取货地点的 $x$ 值
`p_y`	ANY-NUMERICAL	取货地点的 $y$ 值
`d_x`	ANY-NUMERICAL	送货地点的 $x$ 值
`d_y`	ANY-NUMERICAL	送货地点的 $y$ 值

其中：

ANY-NUMERICAL:: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

车辆 SQL ¶

两种实现中车辆 SQL 的公共列：

列	类型	描述
`id`	ANY-NUMERICAL	车辆的标识符。
`capacity`	ANY-NUMERICAL	最大容量单位
`start_open`	ANY-NUMERICAL	起始位置打开的时间（相对于 0）。
`start_close`	ANY-NUMERICAL	起始位置关闭的时间（相对于 0）。
[`start_service`]	ANY-NUMERICAL	在起始位置加载的持续时间。缺失时：使用 $0$ 个时间单位的持续时间。
[`end_open`]	ANY-NUMERICAL	结束位置打开的时间（相对于 0）。缺失时：使用 `start_open` 的值
[`end_close`]	ANY-NUMERICAL	结束位置关闭的时间（相对于 0）。缺失时：使用 `start_close` 的值
[`end_service`]	ANY-NUMERICAL	在结束位置加载的持续时间。缺失时：使用 `start_service` 中的持续时间。

对于 pgr_pickDeliver - 实验，需要位置的开始和结束标识符：

列	类型	描述
`start_node_id`	ANY-INTEGER	起始位置的节点标识符必须与 Matrix SQL 中的顶点标识符匹配。
[`end_node_id`]	ANY-INTEGER	结束位置的节点标识符必须与 Matrix SQL 中的顶点标识符匹配。缺少时：使用 `end_node_id`。

列

类型

描述

start_node_id

ANY-INTEGER

起始位置的节点标识符必须与 Matrix SQL 中的顶点标识符匹配。

[end_node_id]

ANY-INTEGER

结束位置的节点标识符必须与 Matrix SQL 中的顶点标识符匹配。

缺少时：使用 end_node_id。

其中：

ANY-INTEGER:: SMALLINT, INTEGER, BIGINT

对于 pgr_pickDeliverEuclidean - 实验，这需要位置的 $(x, y)$ 值：

列	类型	描述
`start_x`	ANY-NUMERICAL	起始位置的 $x$ 值
`start_y`	ANY-NUMERICAL	起始位置的 $y$ 值
[`end_x`]	ANY-NUMERICAL	结束位置的 $x$ 值缺失时：使用 `start_x` 值。
[`end_y`]	ANY-NUMERICAL	结束位置的 $y$ 值缺失时：使用 `start_y` 值。

其中：

ANY-NUMERICAL:: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

矩阵SQL ¶

(start_vid, end_vid, agg_cost) 的集合

列	类型	描述
`start_vid`	`BIGINT`	起始顶点的标识符。
`end_vid`	`BIGINT`	结束顶点的标识符。
`agg_cost`	`FLOAT`	从 `start_vid` 到 `end_vid` 的总成本。

结果列 ¶

Returns set of
 (seq, vehicle_seq, vehicle_id, stop_seq, stop_type,
     travel_time, arrival_time, wait_time, service_time, departure_time)
 UNION
 (summary row)

列	类型	描述
`seq`	`INTEGER`	从 1 开始的顺序值。
`vehicle_seq`	`INTEGER`	当前车辆从 1 开始的顺序值。解决方案中的第 $n_{t h}$ 辆车。值 $- 2$ 表示它是汇总行。
`vehicle_id`	BIGINT	当前车辆标识符。摘要行有总容量违规情况。当车辆超载或欠载时，就会发生容量违规。
`stop_seq`	INTEGER	当前车辆停止的顺序值，从 1 开始。当前第 $m_{t h}$ 车辆的停止。摘要行包含总时间窗口违规情况。在该地点关闭后到达时，会发生时间窗口违规。
`stop_type`	`INTEGER`	车辆所在的停车位置类型 $- 1$ : 在解决方案摘要行 $1$ : 起始位置 $2$ : 取货位置 $3$ : 送货位置 $6$ : 结束位置并指示车辆的摘要行
`order_id`	`BIGINT`	取货-送货订单对标识符。值 $- 1$ : 当前停留位置没有订单参与。
`cargo`	`FLOAT`	车辆离开停车点时的货物单位。值 $- 1$ 在解决方案摘要行。
`travel_time`	`FLOAT`	从前一个 `stop_seq` 到当前 `stop_seq` 的行程时间。总结一下总的行程时间：所有 `travel_time` 的总和。
`arrival_time`	`FLOAT`	等待当前位置打开所花费的时间。 $- 1$ : 在解决方案摘要行。 $0$ : 在起始位置。
`wait_time`	`FLOAT`	等待当前位置打开所花费的时间。摘要行包含总等待时间：所有 `wait_time` 的总和。
`service_time`	`FLOAT`	当前位置的服务持续时间。摘要行包含总服务时间：所有 `service_time` 的总和。
`departure_time`	`FLOAT`	车辆离开车站的时间。 $a r r i v a l_t i m e + w a i t_t i m e + s e r v i c e_t i m e$ 。结束位置有当前车辆使用的总时间。摘要行包含总解决问题时间： $t o t a l t r a v e l i n g t i m e + t o t a l w a i t i n g t i m e + t o t a l s e r v i c e t i m e$ 。

摘要行 ¶

列	类型	描述
`seq`	`INTEGER`	继续序列
`vehicle_seq`	`INTEGER`	值 $- 2$ 表示它是汇总行。
`vehicle_id`	BIGINT	总容量违规：当车辆超载或欠载时，就会发生容量违规。
`stop_seq`	INTEGER	总时间窗口违规：在该地点关闭后到达时，会发生时间窗口违规。
`stop_type`	`INTEGER`	$- 1$
`order_id`	`BIGINT`	$- 1$
`cargo`	`FLOAT`	$- 1$
`travel_time`	`FLOAT`	总行程时间：所有 `travel_time` 的总和。
`arrival_time`	`FLOAT`	$- 1$
`wait_time`	`FLOAT`	总行程时间：所有 `wait_time` 的总和。
`service_time`	`FLOAT`	总服务时间：所有 `service_time` 的总和。
`departure_time`	`FLOAT`	摘要行包含总解决问题时间： $t o t a l t r a v e l i n g t i m e + t o t a l w a i t i n g t i m e + t o t a l s e r v i c e t i m e$ 。

处理参数 ¶

要定义问题，必须考虑多种因素才能获得一致的结果。本节深入了解如何考虑参数。

容量和需求单位处理
位置
时间处理
因素处理

容量和需求单位处理 ¶

车辆的`容量`可以通过以下方式测量：

体积单位如 $m^{3}$ 。
面积单位如 : math:m^2 （不允许堆叠时）。
重量单位如 $k g$ 。
车辆内可容纳的箱子数量。
车内座位数

取货-送货订单的需求请求必须使用与车辆容量中使用的单位相同的单位。

处理以下问题：10 箱（尺寸相等）苹果和 5 千克羽毛的运输（不装箱）。

如果车辆的容量以箱子来衡量，则需要将羽毛的千克换算为箱子的数量。
如果车辆的容量以 kg 为单位，则需要将一箱苹果换算为 kg。

显示如何完成两种可能的转换

设：- $f_b o x e s$ ： 1 公斤羽毛所需的箱子数量。- $a_w e i g h t$ ： 1 箱子苹果的重量。

容量单位	苹果	羽毛
箱子	10	$5 * f_b o x e s$
千克	$10 * a_w e i g h t$	5

位置 ¶

当使用 pgr_pickDeliverEuclidean - 实验：
- 车辆有起点和终点 $(x, y)$ 对。
- 订单有取货和送货地点 $(x, y)$ 对。
当使用 pgr_pickDeliver - 实验:
- 车辆具有起始位置和结束位置的标识符。
- 订单具有取货和送货地点的标识符。
- 所有标识符都是给定矩阵的索引。

时间处理 ¶

时间是相对于 0 的。所有时间单位都必须转换为 0 参考和相同的时间单位。

假设车辆驾驶员上午 9:00 开始换班，下午 4:30 结束换班，服务时间为 10 分钟 30 秒。

0的含义	时间单位	9:00 am	4:30 pm	10 min 30 secs
0:00 am	小时	9	16.5	$10.5 / 60 = 0.175$
0:00 am	分钟	$9 * 60 = 54$	$16.5 * 60 = 990$	10.5
9:00 am	小时	0	7.5	$10.5 / 60 = 0.175$
9:00 am	分钟	0	$7.5 * 60 = 540$	10.5

因素处理 ¶

因子 充当乘数，将距离值转换为时间单位、矩阵值或欧几里得值。

当值已处于所需时间单位时
- 因数 应为 1
- 当 因子 > 1 时，行程时间更快
- 当 因子 < 1 时，行程时间会变慢

用于 pgr_pickDeliverEuclidean - 实验:

使用以秒为单位的时间单位，以及以纬度/经度为单位的 x/y：因子：取决于点的位置和平均速度，例如 25m/s 是速度。

纬度	转换	因素
45	1经度为(78846.81m)/(25m/s)	3153 s
0	1经度为(111319.46 m)/(25m/s)	4452 s

用于 pgr_pickDeliver - 实验:

给定 $v = d / t$ 因此 $t = d / v$ 并且 因子 变为 $1 / v$

其中：

v:: 速度
d:: 距离
t:: 时间

对于以下等价 $10 m / s \approx 600 m / m i n \approx 36 k m / h r$

使用以秒为单位的时间单位和以米为单位的矩阵：对于矩阵上的 1000m 长度值：

单位	速度	转换	因素	结果
秒	$10 m / s$	$\frac{1}{10 m / s}$	$0.1 s / m$	$1000 m * 0.1 s / m = 100 s$
分钟	$600 m / m i n$	$\frac{1}{600 m / m i n}$	$0.0016 m i n / m$	$1000 m * 0.0016 m i n / m = 1.6 m i n$
小时	$36 k m / h r$	$\frac{1}{36 k m / h r}$	$0.0277 h r / k m$	$1 k m * 0.0277 h r / k m = 0.0277 h r$

另请参阅 ¶

索引和表格