车辆路由功能 - 类别（实验）¶

Warning

可能服务器崩溃

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

Warning

实验功能

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

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

介绍 ¶

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

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

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

特征 ¶

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

局限性

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

取货 & 送货 ¶

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

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

参数 ¶

取货 & 送货 ¶

用于 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_{th}\) 辆车。值 \(-2\) 表示它是汇总行。
`vehicle_id`	BIGINT	当前车辆标识符。摘要行有总容量违规情况。当车辆超载或欠载时，就会发生容量违规。
`stop_seq`	INTEGER	当前车辆停止的顺序值，从 1 开始。当前第 \(m_{th}\) 车辆的停止。摘要行包含总时间窗口违规情况。在该地点关闭后到达时，会发生时间窗口违规。
`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`	车辆离开车站的时间。 \(arrival\_time + wait\_time + service\_time\)。结束位置有当前车辆使用的总时间。摘要行包含总解决问题时间： \(total\ traveling\ time + total\ waiting\ time + total\ service\ time\)。

摘要行 ¶

列	类型	描述
`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`	摘要行包含总解决问题时间： \(total\ traveling\ time + total\ waiting\ time + total\ service\ time\)。

处理参数 ¶

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

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

容量和需求单位处理 ¶

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

体积单位如 \(m^3\)。
面积单位如 : math:m^2 （不允许堆叠时）。
重量单位如 \(kg\)。
车辆内可容纳的箱子数量。
车内座位数

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

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

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

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

设：- \(f\_boxes\)： 1 公斤羽毛所需的箱子数量。- \(a\_weight\)： 1 箱子苹果的重量。

容量单位	苹果	羽毛
箱子	10	\(5 * f\_boxes\)
千克	\(10 * a\_weight\)	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:: 时间

对于以下等价 \(10m/s \approx 600m/min \approx 36 km/hr\)

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

单位	速度	转换	因素	结果
秒	\(10 m/s\)	\(\frac{1}{10m/s}\)	\(0.1s/m\)	\(1000m * 0.1s/m = 100s\)
分钟	\(600 m/min\)	\(\frac{1}{600m/min}\)	\(0.0016min/m\)	\(1000m * 0.0016min/m = 1.6min\)
小时	\(36 km/hr\)	\(\frac{1}{36 km/hr}\)	\(0.0277hr/km\)	\(1km * 0.0277hr/km = 0.0277hr\)

另请参阅 ¶

https://en.wikipedia.org/wiki/Vehicle_routing_problem
查询使用示例数据网络。

索引和表格