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 的
车辆
有开始和结束服务持续时间。
有开始和结束地点的开放和关闭时间。
具有容量。
订单
有提货和送货地点。
有提货和送货地点的开放和关闭时间。
有取货和送货持续时间的服务时间。
有将货物从取货地点移动到交货地点的需求请求。
基于时间的计算:
客户之间的旅行时间为
取货和送货订单对由同一辆车完成。
送货前会进行取货。
参数¶
取货 & 送货¶
用于 pgr_pickDeliverEuclidean - 实验
列 |
类型 |
描述 |
---|---|---|
|
Orders SQL 如下所述。 |
|
|
Vehicles SQL 如下所述。 |
列 |
类型 |
描述 |
---|---|---|
|
Orders SQL 如下所述。 |
|
|
Vehicles SQL 如下所述。 |
|
|
Matrix SQL 如下所述。 |
取货-送货可选参数¶
列 |
类型 |
默认 |
描述 |
---|---|---|---|
|
|
1 |
旅行时间乘数。 请参阅 因素处理 |
|
|
10 |
执行优化的最大周期数。 |
|
|
4 |
要使用的初始解决方案。
|
内部查询¶
订单 SQL¶
两种实现中订单 SQL 的公共列:
列 |
类型 |
描述 |
---|---|---|
|
ANY-INTEGER |
提货-交货订单对的标识符。 |
|
ANY-NUMERICAL |
订单中的单位数量 |
|
ANY-NUMERICAL |
相对于0的时间,提货地点开放。 |
|
ANY-NUMERICAL |
提货地点关闭的时间(相对于 0)。 |
[ |
ANY-NUMERICAL |
在取货地点装载的持续时间。
|
|
ANY-NUMERICAL |
交货地点开放的时间(相对于 0)。 |
|
ANY-NUMERICAL |
交货地点关闭的时间(相对于 0)。 |
[ |
ANY-NUMERICAL |
在交货地点卸货的持续时间。
|
其中:
- ANY-INTEGER:
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
对于 pgr_pickDeliver - 实验,需要位置的取货和送货标识符:
列 |
类型 |
描述 |
---|---|---|
|
ANY-INTEGER |
取货的节点标识符必须与 Matrix SQL 中的顶点标识符匹配。 |
|
ANY-INTEGER |
送货的节点标识符必须与 Matrix SQL 中的顶点标识符匹配。 |
其中:
- ANY-INTEGER:
SMALLINT
,INTEGER
,BIGINT
对于 pgr_pickDeliverEuclidean - 实验,这需要位置的
列 |
类型 |
描述 |
---|---|---|
|
ANY-NUMERICAL |
取货地点的 |
|
ANY-NUMERICAL |
取货地点的 |
|
ANY-NUMERICAL |
送货地点的 |
|
ANY-NUMERICAL |
送货地点的 |
其中:
- ANY-NUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
车辆 SQL¶
两种实现中车辆 SQL 的公共列:
列 |
类型 |
描述 |
---|---|---|
|
ANY-NUMERICAL |
车辆的标识符。 |
|
ANY-NUMERICAL |
最大容量单位 |
|
ANY-NUMERICAL |
起始位置打开的时间(相对于 0)。 |
|
ANY-NUMERICAL |
起始位置关闭的时间(相对于 0)。 |
[ |
ANY-NUMERICAL |
在起始位置加载的持续时间。
|
[ |
ANY-NUMERICAL |
结束位置打开的时间(相对于 0)。
|
[ |
ANY-NUMERICAL |
结束位置关闭的时间(相对于 0)。
|
[ |
ANY-NUMERICAL |
在结束位置加载的持续时间。
|
对于 pgr_pickDeliver - 实验,需要位置的开始和结束标识符:
列 |
类型 |
描述 |
---|---|---|
|
ANY-INTEGER |
起始位置的节点标识符必须与 Matrix SQL 中的顶点标识符匹配。 |
[ |
ANY-INTEGER |
结束位置的节点标识符必须与 Matrix SQL 中的顶点标识符匹配。
|
其中:
- ANY-INTEGER:
SMALLINT
,INTEGER
,BIGINT
对于 pgr_pickDeliverEuclidean - 实验,这需要位置的
列 |
类型 |
描述 |
---|---|---|
|
ANY-NUMERICAL |
起始位置的 |
|
ANY-NUMERICAL |
起始位置的 |
[ |
ANY-NUMERICAL |
结束位置的
|
[ |
ANY-NUMERICAL |
结束位置的
|
其中:
- ANY-NUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
矩阵SQL¶
(start_vid, end_vid, agg_cost)
的集合
列 |
类型 |
描述 |
---|---|---|
|
|
起始顶点的标识符。 |
|
|
结束顶点的标识符。 |
|
|
从 |
结果列¶
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)
列 |
类型 |
描述 |
---|---|---|
|
|
从 1 开始的顺序值。 |
|
|
当前车辆从 1 开始的顺序值。 解决方案中的第
|
|
BIGINT |
当前车辆标识符。
|
|
INTEGER |
当前车辆停止的顺序值,从 1 开始。 当前第
|
|
|
|
|
|
取货-送货订单对标识符。
|
|
|
车辆离开停车点时的货物单位。
|
|
|
从前一个
|
|
|
等待当前位置打开所花费的时间。
|
|
|
等待当前位置打开所花费的时间。
|
|
|
当前位置的服务持续时间。
|
|
|
|
摘要行¶
列 |
类型 |
描述 |
---|---|---|
|
|
继续序列 |
|
|
值 |
|
BIGINT |
总容量违规:
|
|
INTEGER |
总时间窗口违规:
|
|
|
|
|
|
|
|
|
|
|
|
总行程时间:
|
|
|
|
|
|
总行程时间:
|
|
|
总服务时间:
|
|
|
摘要行包含 总解决问题时间:
|
处理参数¶
要定义问题,必须考虑多种因素才能获得一致的结果。 本节深入了解如何考虑参数。
容量和需求单位处理¶
车辆的`容量`可以通过以下方式测量:
体积单位如
。面积单位如 : math:m^2 (不允许堆叠时)。
重量单位如
。车辆内可容纳的箱子数量。
车内座位数
取货-送货订单的 需求 请求必须使用与车辆 容量 中使用的单位相同的单位。
处理以下问题:10 箱(尺寸相等)苹果和 5 千克羽毛的运输(不装箱)。
如果车辆的 容量 以 箱子 来衡量,则需要将 羽毛的千克 换算为 箱子的数量。
如果车辆的 容量 以 kg 为单位,则需要将 一箱苹果 换算为 kg。
显示如何完成两种可能的转换
设:-
容量单位 |
苹果 |
羽毛 |
---|---|---|
箱子 |
10 |
|
千克 |
5 |
位置¶
当使用 pgr_pickDeliverEuclidean - 实验:
车辆有起点和终点
对。订单有取货和送货地点
对。
当使用 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 |
|
0:00 am |
分钟 |
10.5 |
||
9:00 am |
小时 |
0 |
7.5 |
|
9:00 am |
分钟 |
0 |
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 |
给定 因子
变为
其中:
- v:
速度
- d:
距离
- t:
时间
对于以下等价
使用以秒为单位的时间单位和以米为单位的矩阵:对于矩阵上的 1000m 长度值:
单位 |
速度 |
转换 |
因素 |
结果 |
---|---|---|---|---|
秒 |
||||
分钟 |
||||
小时 |
另请参阅¶
索引和表格