`pgr_pickDeliver` - 实验¶

pgr_pickDeliver - 接送车辆路径问题

Warning

可能服务器崩溃

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

Warning

实验功能

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

可用性

版本3.0.0
- 新实验函数

概要¶

问题：将取货-送货对分配并优化到车队中。

优化问题是NP-hard。
有时间窗口的取货和送货。
所有车辆都是平等的。
- 相同的起始位置。
- 相同的结束位置与开始位置相同。
- 所有车辆以相同的速度行驶。
客户负责提货或送货。
- 有开放时间。
- 有关闭时间。
- 有服务时间。
- 具有 (x, y) 位置。
有客户需要送货。
- 客户之间的旅行时间是距离/速度
- 取货和送货是使用同一辆车完成的。
- 送货前会进行取货。

特征¶

所有卡车均在时间 0 出发。
一个位置没有多个时间窗口。
使用的车辆越少越好。
总持续时间越短越好。
等待时间越短越好。
该算法将在以下情况下引发异常
- 如果存在违反时间窗口的取货-送货对
- speed、max_cycles、ma_capacity 具有非法值
将优化六个不同的初始值 - 找到的最佳解决方案将是结果

标识¶

pgr_pickDeliver(Orders SQL, Vehicles SQL, Matrix SQL, [options])

options: [factor, max_cycles, initial_sol]

(seq, vehicle_number, vehicle_id, stop, order_id, stop_type, cargo, travel_time, arrival_time, wait_time, service_time, departure_time)

的集合

示例:: 解决以下问题

给定车辆：

SELECT id, capacity, start_node_id, start_open, start_close
FROM vehicles;
 id | capacity | start_node_id | start_open | start_close
----+----------+---------------+------------+-------------
  1 |       50 |            11 |          0 |          50
  2 |       50 |            11 |          0 |          50
(2 rows)

和顺序：

SELECT id, demand,
       p_node_id, p_open, p_close, p_service,
       d_node_id, d_open, d_close, d_service
FROM orders;
 id | demand | p_node_id | p_open | p_close | p_service | d_node_id | d_open | d_close | d_service
----+--------+-----------+--------+---------+-----------+-----------+--------+---------+-----------
  1 |     10 |        10 |      2 |      10 |         3 |         3 |      6 |      15 |         3
  2 |     20 |        16 |      4 |      15 |         2 |        15 |      6 |      20 |         3
  3 |     30 |         7 |      2 |      10 |         3 |        12 |      3 |      20 |         3
(3 rows)

查询：

SELECT * FROM pgr_pickDeliver(
  $$SELECT id, demand,
       p_node_id, p_open, p_close, p_service,
       d_node_id, d_open, d_close, d_service
    FROM orders$$,
  $$SELECT id, capacity, start_node_id, start_open, start_close
    FROM vehicles$$,
  $$SELECT * from pgr_dijkstraCostMatrix(
    'SELECT * FROM edges ',
    (SELECT array_agg(id) FROM (SELECT p_node_id AS id FROM orders
        UNION
        SELECT d_node_id FROM orders
        UNION
        SELECT start_node_id FROM vehicles) a))
  $$);
 seq | vehicle_seq | vehicle_id | stop_seq | stop_type | stop_id | order_id | cargo | travel_time | arrival_time | wait_time | service_time | departure_time
-----+-------------+------------+----------+-----------+---------+----------+-------+-------------+--------------+-----------+--------------+----------------
   1 |           1 |          1 |        1 |         1 |      11 |       -1 |     0 |           0 |            0 |         0 |            0 |              0
   2 |           1 |          1 |        2 |         2 |       7 |        3 |    30 |           1 |            1 |         1 |            3 |              5
   3 |           1 |          1 |        3 |         3 |      12 |        3 |     0 |           2 |            7 |         0 |            3 |             10
   4 |           1 |          1 |        4 |         2 |      16 |        2 |    20 |           2 |           12 |         0 |            2 |             14
   5 |           1 |          1 |        5 |         3 |      15 |        2 |     0 |           1 |           15 |         0 |            3 |             18
   6 |           1 |          1 |        6 |         6 |      11 |       -1 |     0 |           2 |           20 |         0 |            0 |             20
   7 |           2 |          2 |        1 |         1 |      11 |       -1 |     0 |           0 |            0 |         0 |            0 |              0
   8 |           2 |          2 |        2 |         2 |      10 |        1 |    10 |           3 |            3 |         0 |            3 |              6
   9 |           2 |          2 |        3 |         3 |       3 |        1 |     0 |           3 |            9 |         0 |            3 |             12
  10 |           2 |          2 |        4 |         6 |      11 |       -1 |     0 |           2 |           14 |         0 |            0 |             14
  11 |          -2 |          0 |        0 |        -1 |      -1 |       -1 |    -1 |          16 |           -1 |         1 |           17 |             34
(11 rows)

参数¶

参数是：

列	类型	描述
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¶

返回以下列的 SELECT 语句：

id, demand
p_node_id, p_open, p_close, [p_service,]
d_node_id, d_open, d_close, [d_service,]

其中：

列	类型	描述
`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

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

其中：

ANY-INTEGER:: SMALLINT, INTEGER, BIGINT

车辆 SQL¶

返回以下列的 SELECT 语句：

id, capacity
start_node_id, start_open, start_close [, start_service,]
[end_node_id, end_open, end_close, end_service]

其中：

列	类型	描述
`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` 中的持续时间。

列	类型	描述
`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

矩阵SQL¶

其中：

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

结果列¶

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\)。

另请参阅¶

索引和表格

pgr_pickDeliver - 实验¶

概要¶

特征¶

标识¶

参数¶

取货-送货可选参数¶

订单 SQL¶

车辆 SQL¶

矩阵SQL¶

结果列¶

另请参阅¶

`pgr_pickDeliver` - 实验¶