Modeling and Comparative Analysis of Patient Transportation by Fuel and Electric Vehicles
受国家救护车补贴政策的影响, 非紧急情况下的病人乘坐救护车前往医院的费用比紧急情况下的病人更高, 因此大多数非紧急病人更多的乘坐公共交通或者出租车等前往医院. 同时结合当前新冠疫情影响, 公共交通、出租车以及日常拼车等, 在行驶过程中由于缺乏相应的医疗设备以及专业的医疗人员, 非紧急病人选择这些交通方式前往医院不仅存在一定的安全问题, 而且可能会加快疫情的传播和扩散, 因此对于非紧急病人而言, 一个安全经济有效的交通方式显得尤为重要. 拼车出行是由服务运营商根据乘客需求为其匹配合适的车辆和司机提供服务, 从而完成拼车服务[1]. 随着科技的进步, 当前电动车不仅能够满足人们的日常出行需求, 而且在行驶的过程中对于空气环境也是零污染. 但是当前关于拼车出行以及病人运送问题, 主要还是以传统燃油车为主.
非紧急病人运送问题与拼车出行问题相似之处在于: 寻求一条合理有效的车辆行驶路径, 在满足病人或乘客需求的前提下, 使车辆总行驶成本、车辆使用数等目标达到最优. 在数学模型构建方面, Baldacci等[2]将拼车出行问题建模为一个静态的拨号乘车问题(dail-a-ride problem, DARP), 鼓励员工在上下班的途中接送同事, 以共享最大和路径成本最小为目标. Conrad等[3]首次对电动车车辆的车辆路径问题(recharging vehicle routing problem, RVRP)进行了研究, 考虑了客户时间窗要求和电车充电问题, 以使用的车辆数、车辆总行驶路程和充电成本最小化为目标. Schneider等[4]研究了带有时时间窗和充电站的电动汽车货物运送问题, 以车辆行驶总路程最小化为目标. Felipe等[5]考虑了电动汽车在充电站处使用不同的充电技术, 以电动汽车在不同地点处的充电成本和电池固定损耗成本之和最小化为目标. Bruglieri等[6]提出了一个三阶段数学方法求解城市内物流配送问题, 考虑了客户时间窗、电池容量和电车负载能力, 以电动汽车的使用数量和电动汽车所花费的总时间(行驶时间、充电时间和客户等待时间)最小化为目标. Goeke等[7]研究了带有时间窗的混合车队路径问题, 以车辆行驶路程最短、行驶总成本(充电成本、燃油成本以及司机工资)和电池更换成本为目标建立数学模型.
目前病人运送问题(patient transportation problem, PTP)主要以燃油车为载运工具来完成服务[8-15]. Madsen等[8]研究了老人和残疾人运送问题, 将该问题描述为一个多目标的静态拨号乘车问题, 以车辆总行驶时间、车辆使用数、乘客等待时间、承诺服务偏差以及行驶总成本之和最小化为目标. Rekiek等[9]研究了残疾人运送问题, 以服务质量最大化和使用车辆数最小化为目标. Melachrinoudis等[10]研究了病人运送问题, 以车辆运送成本和客户的不便时间组合最小化为目标. Beaudry等[11]研究了大型医院病人转运问题, 提出了两阶段启发式算法帮助病人和车辆进行快速的匹配. Parragh等[12]研究了含有多约束多目标的救护车运送问题, 以病人不便程度和服务质量为目标构建数学模型. Zhang等[13]考虑了车辆容量、司机和助手的午餐休息时间、病人服务时间以及车辆最长行驶时间等约束, 以车辆总行驶费用和未接受服务的病人数最小化为目标. Lim等[14]研究了救护车的转运问题, 为残疾人和老年病人在住所和医院之间提供运送服务, 考虑了病人的时间窗、病人需求、车辆容量以及医疗助手等约束, 以服务尽可能多的病人和最小化运送成本为目标. Detti等[15]研究了非紧急情况下的病人运送问题, 考虑了不同类型的车辆、病人偏好、车辆与病人的兼容性以及服务质量等约束, 以多个目标的总成本最小化建立数学模型.
综合以上文献分析得知, 有关病人运送问题的研究, 目前主要以燃油车为主, 缺少电动车方面的相关研究; 同时有关电动车运送路径问题, 缺少以病人运送为对象的研究. 因此本文针对电动车及运送病人问题展开讨论, 通过建模与算例对比分析, 希望得到具有创新及实用性的结论.
1 模型构建
1.1 问题描述
本文研究的问题可以描述为: 某病人运送公司拥有
K
辆燃油车和电动车, 为
n
个已知位置、需求
qi
和时间窗
[eai,eli]
的非紧急病人提供去往医院的运送服务, 每辆车上都配备有相应的医疗设备和医疗助手, 车辆必须在病人可接受的时间内到达, 每辆车只服务一条病人运送路线, 且每位病人只能被一辆车服务一次, 所有车辆的起点和终点为同一地点. 考虑到病人运送的安全和非紧急性, 对每辆车的最大平均行驶速度进行相应约束, 车辆必须在每位病人可接受的最长乘车时间范围内将其送到医院. 电车不能搭载病人前往充电站处充电, 否则就不由该辆车提供服务. 将电车在充电站和终点处的充电成本进行区别考虑, 假设在充电站处采用同一快速充电技术, 在终点处采用同一慢速充电技术, 每辆车必须在最长行驶时间范围内回到终点进行定期消毒. 因此在满足所有病人时间窗和需求的前提下, 采用哪种类型车辆进行运送病人, 使得运送总成本最小.
1.2 模型变量及参数
燃油车和纯电动车数学模型的具体变量及参数含义如下所示:
P
: 每位病人对应的上车点集合
P = {1,2,⋯,n}
.
0,2n+1
: 所有车辆起点和终点集合.
K
: 车辆数量集合
K={1,2,⋯,e}
.
R
: 充电站集合
R={1,2,⋯,r}
.
H
: 医院点集合
H=H1∪H2∪⋯∪Hm={n+1,n+2,⋯,2n}
.
V
: 所有节点集合.
Zkki
: 车辆
k
即将离开节点
i
时的载客量.
Zk
: 车辆
k
的最大病人容量.
tij/tkij
: 燃油车/电车
k
在弧
(i,j)
的行驶时间 (min).
Pg
: 燃油车的每升油价 (元/L).
Si/Ski
: 燃油车/电车
k
在节点
i
处的服务等待时间(min).
gk
: 电车
k
在充电站处的充电效率(min/kW·h).
Tk
: 车辆
k
完成每条病人运送路线的最长行驶时间限制(min).
hk
: 车辆
k
每行驶单位里程所消耗的电量/油量(kW·h/km, L/km).
Bk
: 车辆
k
的电池/油箱容量(kW·h/L).
qi
: 病人节点处的座位需求数.
[eai,eli]
: 节点
i
的时间窗(min).
dij
: 弧
(i,j)
之间的距离(km).
Ci
: 病人可接受的最长乘车时间(min).
yki
: 车辆
k
到达节点
i
时的剩余电量/油量(kW·h/L).
yyki
: 电车
k
即将离开节点
i
时的剩余电量(kW·h).
aki
: 车辆
k
到达节点
i
的时间(min).
Ce/Cg
: 燃油车/电车每行驶单位里程所消耗的成本(元/km).
Cr/Cd
: 电车
k
在充电站/终点处的单位充电成本(元/kW·h).
xkij
: 0-1变量, 当车辆
k
从节点
i
到
j
时为1, 否则为0.
sdk
: 车辆最大平均行驶速度(min/km).
1.3 燃油车数学模型
燃油车数学模型的目标函数为: 行驶消耗成本
Fg
和加油成本
Fp
之和最小化, 具体如下:
燃油车行驶消耗成本为: 燃油车单位里程行驶消耗成本×燃油车总行驶路程, 具体如下:
Fg=∑j∈V∑i∈V∑k∈KCgdijxkij
|
(2) |
燃油车回到终点后加满油所需的加油成本为: 汽油单价×(满油油量–剩余油量), 具体如下:
Fp=∑k∈K∑i∈VPg(Bk−yk,2n+1)xki,2n+1
|
(3) |
具体约束条件如下所示:
∑k∈K∑j∈V∖{0}xkij=1,∀i∈P
|
(4) |
∑j∈V∖{2n+1}xkji−∑j∈V∖{0}xkij=0,∀i∈P∪H,k∈K
|
(12) |
∑j∈Vxkn+i,j−∑j∈Vxkij=0,∀i∈P,n+i∈H,k∈K
|
(13) |
Zkki+qjxkij−Zk(1−xkij)⩽Zkkj,∀i,j∈V,k∈K
|
(15) |
eai⩽aki⩽eli,∀i∈V,k∈K
|
(16) |
(ak,n+i−ak,i−Si)∑j∈V∖{0}xkij⩽Ci,∀i∈P,k∈K
|
(18) |
aki+(tij+Si)xkij−Tk(1−xkij)⩽akj,∀k∈K,i,j∈V
|
(19) |
yk,j⩽yk,i−hkdijxkij+Bk(1−xkij),∀k∈K,i,j∈V
|
(20) |
sdkdijxkij⩽tij,∀i,j∈V,k∈K
|
(21) |
Si>0,S0=S2n+1=0,∀i∈P∪H
|
(22) |
xkij∈{0,1},∀i,j∈V,k∈K
|
(24) |
约束条件中: 式(4)确保每位病人能且只能被服务1次; 式(5)–式(7)确保所有车辆从起点出发; 式(8)–式(10)确保所有车辆返回终点; 式(11)防止子回路; 式(12)确保车辆经过的节点保持流守恒; 式(13)确保病人上下车由同一辆车完成; 式(14)和式(15)确保每辆车的载客量不超过车辆容量; 式(16)确保车辆到达时间满足病人时间窗约束; 式(17)表示每辆车的最长行驶时间约束; 式(18)确保每位病人的乘车时间不超过每位病人所接受的最长乘车时间; 式(19)和式(20)分别为车辆到达两个相邻节点处的时间和油量约束; 式(21)为车辆的最大平均行驶速度约束; 式(22)为车辆在节点的等待和服务时间约束; 式(23)为车辆剩余油量约束; 式(24)表示
xkij
为二元变量, 当车辆
k
经过弧
(i,j)
为1, 否则为0.
1.4 电动车数学模型
电动车数学模型的目标函数为: 行驶消耗成本
Fe
和充电成本
Fr
之和最小化, 具体如下:
电车行驶消耗成本为: 电车单位里程行驶消耗成本×总行驶路程, 具体如下:
Fe=∑j∈V∖{0}∑i∈V∖{2n+1}∑k∈KCedijxkij
|
(26) |
电车充电成本为电车在充电站处的充电成本和电车在终点处的充电成本之和, 电车在充电站的充电成本为: 充电站处的单位充电成本×(满电电量−剩余电量), 电车在终点的充电成本为: 终点处的单位充电成本×(满点电量−剩余电量), 具体如下:
Fr=∑k∈K∑j∈V∑i∈RCr(yyki−yki)xkij+∑i∈V∑k∈KCd(yyk,2n+1−yk,2n+1)xki,2n+1
|
(27) |
具体约束条件如下所示:
∑k∈K∑j∈V∖{0}xkij=1,∀i∈P
|
(28) |
∑i∈H∪Rxki,2n+1=1,∀k∈K
|
(34) |
∑j∈V∖{2n+1}xkji−∑j∈V∖{0}xkij=0,∀i∈V∖{0,2n+1},k∈K
|
(36) |
∑j∈Vxkn+i,j−∑j∈Vxkij=0,∀i∈P,n+i∈H,k∈K
|
(37) |
Zkki+qjxkij−Zk(1−xkij)⩽Zkkj,∀i,j∈V,k∈K
|
(40) |
eai⩽aki⩽eli,∀i∈V,k∈K
|
(41) |
(ak,n+i−ak,i−Ski)∑j∈Vxkij⩽Ci,∀i∈P,k∈K
|
(43) |
{aki+(tkij+Ski)xkij−Tk(1−xkij)⩽akj,∀k∈K,i∈P∪H∪{0},j∈V∖{0}
|
(44) |
{aki+[tkij+Ski+(yyki−yki)gk]xkij−Tk(1−xkij)⩽akj,∀k∈K,i∈R,j∈V
|
(45) |
{yyk,i−hkdijxkij+Bk(1−xkij)⩾ykj,∀k∈K,i∈V∖{2n+1},j∈V∖{0}
|
(46) |
sdkdijxkij⩽tkij,∀i,j∈V,k∈K
|
(47) |
{Ski−M∑j∈Vxkij⩾0,Sk,0=Sk,2n+1=0,∀i∈V∖{0,2n+1},k∈K,M>0
|
(48) |
0⩽yki⩽yyki⩽Bk,∀i∈V,k∈K
|
(49) |
yyki=yki,∀i∈P∪H∪{0},k∈K
|
(50) |
yyki=Bk,∀i∈R∪{0,2n+1},k∈K
|
(51) |
xkij∈{0,1},∀i,j∈V,k∈K
|
(52) |
约束条件中: 式(28)确保每位病人能且只能被服务1次; 式(29)–式(31)确保所有电车从起点出发; 式(32)–式(34)确保所有电车返回终点; 式(35)防止子回路; 式(36)确保电车经过的节点保持流守恒; 式(37)确保每位病人由同一辆车接送; 式(38)确保电车不能搭载病人前往充电站充电; 式(39)和式(40)确保电车搭载病人的数量不超过电车容量; 式(41)确保电车在病人时间窗内到达; 式(42)为每辆电车的最长行驶时间约束; 式(43)确保每位病人的乘车时间不超过每位病人所接受的最长乘车时间约束; 式(44)为电车到达两个相邻节点处的时间关系约束; 式(45)为电车在充电站处等待和充满电所花费的时间约束; 式(46)为电车到达两个相邻节点的剩余电量关系约束; 式(47)为电车最大平均行驶速度约束; 式(48)为车辆在节点处的等待和服务时间约束; 式(49)–式(51)为电车在节点处的剩余电量关系约束; 式(52)表示当车辆
k
经过弧
(i,j)
时为1, 否则为0;
2 算例及对比分析
LINGO软件是著名的专业优化软件, 其功能性比较强、计算效果比较好, 与那些包含部分优化功能的非专业软件相比, 通常具有明显的优势. 因此本文利用LINGO内置的分支定界算法来搜索全局最优解, 数学模型和相关数据在LINGO 11.0软件上进行编程求解, 所有数据在Intel(R) Core(TM) i5-4200H CPU @ 2.80 GHz配置的计算机上进行实验.
2.1 算例设计
通过设计相应算例来验证模型的可行性和有效性, 根据任玉珑等[16]提出的电动车与燃油车全寿命周期成本模型, 本文
Cg
和
Ce
分别取值为:
Cg=0.652
,
Ce=0.415
, 燃油车
hk=0.1
, 电动车
hk=0.12
. 本文其余相关参数取值为:
Cr=1.6
,
Cd=0.5
,
Pg=6.12
,
Zk=5
,
gk=1.2
,
Tk=260
,
sdk=1
,
M=3
. 本文选取的算例规模为: 燃油车和电动车各3辆, 8个病人上车点, 8个病人下车点, 5个充电站, 3所医院. 节点1和节点18表示所有车辆的起终点, 病人上车节点
i
对应的下车节点为
n+i
, 下车节点坐标相同的为同一所医院, 节点19–23为充电站. 每个节点位置用坐标
(x,y)
表示, 具体节点位置、时间窗、病人所能接受的最长乘坐时间
Ci
以及病人座位需求数
qi
如表1所示.
2.2 求解结果及对比分析
当燃油车和电车的容量分别取值40 L和40 kW·h, 求解结果分别如表2和表3所示. 由表2可得: 燃油车最短行驶路径消耗成本为104.26元, 回到终点处加满油所需成本为97.87元, 此时总成本为202.13元. 由表3可知: 所有电车均未前往充电站充电, 电车最短行驶路径消耗成本为66.36元, 回到终点处充满电所花费的成本为9.6元, 此时总成本为75.96元.
表 1(Table 1)
表 1 病人运送算例
节点 |
(x,y)
|
[eai,eli]
|
qi
|
Ci
|
| 节点 |
(x,y)
|
[eai,eli]
|
qi
|
| 节点 |
(x,y)
|
[eai,eli]
|
2 |
(36, 21) |
[45, 65] |
2 |
20 |
| 10 |
(36, 9) |
[60, 80] |
−2 |
| 1 |
(21, 21) |
[0, 260] |
3 |
(30, 12) |
[19, 35] |
3 |
35 |
11 |
(36, 9) |
[45, 60] |
−3 |
18 |
(21, 21) |
[0, 260] |
4 |
(36, 9) |
[30, 45] |
2 |
20 |
12 |
(36, 9) |
[45, 65] |
−2 |
19 |
(33, 18) |
[0, 260] |
5 |
(18, 9) |
[155, 175] |
2 |
20 |
13 |
(12, 12) |
[180, 199] |
−2 |
20 |
(24, 9) |
[0, 260] |
6 |
(6, 6) |
[43, 60] |
1 |
25 |
14 |
(12, 12) |
[60, 80] |
−1 |
21 |
(15, 12) |
[0, 260] |
7 |
(9, 18) |
[20, 38] |
2 |
40 |
15 |
(12, 12) |
[58, 75] |
−2 |
22 |
(15, 21) |
[0, 260] |
8 |
(12, 27) |
[160, 180] |
2 |
40 |
16 |
(24, 30) |
[200, 220] |
−2 |
23 |
(21, 27) |
[0, 260] |
9 |
(27, 27) |
[15, 30] |
2 |
20 |
17 |
(24, 30) |
[35, 55] |
−2 |
— |
|
表 1 病人运送算例
|
由表2和表3对比可得: 当电车运送病人行驶总路程较短时, 电车无需前往充电站充电, 此时燃油车和电车行驶路径相同, 燃油车行驶消耗成本约是电车行驶消耗成本的1.57倍, 燃油车回到终点处的加油成本约是电车充电成本的10.19倍. 燃油车总成本约是电动车总成本的2.66倍. 因此当病人运送的总行驶路程较短时, 电车所花费的总成本要远小于燃油车所花费总成本.
为了对比电车前往充电站充电后所花费的总成本和燃油车总成本的差异, 同时进一步验证电车模型的有效性, 在上述算例的基础上对电池容量进行了相应的调整, 假设此时电动车电池容量为6 kW·h, 具体求解结果如表4所示.
由表4可知: 电车1和3均在充电站处充电一次, 电车最短行驶路径消耗成本为66.78元, 在充电站和终点处的充电成本为19.93元, 此时总成本为86.71元. 由表2和表4分别可得燃油车和电车的具体行驶路径如图1和图2所示.
通过表3、表4以及图1、图2对比可知: 当病人运送总路程较长时, 电车必须前往充电站充电才能完成病人运送服务, 虽然电车相比燃油车的总行驶路程更长, 但此时燃油车的最短行驶路径消耗成本约是电车最短行驶路径消耗成本的1.56倍, 燃油车加油成本约是电车充电成本的4.91倍, 燃油车总成本约是电车总成本的2.33倍. 因此当病人运送总路程较长时, 电车所花费的总成本依旧要小于燃油车所花费的总成本.
表 2(Table 2)
表 2 燃油车求解结果
车辆 |
1 |
2 |
3 |
行驶路径 |
1→7→6→14→15→5→13→18 |
1→9→17→8→16→18 |
1→3→4→11→12→2→10→18 |
载客量
变化
|
0→2→3→2→0→2→0→0 |
0→2→0→2→0→0 |
0→3→5→2→0→2→0→0 |
aki
|
0→20→48.81→67.77→70.77→175→199→260 |
0→15→55→160→220→260 |
0→19→30→47.29→53.43→65→80→260 |
yki
|
40→38.76→37.53→36.68→36.68→36.01
→ 35.34→34.06
|
40→39.15→38.73→37.49→36.25 →35.31 |
40→38.73→38.06→37.46→37.46→36.86→36.26→34.64 |
Si
|
0→12.98→6.76→3→97.53→17.29→3→0 |
0→35.76→3→20→3→0 |
0→3→7.37→3→3→3→3→0 |
tij
|
12.37→12.37→8.49→0→6.71→6.71→12.73 |
8.49→4.24→12.37→12.37→9.49 |
12.73→6.71→6→0→6→6→16.16 |
总成本 |
202.13 |
行驶消耗成本 |
104.26 |
加油成本 |
97.87 |
|
表 2 燃油车求解结果
|
表 3(Table 3)
表 3 未前往充电站的电动车求解结果
车辆 |
1 |
2 |
3 |
行驶路径 |
1→7→6→15→14→5→13→18 |
1→9→17→8→16→18 |
1→3→4→12→11→2→10→18 |
载客量
变化
|
0→2→3→1→0→2→0→0 |
0→2→0→2→0→0 |
0→3→5→3→0→2→0→0 |
aki
|
0→27.63→43→70.63→73.63→155→199→260 |
0→15→35→180→200→260 |
0→19→30→45→48→65→74→260 |
yki
|
40→38.52→37.03→36.01→36.01→35.21→
34.40→32.88
|
40→38.98→38.47→36.99→
35.50→34.37
|
40→38.47→37.67→36.95→36.95→36.23→
35.51→33.57
|
yyki
|
40→38.52→37.03→36.01→36.01→35.21→
34.40→40
|
40→38.98→38.47→36.99→
35.50→40
|
40→38.47→37.67→36.95→36.95→36.23→
35.51→40
|
Ski
|
0→3→5.63→3→3→24→3→0 |
0→3→3→3→50.5→→0 |
0→3→3→3→11→3→3→0 |
tkij
|
12.37→12.37→8.49→0→6.71→6.71→12.73 |
8.49→4.24→12.37→12.37→9.49 |
12.73→6.71→6→0→6→6→16.16 |
总成本 |
75.96 |
行驶消耗成本 |
66.36 |
充电成本 |
9.6 |
|
表 3 未前往充电站的电动车求解结果
|
表 4(Table 4)
表 4 前往充电站的电动车求解结果
车辆 |
1 |
2 |
3 |
行驶路径 |
1→7→6→15→14→21→5→13→18 |
1→9→17→8→16→18 |
1→3→4→11→12→2→10→19→18 |
载客量
变化
|
0→2→3→1→0→0→2→0→0 |
0→2→0→2→0→0 |
0→3→5→2→0→2→0→0→0 |
aki
|
0→20→60→71.49→74.49→142.54→155→
180→260
|
0→30→38→167.63→200→260 |
0→28→40.71→49.71→56→65→80→
87.24→260
|
yki
|
6→4.52→3.03→2.01→2.01→1.65→5.49→
4.69→3.16
|
6→4.98→4.47→2.99→1.50→0.37 |
6→4.47→3.67→2.95→2.95→2.23→1.51→
1.00→4.52
|
yyki
|
6→4.52→3.03→2.01→2.01→6→5.49→4.69→6 |
6→4.98→4.47→2.99→1.50→6 |
6→4.47→3.67→2.95→2.95→2.23→1.51→6→6 |
Ski
|
0→11.49→3→3→3→3→5→3→0 |
0→3.76→3→10.63→3→0 |
0→6→3→3→3→3→3→3→0 |
tkij
|
12.37→12.37→8.49→0→3→4.24→6.71→77 |
8.49→4.24→12.37→12.37→9.49 |
12.73→6.71→6→0→6→6→4.24→12.37 |
总成本 |
86.71 |
行驶消耗成本 |
66.78 |
充电成本 |
19.93 |
|
表 4 前往充电站的电动车求解结果
|
3 结论与展望
首先针对当前病人运送问题主要以燃油车为主展开研究, 本文分别构建了燃油车和电动车病人运送数学模型; 其次设计算例并利用LINGO软件进行编程求解, 验证了所构建的数学模型的可行性和有效性; 最后通过两次对比燃油车和电动车数学模型求解结果, 证明了采用电动车进行病人运送的可行性和优越性, 对于研究病人运送问题具有一定的参考意义. 在病人运送成本上, 采用电动车进行病人运送能够有效地降低运送成本; 对于非紧急病人而言, 病人运送成本的降低有利于减少非紧急病人的乘车成本和提高乘车意愿; 在环保方面, 电动车在行驶的过程中对于环境零污染, 有利于推动我国绿色交通的发展. 本文在考虑病人运送总成本时, 只考虑了车辆总行驶消耗成本和充电或加油成本两个主要影响因素, 在实际情况中, 当病人运送规模很大时, 车辆使用数、病人满意度以及司机助手的数量等因素都会对病人运送总成本产生影响, 可作为下一步的研究方向.