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 的已弃用函数

介绍

车辆路径问题 VRPNP-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 提前订单,允许在前面插入更多订单

内部查询

订单 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

其中:

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_vidend_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 开始的顺序值。 解决方案中的第 nth 辆车。

  • 2 表示它是汇总行。

vehicle_id

BIGINT

当前车辆标识符。

  • 摘要行有 总容量违规情况

    • 当车辆超载或欠载时,就会发生容量违规。

stop_seq

INTEGER

当前车辆停止的顺序值,从 1 开始。 当前第 mth 车辆的停止。

  • 摘要行包含 总时间窗口违规情况

    • 在该地点关闭后到达时,会发生时间窗口违规。

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

处理参数

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

容量和需求单位处理

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

  • 体积单位如 m3

  • 面积单位如 : math:m^2 (不允许堆叠时)。

  • 重量单位如 kg

  • 车辆内可容纳的箱子数量。

  • 车内座位数

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

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

  • 如果车辆的 容量箱子 来衡量,则需要将 羽毛的千克 换算为 箱子的数量

  • 如果车辆的 容量kg 为单位,则需要将 一箱苹果 换算为 kg

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

设:- f_boxes1 公斤羽毛所需的箱子数量。- a_weight1 箱子苹果的重量。

容量单位

苹果

羽毛

箱子

10

5f_boxes

千克

10a_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

分钟

960=54

16.560=990

10.5

9:00 am

小时

0

7.5

10.5/60=0.175

9:00 am

分钟

0

7.560=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/s600m/min36km/hr

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

单位

速度

转换

因素

结果

10m/s

110m/s

0.1s/m

1000m0.1s/m=100s

分钟

600m/min

1600m/min

0.0016min/m

1000m0.0016min/m=1.6min

小时

36km/hr

136km/hr

0.0277hr/km

1km0.0277hr/km=0.0277hr

另请参阅

索引和表格