Fairness, efficiency, and flexibility in organ allocation for kidney transplantation
Fairness, Efficiency, and Flexibility in Organ Allocation for Kidney Transplantation | Operations Research (informs.org)
Problem
器官移植被部分患者视为拯救生命的礼物。器官的供体主要有两种渠道，包括活体供体（器官来自亲朋好友）或尸体供体。而大多数接受器官移植的患者，其器官渠道都来自尸体供应。于是需要器官移植的大多数患者首先会加入一个等候池，等待某个不相识的死者捐赠某个符合要求的器官。然而，一个被捐赠的器官可能与许多个患者相匹配。例如，在美国，2010年10月20日就有86391名患者在等待肾移植。此时，如何决策将被捐赠的器官捐赠给一个特定的患者？一般来说，一旦出现待被捐赠的器官，系统就会为该器官与不同患者之间的匹配关系进行打分排序并形成等候名单，该评分由多项指标分数的加权和决定（指标包括血型、透析时间、器官等候时间与患者的年龄等等）。最终器官将会捐赠给得分最高的患者，如果得分最高的患者放弃移植，那么器官会顺位给得分下一位的患者，依此类推。现在面临的又一个问题是，如何为不同的指标分配合适的权重？作者设计了一个可扩展的数据驱动的方法来塑造透明、客观且高效的国家器官移植政策。
Method
作者提出方法的结构如下图所示。展开来说，就是对作者所提方法经输入历史数据、选定指标与公平约束后，得到相应的指标权重，最后计算个指标分数的加权和。
具体步骤如下：
step 1（一个理想的匹配问题）: 计算如下线性规划问题
maximize
∑
(
p
,
o
)
∈
C
LYFT
(
p
,
o
)
x
(
p
,
o
)
subject to
∑
o
:
(
p
,
o
)
∈
C
x
(
p
,
o
)
⩽
1
,
∀
p
∑
p
:
(
p
,
o
)
∈
C
x
(
p
,
o
)
⩽
1
,
∀
o
A
x
⩽
b
x
⩾
0.
\begin{array}{ll}\operatorname{maximize} & \sum_{(p, o) \in \mathscr{C}} \operatorname{LYFT}(p, o) x_{(p, o)} \\\text { subject to } & \sum_{o:(p, o) \in \mathscr{C}} x_{(p, o)} \leqslant 1, \quad \forall p \\& \sum_{p:(p, o) \in \mathscr{C}} x_{(p, o)} \leqslant 1, \quad \forall o \\& A x \leqslant b \\& x \geqslant 0 .\end{array}
maximize subject to ∑(p,o)∈CLYFT(p,o)x(p,o)∑o:(p,o)∈Cx(p,o)⩽1,∀p∑p:(p,o)∈Cx(p,o)⩽1,∀oAx⩽bx⩾0.
其中
x
(
p
,
o
)
x_{(p, o)}
x(p,o)为0-1变量，当为1时指器官
o
o
o被分配给患者
p
p
p，否者为0。
LYFT
(
p
,
o
)
\operatorname{LYFT}(p, o)
LYFT(p,o)指器官
o
o
o被分配给患者
p
p
p后，患者可延长
p
p
p的生命年限。显然，目标函数是极大化总的可延长的生命年限。第一个约束保证每个器官被分配一次，第二个约束保证每个患者至多获得一个捐赠的器官，第三个是决策者感兴趣的公平约束，注意，这些公平约束是线性的。
step 2（对偶信息）：考虑线性规划的对偶性质，记有关公平约束的对偶拉格朗日乘子为
y
y
y，于是上述规划问题等价于
maximize
∑
(
p
,
o
)
∈
C
LYFT
(
p
,
o
)
x
(
p
,
o
)
−
y
T
A
x
+
y
T
b
subject to
∑
o
:
(
p
,
o
)
∈
C
x
(
p
,
o
)
⩽
1
,
∀
p
∑
p
:
(
p
,
o
)
∈
C
x
(
p
,
o
)
⩽
1
,
∀
o
x
⩾
0.
\begin{aligned}\operatorname{maximize} & \sum_{(p, o) \in \mathscr{C}} \operatorname{LYFT}(p, o) x_{(p, o)}-y^T A x+y^T b \\\text { subject to } & \sum_{o:(p, o) \in \mathscr{C}} x_{(p, o)} \leqslant 1, \quad \forall p \\& \sum_{p:(p, o) \in \mathscr{C}} x_{(p, o)} \leqslant 1, \quad \forall o \\& x \geqslant 0 .\end{aligned}
maximize subject to (p,o)∈C∑LYFT(p,o)x(p,o)−yTAx+yTbo:(p,o)∈C∑x(p,o)⩽1,∀pp:(p,o)∈C∑x(p,o)⩽1,∀ox⩾0.
如上优化问题为一个匹配问题。其目标函数可以重写成
c
T
x
+
y
T
b
c^Tx+y^Tb
cTx+yTb，其中，
c
(
p
,
o
)
=
LYFT
(
p
,
o
)
−
(
y
T
A
)
(
p
,
o
)
,
∀
(
p
,
o
)
∈
C
.
c_{(p, o)}=\operatorname{LYFT}(p, o)-\left(y^T A\right)_{(p, o)}, \quad \forall(p, o) \in \mathscr{C} .
c(p,o)=LYFT(p,o)−(yTA)(p,o),∀(p,o)∈C.
step 3（最小二乘回归）：利用历史数据和对偶信息进行线性回归，得到各指标的向量权重，即优化如下问题：
minimize
∑
(
p
,
o
)
∈
C
(
c
(
p
,
o
)
−
w
0
−
∑
j
=
1
n
w
j
f
j
,
(
p
,
o
)
)
2
subject to
w
∈
S
,
\begin{array}{ll}\operatorname{minimize} & \sum_{(p, o) \in \mathscr{C}}\left(c_{(p, o)}-w_0-\sum_{j=1}^n w_j f_{j,(p, o)}\right)^2 \\\text { subject to } & w \in \mathscr{S},\end{array}
minimize subject to ∑(p,o)∈C(c(p,o)−w0−∑j=1nwjfj,(p,o))2w∈S,
其中，
f
j
,
(
p
,
o
)
f_{j,(p, o)}
fj,(p,o)就是
(
p
,
o
)
(p,o)
(p,o)在第
j
j
j项指标上的得分，
w
j
w_j
wj对应第
j
j
j项指标的权重。最后，患者
p
p
p和器官
o
o
o之间的总得分可以表示为
KAS
(
p
,
o
)
=
∑
j
w
j
f
j
,
(
p
,
o
)
\operatorname{KAS}(p, o)=\sum_j w_j f_{j,(p, o)}
KAS(p,o)=j∑wjfj,(p,o)
Summary of Results
为了验证作者所提方法并展示其实用性，作者进行了三个案例分析，在这些案例研究中，作者在不同的场景下设计了新的策略。在其中一项中，作者设计了一项新的政策，该政策在公平属性上与美国2013年提出的政策相匹配，同时基于决策者已经考虑过的公平标准。结果显示，作者所提政策提供了8%的生命年收益的相对增长。
Why Recommends？
作者在本文中聚焦了美国的器官移植政策，提出一种更加公平高效的方式将尸体器官分配给特定患者。在作者所提的方法中，没有事先设定指定的公平约束，因此，决策者可以根据自己的需求灵活地设计公平约束。之后借助作者所提出的这套方法，决策者可以轻松地得出不同指标的权重以及最后的评分。请注意，本文解决的问题是计算不同评价指标的权重，而不同评价指标的具体得分仍由对应专业人员进行评价。
Reshaping National Organ Allocation Policy
Reshaping National Organ Allocation Policy | Operations Research (informs.org)
Problem
美国器官供应移植网络（The Organ Procurement & Transplantation Network，OPTN）在2018年进行了尸体器官分配的重大改革，以创造一个更加公平高效，更具包容性的器官分配系统。为平衡多个效率与公平目标，作者与OPTN合作，提出了一个新的分配框架来指导器官分配。
Method
作者将机器学习方法与优化相结合，来探索器官分配政策。展开来说，作者考虑了一种黑盒函数（blackbox function）
B
B
B，当指标
j
j
j作为主要目标需要被优化，其余目标以约束的形式体现时，模型可以写成
minimize
x
∈
X
B
j
(
x
)
subject to
B
i
(
x
)
≤
b
i
∀
i
≠
j
\begin{aligned}\underset{\mathbf{x} \in \mathcal{X}}{\operatorname{minimize}} \ \ & B_j(\mathbf{x}) \\\text { subject to } & B_i(\mathbf{x}) \leq b_i \quad \forall i \neq j\end{aligned}
x∈Xminimize subject to Bj(x)Bi(x)≤bi∀i=j
注意，作者将上述模型设置成混合整数线性规划问题（Mixed-Integer Linear Programming，MILP）。以肺移植问题为例，作者指出，可以将目标函数设置为找到一组得分权重最小化等待器官移植中的死亡，约束条件表示受限的器官移植距离和移植差异率等。接下来，借助机器学习模型
f
f
f训练历史数据，以近似黑盒函数
B
B
B$f_i(\mathbf{x};\mathbf{\theta}^i\approx B_i(\mathbf{x}))
$。于是，上述模型可以替代为优化如下问题
minimize
x
∈
X
f
j
(
x
;
θ
j
)
subject to
f
i
(
x
;
θ
i
)
≤
b
i
∀
i
\begin{aligned}\underset{\mathbf{x} \in \mathcal{X}}{\operatorname{minimize}} & \ \ f_j\left(\mathbf{x} ; \boldsymbol{\theta}^j\right) \\\text { subject to } & f_i\left(\mathbf{x} ; \boldsymbol{\theta}^i\right) \leq b_i \quad \forall i\end{aligned}
x∈Xminimize subject to fj(x;θj)fi(x;θi)≤bi∀i
这一优化方法有如下重要优点：它使政策制定者能够动态地探索政策和结果的空间，并允许决策者直观灵活地定义其感兴趣的目标和约束。一旦指定了感兴趣的实例，该方法将自动制定并求解相应的MILP，以显示优化后的策略参数及其模拟结果。因此，利益相关者，即使是那些没有技术专长的人，也可以有效地探索不同的政策选择，并在相关权衡中完善他们的价值判断。
Summary of Results
作者与OPTN合作，演示了如何使用所提方法来进行肺移植，作者特别关注了OPTN如今面临的两个重要问题：
- 如何平衡器官在安置效率与地理位置上的分配？（例如，如果一个候选患者在离捐赠者更近的医院进行移植，通过减少器官缺血时间增加的潜在有害影响，进而提高器官安置效率，但另一个地理位置更远的候选者病情更重，可能会更快死亡，那该怎么分配?）
- 儿童患者如何在目前基于分类的移植策略下保持相同的高水平获得器官？（基于分类的移植策略：例如，来自儿科捐赠者的器官可能首先提供给捐赠者医院某一固定距离内的所有儿科患者候选人。如果没有人接受，则将该器官提供给同一边界内的急症成人候选人，然后是更远的儿科候选人，依次类推。注意，作者指出，这种基于分类的器官移植策略备受美国民众批评，因为这一策略考虑了地理位置的隔阂。在作者所提的器官分配政策中，该政策努力摆脱地理位置的藩篱，作者将其称为“连续分配”，与基于分类的器官移植政策形成对比）
对于第一个问题，下图展示了器官运输距离中位数与等候名单上死亡率的关系。可以发现，随着被允许的器官运输距离变长，死亡率呈下降趋势。而当被允许的器官运输距离较小时，器官被分配至地理位置较近的患者，而不是病情更加危急的患者，这虽然导致较高的器官安置率，但可能会影响公平性。在作者与OPTN的商讨中，他们认为器官运输距离在175海里左右是比较可取的。
对于第二个问题，作者认为所提的连续分配策略可以保持与基于分类的移植策略相同水平的儿童器官移植率，只需要求pediatric access的权重在10%以上即可（如下图所示），而且连续分配方式更为公平。
Why Recommends？
自2023年3月9日起，美国所有的肺移植已采用本文所提的方法来进行分配，这套方法将机器学习与MILP相结合，定制一个透明公平且高效的肺移植策略。与现有的方法相比，作者所提的方向将等候名单中的死亡率降低了20%。这一工作还可以拓展至胰脏、肝脏等器官的分配中。
Kidney Exchange: An Operations Perspective
Kidney Exchange: An Operations Perspective | Management Science (informs.org)
Background
肾脏交换项目（Kidney Exchange, KE，或KPD）指的是当一个肾衰竭患者有一个健康的潜在捐献者，捐献者愿意捐献一个肾脏，但由于捐献者的肾脏与患者的肾脏不匹配而无法捐献。两个或更多这样不匹配的病人-捐献者配对可以交换肾脏，这样每个病人都能从另一个病人的捐献者那里得到一个与他/她相容的肾脏。 如今，在美国和其他一些国家，肾脏交换已成为一种标准的移植方式。本文将叙述肾脏交换是如何从独立的移植中心的交换扩大规模到多个医院间的交换。
肾交换一般有两种形式：
-
循环交换。循环交换包含了几组不匹配的病人/捐献者。为保证公平，一般循环交换都需要几台手术同时进行。
-
链式交换。这类肾交换一般由非指向性捐献者（nondirected donor, NDD）发起，向链式交换中第一个病人捐献，该病人的捐献者向第二对病人捐献，以此类推。链条通常以捐献给已故捐献者候选名单上的病人而结束，因为该病人没有可继续肾链的相关在世捐献者。这种方式的好处是手术可以顺序安排，所以链式比循环用的更多。
Operational Issues
-
作者指出当交换库足够大时，分配由血型决定就足够，基本上不需要三对以上的循环。然而，现实中，“足够大”的交换库是一个理想化的概念，因此在实践中，组织类型的不相容性也发挥着非常大的作用。扩大交换库可以帮助难配对组更有效的找到合适的肾脏。其中一种策略是增加交换库中易配对组的数量。通常可以直接从其预期捐献者那里接受移植的患者被排除在交换库外。然而，这些配对可能会从参与肾脏交换中获益，例如，获得匹配度更高的肾脏或来自更年轻捐献者的肾脏，同时顺便帮助难以匹配组获得匹配。
-
静态优化。模型的目标是在限制匹配组或NDD不能匹配超过一次的限制下，最大限度地提高（加权）移植数量。模型如下：
-
动态匹配。肾脏交换库是动态的，患者和捐献者会随着时间的推移而出现。在更快地确定配对以减少等待时间和等待更多人加入以创造更多配对机会之间需要权衡。两种常用的匹配策略是贪心策略和批处理策略。贪心策略是在有可交换肾脏时马上交换。批处理策略则是每隔固定周期在交换库中确定一组最佳交换。Agarwal等人和Ashlagi等人进行了仿真测试，结果表明足够频繁的匹配不会带来任何负面影响。
Summary
设计良好的肾脏交换中心有4个任务：
-
建立一个足够大、不断更新病人/捐献者的匹配库。、
-
减少在大量配对中可能出现的拥堵。目前运用链式交换的非同实性消除手术资源的瓶颈，同时利用整数规划启发式算法进行复杂的匹配提案计算。
-
确保所有交换安全可靠，这涉及了很多方面，比如收费标准，器官运输等。
-
找到并建立中心蓬勃发展的社会支持。
Why Recommends？
作者详尽地介绍了肾脏交换的两种形式、运营问题和挑战，以及解决这些问题的策略和方法，如如何处理匹配不足、如何进行静态优化和动态匹配等。读者可以全面了解肾脏交换的背景和运作机制。
Robust Models for the Kidney Exchange Problem
Robust Models for the Kidney Exchange Problem | Informs Journal on Computing (informs.org)
Problem
肾脏交换项目（KEPs）旨在帮助肾病晚期患者从愿意但医学上不匹配的活体捐献者那里获得肾脏移植。如果患者的捐献者与其他患者相容，而与其他患者相关的捐献者又与第一位患者相容，那么患者就可以交换捐献者，从而使两位患者都能接受移植。如图所示，6个定点表示6对不相容的患者-捐献者。弧表示匹配对之间的相容性。这个情境中保证最大移植数量的解决方案是循环计划是（1，2，3）和（4，6）。然而这个计划可能完全或部分失败。
相容测试会进行两次。首先，进行初步测试（称为虚拟交叉配对）。这些测试所提供的相容性信息将用于制定交换计划。其次，对配对的患者-捐献者组进行更精确的交叉配对测试（此处称为交叉配对，而非虚拟交叉配对）。第二次测试可能会发现虚拟交叉配对未发现的不匹配情况。如果出现这种情况，计划的交换就会取消。
Method
为了尽量减少知情双方的情感伤害，理想的替代解决方案是尽可能保留原始计划解决方案中的顶点的交换。针对交换计划失败的问题，作者提出3种补救策略。1. 简单补救。2. 后置补救。3. 完全补救。作者为每种补救政策开发了鲁棒模型，并提出了解决优化问题的确切技术。
Part 1 General Model
鲁棒交换问题如下：
其中决策变量被定义为
此模型考虑了失败同质性，即假设对失败类型不了解，只知道存在一定数量的失败。目标函数旨在极大化最坏情况下的补救函数，约束则确保每个顶点最多只能参与一个循环或链式交换。
Part 2 Simple Recourse简单补救
只考虑移植失败的成本，无法恢复失败的循环。由于考虑到了失败的可能性，它能让最初提出的移植计划做出更好的决策。简单补救的函数定义为：
简单补救函数等于计划解 x x x中包含的循环和链中在情景 u u u下可行的配对数量。
Part 3 Back -Arcs后置补救
如果失败循环中的其余参与者可以相互移植，允许恢复失败循环的一部分。后置补救的函数定义为：
目标函数极大化了在最终解决方案中的配对数量。由于不包括新的顶点参与，减少了补救策略中可能出现的新的交换失败。
Part 4 Full Recourse完全补救
允许使用替代移植方案完全补救初始方案。目标函数极大化在初始配对方案和最终配对方案中选择的配对数量。
Summary of Result
为了评估鲁棒优化的效果，作者将不同补救政策的鲁棒解与确定性算法的解进行比较。当链长度$l = 3 ，简单补救和回溯弧补救的最优值非常相似，只有在具有 20 个顶点且不确定性预算 ，简单补救和回溯弧补救的最优值非常相似，只有在具有20个顶点且不确定性预算 ，简单补救和回溯弧补救的最优值非常相似，只有在具有20个顶点且不确定性预算b =1,2 的实例以及具有 50 个顶点且 的实例以及具有 50 个顶点且 的实例以及具有50个顶点且b = 4$的实例中存在差异。这表明，与简单补救相比，回溯弧补救提供的额外灵活性不足以减少损失。主要原因是，在几乎所有的实例中，不可能仅选择具有足够数量的回溯弧的循环和链。因此，在最坏情况下，任何选定的循环和链都将被取消。
关于完全补救，它明显优于其他两种策略，在最坏情况下始终取得更好的结果。这种更好的表现在具有50个顶点的实例中得到了加强，在超过一半的实例中，最大损失减少。对于 l = 5 l = 5 l=5的实例，减少损失的值极高，其中在多达 80% 的实例中损失减少。
接着，作者对优先考虑高敏患者的完全补救策略进行验证。将优化后的版本与在相同失败假设下的非优化版本的完全补救策略、确定性算法进行比较。数据结果表明，在失败之前覆盖的总顶点数在鲁棒和确定性问题中并没有显著差异， 在大多数情况下，非优化的完全补救问题实现了最高的值。此外，尽管确定性算法可以提出覆盖高敏患者的交换计划，在失败后大量的患者无法进行移植。随着实例的规模增长，差异逐渐增大。而在鲁棒算法中，经过失败后继续进行移植的高度敏感患者数量显著增加。文章来源：https://www.toymoban.com/news/detail-833210.html
Why Recommend?
本文介绍了肾脏交换计划（KEPs）的建模和优化方法相关的原创性工作。由于患者退出交换计划（例如，更精确的配型测试显示新的不配型或患者的健康状况使其无法参与 KEP），作者提供了一个能最大限度地降低改变分配所带来的物质和精神成本的解决方案。除此之外，有别于前人的KEP相关模型，本文作者在极大化可进行移植的预期数量时，同时保护了高度敏感患者的配型机会。文章来源地址https://www.toymoban.com/news/detail-833210.html
参考文献：
- Bertsimas D, Farias V F, Trichakis N. Fairness, efficiency, and flexibility in organ allocation for kidney transplantation[J]. Operations Research, 2013, 61(1): 73-87.
- Papalexopoulos T, Alcorn J, Bertsimas D, et al. Reshaping national organ allocation policy[J]. Operations Research, 2023, forthcoming.
- Ashlagi I, Roth A E. Kidney exchange: an operations perspective[J]. Management Science, 2021, 67(9): 5455-5478.
- Carvalho M, Klimentova X, Glorie K, et al. Robust models for the kidney exchange problem[J]. INFORMS Journal on Computing, 2021, 33(3): 861-881.
到了这里，关于服务运营 ｜ INFORMS论文精选：公平高效！运筹学下的器官移植的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
