一种全渠道药品零售订单的协同履行优化方法

摘要

本发明属于全渠道运作管理领域，提供了一种全渠道药品零售订单的协同履行优化方法。本发明针对全渠道药品零售订单履行决策的订单分配、协同的多商品网络流、车辆调度的联合决策问题，基于分解迭代的思想，设计并实现了一种分解‑迭代‑搜索算法，将复杂联合决策问题中关联子问题解耦分解，并通过参数传递迭代求解得到决策方案。本发明的效果和益处是通过采用分解的思路有效地求解有订单完整交付要求的多个库存位置的药品全渠道订单履行问题，充分利用决策子问题之间的信息，优化订单处理过程和车辆路径，降低订单履行成本并提高订单履行方案决策的科学性以及订单处理的效率，为全渠道药品订单履行运作实践提供决策支持。

说明书

技术领域

本发明属于全渠道运作管理领域，涉及一种全渠道药品零售订单的协同履行优化方法。

背景技术

全渠道药品零售模式能够将网上药店的价格优势、品类优势和服务交互等优势与线下实体药店的便利性结合起来，通过“线上药店下单、线下药店履约”的形式，将多样的客户需求与分散的药品库存对接起来，打破药品供需的时空限制，通过线下药店提供保险、药剂师咨询、准时送达等附加药事服务，提高了消费者的服务体验和满意度。

然而，在全渠道药品零售规模不断扩张的同时，其日常运营也受到极大挑战，其中首要难题就是订单履行决策，即订单中药品从哪些药店于何时出货、并由哪一辆车进行于何时经由哪些路径进行配送。由于药品这类商品的特殊性，药品全渠道零售对配送的及时性和准时性要求较高，同时又面临着分散库存和协同配送的矛盾，上述履约决策面临着如下难点：在库存方面，目前中国可在线零售药品高达20万种药品，药品的储运条件严格且多样，而实体药店可存放的药品种类和数量有限，因此药品全渠道运作有多库存地点、库存重叠的特点；在配送方面，一种疾病的治疗往往需要多种药物的组合搭配使用，药物配伍也是药品的特殊属性，药品订单往往具有“一单多品”的属性，且订单需求具有高度随机性，考虑药物商品的特殊性，药品配送需要保证订单完整送达。综上所述，药品全渠道零售的订单履行优化是对订单分配、协同的多商品网络流、车辆调度问题的协同决策，是一类新的协同决策问题且决策空间巨大且对求解速度和质量要求较高，需要构建新的协同决策模型以及相应的高效快速的优化算法，保证高效率、准时的药品全渠道订单配送。

针对药品行业种类繁多和库存分散的特点，以及药品配伍和时间要求的使用特性，药品全渠道零售订单的履行优化综合考虑多库存地点、订单时间限制、多车场的车辆分布等特征，包含订单分配问题、多商品网络流问题、车辆路径问题这三个相互耦合的NP难题。该问题是不成对取送货车辆路径问题 (UPDVRP)和带时间窗的多次取货-送货车辆路径问题(MPD-VRP-TW)两个科学问题的耦合集成，是随着药品全渠道零售的普及新涌现出的一类科学问题。本发明将这两个难题结合起来进行联合优化，问题的复杂性更高，而目前在全渠道运作优化领域，尚未有关于带时间限制的药品全渠道协同订单履行这一集成问题和相关优化方法的专利。在学术研究方面，虽然已有解决UPDVRP和 MPD-VRP-TW这两个科学问题的优化方法的成果，但是对于本专利考虑的 UPDVRP和MPD-VRP-TW耦合的一类新的订单履约问题，这类新问题具有决策空间大、决策变量关系复杂且不规则的特点，目前尚未有相关的研究成果。由于精确算法求解时间长，因而难以满足应用实践；而现有的启发式算法解决这类决策变量关系不规则问题存在搜索效率低、方案效果差等缺陷，因此现有的优化方法很难用来求解这类新问题。

在药品全渠道运作背景下，针对城市内某时刻收到的一批多品线上订单，结合订单中的药品需求和，考虑实体药店库存分布、分布在城市路网中的车辆位置，决策订单中的药品分配到哪些药店，以及如何安排车辆进行订单协同配送，决策内容包括决策订单分配、车辆派遣与取送货协同配送路径等内容，降低订单履行的作业成本。全渠道模式的库存具有位置上分散、逻辑上共享的特点，存在库存协同的需求，更进一步地增加了全渠道订单履行决策的困难。在该发明中，由于库存持有限制，可能需要多个实体药店协同完成同一订单的备货，即同一订单中的不同药品需求可能被分配给不同实体药店备货，然后通过同一车辆的依次访问，实现订单完整交付需求，即通过一次配送完成订单需求。在企业实践中，面临这类问题往往是采用贪心规则进行决策，但是由于该问题包含多个决策子问题，且子问题之间存在耦合关系，因此该问题的决策变量之间结构复杂且不规则，基于贪心规则的决策方法效果较差。

发明内容

本发明是在全渠道运作模式下，根据全渠道药品零售的多库存位置、分散库存的库存特点和“一单多品”、订单完整交付的订单特性，综合考虑库存限制和时间要求，在多个履行主体之间进行订单分配、协同的多商品网络流、车辆调度等决策，降低全渠道零售订单的履行成本。本发明在考虑多个库存位置耦合关系的前提下，将订单分配问题、多商品网络流问题和车辆路径问题等问题进行联合决策，提出了一种分解-迭代-搜索的全渠道药品零售订单的协同履行决策优化方法。本发明基于分解迭代的思想，设计并实现了一种分解迭代搜索算法，将复杂联合决策问题中关联子问题解耦分解，并通过子问题解得到的迭代参数传递迭代地实现联合求解，进而得到原问题的解决方案，能够科学有效地解决这种包含多个耦合的决策子问题的难题。本发明可以为具有相同需求的全渠道运作或物流园区配送调度提供决策支持，提高运作方案的科学性、有效性和高效性。

本发明的基本原理：将全渠道药品零售订单的协同履行问题描述为某地区的全渠道药品零售商利用由多个实体药店组成的药店网络和自有配送车队来满足该地区居民的药品订单需求的运作问题。该零售商经营多品种药品，药店之间的库存品种是部分重叠的，为消费者提供订单配送时间承诺。由于药品严格的储运条件要求配送过程中必须进行温度控制，因此配送过程中存在与运输时间相关的药品控温运输成本，这一成本与药品品类有关。假设单个订单中同一药品的订购数量最多只有一个，因为多个请求订单的处理方式与单个请求订单的处理方式基本相同。同时，配送车队的车辆分散在路网中，所有车辆都有运输体积限制。本发明在这样的条件下，基于库存信息与订单数据，采用分解-迭代-搜索的研究思路，将问题拆分成两个子问题，然后分别设计改进的 Hungarian-Dijkstra算法(MHDA)和贪心搜索算法(Greedy search algorithm， GSA)求解两个子问题，通过商品流变量来调整算法的迭代过程，直到两个子问题得到的商品流变量能够完成匹配，最后再利用整体的变邻域搜索算法对迭代解进行进一步优化，进而得到问题结果。

本发明的技术方案：

一种全渠道药品零售订单的协同履行优化方法，所采用的决策支持系统包括初始化模块、信息输入模块、计算模块1、计算模块2、计算模块3、迭代协调模块、计算模块4和决策输出模块。各个模块的功能如下：初始化模块用来获取实体网络数据和车队数据，作为决策模型的参数和资源约束信息；信息输入模块用来输入某批次的订单需求数据；计算模块1用于对全渠道药品零售订单的协同履行问题进行建模，并根据实体网络数据与订单需求信息对原问题模型进行分解得到两个子模型(模型A和模型B)及相关参数；计算模块2采用改进的Hungarian-Dijkstra算法(MHDA)求解计算模块1的模型A，得到订单中药品的分配方案，以及订单与车辆的分配信息，作为计算模块3的输入和迭代参数；计算模块3基于计算模块2得到的分配方案，采用基于多个邻域的搜索算法求解计算模块1的模型B，得到完整的订单履行方案，并且得到新的订单与车辆的分配信息，作为迭代参数；迭代协调模块判断计算模块2和计算模块3 的订单与车辆的分配信息是否匹配，来控制迭代程序；计算模块4通过邻域搜索对迭代完成后的解进行搜索优化；决策输出模块用于将计算模块4获得决策结果进行可读形式表示并作为决策支持提供给决策者。

基于上述思想和系统模块描述，本发明技术方案的具体步骤如下：

(1)初始化模块：问题参数设置

步骤1：将某地区的药店网络表示为一个由|P|个分散在该地区内实体药店组成，为该地区提供|M|种药品，每个实体药店的药品库存是部分重叠但不完全相同，同时由于药品运输条件的严格要求，每种药品都有对应的温控运输成本。另外|K|辆同质车辆分布在该地区的路网中的不同位置，车辆存在一个容积限制 V，且车辆在路网中有时间参数和成本参数。这些网络设置组成了该问题的决策问题参数，并作为后续模型的资源约束信息。

(2)信息输入模块

步骤2：输入某批次|O|个订单需求的数据，主要包括订单位置、订单时间，以及订单中的药品需求。

(3)计算模块1：问题建模与问题分解

步骤3.1：问题建模

基于初始化模块和信息输入模块对全渠道药品零售订单的协同履行问题进行描述，并建立混合整数规划数学模型TD-UMPD-VRPT，主要决策包括车辆派遣决策U、订单中药品分配决策Y、商品流决策Z、车辆流决策X。

步骤3.2：问题分解

根据药店分布和药店库存数据等实体网络数据与订单需求信息对原问题模型进行分解，得到分解后的两个子模型(模型A和模型B)，并通过相应耦合约束及参数向子模型中添加有效约束便于后续迭代；

(4)计算模块2：求解模型A与相应的迭代参数

步骤4.1：模型A的求解

通过在Hungarian算法中内嵌Dijkstra算法得到改进的Hungarian-Dijkstra算法(MHDA)来求解模型A，即，利用Dijkstra算法求解多车辆最短路径问题得到多药品商品流对应的成本矩阵，并根据成本矩阵利用Hungarian算法求解订单中的药品分配问题，得到包括多商品网络流的订单分配结果。

步骤4.2：得到迭代参数

根据模型A的求解结果得到订单中药品的分配方案，以及订单与车辆的分配信息，作为下一步骤的输入和迭代参数；

(5)计算模块3：求解模型B与相应的迭代参数

步骤5.1：模型B的求解

基于步骤4.2得到的分配方案，采用贪心搜索算法(GSA)得到初始路径方案，并通过邻域搜索改进初始路径方案，进而得到模型B的求解结果，得到完整的订单履行方案。

步骤5.2：模型B的求解

根据模型B的求解结果得到新的订单与车辆的分配信息，作为迭代参数；

(6)迭代协调模块

步骤6：判断步骤4.2和步骤5.2得到的订单与车辆的分配信息是否匹配，若匹配，则得到最终迭代订单履行方案，进行下一步骤；否则，则将步骤5.2的订单与车辆的分配信息反馈到步骤4，重新执行迭代程序；

(7)计算模块4：搜索改进

步骤7：采用邻域结构设计变邻域搜索算法对步骤6得到的最终迭代订单履行方案进行进一步搜索优化。

(8)决策输出模块

步骤8：将步骤7得到的车辆派遣决策U、订单中药品分配决策Y、商品流决策Z、车辆流决策X结果转化为可读形式表示，作为决策支持提供给决策者。

本发明的效果和益处：

1、本发明针对全渠道药品零售运作，提出了一种由于全渠道特点和药品零售特点所引发的新的订单履行问题，并通过建模对问题进行正式描述；

2、本发明考虑库存分散、药品配伍、时间要求等特性，采用分解的研究思路有效地求解有订单完整交付要求的多个库存位置的药品全渠道零售订单的履行问题，能够充分利用决策子问题之间的信息，优化订单处理过程和车辆路径；

3、本发明为全渠道药品零售商开展配送实践提供决策支持，可以提高订单履行方案决策的科学性和订单处理的高效性，进而提高企业运作和资源利用的效率。

附图说明

图1是本发明的全渠道药品零售订单的协同履行方法中的决策支持系统的各系统模块之间的结构关系示意图。

图2是本发明全渠道药品零售订单的协同履行优化方法框架图。

具体实施方式

为使本发明的内容和优点更加清晰，以下结合技术方案和附图详细、完整叙述本发明的具体实施方式。

图1是本发明的全渠道药品零售订单的协同履行的决策支持系统的系统模块之间结构关系示意图，可以看出本发明的全渠道药品零售订单的协同履行决策支持系统由初始化模块、信息输入模块、计算模块1、计算模块2、计算模块 3、迭代协调模块、计算模块4、决策输出模块组成，其中初始化模块是企业运作资源的信息，信息输入模块接收全渠道订单信息，然后针对订单信息，在现有运作资源条件下通过计算模块1、计算模块2、计算模块3、迭代协调模块、计算模块4计算这部分订单的分配方案和配送路径方案，完成协同订单履行的决策。参考图1可知，本发明提供的全渠道药品零售订单的协同履行优化方法包括以下步骤：

步骤1：初始化模块，将运作资源输入到系统中，确定决策问题参数和相应的资源约束；相关参数包括实体药店的位置、药店的库存情况、车辆的当前位置、车辆行驶的时间参数和成本参数、药品的温控运输成本参数。

步骤2：信息输入模块，输入某批次订单需求的数据，主要包括订单位置、订单时间，以及订单中的药品需求。

步骤3：计算模块1，基于初始化模块和信息输入模块对全渠道药品零售订单协同的履行问题进行描述，并建立混合整数规划数学模型，主要决策包括车辆派遣决策U、订单中药品分配决策Y、商品流决策Z、车辆流决策X。根据药店分布和药店库存数据等实体网络数据与订单需求信息对原问题模型进行分解，得到分解后的两个子模型(模型A和模型B)，并通过相应耦合约束及参数向子模型中添加有效约束便于后续迭代；

步骤4：计算模块2，采用改进的Hungarian-Dijkstra算法(MHDA)求解模型A，得到包括多商品网络流的订单分配结果，进而得到订单中药品的分配方案，以及订单与车辆的分配信息，作为下一步骤的输入和迭代参数；

步骤5：计算模块3，基于步骤4得到的分配方案，采用贪心搜索算法(GSA) 得到初始路径方案，并通过邻域搜索改进初始路径方案，进而得到模型B的求解结果，得到完整的订单履行方案。进而得到新的订单与车辆的分配信息，作为迭代参数；

步骤6：迭代协调模块，判断步骤4和步骤5得到的订单与车辆的分配信息是否匹配，若匹配，则得到最终迭代订单履行方案，进行下一步骤；否则，则将步骤5的订单与车辆的分配信息反馈到步骤4，重新执行迭代程序；

步骤7：计算模块4，采用合适的邻域结构设计变邻域搜索算法对步骤6得到的最终迭代订单履行方案进行进一步搜索优化。

步骤8：决策输出模块，将步骤7得到的车辆派遣决策U、订单中药品分配决策Y、商品流决策Z、车辆流决策X结果转化为可读形式表示，作为决策支持提供给决策者。

在本发明提供的方法中，通过运作资源信息和订单需求信息能够建立有时间承诺且存在时间依赖的不成对且多点取送货的车辆路径问题 TD-UMPD-VRPT(time-dependentunpaired-multiple pickup and delivery vehicle routing problem with deliverytime commitment)模型，并设计分解-迭代-搜索算法，将问题分解成两个子问题分别进行求解，然后通过商品流变量来调整算法的迭代过程，直到迭代程序结束，再设计合适的邻域结构通过变邻域搜索对迭代结果进行进一步优化，最终得到协同订单履行方案。基于本发明提供的方法在全渠道药品零售模式下，充分考虑了全渠道的订单履行特点和药品需求特点，为全渠道运作中实体药店备货和车辆配送提供了优化方案。

结合图2本发明全渠道药品零售订单的协同履行优化方法框架图，以一个由|P|个实体药店、|K|个车辆、|M|种药品库存组成的全渠道药店网络，决策|O|个订单需求的协同订单履行方案为例，下面分别对本发明提出的全渠道药品零售订单的协同履行优化方法的具体实施步骤如下：

步骤1：需要先确定全渠道零售商的运作资源配置情况，M为药品集合，K为车辆集合，P为实体药店集合，N

步骤2：确定收到的订单需求信息，O为订单集合，N

步骤3：计算模块1，基于初始化模块的运作资源配置和信息输入模块的订单需求信息，对全渠道药品零售订单的协同履行问题进行描述，构建 TD-UMPD-VRPT模型，根据药店分布、药店库存数据、订单需求等信息，获取包括商品流和车辆流的订单履行方案。所述TD-UMPD-VRPT模型的目标函数采用公式(1)来表示：

其中，M为药品集合，M

所述TD-UMPD-VRPT模型的约束条件采用公式(2)-(20)来表示：

(a)订单拆分和分配决策相关的约束

(b)订单分配和多商品流决策的耦合约束

(c)多商品流决策相关的约束

(d)多商品流和车辆路径决策的耦合约束

(e)取送货车辆路径决策相关的约束

其中，0-1型决策变量

通过移除公式(10)，可以将模型分解成模型A和模型B两个子问题。

模型A：

约束条件：包括公式(2)、公式(3)、公式(8)以及

其中，其中，K

模型B：

约束条件：公式(11)-(20)以及

其中，N

模型A和模型B的新增约束的提出，实现了两个子问题求解过程的传递与衔接，保证该问题的解随着迭代过程的进行不断修正和优化。分别求解两个子问题，通过子问题得到的迭代参数控制迭代过程，直到迭代参数匹配完成联合求解，得到原问题的解决方案。

步骤4：计算模块2，采用改进的Hungarian-Dijkstra算法(MHDA)求解模型A，模型A主要包括两个决策，分别是订单分配决策和多商品网络流决策，目标函数是最小化总商品流成本，而模型A中总的商品流成本为每个订单o的每个药品m的流向成本之和，即每种药品的指派问题相互独立，因此，可以针对每个药品进行相应的指派问题求解，即给定成本矩阵，可以通过求解标准分配问题 (AP)来进行药物分配决策。同样，给定商品分配计划，使商品流成本最小化可视为一个起始节点和结束节点固定的多车辆最短路径问题，所以模型A可以表示为AP和MVSP的组合。因此可以将模型A转化为多种药品m的标准分配问题 (AP)和多车辆最短路径问题(MVSP)的组合，并将Dijkstra算法嵌入Hungarian 算法中，构建了一种多项式时间优化算法(改进的Hungarian-Dijkstra算法， MHDA)用于求解这一模型，即通过Dijkstra算法求解MVSP问题得到每种药品的商品流成本组成的成本矩阵作为AP问题的参数，通过Hungarian算法求解 AP问题得到订单中药品的分配方案。

根据库存情况确定持有每种药品的每个药店所能提供的订单中药品需求，然后计算每种药品分配给持有该药品库存的所有药店的商品流成本。更具体地说，药品m的成本矩阵中的元素d

下面对如何从模型A的解决方案中得到迭代参数进行举例说明。

例如，模型A的解决方案为

步骤5：计算模块3，步骤4得到的订单中药品的分配方案M

以车辆k为例，首先，基于模型A得到订单与车辆的分配信息

下面对如何从模型B的解决方案中得到迭代参数进行举例说明。

例如，模型B的解决方案为

步骤6：迭代协调模块，通过求解模型A得到其最优解分配方案Y

判断

步骤7：计算模块4，为了改善迭代完成后得到的订单履行方案，采用合适的邻域结构设计变邻域搜索算法对最终迭代订单履行方案进行进一步搜索优化。主要思路是通过不同的邻域结构破坏最终迭代订单履行方案，得到待满足的订单需求集合，然后应用基于最小插入成本的局部搜索程序将待满足的订单需求重新插入到方案中以满足所有的订单需求，获得信息的订单履行方案。根据问题特点，设计的邻域结构主要有交换两辆车的全部取送货任务、调整部分分配结果、调整部分路径结果三种类型。

步骤8：决策输出模块，将最终得到的车辆派遣决策u